Add pool_realloc_base() and pool_realloc_base_moveable() to allow a region to be...

diff --git a/n.sh b/n.sh
index 77af046..9c38ecb 100755 (executable)
--- a/n.sh
+++ b/n.sh
@@ -1,10 +1,10 @@
 #!/bin/sh
 
 echo "generate test script"
-./pool_test_gen 64 256 1024 16 >pool_test.txt
+./pool_test_gen 64 256 1024 16 false >pool_test.txt
 
-echo "run test script, non-moveable"
-./pool_test_run 64 256 <pool_test.txt
+#echo "run test script, non-moveable"
+#./pool_test_run 64 256 <pool_test.txt
 
 echo "run test script, moveable"
-./pool_test_run 64 256 1 <pool_test.txt
+./pool_test_run 64 256 true <pool_test.txt

diff --git a/pool.c b/pool.c
index 9743443..70af153 100644 (file)
--- a/pool.c
+++ b/pool.c
@@ -1,6 +1,6 @@
 #include <assert.h>
 #include <limits.h>
-//#include <stdio.h> // temporary
+#include <stdio.h> // temporary
 #include <stdlib.h>
 #include "pool.h"
 
@@ -167,6 +167,88 @@ resize:
   return true;
 }
 
+bool pool_realloc_base(
+  struct pool_head *head,
+  struct pool_item *item,
+  int size
+) {
+  struct pool_item *p, *q;
+  int size_change, avail, gap;
+
+  // item must be already allocated
+  assert(item->prev && item->next);
+
+  // try to change current block size without copying
+  size_change = size + item->base - item->limit;
+  if (item->limit - size >= item->prev->limit)
+    goto resize;
+
+  // check size, disregarding fragmentation
+  avail = head->avail - size_change;
+  if (avail < 0)
+    return false;
+
+  // last-fit algorithm, until our own list entry
+  p = &head->item;
+  do {
+    q = p;
+    p = q->prev;
+    if (p == item)
+      goto ourself;
+    gap = q->base - p->limit;
+    if (size <= gap)
+      goto found;
+    assert(p != &head->item);
+    avail -= gap;
+  } while (avail >= 0);
+  return false;
+
+ourself:
+  // first-fit algorithm, including and after our own list entry,
+  // the first iteration (ours) is different because p != q->prev,
+  // this causes us to ignore our own entry in the gap calculation
+  p = p->prev;
+  goto loop_entry;
+  do {
+    q = p;
+    p = q->prev;
+  loop_entry:
+    gap = q->base - p->limit;
+    if (size <= gap)
+      goto found;
+    if (p == &head->item)
+      break;
+    avail -= gap;
+  } while (avail >= 0);
+  return false;
+
+found:
+  // if realloc is used, then user must provide move_up routine
+  // (when called from here, it is always non-overlapping or upwards)
+  assert(head->move_up);
+  head->move_up(item, q->base);
+  //item->base += q->base - item->limit;
+  item->limit = q->base;
+ 
+  // remove from list
+  item->prev->next = item->next;
+  item->next->prev = item->prev;
+
+  // insert into list at found position
+  item->prev = p;
+  p->next = item;
+  item->next = q;
+  q->prev = item;
+
+resize:
+  item->base = item->limit - size;
+
+  // keep track of total allocation
+  head->avail -= size_change;
+ check_invariants(head);
+  return true;
+}
+
 void pool_free(struct pool_head *head, struct pool_item *item) {
   // item must be already allocated
   assert(item->prev && item->next);
@@ -296,7 +378,7 @@ blocker_test:
     p = q;
     q = p->next;
     if (q == item)
-      goto ourself;
+      break;
 
     // calculate gap at current position
     gap = q->base - p->limit;
@@ -345,7 +427,6 @@ blocker_test:
     assert(q != &head->item);
   }
 
-ourself:
 #ifdef TRY_REALLOC
   // optional step: try an ordinary realloc in rest of list
   // this is because if the pool consists of a tightly packed region
