prevent some compiler warnings
[poe-xs-queue-array.git] / queue.c
diff --git a/queue.c b/queue.c
index 6ddd63f..9f6e788 100644 (file)
--- a/queue.c
+++ b/queue.c
@@ -3,15 +3,28 @@
 #include "XSUB.h"\r
 \r
 #include "queue.h"\r
+#include "alloc.h"\r
 \r
-#define DEBUG(x) x\r
-/*#define DEBUG(x)*/\r
+/*#define DEBUG(x) x*/\r
+#define DEBUG(x)\r
+#define DEBUG_ERR(x) x\r
+/*#define DEBUG_ERR(x)*/\r
+\r
+/*#define KEEP_STATS 1*/\r
+\r
+#if KEEP_STATS\r
+#define STATS(x) x\r
+#else\r
+#define STATS(x)\r
+#endif\r
 \r
 #define PQ_START_SIZE 10\r
 #define AT_START 0\r
 #define AT_END 1\r
 \r
-pq_id_t queue_seq;\r
+#define STUPID_IDS 0\r
+\r
+#define LARGE_QUEUE_SIZE 50\r
 \r
 /*\r
 We store the queue in a similar way to the way perl deals with arrays,\r
@@ -52,6 +65,11 @@ struct poe_queue_tag {
 \r
   /* the actual entries */\r
   pq_entry *entries;\r
