- moved the structural queue code to queue.c, Array.xs is purely an
[poe-xs-queue-array.git] / queue.c
CommitLineData
a0e4f61f
TC
1#include "EXTERN.h"\r
2#include "perl.h"\r
3#include "XSUB.h"\r
4\r
5#include "queue.h"\r
6\r
c50a32c9
TC
7/*#define DEBUG(x) x*/\r
8#define DEBUG(x)\r
9#define DEBUG_ERR(x) x\r
10/*#define DEBUG_ERR(x)*/\r
a0e4f61f
TC
11\r
12#define PQ_START_SIZE 10\r
13#define AT_START 0\r
14#define AT_END 1\r
15\r
16pq_id_t queue_seq;\r
17\r
18/*\r
19We store the queue in a similar way to the way perl deals with arrays,\r
20we keep a block of memory, but the first element may or may not be in use,\r
21depending on the pattern of usage.\r
22\r
23There'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
29This 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
35We use a perl hash (HV *) to store the mapping from ids to priorities.\r
36\r
37*/\r
38struct 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
60poe_create - create a new queue object.\r
61\r
62No parameters. returns the new queue object.\r
63\r
64*/\r
65poe_queue *\r
66pq_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
86pq_delete - release the queue object.\r
87\r
88This also releases one reference from each SV in the queue.\r
89\r
90*/\r
91void\r
92pq_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
110pq_new_id - generate a new item id.\r
111\r
112Internal use only.\r
113\r
114This, the following 3 functions and pq_create, pq_delete, should be\r
115all that needs to be modified if we change hash implementations.\r
116\r
117*/\r
118static\r
119pq_id_t\r
120pq_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
134pq_release_id - releases an id for future use.\r
135*/\r
136static\r
137void\r
138pq_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
145pq_item_priority - get the priority of an item given it's id\r
146*/\r
147static\r
148int\r
149pq_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
161pq_set_id_priority - set the priority of an item in the id hash\r
162*/\r
163static\r
164void\r
165pq_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
c50a32c9
TC
174/*\r
175pq_move_items - moves items around.\r
176\r
177This encapsulates the old calls to memmove(), providing a single place\r
178to add error checking.\r
179*/\r
180static void\r
181pq_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
a0e4f61f
TC
208/*\r
209pq_realloc - make space at the front of back of the queue.\r
210\r
211This adjusts the queue to allow insertion of a single item at the\r
212front or the back of the queue.\r
213\r
214If the queue has 33% or more space available we simple adjust the\r
215position of the in-use items within the array. We try not to push the\r
216items right up against the opposite end of the array, since we might\r
217need to insert items there too.\r
218\r
219If the queue has less than 33% space available we allocate another 50%\r
220space. We then only move the queue elements if we need space at the\r
221front, since the reallocation has just opened up a huge space at the\r
222back. Since we're reallocating exponentially larger sizes we should\r
223have a constant time cost on reallocation per queue item stored (but\r
224other costs are going to be higher.)\r
225\r
226*/\r
227static\r
228void\r
229pq_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
a0e4f61f
TC
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
c50a32c9 244 pq_move_items(pq, new_start, pq->start, count);\r
a0e4f61f
TC
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
c50a32c9 261 pq_move_items(pq, new_start, pq->start, count);\r
a0e4f61f
TC
262 pq->start = new_start;\r
263 pq->end = new_start + count;\r
264 }\r
265 }\r
a0e4f61f
TC
266 DEBUG( fprintf(stderr, " final: %d %d %d\n", pq->start, pq->end, pq->alloc) );\r
267}\r
268\r
269/*\r
270pq_insertion_point - figure out where to insert an item with the given\r
271priority\r
272\r
273Internal.\r
274*/\r
275static\r
276int\r
277pq_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
289int\r
290pq_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
c50a32c9 337 pq_move_items(pq, i+1, i, pq->end - i);\r
a0e4f61f
TC
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
c50a32c9 348 pq_move_items(pq, pq->start-1, pq->start, i - pq->start);\r
a0e4f61f
TC
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
364int\r
365pq_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
380int\r
381pq_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
389int\r
390pq_get_item_count(poe_queue *pq) {\r
391 return pq->end - pq->start;\r
392}\r
393\r
394/*\r
395pq_test_filter - the XS magic involved in passing the payload to a\r
396filter function.\r
397*/\r
398static\r
399int\r
400pq_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
431pq_find_item - search for an item we know is there.\r
432\r
433Internal.\r
434*/\r
435static\r
436int\r
437pq_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
448int\r
449pq_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
c50a32c9 474 pq_move_items(pq, index, index+1, pq->end - index - 1);\r
a0e4f61f
TC
475 --pq->end;\r
476 }\r
c50a32c9
TC
477 DEBUG( fprintf(stderr, "removed (%d, %p (%d))\n", id, removed->payload,\r
478 SvREFCNT(removed->payload)) );\r
a0e4f61f
TC
479\r
480 return 1;\r
481}\r
482\r
483int\r
484pq_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
515We need to keep the following 2 functions in sync (or combine the\r
516common code.)\r
517*/\r
518int\r
519pq_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
c50a32c9 557 pq_move_items(pq, insert_at + 1, insert_at, index - insert_at);\r
a0e4f61f
TC
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
c50a32c9 563 pq_move_items(pq, index, index + 1, insert_at - index);\r
a0e4f61f
TC
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
574int\r
575pq_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
c50a32c9 617 pq_move_items(pq, insert_at + 1, insert_at, index - insert_at);\r
a0e4f61f
TC
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
c50a32c9 623 pq_move_items(pq, index, index + 1, insert_at - index);\r
a0e4f61f
TC
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
635int\r
636pq_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
659pq_dump - dump the internals of the queue structure.\r
660*/\r
661void\r
662pq_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