queue.c

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