+\r
+#if KEEP_STATS\r
+  int total_finds;\r
+  int binary_finds;\r
+#endif\r
 };\r
 \r
 /*\r
@@ -62,7 +80,7 @@ No parameters.  returns the new queue object.
 */\r
 poe_queue *\r
 pq_create(void) {\r
-  poe_queue *pq = malloc(sizeof(poe_queue));\r
+  poe_queue *pq = mymalloc(sizeof(poe_queue));\r
   \r
   if (pq == NULL)\r
     croak("Out of memory");\r
@@ -71,10 +89,15 @@ pq_create(void) {
   pq->alloc = PQ_START_SIZE;\r
   pq->queue_seq = 0;\r
   pq->ids = newHV();\r
-  pq->entries = calloc(sizeof(pq_entry), PQ_START_SIZE);\r
+  pq->entries = mymalloc(sizeof(pq_entry) * PQ_START_SIZE);\r
+  memset(pq->entries, 0, sizeof(pq_entry) * PQ_START_SIZE);\r
   if (pq->entries == NULL)\r
     croak("Out of memory");\r
 \r
+#if KEEP_STATS\r
+  pq->total_finds = pq->binary_finds = 0;\r
+#endif\r
+\r
   DEBUG( fprintf(stderr, "pq_create() => %p\n", pq) );\r
 \r
   return pq;\r
@@ -99,9 +122,9 @@ pq_delete(poe_queue *pq) {
   SvREFCNT_dec((SV *)pq->ids);\r
   pq->ids = NULL;\r
   if (pq->entries)\r
-    free(pq->entries);\r
+    myfree(pq->entries);\r
   pq->entries = NULL;\r
-  free(pq);\r
+  myfree(pq);\r
 }\r
 \r
 /*\r
@@ -116,14 +139,31 @@ all that needs to be modified if we change hash implementations.
 static\r
 pq_id_t\r
 pq_new_id(poe_queue *pq, pq_priority_t priority) {\r
-  int seq = ++pq->queue_seq;\r
-  SV *index = newSViv(seq);\r
+#if STUPID_IDS\r
+  int seq;\r
+  int i;\r
+  int found;\r
+  \r
+  do {\r
+    seq = ++pq->queue_seq;\r
+    found = 0;\r
+    for (i = pq->start; i < pq->end; ++i) {\r
+      if (pq->entries[i].id == seq) {\r
+       found = 1;\r
+       break;\r
+      }\r
+    }\r
+  } while (found);\r
+\r
+  return seq;\r
+#else\r
+  pq_id_t seq = ++pq->queue_seq;;\r
 \r
-  while (hv_exists_ent(pq->ids, index, 0)) {\r
+  while (hv_exists(pq->ids, (char *)&seq, sizeof(seq))) {\r
     seq = ++pq->queue_seq;\r
-    sv_setiv(index, seq);\r
   }\r
-  hv_store_ent(pq->ids, index, newSVnv(priority), 0);\r
+  hv_store(pq->ids, (char *)&seq, sizeof(seq), newSVnv(priority), 0);\r
+#endif\r
 \r
   return seq;\r
 }\r
@@ -134,9 +174,10 @@ pq_release_id - releases an id for future use.
 static\r
 void\r
 pq_release_id(poe_queue *pq, pq_id_t id) {\r
-  SV *id_sv = sv_2mortal(newSViv(id));\r
-\r
-  hv_delete_ent(pq->ids, id_sv, 0, 0);\r
+#if STUPID_IDS\r
+#else\r
+  hv_delete(pq->ids, (char *)&id, sizeof(id), 0);\r
+#endif\r
 }\r
 \r
 /*\r
@@ -145,14 +186,27 @@ pq_item_priority - get the priority of an item given it's id
 static\r
 int\r
 pq_item_priority(poe_queue *pq, pq_id_t id, pq_priority_t *priority) {\r
-  HE *entry = hv_fetch_ent(pq->ids, sv_2mortal(newSViv(id)), 0, 0);\r
+#if STUPID_IDS\r
+  int i;\r
 \r
-  if (!entry)\r
+  for (i = pq->start; i < pq->end; ++i) {\r
+    if (pq->entries[i].id == id) {\r
+      *priority = pq->entries[i].priority;\r
+      return 1;\r
+    }\r
+  }\r
+\r
+  return 0;\r
+#else\r
+  SV **entry = hv_fetch(pq->ids, (char *)&id, sizeof(id), 0);\r
+\r
+  if (!entry || !*entry)\r
     return 0;\r
 \r
-  *priority = SvNV(HeVAL(entry));\r
+  *priority = SvNV(*entry);\r
 \r
   return 1;\r
+#endif\r
 }\r
 \r
 /*\r
@@ -161,12 +215,50 @@ pq_set_id_priority - set the priority of an item in the id hash
 static\r
 void\r
 pq_set_id_priority(poe_queue *pq, pq_id_t id, pq_priority_t new_priority) {\r
-  HE *entry = hv_fetch_ent(pq->ids, sv_2mortal(newSViv(id)), 0, 0);\r
+#if STUPID_IDS\r
+  /* nothing to do, caller set it in the array */\r
+#else\r
+  SV **entry = hv_fetch(pq->ids, (char *)&id, sizeof(id), 0);\r
 \r
-  if (!entry)\r
+  if (!entry && !*entry)\r
     croak("pq_set_priority: id not found");\r
 \r
-  sv_setnv(HeVAL(entry), new_priority);\r
+  sv_setnv(*entry, new_priority);\r
+#endif\r
+}\r
+\r
+/*\r
+pq_move_items - moves items around.\r
+\r
+This encapsulates the old calls to memmove(), providing a single place\r
+to add error checking.\r
+*/\r
+static void\r
+pq_move_items(poe_queue *pq, int target, int src, int count) {\r
+\r
+  DEBUG_ERR(\r
+  {\r
+    int die = 0;\r
+    if (src < pq->start) {\r
+      fprintf(stderr, "src %d less than start %d\n", src, pq->start);\r
+      ++die;\r
+    }\r
+    if (src + count > pq->end) {\r
+      fprintf(stderr, "src %d + count %d beyond end %d\n", src, count, pq->end);\r
+      ++die;\r
+    }\r
+    if (target < 0) {\r
+      fprintf(stderr, "target %d < 0\n", target);\r
+      ++die;\r
+    }\r
+    if (target + count > pq->alloc) {\r
+      fprintf(stderr, "target %d + count %d > alloc %d\n", target, count, pq->alloc);\r
+      ++die;\r
+    }\r
+    if (die) *(char *)0 = '\0';\r
+  }\r
+  )\r
+  memmove(pq->entries + target, pq->entries + src, count * sizeof(pq_entry));\r
 }\r
 \r
 /*\r
@@ -194,7 +286,6 @@ pq_realloc(poe_queue *pq, int at_end) {
   int count = pq->end - pq->start;\r
 \r
   DEBUG( fprintf(stderr, "pq_realloc((%d, %d, %d), %d)\n", pq->start, pq->end, pq->alloc, at_end) );\r
-  pq_dump(pq);\r
   if (count * 3 / 2 < pq->alloc) {\r
     /* 33 % or more space available, use some of it */\r
     int new_start;\r
@@ -206,14 +297,13 @@ pq_realloc(poe_queue *pq, int at_end) {
       new_start = (pq->alloc - count) * 2 / 3;\r
     }\r
     DEBUG( fprintf(stderr, "  moving start to %d\n", new_start) );\r
-    memmove(pq->entries + new_start, pq->entries + pq->start,\r
-           count * sizeof(pq_entry));\r
+    pq_move_items(pq, new_start, pq->start, count);\r
     pq->start = new_start;\r
     pq->end = new_start + count;\r
   }\r
   else {\r
     int new_alloc = pq->alloc * 3 / 2;\r
-    pq->entries = realloc(pq->entries, sizeof(pq_entry) * new_alloc);\r
+    pq->entries = myrealloc(pq->entries, sizeof(pq_entry) * new_alloc);\r
     pq->alloc = new_alloc;\r
 \r
     if (!pq->entries)\r
@@ -224,13 +314,11 @@ pq_realloc(poe_queue *pq, int at_end) {
     if (!at_end) {\r
       int new_start = (new_alloc - count) * 2 / 3;\r
       DEBUG( fprintf(stderr, "  moving start to %d\n", new_start) );\r
-      memmove(pq->entries + new_start, pq->entries + pq->start,\r
-             count * sizeof(pq_entry));\r
+      pq_move_items(pq, new_start, pq->start, count);\r
       pq->start = new_start;\r
       pq->end = new_start + count;\r
     }\r
   }\r
-  pq_dump(pq);\r
   DEBUG( fprintf(stderr, "  final: %d %d %d\n", pq->start, pq->end, pq->alloc) );\r
 }\r
 \r
