Branch data Line data Source code
1 : : /*
2 : : * See the file "COPYING" in the main distribution directory for copyright.
3 : : */
4 : :
5 : : #ifndef lint
6 : : static const char rcsid[] =
7 : : "@(#) $Id: cq.c 6219 2008-10-01 05:39:07Z vern $ (LBL)";
8 : : #endif
9 : :
10 : : #include <sys/types.h>
11 : :
12 : : #include <errno.h>
13 : : #include <stdio.h>
14 : : #include <stdlib.h>
15 : : #include <string.h>
16 : : #ifdef HAVE_MEMORY_H
17 : : #include <memory.h>
18 : : #endif
19 : : #include <math.h>
20 : :
21 : : #ifdef CQ_DEVELOPMENT
22 : : #include <lbl/gnuc.h>
23 : : #include <lbl/os-proto.h>
24 : : #endif
25 : :
26 : : #include "cq.h"
27 : :
28 : : /* Priority to virtual bucket (int) */
29 : : #define PRI2VBUCKET(hp, p) ((int)((p) / (hp)->bwidth))
30 : :
31 : : /* Priority to bucket (int) */
32 : : #define PRI2BUCKET(hp, p) \
33 : : ((int)fmod((p) / (hp)->bwidth, (double)((hp)->nbuckets)))
34 : :
35 : : /* Priority to bucket top (double) */
36 : : #define PRI2BUCKETTOP(hp, p) ((hp)->bwidth * (((p) / (hp)->bwidth) + 1.5))
37 : :
38 : : /* True if bucket is in use */
39 : : #define BUCKETINUSE(bp) ((bp)->cookie != NULL)
40 : :
41 : : /* Private data */
42 : : struct cq_handle {
43 : : int nbuckets; /* number of buckets */
44 : : int qlen; /* number of queued entries */
45 : : int max_qlen; /* max. number of queued entries */
46 : : int himark; /* high bucket threshold */
47 : : int lowmark; /* low bucket threshold */
48 : : int nextbucket; /* next bucket to check */
49 : : int noresize; /* don't resize while we're resizing */
50 : : double lastpri; /* last priority */
51 : : double ysize; /* length of a year */
52 : : double bwidth; /* width of each bucket */
53 : : double buckettop; /* priority of top of current bucket */
54 : : struct cq_bucket *buckets; /* array of buckets */
55 : : };
56 : :
57 : : struct cq_bucket {
58 : : double pri;
59 : : void *cookie;
60 : : struct cq_bucket *next;
61 : : };
62 : :
63 : : #ifdef DEBUG
64 : : #ifdef CQ_DEVELOPMENT
65 : : extern int debug;
66 : : #else
67 : : int debug = 0;
68 : : #endif
69 : : #endif
70 : :
71 : : static unsigned int memory_allocation = 0;
72 : :
73 : : static struct cq_bucket *free_list = 0;
74 : :
75 : : /* Forwards */
76 : : static int cq_resize(struct cq_handle *, int);
77 : : static void cq_destroybuckets(struct cq_bucket *, int);
78 : : #ifdef DEBUG
79 : : static int cq_debugbucket(struct cq_handle *, struct cq_bucket *);
80 : : void cq_debug(struct cq_handle *, int);
81 : : #endif
82 : :
83 : :
84 : : /* Initialize a calendar queue */
85 : : struct cq_handle *
86 : : cq_init(register double ysize, register double placebo)
87 : 0 : {
88 : : register struct cq_handle *hp;
89 : :
90 : : #ifdef DEBUG
91 [ # # ]: 0 : if (debug > 1)
92 : 0 : fprintf(stderr, "cq_init(%f)\n", ysize);
93 : : #endif
94 : : /* The year size be positive */
95 [ # # ]: 0 : if (ysize <= 0.0) {
96 : 0 : errno = EINVAL;
97 : 0 : return (NULL);
98 : : }
99 : :
100 : : /* Allocate handle */
101 : 0 : hp = (struct cq_handle *)malloc(sizeof(*hp));
102 : 0 : memory_allocation += sizeof(*hp);
103 [ # # ]: 0 : if (hp == NULL)
104 : 0 : return (NULL);
105 [ # # ]: 0 : memset(hp, 0, sizeof(*hp));
106 : :
107 : : /* Initialize handle */
108 : 0 : hp->ysize = ysize;
109 : 0 : hp->max_qlen = 0;
110 : :
111 : : /* Allocate initial buckets and finish handle initialization */
112 [ # # ]: 0 : if (cq_resize(hp, 0) < 0) {
113 : 0 : free(hp);
114 : 0 : memory_allocation -= sizeof(*hp);
115 : 0 : return (NULL);
116 : : }
117 : 0 : return (hp);
118 : : }
119 : :
120 : : /* Returns zero on success, -1 on error (with errno set) */
121 : : int
122 : : cq_enqueue(register struct cq_handle *hp, register double pri,
123 : : register void *cookie)
124 : 0 : {
125 : : register struct cq_bucket *bp, *bp2;
126 : : #ifdef DEBUG
127 : : register int q1, q2;
128 : : register struct cq_bucket *buckethead;
129 : : #endif
130 : :
131 : : #ifdef DEBUG
132 [ # # ]: 0 : if (debug > 1)
133 : 0 : fprintf(stderr, "cq_enqueue(%f)\n", pri);
134 : : #endif
135 : :
136 : : /* The priority must be positive and the cookie non-null */
137 [ # # ][ # # ]: 0 : if (pri <= 0.0 || cookie == NULL) {
138 : 0 : errno = EINVAL;
139 : 0 : return (-1);
140 : : }
141 : :
142 : : /* We might as well resize now if we're going to need to */
143 [ # # ][ # # ]: 0 : if (hp->qlen + 1 > hp->himark && cq_resize(hp, 1) < 0)
144 : 0 : return (-1);
145 : :
146 : 0 : bp = hp->buckets + PRI2BUCKET(hp, pri);
147 : : #ifdef DEBUG
148 [ # # ]: 0 : if (debug) {
149 : 0 : buckethead = bp;
150 : 0 : q1 = cq_debugbucket(hp, buckethead);
151 : : } else {
152 : 0 : buckethead = NULL;
153 : 0 : q1 = 0;
154 : : }
155 : : #endif
156 [ # # ]: 0 : if (BUCKETINUSE(bp)) {
157 : : /* Allocate chained bucket */
158 [ # # ]: 0 : if (free_list) {
159 : 0 : bp2 = free_list;
160 : 0 : free_list = free_list->next;
161 : : } else {
162 : 0 : bp2 = (struct cq_bucket *)malloc(sizeof(*bp2));
163 : 0 : memory_allocation += sizeof(*bp2);
164 [ # # ]: 0 : if (bp2 == NULL)
165 : 0 : return (-1);
166 : : }
167 [ # # ]: 0 : memset(bp2, 0, sizeof(*bp2));
168 [ # # ]: 0 : if (pri < bp->pri) {
169 : : /* Insert new bucket at head of queue */
170 : 0 : *bp2 = *bp;
171 : 0 : bp->next = bp2;
172 : : } else {
173 : : /* Insert entry in order (fifo when pri's are equal) */
174 [ # # ][ # # ]: 0 : while (bp->next != NULL && pri >= bp->next->pri)
175 : 0 : bp = bp->next;
176 : 0 : bp2->next = bp->next;
177 : 0 : bp->next = bp2;
178 : 0 : bp = bp2;
179 : : }
180 : : }
181 : 0 : bp->pri = pri;
182 : 0 : bp->cookie = cookie;
183 [ # # ]: 0 : if (++hp->qlen > hp->max_qlen)
184 : 0 : hp->max_qlen = hp->qlen;
185 : : #ifdef DEBUG
186 [ # # ]: 0 : if (debug) {
187 : 0 : q2 = cq_debugbucket(hp, buckethead);
188 [ # # ]: 0 : if (q1 + 1 != q2) {
189 : 0 : fprintf(stderr, "enqueue length wrong\n");
190 : 0 : cq_dump(hp);
191 : 0 : abort();
192 : : }
193 : : }
194 : : #endif
195 : :
196 : : /* If new priority is old, we need to recalculate nextbucket */
197 [ # # ][ # # ]: 0 : if (hp->lastpri == 0.0 || hp->lastpri > pri) {
198 : 0 : hp->lastpri = pri;
199 : 0 : hp->nextbucket = PRI2BUCKET(hp, hp->lastpri);
200 : 0 : hp->buckettop = PRI2BUCKETTOP(hp, hp->lastpri);
201 : : }
202 : : #ifdef notdef
203 : : if (debug)
204 : : cq_debug(hp, 0);
205 : : #endif
206 : 0 : return (0);
207 : : }
208 : :
209 : : void *
210 : : cq_dequeue(register struct cq_handle *hp, double pri)
211 : 0 : {
212 : : register int n;
213 : : register struct cq_bucket *bp, *bp2, *lowbp;
214 : : register void *cookie;
215 : :
216 : : #ifdef DEBUG
217 [ # # ]: 0 : if (debug > 1)
218 : 0 : fprintf(stderr, "cq_dequeue(%f)\n", pri);
219 : : #endif
220 [ # # ]: 0 : if (pri < hp->lastpri)
221 : : /* For sure nothing to do. */
222 : 0 : return (NULL);
223 : :
224 : 0 : lowbp = NULL;
225 [ # # ]: 0 : for (n = hp->nbuckets, bp = hp->buckets + hp->nextbucket; n > 0; --n) {
226 : : /* Check bucket if it contains an entry (in the current year) */
227 [ # # ]: 0 : if (BUCKETINUSE(bp)) {
228 [ # # ]: 0 : if (bp->pri < hp->buckettop) {
229 : : /* Check first entry in this bucket */
230 [ # # ]: 0 : if (pri >= bp->pri) {
231 : 0 : cookie = bp->cookie;
232 : 0 : hp->lastpri = bp->pri;
233 : : /* Shouldn't nextbucket now point here?? */
234 : 0 : hp->nextbucket = PRI2BUCKET(hp, hp->lastpri);
235 : 0 : hp->buckettop = PRI2BUCKETTOP(hp, hp->lastpri);
236 [ # # ]: 0 : if (bp->next == NULL) {
237 : : /* Zero out first entry */
238 : 0 : bp->pri = 0.0;
239 : 0 : bp->cookie = NULL;
240 : : } else {
241 : : /* Update 1st entry with next */
242 : 0 : bp2 = bp->next;
243 : 0 : *bp = *bp2;
244 : 0 : bp2->next = free_list;
245 : 0 : free_list = bp2;
246 : : /* free(bp2); */
247 : : }
248 : 0 : --hp->qlen;
249 [ # # ]: 0 : if (hp->qlen < hp->lowmark)
250 : 0 : (void)cq_resize(hp, 0);
251 : : #ifdef notdef
252 : : if (debug)
253 : : cq_debug(hp, 0);
254 : : #endif
255 : 0 : return (cookie);
256 : : }
257 : :
258 : : /* The first entry is in the current year
259 : : * but comes after pri. This means we're
260 : : * not going to find *any* subsequent entries
261 : : * that come before pri. So we're done.
262 : : */
263 : 0 : hp->lastpri = bp->pri;
264 : 0 : hp->nextbucket = PRI2BUCKET(hp, hp->lastpri);
265 : 0 : hp->buckettop = PRI2BUCKETTOP(hp, hp->lastpri);
266 : 0 : return (NULL);
267 : : #if 0
268 : : /* Search linked list */
269 : : /* Why is this necessary? Since the list
270 : : * is sorted, and we already know that the
271 : : * first entry has too high a priority,
272 : : * none of the others can be ready to
273 : : * dequeue, right??
274 : : */
275 : : for (bp2 = bp; (bp3 = bp2->next) != NULL;
276 : : bp2 = bp3) {
277 : : /* Don't look past end of bucket */
278 : : if (bp3->pri >= hp->buckettop)
279 : : break;
280 : : if (pri >= bp3->pri) {
281 : : /* Unlink entry */
282 : : cookie = bp3->cookie;
283 : : hp->lastpri = bp->pri;
284 : : bp2->next = bp3->next;
285 : : free(bp3);
286 : : memory_allocation -= sizeof(*bp3);
287 : : --hp->qlen;
288 : : if (hp->qlen < hp->lowmark)
289 : : (void)cq_resize(hp, 0);
290 : : return (cookie);
291 : : }
292 : : }
293 : : #endif
294 : : }
295 : :
296 : : /* Keep track of lowest priority bucket */
297 [ # # ][ # # ]: 0 : if (lowbp == NULL || lowbp->pri > bp->pri)
298 : 0 : lowbp = bp;
299 : : }
300 : :
301 : : /* Step to next bucket */
302 : 0 : hp->buckettop += hp->bwidth;
303 : 0 : ++hp->nextbucket;
304 [ # # ]: 0 : if (hp->nextbucket < hp->nbuckets)
305 : 0 : ++bp;
306 : : else {
307 : 0 : bp = hp->buckets;
308 : 0 : hp->nextbucket = 0;
309 : : }
310 : : }
311 : :
312 : : /*
313 : : * If we got here, we checked all the buckets but came up
314 : : * empty. This can happen when the queued priorities are
315 : : * really sparse (e.g. when there is more than a year
316 : : * between two adjacent entries).
317 : : *
318 : : * If there was at least one bucket in use, check to see
319 : : * if it's the one we're looking for. Also, update nextbucket
320 : : * (and buckettop) with this bucket.
321 : : */
322 [ # # ]: 0 : if (lowbp != NULL) {
323 : 0 : cookie = NULL;
324 : 0 : bp = lowbp;
325 [ # # ]: 0 : if (pri >= bp->pri) {
326 : 0 : cookie = bp->cookie;
327 [ # # ]: 0 : if (bp->next == NULL) {
328 : : /* Zero out first entry */
329 : 0 : bp->pri = 0.0;
330 : 0 : bp->cookie = NULL;
331 : : } else {
332 : : /* Update 1st entry with next */
333 : 0 : bp2 = bp->next;
334 : 0 : *bp = *bp2;
335 : 0 : bp2->next = free_list;
336 : 0 : free_list = bp2;
337 : : /* free(bp2); */
338 : : }
339 : 0 : --hp->qlen;
340 : : /* If we resize, we don't need to update */
341 [ # # ]: 0 : if (hp->qlen < hp->lowmark) {
342 : 0 : (void)cq_resize(hp, 0);
343 : 0 : return (cookie);
344 : : }
345 : : }
346 : 0 : hp->lastpri = lowbp->pri;
347 : 0 : hp->nextbucket = PRI2BUCKET(hp, hp->lastpri);
348 : 0 : hp->buckettop = PRI2BUCKETTOP(hp, hp->lastpri);
349 [ # # ]: 0 : if (cookie != NULL)
350 : 0 : return (cookie);
351 : : }
352 : :
353 : : /* Checked all buckets */
354 : 0 : return (NULL);
355 : : }
356 : :
357 : : void *
358 : : cq_remove(register struct cq_handle *hp, register double pri,
359 : : register void *cookie)
360 : 0 : {
361 : : register struct cq_bucket *bp, *bp2;
362 : :
363 : : /* The priority must be positive and the cookie non-null */
364 [ # # ][ # # ]: 0 : if (pri <= 0.0 || cookie == NULL)
365 : 0 : return (-0);
366 : :
367 : 0 : bp = hp->buckets + PRI2BUCKET(hp, pri);
368 [ # # ]: 0 : if (! BUCKETINUSE(bp))
369 : 0 : return (0);
370 : :
371 [ # # ][ # # ]: 0 : for ( bp2 = 0; bp && cookie != bp->cookie; bp = bp->next ) {
372 [ # # ]: 0 : if ( pri < bp->pri )
373 : 0 : return (0);
374 : 0 : bp2 = bp;
375 : : }
376 : :
377 [ # # ]: 0 : if ( ! bp )
378 : 0 : return (-0);
379 : :
380 : : /* Unlink entry */
381 [ # # ]: 0 : if ( ! bp2 ) {
382 : : /* Remove first element */
383 [ # # ]: 0 : if ( ! bp->next ) {
384 : : /* Zero out first entry */
385 : 0 : bp->pri = 0.0;
386 : 0 : bp->cookie = NULL;
387 : : } else {
388 : : /* Update 1st entry with next */
389 : 0 : bp2 = bp->next;
390 : 0 : *bp = *bp2;
391 : 0 : bp2->next = free_list;
392 : 0 : free_list = bp2;
393 : : }
394 : : }
395 : : else {
396 : : /* Remove not-first element */
397 : 0 : bp2->next = bp->next;
398 : 0 : bp->next = free_list;
399 : 0 : free_list = bp;
400 : : }
401 : 0 : --hp->qlen;
402 : :
403 [ # # ]: 0 : if (hp->qlen < hp->lowmark)
404 : 0 : (void)cq_resize(hp, 0);
405 : :
406 : : /* buckettop etc. don't need to be updated, right? */
407 : 0 : return cookie;
408 : : }
409 : :
410 : : int
411 : : cq_size(struct cq_handle *hp)
412 : 0 : {
413 : 0 : return hp->qlen;
414 : : }
415 : :
416 : : int
417 : : cq_max_size(struct cq_handle *hp)
418 : 0 : {
419 : 0 : return hp->max_qlen;
420 : : }
421 : :
422 : : /* Return without doing anything if we fail to allocate a new bucket array */
423 : : static int
424 : : cq_resize(register struct cq_handle *hp, register int grow)
425 : 0 : {
426 : : register int n, nbuckets, oldnbuckets;
427 : : register size_t size;
428 : : register struct cq_bucket *bp, *bp2, *buckets, *oldbuckets;
429 : : struct cq_handle savedhandle;
430 : :
431 [ # # ]: 0 : if (hp->noresize)
432 : 0 : return (0);
433 : : #ifdef DEBUG
434 [ # # ]: 0 : if (debug)
435 : 0 : cq_debug(hp, 0);
436 : : #endif
437 : :
438 : : /* Save old bucket array */
439 : 0 : oldnbuckets = hp->nbuckets;
440 : 0 : oldbuckets = hp->buckets;
441 : :
442 : : /* If no old buckets, we're initializing */
443 [ # # ]: 0 : if (oldbuckets == NULL)
444 : 0 : nbuckets = 2;
445 [ # # ]: 0 : else if (grow)
446 : 0 : nbuckets = oldnbuckets * 2;
447 : : else
448 : 0 : nbuckets = oldnbuckets / 2;
449 : :
450 : : /* XXX could check that nbuckets is a power of 2 */
451 : :
452 : 0 : size = sizeof(*buckets) * nbuckets;
453 : 0 : buckets = (struct cq_bucket *)malloc(size);
454 : 0 : memory_allocation += size;
455 : :
456 [ # # ]: 0 : if (buckets == NULL)
457 : 0 : return (-1);
458 [ # # ]: 0 : memset(buckets, 0, size);
459 : :
460 : : /* Save a copy of the handle in case we have dynamic memory problems */
461 : 0 : savedhandle = *hp;
462 : :
463 : : /* Install new bucket array */
464 : 0 : hp->nbuckets = nbuckets;
465 : 0 : hp->buckets = buckets;
466 : :
467 : : /* Initialize other parameters */
468 : 0 : hp->himark = hp->nbuckets * 1.5;
469 : 0 : hp->lowmark = (hp->nbuckets / 2) - 2;
470 : 0 : hp->bwidth = hp->ysize / (double)hp->nbuckets;
471 : :
472 : : /* Tell cq_enqueue() to update nextbucket and buckettop */
473 : 0 : hp->lastpri = 0.0;
474 : :
475 : : #ifdef DEBUG
476 [ # # ]: 0 : if (debug > 1)
477 : 0 : fprintf(stderr,
478 : : "buckets 0x%lx, nbuckets %d, bwidth %f, buckettop %f\n",
479 : : (u_long)hp->buckets,
480 : : hp->nbuckets,
481 : : hp->bwidth, hp->buckettop);
482 : : #endif
483 : :
484 : : /* We're done if we were just initializing */
485 [ # # ]: 0 : if (oldbuckets == NULL)
486 : 0 : return (0);
487 : :
488 : : /* Insert entries from old bucket array into new one */
489 : 0 : ++hp->noresize;
490 : 0 : hp->qlen = 0;
491 [ # # ]: 0 : for (bp = oldbuckets, n = oldnbuckets; n > 0; --n, ++bp)
492 [ # # ]: 0 : if (BUCKETINUSE(bp))
493 [ # # ]: 0 : for (bp2 = bp; bp2 != NULL; bp2 = bp2->next) {
494 [ # # ]: 0 : if (cq_enqueue(hp, bp2->pri, bp2->cookie) < 0) {
495 : : /* Bummer! */
496 : 0 : *hp = savedhandle;
497 : : /* hp->resize restored */
498 : 0 : cq_destroybuckets(buckets, nbuckets);
499 : 0 : free(buckets);
500 : 0 : memory_allocation -= size;
501 : 0 : return (-1);
502 : : }
503 : : }
504 : 0 : --hp->noresize;
505 : :
506 : 0 : cq_destroybuckets(oldbuckets, oldnbuckets);
507 : 0 : free(oldbuckets);
508 : 0 : memory_allocation -= sizeof(*buckets) * oldnbuckets;
509 : : #ifdef DEBUG
510 [ # # ]: 0 : if (debug)
511 : 0 : cq_debug(hp, 0);
512 : : #endif
513 : 0 : return (0);
514 : : }
515 : :
516 : : static void
517 : : cq_destroybuckets(register struct cq_bucket *buckets, register int n)
518 : 0 : {
519 : : register struct cq_bucket *bp, *bp2, *bp3;
520 : :
521 [ # # ]: 0 : for (bp = buckets; n > 0; --n, ++bp) {
522 : 0 : bp2 = bp->next;
523 [ # # ]: 0 : while (bp2 != NULL) {
524 : 0 : bp3 = bp2->next;
525 : 0 : bp2->next = free_list;
526 : 0 : free_list = bp2;
527 : : /* free(bp2); */
528 : 0 : bp2 = bp3;
529 : : }
530 : : }
531 : 0 : }
532 : :
533 : : /* Destroy a calendar queue */
534 : : void
535 : : cq_destroy(register struct cq_handle *hp)
536 : 0 : {
537 : :
538 : 0 : cq_destroybuckets(hp->buckets, hp->nbuckets);
539 [ # # ]: 0 : while (free_list) {
540 : 0 : struct cq_bucket *next_free = free_list->next;
541 : 0 : free(free_list);
542 : 0 : free_list = next_free;
543 : : }
544 : 0 : memory_allocation -= sizeof(struct cq_bucket) * hp->nbuckets;
545 : 0 : free(hp->buckets);
546 : 0 : free(hp);
547 : 0 : memory_allocation -= sizeof(*hp);
548 : 0 : }
549 : :
550 : : unsigned int
551 : : cq_memory_allocation(void)
552 : 0 : {
553 : 0 : return memory_allocation;
554 : : }
555 : :
556 : : #ifdef DEBUG
557 : : static int
558 : : cq_debugbucket(register struct cq_handle *hp,
559 : : register struct cq_bucket *buckets)
560 : 0 : {
561 : : register int qlen;
562 : : register struct cq_bucket *bp, *bp2;
563 : : double pri;
564 : :
565 : 0 : qlen = 0;
566 : 0 : pri = 0.0;
567 [ # # ]: 0 : for (bp = buckets; bp != NULL; bp = bp->next) {
568 [ # # ]: 0 : if (BUCKETINUSE(bp)) {
569 : 0 : ++qlen;
570 : 0 : bp2 = hp->buckets + PRI2BUCKET(hp, bp->pri);
571 [ # # ]: 0 : if (bp2 != buckets) {
572 : 0 : fprintf(stderr,
573 : : "%f in wrong bucket! (off by %d)\n",
574 : : bp->pri, bp2 - buckets);
575 : 0 : cq_dump(hp);
576 : 0 : abort();
577 : : }
578 [ # # ]: 0 : if (bp->pri < pri) {
579 : 0 : fprintf(stderr,
580 : : "bad pri order %f < %f (qlen %d)\n",
581 : : bp->pri, pri, qlen);
582 : 0 : cq_dump(hp);
583 : 0 : abort();
584 : : }
585 : 0 : pri = bp->pri;
586 : : }
587 : : }
588 : 0 : return (qlen);
589 : : }
590 : :
591 : : void
592 : : cq_debug(register struct cq_handle *hp, register int print)
593 : 0 : {
594 : : register int n, qlen, xnextbucket, nextbucket;
595 : : register struct cq_bucket *bp, *lowbp;
596 : : register double xbuckettop, buckettop;
597 : :
598 : 0 : qlen = 0;
599 : 0 : lowbp = NULL;
600 : 0 : bp = hp->buckets + hp->nextbucket;
601 [ # # ]: 0 : for (n = hp->nbuckets; n > 0; --n) {
602 [ # # ][ # # ]: 0 : if (BUCKETINUSE(bp) && (lowbp == NULL || lowbp->pri > bp->pri))
[ # # ]
603 : 0 : lowbp = bp;
604 : :
605 : 0 : qlen += cq_debugbucket(hp, bp);
606 : :
607 : : /* Step to next bucket */
608 : 0 : ++bp;
609 [ # # ]: 0 : if (bp >= hp->buckets + hp->nbuckets)
610 : 0 : bp = hp->buckets;
611 : : }
612 : :
613 [ # # ]: 0 : if (lowbp != NULL) {
614 : : /* We expect lastpri gt or eq to the lowest queued priority */
615 [ # # ]: 0 : if (lowbp->pri < hp->lastpri) {
616 : 0 : fprintf(stderr, "lastpri wacked (%f < %f)\n",
617 : : lowbp->pri, hp->lastpri);
618 : 0 : cq_dump(hp);
619 : 0 : abort();
620 : : }
621 : :
622 : : /* Must search for the next entry just as cq_dequeue() would */
623 : 0 : nextbucket = hp->nextbucket;
624 : 0 : buckettop = hp->buckettop;
625 : 0 : bp = hp->buckets + nextbucket;
626 [ # # ]: 0 : for (n = hp->nbuckets; n > 0; --n) {
627 [ # # ][ # # ]: 0 : if (BUCKETINUSE(bp) && bp->pri < buckettop)
628 : 0 : break;
629 : :
630 : : /* Step to next bucket */
631 : 0 : ++bp;
632 : 0 : ++nextbucket;
633 : 0 : buckettop += hp->bwidth;
634 [ # # ]: 0 : if (bp >= hp->buckets + hp->nbuckets) {
635 : 0 : bp = hp->buckets;
636 : 0 : nextbucket = 0;
637 : : }
638 : : }
639 : :
640 : 0 : xnextbucket = PRI2BUCKET(hp, lowbp->pri);
641 [ # # ]: 0 : if (xnextbucket != nextbucket) {
642 : 0 : fprintf(stderr, "nextbucket wacked (%d != %d)\n",
643 : : xnextbucket, nextbucket);
644 : 0 : cq_dump(hp);
645 : 0 : abort();
646 : : }
647 : :
648 : 0 : xbuckettop = PRI2BUCKETTOP(hp, lowbp->pri);
649 [ # # ]: 0 : if (xbuckettop != buckettop) {
650 : 0 : fprintf(stderr, "buckettop wacked (%f != %f)\n",
651 : : xbuckettop, buckettop);
652 : 0 : cq_dump(hp);
653 : 0 : abort();
654 : : }
655 : : }
656 [ # # ]: 0 : if (qlen != hp->qlen) {
657 : 0 : fprintf(stderr, "qlen wacked (%d != %d)\n", qlen, hp->qlen);
658 : 0 : cq_dump(hp);
659 : 0 : abort();
660 : : }
661 : 0 : }
662 : :
663 : : void
664 : : cq_dump(register struct cq_handle *hp)
665 : 0 : {
666 : : // ### FIXME
667 : : register struct cq_bucket *bp, *bp2;
668 : : register int n;
669 : :
670 : 0 : fprintf(stderr,
671 : : "\ncq_dump(): nbucket %d, qlen %d, nextbucket %d, lastpri %f\n",
672 : : hp->nbuckets, hp->qlen, hp->nextbucket, hp->lastpri);
673 : 0 : fprintf(stderr, "\tysize %f, bwidth %f, buckettop %f\n",
674 : : hp->ysize, hp->bwidth, hp->buckettop);
675 : :
676 : 0 : bp = hp->buckets;
677 [ # # ]: 0 : for (n = 0, bp = hp->buckets; n < hp->nbuckets; ++n, ++bp) {
678 [ # # ]: 0 : fprintf(stderr, " %c %2d: %f (0x%lx)\n",
679 : : (n == hp->nextbucket) ? '+' : ' ', n,
680 : : bp->pri, (u_long)bp->cookie);
681 [ # # ]: 0 : for (bp2 = bp->next; bp2 != NULL; bp2 = bp2->next)
682 : 0 : fprintf(stderr, " %f (0x%lx)\n",
683 : : bp2->pri, (u_long)bp2->cookie);
684 : : }
685 : 0 : }
686 : : #endif
|
