added a stupid implementation of the id management code, which can't leak
[poe-xs-queue-array.git] / queue.c
1 #include "EXTERN.h"\r
2 #include "perl.h"\r
3 #include "XSUB.h"\r
4 \r
5 #include "queue.h"\r
6 #include "alloc.h"\r
7 \r
8 /*#define DEBUG(x) x*/\r
9 #define DEBUG(x)\r
10 #define DEBUG_ERR(x) x\r
11 /*#define DEBUG_ERR(x)*/\r
12 \r
13 #define PQ_START_SIZE 10\r
14 #define AT_START 0\r
15 #define AT_END 1\r
16 \r
17 #define STUPID_IDS 0\r
18 \r
19 /*\r
20 We store the queue in a similar way to the way perl deals with arrays,\r
21 we keep a block of memory, but the first element may or may not be in use,\r
22 depending on the pattern of usage.\r
23 \r
24 There's 3 value controlling usage of the array:\r
25 \r
26   - alloc - the number of elements allocated in total\r
27   - start - the first element in use in the array\r
28   - end - one past the end of the last element in the array\r
29 \r
30 This has the properties that:\r
31 \r
32   start == 0 - no space at the front\r
33   end == alloc - no space at the end\r
34   end - start - number of elements in the queue\r
35 \r
36 We use a perl hash (HV *) to store the mapping from ids to priorities.\r
37 \r
38 */\r
39 struct poe_queue_tag {\r
40   /* the first entry in use */\r
41   int start;\r
42 \r
43   /* 1 past the last entry in use, hence end - start is the number of \r
44      entries in the queue */\r
45   int end;\r
46 \r
47   /* the total number of entries allocated */\r
48   int alloc;\r
49 \r
50   /* used to generate item ids */\r
51   pq_id_t queue_seq;\r
52 \r
53   /* used to track in use item ids */\r
54   HV *ids;\r
55 \r
56   /* the actual entries */\r
57   pq_entry *entries;\r
58 };\r
59 \r
60 /*\r
61 poe_create - create a new queue object.\r
62 \r
63 No parameters.  returns the new queue object.\r
64 \r
65 */\r
66 poe_queue *\r
67 pq_create(void) {\r
68   poe_queue *pq = mymalloc(sizeof(poe_queue));\r
69   \r
70   if (pq == NULL)\r
71     croak("Out of memory");\r
72   pq->start = 0;\r
73   pq->end = 0;\r
74   pq->alloc = PQ_START_SIZE;\r
75   pq->queue_seq = 0;\r
76   pq->ids = newHV();\r
77   pq->entries = mymalloc(sizeof(pq_entry) * PQ_START_SIZE);\r
78   memset(pq->entries, 0, sizeof(pq_entry) * PQ_START_SIZE);\r
79   if (pq->entries == NULL)\r
80     croak("Out of memory");\r
81 \r
82   DEBUG( fprintf(stderr, "pq_create() => %p\n", pq) );\r
83 \r
84   return pq;\r
85 }\r
86 \r
87 /*\r
88 pq_delete - release the queue object.\r
89 \r
90 This also releases one reference from each SV in the queue.\r
91 \r
92 */\r
93 void\r
94 pq_delete(poe_queue *pq) {\r
95   int i;\r
96 \r
97   DEBUG( fprintf(stderr, "pq_delete(%p)\n", pq) );\r
98   if (pq->end > pq->start) {\r
99     for (i = pq->start; i < pq->end; ++i) {\r
100       SvREFCNT_dec(pq->entries[i].payload);\r
101     }\r
102   }\r
103   SvREFCNT_dec((SV *)pq->ids);\r
104   pq->ids = NULL;\r
105   if (pq->entries)\r
106     myfree(pq->entries);\r
107   pq->entries = NULL;\r
108   myfree(pq);\r
109 }\r
110 \r
111 /*\r
112 pq_new_id - generate a new item id.\r
113 \r
114 Internal use only.\r
115 \r
116 This, the following 3 functions and pq_create, pq_delete, should be\r
117 all that needs to be modified if we change hash implementations.\r
118 \r
119 */\r
120 static\r
121 pq_id_t\r
122 pq_new_id(poe_queue *pq, pq_priority_t priority) {\r
123 #if STUPID_IDS\r
124   int seq;\r
125   int i;\r
126   int found;\r
127   \r
128   do {\r
129     seq = ++pq->queue_seq;\r
130     found = 0;\r
131     for (i = pq->start; i < pq->end; ++i) {\r
132       if (pq->entries[i].id == seq) {\r
133         found = 1;\r
134         break;\r
135       }\r
136     }\r
137   } while (found);\r
138 \r
139   return seq;\r
140 #else\r
141   int seq = ++pq->queue_seq;;\r
142   SV *index = sv_2mortal(newSViv(seq));\r
143 \r
144   while (hv_exists_ent(pq->ids, index, 0)) {\r
145     seq = ++pq->queue_seq;\r
146     sv_setiv(index, seq);\r
147   }\r
148   hv_store_ent(pq->ids, index, newSVnv(priority), 0);\r
149 #endif\r
150 \r
151   return seq;\r
152 }\r
153 \r
154 /*\r
155 pq_release_id - releases an id for future use.\r
156 */\r
157 static\r
158 void\r
159 pq_release_id(poe_queue *pq, pq_id_t id) {\r
160 #if STUPID_IDS\r
161 #else\r
162   SV *id_sv = sv_2mortal(newSViv(id));\r
163 \r
164   hv_delete_ent(pq->ids, id_sv, 0, 0);\r
165 #endif\r
166 }\r
167 \r
168 /*\r
169 pq_item_priority - get the priority of an item given it's id\r
170 */\r
171 static\r
172 int\r
173 pq_item_priority(poe_queue *pq, pq_id_t id, pq_priority_t *priority) {\r
174 #if STUPID_IDS\r
175   int i;\r
176 \r
177   for (i = pq->start; i < pq->end; ++i) {\r
178     if (pq->entries[i].id == id) {\r
179       *priority = pq->entries[i].priority;\r
180       return 1;\r
181     }\r
182   }\r
183 \r
184   return 0;\r
185 #else\r
186   HE *entry = hv_fetch_ent(pq->ids, sv_2mortal(newSViv(id)), 0, 0);\r
187 \r
188   if (!entry)\r
189     return 0;\r
190 \r
191   *priority = SvNV(HeVAL(entry));\r
192 \r
193   return 1;\r
194 #endif\r
195 }\r
196 \r
197 /*\r
198 pq_set_id_priority - set the priority of an item in the id hash\r
199 */\r
200 static\r
201 void\r
202 pq_set_id_priority(poe_queue *pq, pq_id_t id, pq_priority_t new_priority) {\r
203 #if STUPID_IDS\r
204   /* nothing to do, caller set it in the array */\r
205 #else\r
206   HE *entry = hv_fetch_ent(pq->ids, sv_2mortal(newSViv(id)), 0, 0);\r
207 \r
208   if (!entry)\r
209     croak("pq_set_priority: id not found");\r
210 \r
211   sv_setnv(HeVAL(entry), new_priority);\r
212 #endif\r
213 }\r
214 \r
215 /*\r
216 pq_move_items - moves items around.\r
217 \r
218 This encapsulates the old calls to memmove(), providing a single place\r
219 to add error checking.\r
220 */\r
221 static void\r
222 pq_move_items(poe_queue *pq, int target, int src, int count) {\r
223 \r
224   DEBUG_ERR(\r
225   {\r
226     int die = 0;\r
227     if (src < pq->start) {\r
228       fprintf(stderr, "src %d less than start %d\n", src, pq->start);\r
229       ++die;\r
230     }\r
231     if (src + count > pq->end) {\r
232       fprintf(stderr, "src %d + count %d beyond end %d\n", src, count, pq->end);\r
233       ++die;\r
234     }\r
235     if (target < 0) {\r
236       fprintf(stderr, "target %d < 0\n", target);\r
237       ++die;\r
238     }\r
239     if (target + count > pq->alloc) {\r
240       fprintf(stderr, "target %d + count %d > alloc\n", target, count, pq->alloc);\r
241       ++die;\r
242     }\r
243     if (die) *(char *)0 = '\0';\r
244   }\r
245   )\r
246   memmove(pq->entries + target, pq->entries + src, count * sizeof(pq_entry));\r
247 }\r
248 \r
249 /*\r
250 pq_realloc - make space at the front of back of the queue.\r
251 \r
252 This adjusts the queue to allow insertion of a single item at the\r
253 front or the back of the queue.\r
254 \r
255 If the queue has 33% or more space available we simple adjust the\r
256 position of the in-use items within the array.  We try not to push the\r
257 items right up against the opposite end of the array, since we might\r
258 need to insert items there too.\r
259 \r
260 If the queue has less than 33% space available we allocate another 50%\r
261 space.  We then only move the queue elements if we need space at the\r
262 front, since the reallocation has just opened up a huge space at the\r
263 back.  Since we're reallocating exponentially larger sizes we should\r
264 have a constant time cost on reallocation per queue item stored (but\r
265 other costs are going to be higher.)\r
266 \r
267 */\r
268 static\r
269 void\r
270 pq_realloc(poe_queue *pq, int at_end) {\r
271   int count = pq->end - pq->start;\r
272 \r
273   DEBUG( fprintf(stderr, "pq_realloc((%d, %d, %d), %d)\n", pq->start, pq->end, pq->alloc, at_end) );\r
274   if (count * 3 / 2 < pq->alloc) {\r
275     /* 33 % or more space available, use some of it */\r
276     int new_start;\r
277 \r
278     if (at_end) {\r
279       new_start = (pq->alloc - count) / 3;\r
280     }\r
281     else {\r
282       new_start = (pq->alloc - count) * 2 / 3;\r
283     }\r
284     DEBUG( fprintf(stderr, "  moving start to %d\n", new_start) );\r
285     pq_move_items(pq, new_start, pq->start, count);\r
286     pq->start = new_start;\r
287     pq->end = new_start + count;\r
288   }\r
289   else {\r
290     int new_alloc = pq->alloc * 3 / 2;\r
291     pq->entries = myrealloc(pq->entries, sizeof(pq_entry) * new_alloc);\r
292     pq->alloc = new_alloc;\r
293 \r
294     if (!pq->entries)\r
295       croak("Out of memory");\r
296 \r
297     DEBUG( fprintf(stderr, "  - expanding to %d entries\n", new_alloc) );\r
298 \r
299     if (!at_end) {\r
300       int new_start = (new_alloc - count) * 2 / 3;\r
301       DEBUG( fprintf(stderr, "  moving start to %d\n", new_start) );\r
302       pq_move_items(pq, new_start, pq->start, count);\r
303       pq->start = new_start;\r
304       pq->end = new_start + count;\r
305     }\r
306   }\r
307   DEBUG( fprintf(stderr, "  final: %d %d %d\n", pq->start, pq->end, pq->alloc) );\r
308 }\r
309 \r
310 /*\r
311 pq_insertion_point - figure out where to insert an item with the given\r
312 priority\r
313 \r
314 Internal.\r
315 */\r
316 static\r
317 int\r
318 pq_insertion_point(poe_queue *pq, pq_priority_t priority) {\r
319   /* for now this is just a linear search, later we should make it \r
320      binary */\r
321   int i = pq->end;\r
322   while (i > pq->start &&\r
323          priority < pq->entries[i-1].priority) {\r
324     --i;\r
325   }\r
326 \r
327   return i;\r
328 }\r
329 \r
330 int\r
331 pq_enqueue(poe_queue *pq, pq_priority_t priority, SV *payload) {\r
332   int fill_at;\r
333   pq_id_t id = pq_new_id(pq, priority);\r
334 \r
335   DEBUG( fprintf(stderr, "pq_enqueue(%f, %p)\n", priority, payload) );\r
336   if (pq->start == pq->end) {\r
337     DEBUG( fprintf(stderr, "  - on empty queue\n") );\r
338     /* allow room at front and back for new entries */\r
339     pq->start = pq->alloc / 3;\r
340     pq->end = pq->start + 1;\r
341     fill_at = pq->start;\r
342   }\r
343   else if (priority >= pq->entries[pq->end-1].priority) {\r
344     DEBUG( fprintf(stderr, "  - at the end\n") );\r
345     if (pq->end == pq->alloc)\r
346       /* past the end - need to realloc or make some space */\r
347       pq_realloc(pq, AT_END);\r
348     \r
349     fill_at = pq->end;\r
350     ++pq->end;\r
351   }\r
352   else if (priority < pq->entries[pq->start].priority) {\r
353     DEBUG( fprintf(stderr, "  - at the front\n") );\r
354     if (pq->start == 0)\r
355       /* no space at the front, make some */\r
356       pq_realloc(pq, AT_START);\r
357 \r
358     --pq->start;\r
359     fill_at = pq->start;\r
360   }\r
361   else {\r
362     int i;\r
363     DEBUG( fprintf(stderr, "  - in the middle\n") );\r
364     i = pq_insertion_point(pq, priority);\r
365     \r
366     /* if we're near the end we want to push entries up, otherwise down */\r
367     if (i - pq->start > (pq->end - pq->start) / 2) {\r
368       DEBUG( fprintf(stderr, "    - closer to the back (%d -> [ %d %d ])\n",\r
369                      i, pq->start, pq->end) );\r
370       /* make sure we have space, this might end up copying twice, \r
371          but too bad for now */\r
372       if (pq->end == pq->alloc) {\r
373         int old_start = pq->start;\r
374         pq_realloc(pq, AT_END);\r
375         i += pq->start - old_start;\r
376       }\r
377       \r
378       pq_move_items(pq, i+1, i, pq->end - i);\r
379       ++pq->end;\r
380       fill_at = i;\r
381     }\r
382     else {\r
383       DEBUG( fprintf(stderr, "    - closer to the front (%d -> [ %d %d ])\n",\r
384                      i, pq->start, pq->end) );\r
385       if (pq->start == 0) {\r
386         pq_realloc(pq, AT_START);\r
387         i += pq->start;\r
388       }\r
389       pq_move_items(pq, pq->start-1, pq->start, i - pq->start);\r
390       --pq->start;\r
391       fill_at = i-1;\r
392     }\r
393   }\r
394   pq->entries[fill_at].priority = priority;\r
395   pq->entries[fill_at].id = id;\r
396   pq->entries[fill_at].payload = newSVsv(payload);\r
397 \r
398   return id;\r
399 }\r
400 \r
401 /*\r
402   Note: it's up to the caller to release the SV.  The XS code does this \r
403   by making it mortal.\r
404 */\r
405 int\r
406 pq_dequeue_next(poe_queue *pq, pq_priority_t *priority, pq_id_t *id, SV **payload) {\r
407   pq_entry *entry;\r
408   /* the caller needs to release the payload (somehow) */\r
409   if (pq->start == pq->end)\r
410     return 0;\r
411 \r
412   entry = pq->entries + pq->start++;\r
413   *priority = entry->priority;\r
414   *id = entry->id;\r
415   *payload = entry->payload;\r
416   pq_release_id(pq, entry->id);\r
417 \r
418   return 1;\r
419 }\r
420 \r
421 int\r
422 pq_get_next_priority(poe_queue *pq, pq_priority_t *priority) {\r
423   if (pq->start == pq->end)\r
424     return 0;\r
425 \r
426   *priority = pq->entries[pq->start].priority;\r
427   return 1;\r
428 }\r
429 \r
430 int\r
431 pq_get_item_count(poe_queue *pq) {\r
432   return pq->end - pq->start;\r
433 }\r
434 \r
435 /*\r
436 pq_test_filter - the XS magic involved in passing the payload to a\r
437 filter function.\r
438 */\r
439 static\r
440 int\r
441 pq_test_filter(pq_entry *entry, SV *filter) {\r
442   /* man perlcall for the magic here */\r
443   dSP;\r
444   int count;\r
445   SV *result_sv;\r
446   int result;\r
447 \r
448   ENTER;\r
449   SAVETMPS;\r
450   PUSHMARK(SP);\r
451   XPUSHs(sv_2mortal(newSVsv(entry->payload)));\r
452   PUTBACK;\r
453 \r
454   count = call_sv(filter, G_SCALAR);\r
455 \r
456   SPAGAIN;\r
457 \r
458   if (count != 1) \r
459     croak("got other than 1 value in scalar context");\r
460 \r
461   result_sv = POPs;\r
462   result = SvTRUE(result_sv);\r
463 \r
464   PUTBACK;\r
465   FREETMPS;\r
466   LEAVE;\r
467 \r
468   return result;\r
469 }\r
470 \r
471 /*\r
472 pq_find_item - search for an item we know is there.\r
473 \r
474 Internal.\r
475 */\r
476 static\r
477 int\r
478 pq_find_item(poe_queue *pq, pq_id_t id, pq_priority_t priority) {\r
479   int i;\r
480 \r
481   for (i = pq->start; i < pq->end; ++i) {\r
482     if (pq->entries[i].id == id)\r
483       return i;\r
484   }\r
485   DEBUG(fprintf(stderr, "pq_find_item %d => %f\n", id, priority) );\r
486   croak("Internal inconsistency: event should have been found");\r
487 }\r
488 \r
489 int\r
490 pq_remove_item(poe_queue *pq, pq_id_t id, SV *filter, pq_entry *removed) {\r
491   pq_priority_t priority;\r
492   int index;\r
493 \r
494   if (!pq_item_priority(pq, id, &priority)) {\r
495     errno = ESRCH;\r
496     return 0;\r
497   }\r
498 \r
499   index = pq_find_item(pq, id, priority);\r
500 \r
501   if (!pq_test_filter(pq->entries + index, filter)) {\r
502     errno = EPERM;\r
503     return 0;\r
504   }\r
505 \r
506   *removed = pq->entries[index];\r
507   pq_release_id(pq, id);\r
508   if (index == pq->start) {\r
509     ++pq->start;\r
510   }\r
511   else if (index == pq->end - 1) {\r
512     --pq->end;\r
513   }\r
514   else {\r
515     pq_move_items(pq, index, index+1, pq->end - index - 1);\r
516     --pq->end;\r
517   }\r
518   DEBUG( fprintf(stderr, "removed (%d, %p (%d))\n", id, removed->payload,\r
519                  SvREFCNT(removed->payload)) );\r
520 \r
521   return 1;\r
522 }\r
523 \r
524 int\r
525 pq_remove_items(poe_queue *pq, SV *filter, int max_count, pq_entry **entries) {\r
526   int in_index, out_index;\r
527   int remove_count = 0;\r
528   \r
529   *entries = NULL;\r
530   if (pq->start == pq->end)\r
531     return 0;\r
532 \r
533   *entries = mymalloc(sizeof(pq_entry) * (pq->end - pq->start));\r
534   if (!*entries)\r
535     croak("Out of memory");\r
536   \r
537   in_index = out_index = pq->start;\r
538   while (in_index < pq->end && remove_count < max_count) {\r
539     if (pq_test_filter(pq->entries + in_index, filter)) {\r
540       pq_release_id(pq, pq->entries[in_index].id);\r
541       (*entries)[remove_count++] = pq->entries[in_index++];\r
542     }\r
543     else {\r
544       pq->entries[out_index++] = pq->entries[in_index++];\r
545     }\r
546   }\r
547   while (in_index < pq->end) {\r
548     pq->entries[out_index++] = pq->entries[in_index++];\r
549   }\r
550   pq->end = out_index;\r
551   \r
552   return remove_count;\r
553 }\r
554 \r
555 /*\r
556 We need to keep the following 2 functions in sync (or combine the\r
557 common code.)\r
558 */\r
559 int\r
560 pq_set_priority(poe_queue *pq, pq_id_t id, SV *filter, pq_priority_t new_priority) {\r
561   pq_priority_t old_priority;\r
562   int index, insert_at;\r
563 \r
564   if (!pq_item_priority(pq, id, &old_priority)) {\r
565     errno = ESRCH;\r
566     return 0;\r
567   }\r
568 \r
569   index = pq_find_item(pq, id, old_priority);\r
570 \r
571   if (!pq_test_filter(pq->entries + index, filter)) {\r
572     errno = EPERM;\r
573     return 0;\r
574   }\r
575 \r
576   DEBUG( fprintf(stderr, " - index %d  oldp %f newp %f\n", index, old_priority, new_priority) );\r
577 \r
578   if (pq->end - pq->start == 1) {\r
579     DEBUG( fprintf(stderr, "   -- one item\n") );\r
580     /* only the one item anyway */\r
581     pq->entries[pq->start].priority = new_priority;\r
582   }\r
583   else {\r
584     insert_at = pq_insertion_point(pq, new_priority);\r
585     DEBUG( fprintf(stderr, "   - new index %d\n", insert_at) );\r
586     /* the item is still in the queue, so either side of it means it\r
587        won't move */\r
588     if (insert_at == index || insert_at == index+1) {\r
589       DEBUG( fprintf(stderr, "   -- change in place\n") );\r
590       pq->entries[index].priority = new_priority;\r
591     }\r
592     else {\r
593       pq_entry saved = pq->entries[index];\r
594       saved.priority = new_priority;\r
595 \r
596       if (insert_at < index) {\r
597         DEBUG( fprintf(stderr, "  - insert_at < index\n") );\r
598         pq_move_items(pq, insert_at + 1, insert_at, index - insert_at);\r
599         pq->entries[insert_at] = saved;\r
600       }\r
601       else {\r
602         DEBUG( fprintf(stderr, "  - insert_at > index\n") );\r
603         --insert_at;\r
604         pq_move_items(pq, index, index + 1, insert_at - index);\r
605         pq->entries[insert_at] = saved;\r
606       }\r
607     }\r
608   }\r
609 \r
610   pq_set_id_priority(pq, id, new_priority);\r
611 \r
612   return 1;  \r
613 }\r
614 \r
615 int\r
616 pq_adjust_priority(poe_queue *pq, pq_id_t id, SV *filter, double delta, pq_priority_t *priority) {\r
617   pq_priority_t old_priority, new_priority;\r
618   int index, insert_at;\r
619 \r
620   DEBUG( fprintf(stderr, "pq_adjust_priority(..., %d, %p, %f, ...)\n", id, filter, delta) );\r
621 \r
622   if (!pq_item_priority(pq, id, &old_priority)) {\r
623     errno = ESRCH;\r
624     return 0;\r
625   }\r
626 \r
627   index = pq_find_item(pq, id, old_priority);\r
628 \r
629   if (!pq_test_filter(pq->entries + index, filter)) {\r
630     errno = EPERM;\r
631     return 0;\r
632   }\r
633 \r
634   new_priority = old_priority + delta;\r
635 \r
636   DEBUG( fprintf(stderr, " - index %d  oldp %f newp %f\n", index, old_priority, new_priority) );\r
637 \r
638   if (pq->end - pq->start == 1) {\r
639     DEBUG( fprintf(stderr, "   -- one item\n") );\r
640     /* only the one item anyway */\r
641     pq->entries[pq->start].priority = new_priority;\r
642   }\r
643   else {\r
644     insert_at = pq_insertion_point(pq, new_priority);\r
645     DEBUG( fprintf(stderr, "   - new index %d\n", insert_at) );\r
646     /* the item is still in the queue, so either side of it means it\r
647        won't move */\r
648     if (insert_at == index || insert_at == index+1) {\r
649       DEBUG( fprintf(stderr, "   -- change in place\n") );\r
650       pq->entries[index].priority = new_priority;\r
651     }\r
652     else {\r
653       pq_entry saved = pq->entries[index];\r
654       saved.priority = new_priority;\r
655 \r
656       if (insert_at < index) {\r
657         DEBUG( fprintf(stderr, "  - insert_at < index\n") );\r
658         pq_move_items(pq, insert_at + 1, insert_at, index - insert_at);\r
659         pq->entries[insert_at] = saved;\r
660       }\r
661       else {\r
662         DEBUG( fprintf(stderr, "  - insert_at > index\n") );\r
663         --insert_at;\r
664         pq_move_items(pq, index, index + 1, insert_at - index);\r
665         pq->entries[insert_at] = saved;\r
666       }\r
667     }\r
668   }\r
669 \r
670   pq_set_id_priority(pq, id, new_priority);\r
671   *priority = new_priority;\r
672 \r
673   return 1;  \r
674 }\r
675 \r
676 int\r
677 pq_peek_items(poe_queue *pq, SV *filter, int max_count, pq_entry **items) {\r
678   int count = 0;\r
679   int i;\r
680 \r
681   *items = NULL;\r
682   if (pq->end == pq->start)\r
683     return 0;\r
684 \r
685   *items = mymalloc(sizeof(pq_entry) * (pq->end - pq->start));\r
686   for (i = pq->start; i < pq->end; ++i) {\r
687     if (pq_test_filter(pq->entries + i, filter)) {\r
688       (*items)[count++] = pq->entries[i];\r
689     }\r
690   }\r
691   if (!count) {\r
692     myfree(*items);\r
693     *items = NULL;\r
694   }\r
695 \r
696   return count;\r
697 }\r
698 \r
699 /*\r
700 pq_dump - dump the internals of the queue structure.\r
701 */\r
702 void\r
703 pq_dump(poe_queue *pq) {\r
704   int i;\r
705   HE *he;\r
706 \r
707   fprintf(stderr, "poe_queue\n");\r
708   fprintf(stderr, "  start: %d\n", pq->start);\r
709   fprintf(stderr, "    end: %d\n", pq->end);\r
710   fprintf(stderr, "  alloc: %d\n", pq->alloc);\r
711   fprintf(stderr, "    seq: %d\n", pq->queue_seq);\r
712   fprintf(stderr, "  **Queue Entries:\n"\r
713          "      index:   id  priority    SV\n");\r
714   for (i = pq->start; i < pq->end; ++i) {\r
715     pq_entry *entry = pq->entries + i;\r
716     fprintf(stderr, "      %5d: %5d %8f  %p (%u)\n", i, entry->id, entry->priority,\r
717            entry->payload, (unsigned)SvREFCNT(entry->payload));\r
718   }\r
719   fprintf(stderr, "  **Hash entries:\n");\r
720   hv_iterinit(pq->ids);\r
721   while ((he = hv_iternext(pq->ids)) != NULL) {\r
722     STRLEN len;\r
723     fprintf(stderr, "   %s => %f\n", HePV(he, len), SvNV(hv_iterval(pq->ids, he)));\r
724   }\r
725 }\r