@@ -243,15 +331,38 @@ Internal.
 static\r
 int\r
 pq_insertion_point(poe_queue *pq, pq_priority_t priority) {\r
-  /* for now this is just a linear search, later we should make it \r
-     binary */\r
-  int i = pq->end;\r
-  while (i > pq->start &&\r
-         priority < pq->entries[i-1].priority) {\r
-    --i;\r
+  if (pq->end - pq->start < LARGE_QUEUE_SIZE) {\r
+    int i = pq->end;\r
+    while (i > pq->start &&\r
+           priority < pq->entries[i-1].priority) {\r
+      --i;\r
+    }\r
+    return i;\r
   }\r
+  else {\r
+    int lower = pq->start;\r
+    int upper = pq->end - 1;\r
+    while (1) {\r
+      int midpoint = (lower + upper) >> 1;\r
 \r
-  return i;\r
+      if (upper < lower)\r
+        return lower;\r
+      \r
+      if (priority < pq->entries[midpoint].priority) {\r
+        upper = midpoint - 1;\r
+        continue;\r
+      }\r
+      if (priority > pq->entries[midpoint].priority) {\r
+        lower = midpoint + 1;\r
+        continue;\r
+      }\r
+      while (midpoint < pq->end &&\r
+             priority == pq->entries[midpoint].priority) {\r
+        ++midpoint;\r
+      }\r
+      return midpoint;\r
+    }\r
+  }\r
 }\r
 \r
 int\r
@@ -302,7 +413,7 @@ pq_enqueue(poe_queue *pq, pq_priority_t priority, SV *payload) {
         i += pq->start - old_start;\r
       }\r
       \r
-      memmove(pq->entries + i + 1, pq->entries + i, (pq->end - i) * sizeof(pq_entry));\r
+      pq_move_items(pq, i+1, i, pq->end - i);\r
       ++pq->end;\r
       fill_at = i;\r
     }\r
