\r
/*#define DEBUG(x) x*/\r
#define DEBUG(x)\r
-#define DEBUG_ERR(x) x\r
-/*#define DEBUG_ERR(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
\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
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
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
- while (hv_exists_ent(pq->ids, index, 0)) {\r
+ return seq;\r
+#else\r
+ pq_id_t seq = ++pq->queue_seq;;\r
+\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
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
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
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
++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
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
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
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
+\r
+/*\r
+pq__set_errno_queue - set errno\r
+\r
+This just sets errno for testing purposes.\r
+*/\r
+void\r
+pq__set_errno_queue(int value) {\r
+ errno = value;\r
+}\r
+\r
projects / poe-xs-queue-array.git / blobdiff