00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #ifndef _XENO_NUCLEUS_QUEUE_H
00022 #define _XENO_NUCLEUS_QUEUE_H
00023
00024 #include <nucleus/types.h>
00025 #include <nucleus/assert.h>
00026
00027 #ifndef CONFIG_XENO_OPT_DEBUG_QUEUES
00028 #define CONFIG_XENO_OPT_DEBUG_QUEUES 0
00029 #endif
00030
00031
00032
00033 typedef struct xnholder {
00034
00035 struct xnholder *next;
00036 struct xnholder *last;
00037
00038 } xnholder_t;
00039
00040 static inline void inith(xnholder_t *holder)
00041 {
00042
00043 holder->last = holder;
00044 holder->next = holder;
00045 }
00046
00047 static inline void ath(xnholder_t *head, xnholder_t *holder)
00048 {
00049
00050 holder->last = head;
00051 holder->next = head->next;
00052 holder->next->last = holder;
00053 head->next = holder;
00054 }
00055
00056 static inline void dth(xnholder_t *holder)
00057 {
00058 holder->last->next = holder->next;
00059 holder->next->last = holder->last;
00060 }
00061
00062
00063
00064 typedef struct xnqueue {
00065
00066 xnholder_t head;
00067 int elems;
00068 #if defined(__KERNEL__) && XENO_DEBUG(QUEUES)
00069 DECLARE_XNLOCK(lock);
00070 #endif
00071
00072 } xnqueue_t;
00073
00074 #if XENO_DEBUG(QUEUES) && (defined(CONFIG_SMP) || XENO_DEBUG(XNLOCK))
00075 #define XNQUEUE_INITIALIZER(q) { { &(q).head, &(q).head }, 0, XNARCH_LOCK_UNLOCKED }
00076 #else
00077 #define XNQUEUE_INITIALIZER(q) { { &(q).head, &(q).head }, 0 }
00078 #endif
00079
00080 #define DEFINE_XNQUEUE(q) xnqueue_t q = XNQUEUE_INITIALIZER(q)
00081
00082 static inline void initq(xnqueue_t *qslot)
00083 {
00084 inith(&qslot->head);
00085 qslot->elems = 0;
00086 #if defined(__KERNEL__) && XENO_DEBUG(QUEUES)
00087 xnlock_init(&qslot->lock);
00088 #endif
00089 }
00090
00091 #if XENO_DEBUG(QUEUES)
00092
00093 #if defined(__KERNEL__) || defined(__XENO_SIM__)
00094
00095 #define XENO_DEBUG_CHECK_QUEUE(__qslot) \
00096 do { \
00097 xnholder_t *curr; \
00098 spl_t s; \
00099 int nelems = 0; \
00100 xnlock_get_irqsave(&(__qslot)->lock,s); \
00101 curr = (__qslot)->head.last; \
00102 while (curr != &(__qslot)->head && nelems < (__qslot)->elems) \
00103 curr = curr->last, nelems++; \
00104 if (curr != &(__qslot)->head || nelems != (__qslot)->elems) \
00105 xnpod_fatal("corrupted queue, qslot->elems=%d/%d, qslot=%p at %s:%d", \
00106 nelems, \
00107 (__qslot)->elems, \
00108 __qslot, \
00109 __FILE__,__LINE__); \
00110 xnlock_put_irqrestore(&(__qslot)->lock,s); \
00111 } while(0)
00112
00113 #define XENO_DEBUG_INSERT_QUEUE(__qslot,__holder) \
00114 do { \
00115 xnholder_t *curr; \
00116 spl_t s; \
00117 xnlock_get_irqsave(&(__qslot)->lock,s); \
00118 curr = (__qslot)->head.last; \
00119 while (curr != &(__qslot)->head && (__holder) != curr) \
00120 curr = curr->last; \
00121 if (curr == (__holder)) \
00122 xnpod_fatal("inserting element twice, holder=%p, qslot=%p at %s:%d", \
00123 __holder, \
00124 __qslot, \
00125 __FILE__,__LINE__); \
00126 if ((__holder)->last == NULL) \
00127 xnpod_fatal("holder=%p not initialized, qslot=%p", \
00128 __holder, \
00129 __qslot); \
00130 xnlock_put_irqrestore(&(__qslot)->lock,s); \
00131 } while(0)
00132
00133 #define XENO_DEBUG_REMOVE_QUEUE(__qslot,__holder) \
00134 do { \
00135 xnholder_t *curr; \
00136 spl_t s; \
00137 xnlock_get_irqsave(&(__qslot)->lock,s); \
00138 curr = (__qslot)->head.last; \
00139 while (curr != &(__qslot)->head && (__holder) != curr) \
00140 curr = curr->last; \
00141 if (curr == &(__qslot)->head) \
00142 xnpod_fatal("removing non-linked element, holder=%p, qslot=%p at %s:%d", \
00143 __holder, \
00144 __qslot, \
00145 __FILE__,__LINE__); \
00146 xnlock_put_irqrestore(&(__qslot)->lock,s); \
00147 } while(0)
00148
00149 #else
00150
00151
00152
00153
00154 #define XENO_DEBUG_CHECK_QUEUE(__qslot)
00155 #define XENO_DEBUG_INSERT_QUEUE(__qslot,__holder)
00156 #define XENO_DEBUG_REMOVE_QUEUE(__qslot,__holder)
00157
00158 #endif
00159
00160
00161
00162
00163 #define insertq(__qslot,__head,__holder) \
00164 ({ XENO_DEBUG_CHECK_QUEUE(__qslot); \
00165 XENO_DEBUG_INSERT_QUEUE(__qslot,__holder); \
00166 ath((__head)->last,__holder); \
00167 ++(__qslot)->elems; })
00168
00169 #define prependq(__qslot,__holder) \
00170 ({ XENO_DEBUG_CHECK_QUEUE(__qslot); \
00171 XENO_DEBUG_INSERT_QUEUE(__qslot,__holder); \
00172 ath(&(__qslot)->head,__holder); \
00173 ++(__qslot)->elems; })
00174
00175 #define appendq(__qslot,__holder) \
00176 ({ XENO_DEBUG_CHECK_QUEUE(__qslot); \
00177 XENO_DEBUG_INSERT_QUEUE(__qslot,__holder); \
00178 ath((__qslot)->head.last,__holder); \
00179 ++(__qslot)->elems; })
00180
00181 #define removeq(__qslot,__holder) \
00182 ({ XENO_DEBUG_CHECK_QUEUE(__qslot); \
00183 XENO_DEBUG_REMOVE_QUEUE(__qslot,__holder); \
00184 dth(__holder); \
00185 --(__qslot)->elems; })
00186
00187 #else
00188
00189 static inline void insertq(xnqueue_t *qslot,
00190 xnholder_t *head, xnholder_t *holder)
00191 {
00192
00193 ath(head->last, holder);
00194 ++qslot->elems;
00195 }
00196
00197 static inline void prependq(xnqueue_t *qslot, xnholder_t *holder)
00198 {
00199
00200 ath(&qslot->head, holder);
00201 ++qslot->elems;
00202 }
00203
00204 static inline void appendq(xnqueue_t *qslot, xnholder_t *holder)
00205 {
00206
00207 ath(qslot->head.last, holder);
00208 ++qslot->elems;
00209 }
00210
00211 static inline void removeq(xnqueue_t *qslot, xnholder_t *holder)
00212 {
00213 dth(holder);
00214 --qslot->elems;
00215 }
00216
00217 #endif
00218
00219 static inline xnholder_t *getheadq(xnqueue_t *qslot)
00220 {
00221 xnholder_t *holder = qslot->head.next;
00222 return holder == &qslot->head ? NULL : holder;
00223 }
00224
00225 static inline xnholder_t *getq(xnqueue_t *qslot)
00226 {
00227 xnholder_t *holder = getheadq(qslot);
00228 if (holder)
00229 removeq(qslot, holder);
00230 return holder;
00231 }
00232
00233 static inline xnholder_t *nextq(xnqueue_t *qslot, xnholder_t *holder)
00234 {
00235 xnholder_t *nextholder = holder->next;
00236 return nextholder == &qslot->head ? NULL : nextholder;
00237 }
00238
00239 static inline xnholder_t *popq(xnqueue_t *qslot, xnholder_t *holder)
00240 {
00241 xnholder_t *nextholder = nextq(qslot, holder);
00242 removeq(qslot, holder);
00243 return nextholder;
00244 }
00245
00246 static inline int countq(xnqueue_t *qslot)
00247 {
00248 return qslot->elems;
00249 }
00250
00251 static inline int emptyq_p(xnqueue_t *qslot)
00252 {
00253 return qslot->head.next == &qslot->head;
00254 }
00255
00256 static inline void moveq(xnqueue_t *dstq, xnqueue_t *srcq)
00257 {
00258 xnholder_t *headsrc = srcq->head.next;
00259 xnholder_t *tailsrc = srcq->head.last;
00260 xnholder_t *headdst = &dstq->head;
00261
00262 if (emptyq_p(srcq))
00263 return;
00264
00265
00266 headsrc->last->next = tailsrc->next;
00267 tailsrc->next->last = headsrc->last;
00268 headsrc->last = headdst;
00269 tailsrc->next = headdst->next;
00270 headdst->next->last = tailsrc;
00271 headdst->next = headsrc;
00272 dstq->elems += srcq->elems;
00273 srcq->elems = 0;
00274 }
00275
00276
00277
00278 typedef struct xnpholder {
00279
00280 xnholder_t plink;
00281 int prio;
00282
00283 } xnpholder_t;
00284
00285 static inline void initph(xnpholder_t *holder)
00286 {
00287 inith(&holder->plink);
00288
00289 }
00290
00291
00292
00293
00294 typedef struct xnpqueue { xnqueue_t pqueue; } xnpqueue_t;
00295
00296 static inline void initpq(xnpqueue_t *pqslot)
00297 {
00298 initq(&pqslot->pqueue);
00299 }
00300
00301 static inline void insertpq(xnpqueue_t *pqslot,
00302 xnpholder_t *head, xnpholder_t *holder)
00303 {
00304
00305 insertq(&pqslot->pqueue, &head->plink, &holder->plink);
00306 }
00307
00308 static inline void insertpqf(xnpqueue_t *pqslot, xnpholder_t *holder, int prio)
00309 {
00310
00311
00312 xnholder_t *curr;
00313
00314 for (curr = pqslot->pqueue.head.last;
00315 curr != &pqslot->pqueue.head; curr = curr->last) {
00316 if (prio <= ((xnpholder_t *)curr)->prio)
00317 break;
00318 }
00319
00320 holder->prio = prio;
00321
00322 insertq(&pqslot->pqueue, curr->next, &holder->plink);
00323 }
00324
00325 static inline void insertpql(xnpqueue_t *pqslot, xnpholder_t *holder, int prio)
00326 {
00327
00328
00329 xnholder_t *curr;
00330
00331 for (curr = pqslot->pqueue.head.next;
00332 curr != &pqslot->pqueue.head; curr = curr->next) {
00333 if (prio >= ((xnpholder_t *)curr)->prio)
00334 break;
00335 }
00336
00337 holder->prio = prio;
00338
00339 insertq(&pqslot->pqueue, curr, &holder->plink);
00340 }
00341
00342 static inline xnpholder_t *findpqh(xnpqueue_t *pqslot, int prio)
00343 {
00344
00345
00346 xnholder_t *curr;
00347
00348 for (curr = pqslot->pqueue.head.next;
00349 curr != &pqslot->pqueue.head; curr = curr->next) {
00350 if (prio >= ((xnpholder_t *)curr)->prio)
00351 break;
00352 }
00353
00354 if (curr && ((xnpholder_t *)curr)->prio == prio)
00355 return (xnpholder_t *)curr;
00356
00357 return NULL;
00358 }
00359
00360 static inline void insertpqfr(xnpqueue_t *pqslot, xnpholder_t *holder, int prio)
00361 {
00362
00363
00364
00365
00366
00367 xnholder_t *curr;
00368
00369 for (curr = pqslot->pqueue.head.last;
00370 curr != &pqslot->pqueue.head; curr = curr->last) {
00371 if (prio >= ((xnpholder_t *)curr)->prio)
00372 break;
00373 }
00374
00375 holder->prio = prio;
00376
00377 insertq(&pqslot->pqueue, curr->next, &holder->plink);
00378 }
00379
00380 static inline void insertpqlr(xnpqueue_t *pqslot, xnpholder_t *holder, int prio)
00381 {
00382
00383
00384
00385
00386
00387 xnholder_t *curr;
00388
00389 for (curr = pqslot->pqueue.head.next;
00390 curr != &pqslot->pqueue.head; curr = curr->next) {
00391 if (prio <= ((xnpholder_t *)curr)->prio)
00392 break;
00393 }
00394
00395 holder->prio = prio;
00396
00397 insertq(&pqslot->pqueue, curr, &holder->plink);
00398 }
00399
00400 static inline xnpholder_t *findpqhr(xnpqueue_t *pqslot, int prio)
00401 {
00402
00403
00404
00405
00406
00407 xnholder_t *curr;
00408
00409 for (curr = pqslot->pqueue.head.next;
00410 curr != &pqslot->pqueue.head; curr = curr->next) {
00411 if (prio <= ((xnpholder_t *)curr)->prio)
00412 break;
00413 }
00414
00415 if (curr && ((xnpholder_t *)curr)->prio == prio)
00416 return (xnpholder_t *)curr;
00417
00418 return NULL;
00419 }
00420
00421 static inline void appendpq(xnpqueue_t *pqslot, xnpholder_t *holder)
00422 {
00423 holder->prio = 0;
00424 appendq(&pqslot->pqueue, &holder->plink);
00425 }
00426
00427 static inline void prependpq(xnpqueue_t *pqslot, xnpholder_t *holder)
00428 {
00429 holder->prio = 0;
00430 prependq(&pqslot->pqueue, &holder->plink);
00431 }
00432
00433 static inline void removepq(xnpqueue_t *pqslot, xnpholder_t *holder)
00434 {
00435 removeq(&pqslot->pqueue, &holder->plink);
00436 }
00437
00438 static inline xnpholder_t *getheadpq(xnpqueue_t *pqslot)
00439 {
00440 return (xnpholder_t *)getheadq(&pqslot->pqueue);
00441 }
00442
00443 static inline xnpholder_t *nextpq(xnpqueue_t *pqslot, xnpholder_t *holder)
00444 {
00445 return (xnpholder_t *)nextq(&pqslot->pqueue, &holder->plink);
00446 }
00447
00448 static inline xnpholder_t *getpq(xnpqueue_t *pqslot)
00449 {
00450 return (xnpholder_t *)getq(&pqslot->pqueue);
00451 }
00452
00453 static inline xnpholder_t *poppq(xnpqueue_t *pqslot, xnpholder_t *holder)
00454 {
00455 return (xnpholder_t *)popq(&pqslot->pqueue, &holder->plink);
00456 }
00457
00458 static inline int countpq(xnpqueue_t *pqslot)
00459 {
00460 return countq(&pqslot->pqueue);
00461 }
00462
00463 static inline int emptypq_p(xnpqueue_t *pqslot)
00464 {
00465 return emptyq_p(&pqslot->pqueue);
00466 }
00467
00468
00469
00470 typedef struct xngholder {
00471
00472 xnpholder_t glink;
00473 void *data;
00474
00475 } xngholder_t;
00476
00477 static inline void initgh(xngholder_t *holder, void *data)
00478 {
00479 inith(&holder->glink.plink);
00480 holder->data = data;
00481 }
00482
00483
00484
00485 typedef struct xngqueue {
00486
00487 xnpqueue_t gqueue;
00488 xnqueue_t *freehq;
00489 void (*starvation) (xnqueue_t *);
00490 int threshold;
00491
00492 } xngqueue_t;
00493
00494 static inline void initgq(xngqueue_t *gqslot,
00495 xnqueue_t *freehq,
00496 void (*starvation) (xnqueue_t *),
00497 int threshold)
00498 {
00499 initpq(&gqslot->gqueue);
00500 gqslot->freehq = freehq;
00501 gqslot->starvation = starvation;
00502 gqslot->threshold = threshold;
00503 }
00504
00505 static inline xngholder_t *allocgh(xngqueue_t *gqslot)
00506 {
00507 if (countq(gqslot->freehq) < gqslot->threshold)
00508 gqslot->starvation(gqslot->freehq);
00509
00510 return (xngholder_t *)getq(gqslot->freehq);
00511 }
00512
00513 static inline void *removegh(xngqueue_t *gqslot, xngholder_t *holder)
00514 {
00515 removepq(&gqslot->gqueue, &holder->glink);
00516 appendq(gqslot->freehq, &holder->glink.plink);
00517 return holder->data;
00518 }
00519
00520 static inline void insertgqf(xngqueue_t *gqslot, void *data, int prio)
00521 {
00522 xngholder_t *holder = allocgh(gqslot);
00523 holder->data = data;
00524 return insertpqf(&gqslot->gqueue, &holder->glink, prio);
00525 }
00526
00527 static inline void insertgql(xngqueue_t *gqslot, void *data, int prio)
00528 {
00529 xngholder_t *holder = allocgh(gqslot);
00530 holder->data = data;
00531 insertpql(&gqslot->gqueue, &holder->glink, prio);
00532 }
00533
00534 static inline void appendgq(xngqueue_t *gqslot, void *data)
00535 {
00536 xngholder_t *holder = allocgh(gqslot);
00537 holder->data = data;
00538 appendpq(&gqslot->gqueue, &holder->glink);
00539 }
00540
00541 static inline void prependgq(xngqueue_t *gqslot, void *data)
00542 {
00543 xngholder_t *holder = allocgh(gqslot);
00544 holder->data = data;
00545 prependpq(&gqslot->gqueue, &holder->glink);
00546 }
00547
00548 static inline xngholder_t *getheadgq(xngqueue_t *gqslot)
00549 {
00550 return (xngholder_t *)getheadpq(&gqslot->gqueue);
00551 }
00552
00553 static inline xngholder_t *nextgq(xngqueue_t *gqslot, xngholder_t *holder)
00554 {
00555 return (xngholder_t *)nextpq(&gqslot->gqueue, &holder->glink);
00556 }
00557
00558 static inline void *getgq(xngqueue_t *gqslot)
00559 {
00560 xngholder_t *holder = getheadgq(gqslot);
00561
00562 if (!holder)
00563 return NULL;
00564
00565 appendq(gqslot->freehq, &getpq(&gqslot->gqueue)->plink);
00566
00567 return holder->data;
00568 }
00569
00570 static inline xngholder_t *popgq(xngqueue_t *gqslot, xngholder_t *holder)
00571 {
00572 xngholder_t *nextholder = nextgq(gqslot, holder);
00573 removegh(gqslot, holder);
00574 return nextholder;
00575 }
00576
00577 static inline xngholder_t *findgq(xngqueue_t *gqslot, void *data)
00578 {
00579 xnholder_t *holder;
00580
00581 for (holder = gqslot->gqueue.pqueue.head.next;
00582 holder != &gqslot->gqueue.pqueue.head; holder = holder->next) {
00583 if (((xngholder_t *)holder)->data == data)
00584 return (xngholder_t *)holder;
00585 }
00586
00587 return NULL;
00588 }
00589
00590 static inline void *removegq(xngqueue_t *gqslot, void *data)
00591 {
00592 xngholder_t *holder = findgq(gqslot, data);
00593 return holder ? removegh(gqslot, holder) : NULL;
00594 }
00595
00596 static inline int countgq(xngqueue_t *gqslot)
00597 {
00598 return countpq(&gqslot->gqueue);
00599 }
00600
00601 static inline int emptygq_p(xngqueue_t *gqslot)
00602 {
00603 return emptypq_p(&gqslot->gqueue);
00604 }
00605
00606 #endif