@@ -313,8 +424,7 @@ pq_enqueue(poe_queue *pq, pq_priority_t priority, SV *payload) {
        pq_realloc(pq, AT_START);\r
        i += pq->start;\r
       }\r
-      memmove(pq->entries + pq->start - 1, pq->entries + pq->start,\r
-            (i - pq->start) * sizeof(pq_entry));\r
+      pq_move_items(pq, pq->start-1, pq->start, i - pq->start);\r
       --pq->start;\r
       fill_at = i-1;\r
     }\r
@@ -406,12 +516,53 @@ int
 pq_find_item(poe_queue *pq, pq_id_t id, pq_priority_t priority) {\r
   int i;\r
 \r
-  for (i = pq->start; i < pq->end; ++i) {\r
-    if (pq->entries[i].id == id)\r
-      return i;\r
+  STATS(++pq->total_finds);\r
+  if (pq->end - pq->start < LARGE_QUEUE_SIZE) {\r
+    for (i = pq->start; i < pq->end; ++i) {\r
+      if (pq->entries[i].id == id)\r
+        return i;\r
+    }\r
+    DEBUG(fprintf(stderr, "pq_find_item %d => %f\n", id, priority) );\r
+    croak("Internal inconsistency: event should have been found");\r
+  }\r
+\r
+  /* try a binary search */\r
+  /* simply translated from the perl */\r
+  STATS(++pq->binary_finds);\r
+  {\r
+    int lower = pq->start;\r
+    int upper = pq->end - 1;\r
+    int linear_point;\r
+    while (1) {\r
+      int midpoint = (upper + lower) >> 1;\r
+      if (upper < lower) {\r
+        croak("Internal inconsistency, priorities out of order");\r
+      }\r
+      if (priority < pq->entries[midpoint].priority) {\r
+        upper = midpoint - 1;\r
+        continue;\r
+      }\r
+      if (priority > pq->entries[midpoint].priority) {\r
+        lower = midpoint + 1;\r
+        continue;\r
+      }\r
+      linear_point = midpoint;\r
+      while (linear_point >= pq->start &&\r
+             priority == pq->entries[linear_point].priority) {\r
+        if (pq->entries[linear_point].id == id)\r
+          return linear_point;\r
+        --linear_point;\r
+      }\r
+      linear_point = midpoint;\r
+      while ( (++linear_point < pq->end) &&\r
+              priority == pq->entries[linear_point].priority) {\r
+        if (pq->entries[linear_point].id == id)\r
+          return linear_point;\r
+      }\r
+\r
+      croak("internal inconsistency: event should have been found");\r
+    }\r
   }\r
-  DEBUG(fprintf(stderr, "pq_find_item %d => %f\n", id, priority) );\r
-  croak("Internal inconsistency: event should have been found");\r
 }\r
 \r
 int\r
@@ -440,10 +591,11 @@ pq_remove_item(poe_queue *pq, pq_id_t id, SV *filter, pq_entry *removed) {
     --pq->end;\r
   }\r
   else {\r
-    memmove(pq->entries + index, pq->entries + index + 1,\r
-           sizeof(pq_entry) * (pq->end - index - 1));\r
+    pq_move_items(pq, index, index+1, pq->end - index - 1);\r
     --pq->end;\r
   }\r
+  DEBUG( fprintf(stderr, "removed (%d, %p (%d))\n", id, removed->payload,\r
+                SvREFCNT(removed->payload)) );\r
 \r
   return 1;\r
 }\r