@@ -484,6 +565,244 @@ resize:
   return true;
 }
 
+bool pool_realloc_base_moveable(
+  struct pool_head *head,
+  struct pool_item *item,
+  int size
+) {
+  struct pool_item *p, *q;
+  int size_change, avail, gap;
+#ifdef TRY_BLOCKER
+  struct pool_item *blocker;
+  int blocker_size;
+#endif
+#ifdef TRY_REALLOC
+  int avail_save;
+#endif
+
+  // item must be already allocated
+  assert(item->prev && item->next);
+
+  // try to change current block size without copying
+  size_change = size + item->base - item->limit;
+#ifndef TRY_BLOCKER
+  if (item->limit - size >= item->prev->limit)
+    goto resize;
+#endif
+
+  // check size, disregarding fragmentation
+  avail = head->avail - size_change;
+  if (avail < 0)
+    return false;
+ 
+  // last-fit algorithm, until our own list entry
+  p = &head->item;
+
+#ifdef TRY_BLOCKER
+blocker_test:
+  // enter here when blocker has changed
+  blocker = item->prev;
+
+  // see if we fit, given the new blocker 
+  if (item->limit - size >= blocker->limit)
+    goto resize;
+
+  // otherwise, see if blocker is moveable
+  blocker_size =
+    blocker == &head->item ? INT_MAX : blocker->limit - blocker->base;
+#endif
+
+  while (true) {
+    q = p;
+    p = q->prev;
+    if (p == item)
+      break;
+
+    // calculate gap at current position
+    gap = q->base - p->limit;
+
+    // see if request fits in gap
+    if (size <= gap)
+      goto found;
+
+#ifdef TRY_BLOCKER
+    // see if blocker fits in gap
+    if (blocker_size <= gap) {
+      // if moveable realloc is used, then user must provide move_up routine
+      assert(head->move_up);
+      head->move_up(blocker, q->base);
+      blocker->base += q->base - blocker->limit;
+      blocker->limit = q->base;
+
+      // remove from list
+      blocker->prev->next = blocker->next;
+      blocker->next->prev = blocker->prev;
+
+      // insert into list at gap position
+      blocker->prev = p;
+      p->next = blocker;
+      blocker->next = q;
+      q->prev = blocker;
+
+      // calculate new blocker
+      p = blocker;
+      goto blocker_test;
+    }
+#endif
+
+    // if gap is too large, move block before gap up into gap
+    avail -= gap;
+    if (avail < 0) {
+      avail += gap;
+
+      // if moveable realloc is used, then user must provide move_up routine
+      assert(head->move_up);
+      head->move_up(p, q->base);
+      p->base += q->base - p->limit;
+      p->limit = q->base;
+    }
+
+    assert(p != &head->item);
+  }
+
+#ifdef TRY_REALLOC
+  // optional step: try an ordinary realloc in rest of list
+  // this is because if the pool consists of a tightly packed region
+  // preceded by a mainly free region, it's best to move us to there
+  avail_save = avail;
+
+  // last-fit algorithm, including and before our own list entry,
+  // the first iteration (ours) is different because p != q->prev,
+  // this causes us to ignore our own entry in the gap calculation
+  p = p->prev;
+  goto loop_entry;
+  do {
+    q = p;
+    p = q->prev;
+  loop_entry:
+    gap = q->base - p->limit;
+    if (size <= gap)
+      goto found;
+    if (p == &head->item)
+      break;
+    avail -= gap;
+  } while (avail >= 0);
+
+  avail = avail_save;
+  q = item->next;
+#endif
+
+  // calculate gap that would be left if we didn't move ourself,
+  // if too large, move block before gap (ourself) up into gap
+  gap = q->base - item->limit;
+  avail -= gap;
+  if (avail < 0) {
+    avail += gap;
+
+    // if moveable realloc is used, then user must provide move_up routine
+    assert(head->move_up);
+    head->move_up(item, q->base);
+    item->base += q->base - item->limit;
+    item->limit = q->base;
+
+#ifndef TRY_REALLOC
+    // if didn't do ordinary realloc above, see if we now fit
+    if (item->limit - size >= item->prev->limit)
+      goto resize;
+#endif
+  }
+
+  // at this point we will not move our own block anymore (because
+  // a first-fit approach is risky, given the likelihood that we will
+  // soon want to resize again), compact the remainder up from bottom 
+  q = &head->item;
+  while (true) {
+    p = q;
+    q = p->next;
+    if (p == item) {
+      assert(item->limit - size >= item->prev->limit);
+      goto resize;
+    }
+
+    // calculate gap at current position
+    gap = q->base - p->limit;
+
+#ifdef TRY_BLOCKER
+    // see if blocker fits in gap
+    if (blocker_size <= gap && blocker != q) {
+      // if moveable realloc is used, then user must provide move routine
+      assert(head->move);
+      head->move(blocker, p->limit);
+      blocker->limit += p->limit - blocker->base;
+      blocker->base = p->limit;
+
+      // remove from list
+      blocker->prev->next = blocker->next;
+      blocker->next->prev = blocker->prev;
+
+      // insert into list at gap position
+      blocker->prev = p;
+      p->next = blocker;
+      blocker->next = q;
+      q->prev = blocker;
+
+      // calculate new blocker
+      q = blocker;
+      blocker = item->prev;
+
+      // see if we fit, given the new blocker
+      if (item->limit - size >= blocker->limit)
+        goto resize;
+
+      // otherwise, see if blocker is moveable
+      blocker_size =
+        blocker == &head->item ? INT_MAX : blocker->limit - blocker->base;
+      continue;
+    }
+#endif
+
+    // if gap too large, move block after gap down into gap
+    avail -= gap;
+    if (avail < 0) {
+      avail += gap;
+
+      // if moveable realloc is used, user must provide move routine
+      assert(head->move);
+      head->move(q, p->limit);
+      q->limit += p->limit - q->base;
+      q->base = p->limit;
+    }
+
+    assert(q != &head->item);
+  }
+
+found:
+  // if moveable realloc is used, then user must provide move_up routine
+  // (when called from here, it is always non-overlapping or upwards)
+  assert(head->move_up);
+  head->move_up(item, q->base);
+  //item->base += q->base - item->limit;
+  item->limit = q->base;
+ 
+  // remove from list
+  item->prev->next = item->next;
+  item->next->prev = item->prev;
+
+  // insert into list at found position
+  item->prev = p;
+  p->next = item;
+  item->next = q;
+  q->prev = item;
+
+resize:
+  item->base = item->limit - size;
+
+  // keep track of total allocation
+  head->avail -= size_change;
+ check_invariants(head);
+  return true;
+}
+
 void pool_move_item(struct pool_item *from, struct pool_item *to) {
   // from-item must be already allocated
   assert(from->prev && from->next);

diff --git a/pool.h b/pool.h
index d1f6fa7..3928cd3 100644 (file)
--- a/pool.h
+++ b/pool.h
@@ -34,6 +34,11 @@ bool pool_realloc(
   struct pool_item *item,
   int size
 );
+bool pool_realloc_base(
+  struct pool_head *head,
+  struct pool_item *item,
+  int size
+);
 void pool_free(struct pool_head *head, struct pool_item *item);
 bool pool_alloc_moveable(
   struct pool_head *head,
@@ -45,6 +50,11 @@ bool pool_realloc_moveable(
   struct pool_item *item,
   int size
 );
+bool pool_realloc_base_moveable(
+  struct pool_head *head,
+  struct pool_item *item,
+  int size
+);
 void pool_move_item(struct pool_item *from, struct pool_item *to);
 
 #endif

diff --git a/pool_test_gen.c b/pool_test_gen.c
index 9672323..d0e0abe 100644 (file)
--- a/pool_test_gen.c
+++ b/pool_test_gen.c
@@ -10,14 +10,15 @@ int rand_int(int n) {
 
 int main(int argc, char **argv) {
   if (argc < 5) {
-    printf("usage: %s n_items pool_size n_events item_size [seed]\n", argv[0]);
+    printf("usage: %s n_items pool_size n_events item_size [base [seed]]\n", argv[0]);
     exit(EXIT_FAILURE);
   }
   int n_items = atoi(argv[1]);
   int pool_size = atoi(argv[2]);
   int n_events = atoi(argv[3]);
   int item_size = atoi(argv[4]);
-  int seed = argc >= 6 ? atoi(argv[5]) : 1;
+  bool base = argc >= 6 ? strcmp(argv[5], "false") != 0 : false;
+  int seed = argc >= 7 ? atoi(argv[6]) : 1;
 
   int *items = malloc(n_items * sizeof(int));
   rassert(items);
@@ -46,7 +47,8 @@ int main(int argc, char **argv) {
       int size = rand_int(item_size);
       bool success = pool_used + size - old_size <= pool_size;
       printf(
-        "realloc %d %d %d %s\n",
+        "realloc%s %d %d %d %s\n",
+        base && rand_int(3) == 0 ? "_base" : "",
         item,
         old_size,
         size,

diff --git a/pool_test_run.c b/pool_test_run.c
index 13e1139..27561c2 100644 (file)
--- a/pool_test_run.c
+++ b/pool_test_run.c
@@ -69,7 +69,7 @@ int main(int argc, char **argv) {
   }
   int n_items = atoi(argv[1]);
   int pool_size = atoi(argv[2]);
-  bool moveable = argc >= 4 ? (bool)atoi(argv[3]) : false;
+  bool moveable = argc >= 4 ? strcmp(argv[3], "false") != 0 : false;
 
   struct pool_head head;
   pool_init(&head, 0, pool_size, move, move_up);
@@ -194,6 +194,71 @@ int main(int argc, char **argv) {
         }
       }
     }
+    else if (strcmp(buf, "realloc_base") == 0) {
+      int item, old_size, size;
+      rassert(scanf("%d %d %d %s", &item, &old_size, &size, buf) == 4);
+      rassert(item >= 0 && item < n_items);
+      rassert(old_size >= 0);
+      rassert(size >= 0);
+      bool success;
+      if (strcmp(buf, "false") == 0)
+        success = false;
+      else if (strcmp(buf, "true") == 0)
+        success = true;
+      else
+        rassert(false);
+      printf(
+        "realloc_base %d %d %d %s\n",
+        item,
+        old_size,
+        size,
+        success ? "true" : "false"
+      );
+      if (items[item].prev == NULL)
+        printf("... not allocated, ignore\n");
+      else {
+        int base = items[item].base;
+        int actual_old_size = items[item].limit - items[item].base;
+        if (actual_old_size != old_size) {
+          printf(
+            "... old size %d, should be %d\n",
+            actual_old_size,
+            old_size
+          );
+          rassert(actual_old_size <= old_size);
+        }
+ printf("old region [%d,%d)\n", base, base + actual_old_size);
+        hash_verify(item, base, 0, actual_old_size - size);
+        bool result =
+          moveable ?
+            pool_realloc_base_moveable(&head, items + item, size) :
+            pool_realloc_base(&head, items + item, size);
+        printf(
+          "... %s\n",
+          result == success ?
+            "ok" :
+            result ? "succeeded, should fail" : "failed, should succeed"
+        );
+        if (result) {
+          if (!success) {
+            printf("... undo\n");
+            rassert(pool_realloc_base(&head, items + item, actual_old_size));
+          }
+          else {
+            base = items[item].base;
+            rassert(items[item].limit == base + size);
+ printf("new region [%d,%d)\n", base, base + size);
+            hash_verify(
+              item,
+              base + size - actual_old_size,
+              size >= actual_old_size ? 0 : actual_old_size - size,
+              actual_old_size
+            );
+            hash_init(item, base, 0, size);
+          }
+        }
+      }
+    }
     else if (strcmp(buf, "free") == 0) {
       int item, old_size;
       rassert(scanf("%d %d", &item, &old_size) == 2);