prevent some compiler warnings
[poe-xs-queue-array.git] / queue.c
diff --git a/queue.c b/queue.c
index 3bbc49c..9f6e788 100644 (file)
--- a/queue.c
+++ b/queue.c
 #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
 #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
 we keep a block of memory, but the first element may or may not be in use,\r
@@ -55,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
@@ -79,6 +94,10 @@ pq_create(void) {
   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
@@ -138,14 +157,12 @@ pq_new_id(poe_queue *pq, pq_priority_t priority) {
 \r
   return seq;\r
 #else\r
-  int seq = ++pq->queue_seq;;\r
-  SV *index = sv_2mortal(newSViv(seq));\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
@@ -159,9 +176,7 @@ void
 pq_release_id(poe_queue *pq, pq_id_t id) {\r
 #if STUPID_IDS\r
 #else\r
-  SV *id_sv = sv_2mortal(newSViv(id));\r
-\r
-  hv_delete_ent(pq->ids, id_sv, 0, 0);\r
+  hv_delete(pq->ids, (char *)&id, sizeof(id), 0);\r
 #endif\r
 }\r
 \r
@@ -183,12 +198,12 @@ pq_item_priority(poe_queue *pq, pq_id_t id, pq_priority_t *priority) {
 \r
   return 0;\r
 #else\r
-  HE *entry = hv_fetch_ent(pq->ids, sv_2mortal(newSViv(id)), 0, 0);\r
+  SV **entry = hv_fetch(pq->ids, (char *)&id, sizeof(id), 0);\r
 \r
-  if (!entry)\r
+  if (!entry || !*entry)\r
     return 0;\r
 \r
-  *priority = SvNV(HeVAL(entry));\r
+  *priority = SvNV(*entry);\r
 \r
   return 1;\r
 #endif\r
@@ -203,12 +218,12 @@ pq_set_id_priority(poe_queue *pq, pq_id_t id, pq_priority_t new_priority) {
 #if STUPID_IDS\r
   /* nothing to do, caller set it in the array */\r
 #else\r
-  HE *entry = hv_fetch_ent(pq->ids, sv_2mortal(newSViv(id)), 0, 0);\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
@@ -237,7 +252,7 @@ pq_move_items(poe_queue *pq, int target, int src, int count) {
       ++die;\r
     }\r
     if (target + count > pq->alloc) {\r
-      fprintf(stderr, "target %d + count %d > alloc\n", 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
@@ -316,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
@@ -478,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
@@ -720,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