@@ -457,7 +609,7 @@ pq_remove_items(poe_queue *pq, SV *filter, int max_count, pq_entry **entries) {
   if (pq->start == pq->end)\r
     return 0;\r
 \r
-  *entries = malloc(sizeof(pq_entry) * (pq->end - pq->start));\r
+  *entries = mymalloc(sizeof(pq_entry) * (pq->end - pq->start));\r
   if (!*entries)\r
     croak("Out of memory");\r
   \r
@@ -522,15 +674,13 @@ pq_set_priority(poe_queue *pq, pq_id_t id, SV *filter, pq_priority_t new_priorit
 \r
       if (insert_at < index) {\r
         DEBUG( fprintf(stderr, "  - insert_at < index\n") );\r
-        memmove(pq->entries + insert_at + 1, pq->entries + insert_at,\r
-               sizeof(pq_entry) * (index - insert_at));\r
+       pq_move_items(pq, insert_at + 1, insert_at, index - insert_at);\r
         pq->entries[insert_at] = saved;\r
       }\r
       else {\r
         DEBUG( fprintf(stderr, "  - insert_at > index\n") );\r
        --insert_at;\r
-       memmove(pq->entries + index, pq->entries + index + 1,\r
-               sizeof(pq_entry) * (insert_at - index));\r
+       pq_move_items(pq, index, index + 1, insert_at - index);\r
         pq->entries[insert_at] = saved;\r
       }\r
     }\r
@@ -584,15 +734,13 @@ pq_adjust_priority(poe_queue *pq, pq_id_t id, SV *filter, double delta, pq_prior
 \r
       if (insert_at < index) {\r
         DEBUG( fprintf(stderr, "  - insert_at < index\n") );\r
-        memmove(pq->entries + insert_at + 1, pq->entries + insert_at,\r
-               sizeof(pq_entry) * (index - insert_at));\r
+       pq_move_items(pq, insert_at + 1, insert_at, index - insert_at);\r
         pq->entries[insert_at] = saved;\r
       }\r
       else {\r
         DEBUG( fprintf(stderr, "  - insert_at > index\n") );\r
        --insert_at;\r
-       memmove(pq->entries + index, pq->entries + index + 1,\r
-               sizeof(pq_entry) * (insert_at - index));\r
+       pq_move_items(pq, index, index + 1, insert_at - index);\r
         pq->entries[insert_at] = saved;\r
       }\r
     }\r
@@ -613,14 +761,14 @@ pq_peek_items(poe_queue *pq, SV *filter, int max_count, pq_entry **items) {
   if (pq->end == pq->start)\r
     return 0;\r
 \r
-  *items = malloc(sizeof(pq_entry) * (pq->end - pq->start));\r
+  *items = mymalloc(sizeof(pq_entry) * (pq->end - pq->start));\r
   for (i = pq->start; i < pq->end; ++i) {\r
     if (pq_test_filter(pq->entries + i, filter)) {\r
       (*items)[count++] = pq->entries[i];\r
     }\r
   }\r
   if (!count) {\r
-    free(*items);\r
+    myfree(*items);\r
     *items = NULL;\r
   }\r
 \r
@@ -651,6 +799,34 @@ pq_dump(poe_queue *pq) {
   hv_iterinit(pq->ids);\r
   while ((he = hv_iternext(pq->ids)) != NULL) {\r
     STRLEN len;\r
-    fprintf(stderr, "   %s => %f\n", HePV(he, len), SvNV(hv_iterval(pq->ids, he)));\r
+    fprintf(stderr, "   %d => %f\n", *(pq_id_t *)HePV(he, len), SvNV(hv_iterval(pq->ids, he)));\r
+  }\r
+}\r
+\r
+/*\r
+pq_verify - basic verification of the structure of the queue\r
+\r
+For now check for duplicate ids in sequence.\r
+*/\r
+void\r
+pq_verify(poe_queue *pq) {\r
+  int i;\r
+  int lastid;\r
+  int found_err = 0;\r
+\r
+  if (pq->start != pq->end) {\r
+    lastid = pq->entries[pq->start].id;\r
+    i = pq->start + 1;\r
+    while (i < pq->end) {\r
+      if (pq->entries[i].id == lastid) {\r
+        fprintf(stderr, "Duplicate id %d at %d\n", lastid, i);\r
+        ++found_err;\r
+      }\r
+      ++i;\r
+    }\r
+  }\r
+  if (found_err) {\r
+    pq_dump(pq);\r
+    exit(1);\r
   }\r
 }\r