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