Return to queue.h CVS log

Up to [GnuMach] / OSKit-Mach / kern

Annotation of OSKit-Mach/kern/queue.h, revision 1.1

1.1     ! root        1: /*
        !             2:  * Mach Operating System
        !             3:  * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
        !             4:  * All Rights Reserved.
        !             5:  *
        !             6:  * Permission to use, copy, modify and distribute this software and its
        !             7:  * documentation is hereby granted, provided that both the copyright
        !             8:  * notice and this permission notice appear in all copies of the
        !             9:  * software, derivative works or modified versions, and any portions
        !            10:  * thereof, and that both notices appear in supporting documentation.
        !            11:  *
        !            12:  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
        !            13:  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
        !            14:  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
        !            15:  *
        !            16:  * Carnegie Mellon requests users of this software to return to
        !            17:  *
        !            18:  *  Software Distribution Coordinator  or  [email protected]
        !            19:  *  School of Computer Science
        !            20:  *  Carnegie Mellon University
        !            21:  *  Pittsburgh PA 15213-3890
        !            22:  *
        !            23:  * any improvements or extensions that they make and grant Carnegie Mellon rights
        !            24:  * to redistribute these changes.
        !            25:  */
        !            26: /*
        !            27:  *     File:   queue.h
        !            28:  *     Author: Avadis Tevanian, Jr.
        !            29:  *     Date:   1985
        !            30:  *
        !            31:  *     Type definitions for generic queues.
        !            32:  *
        !            33:  */
        !            34: 
        !            35: #ifndef        _KERN_QUEUE_H_
        !            36: #define        _KERN_QUEUE_H_
        !            37: 
        !            38: #include <kern/lock.h>
        !            39: 
        !            40: /*
        !            41:  *     Queue of abstract objects.  Queue is maintained
        !            42:  *     within that object.
        !            43:  *
        !            44:  *     Supports fast removal from within the queue.
        !            45:  *
        !            46:  *     How to declare a queue of elements of type "foo_t":
        !            47:  *             In the "*foo_t" type, you must have a field of
        !            48:  *             type "queue_chain_t" to hold together this queue.
        !            49:  *             There may be more than one chain through a
        !            50:  *             "foo_t", for use by different queues.
        !            51:  *
        !            52:  *             Declare the queue as a "queue_t" type.
        !            53:  *
        !            54:  *             Elements of the queue (of type "foo_t", that is)
        !            55:  *             are referred to by reference, and cast to type
        !            56:  *             "queue_entry_t" within this module.
        !            57:  */
        !            58: 
        !            59: /*
        !            60:  *     A generic doubly-linked list (queue).
        !            61:  */
        !            62: 
        !            63: struct queue_entry {
        !            64:        struct queue_entry      *next;          /* next element */
        !            65:        struct queue_entry      *prev;          /* previous element */
        !            66: };
        !            67: 
        !            68: typedef struct queue_entry     *queue_t;
        !            69: typedef        struct queue_entry      queue_head_t;
        !            70: typedef        struct queue_entry      queue_chain_t;
        !            71: typedef        struct queue_entry      *queue_entry_t;
        !            72: 
        !            73: /*
        !            74:  *     enqueue puts "elt" on the "queue".
        !            75:  *     dequeue returns the first element in the "queue".
        !            76:  *     remqueue removes the specified "elt" from the specified "queue".
        !            77:  */
        !            78: 
        !            79: #define enqueue(queue,elt)     enqueue_tail(queue, elt)
        !            80: #define        dequeue(queue)          dequeue_head(queue)
        !            81: 
        !            82: void           enqueue_head();
        !            83: void           enqueue_tail();
        !            84: queue_entry_t  dequeue_head();
        !            85: queue_entry_t  dequeue_tail();
        !            86: void           remqueue();
        !            87: 
        !            88: /*
        !            89:  *     Macro:          queue_init
        !            90:  *     Function:
        !            91:  *             Initialize the given queue.
        !            92:  *     Header:
        !            93:  *             void queue_init(q)
        !            94:  *                     queue_t         q;      *MODIFIED*
        !            95:  */
        !            96: #define        queue_init(q)   ((q)->next = (q)->prev = q)
        !            97: 
        !            98: /*
        !            99:  *     Macro:          queue_first
        !           100:  *     Function:
        !           101:  *             Returns the first entry in the queue,
        !           102:  *     Header:
        !           103:  *             queue_entry_t queue_first(q)
        !           104:  *                     queue_t q;              *IN*
        !           105:  */
        !           106: #define        queue_first(q)  ((q)->next)
        !           107: 
        !           108: /*
        !           109:  *     Macro:          queue_next
        !           110:  *     Function:
        !           111:  *             Returns the entry after an item in the queue.
        !           112:  *     Header:
        !           113:  *             queue_entry_t queue_next(qc)
        !           114:  *                     queue_t qc;
        !           115:  */
        !           116: #define        queue_next(qc)  ((qc)->next)
        !           117: 
        !           118: /*
        !           119:  *     Macro:          queue_last
        !           120:  *     Function:
        !           121:  *             Returns the last entry in the queue.
        !           122:  *     Header:
        !           123:  *             queue_entry_t queue_last(q)
        !           124:  *                     queue_t q;               *IN*
        !           125:  */
        !           126: #define        queue_last(q)   ((q)->prev)
        !           127: 
        !           128: /*
        !           129:  *     Macro:          queue_prev
        !           130:  *     Function:
        !           131:  *             Returns the entry before an item in the queue.
        !           132:  *     Header:
        !           133:  *             queue_entry_t queue_prev(qc)
        !           134:  *                     queue_t qc;
        !           135:  */
        !           136: #define        queue_prev(qc)  ((qc)->prev)
        !           137: 
        !           138: /*
        !           139:  *     Macro:          queue_end
        !           140:  *     Function:
        !           141:  *             Tests whether a new entry is really the end of
        !           142:  *             the queue.
        !           143:  *     Header:
        !           144:  *             boolean_t queue_end(q, qe)
        !           145:  *                     queue_t q;
        !           146:  *                     queue_entry_t qe;
        !           147:  */
        !           148: #define        queue_end(q, qe)        ((q) == (qe))
        !           149: 
        !           150: /*
        !           151:  *     Macro:          queue_empty
        !           152:  *     Function:
        !           153:  *             Tests whether a queue is empty.
        !           154:  *     Header:
        !           155:  *             boolean_t queue_empty(q)
        !           156:  *                     queue_t q;
        !           157:  */
        !           158: #define        queue_empty(q)          queue_end((q), queue_first(q))
        !           159: 
        !           160: 
        !           161: /*----------------------------------------------------------------*/
        !           162: /*
        !           163:  * Macros that operate on generic structures.  The queue
        !           164:  * chain may be at any location within the structure, and there
        !           165:  * may be more than one chain.
        !           166:  */
        !           167: 
        !           168: /*
        !           169:  *     Macro:          queue_enter
        !           170:  *     Function:
        !           171:  *             Insert a new element at the tail of the queue.
        !           172:  *     Header:
        !           173:  *             void queue_enter(q, elt, type, field)
        !           174:  *                     queue_t q;
        !           175:  *                     <type> elt;
        !           176:  *                     <type> is what's in our queue
        !           177:  *                     <field> is the chain field in (*<type>)
        !           178:  */
        !           179: #define queue_enter(head, elt, type, field)                    \
        !           180: {                                                              \
        !           181:        register queue_entry_t prev;                            \
        !           182:                                                                \
        !           183:        prev = (head)->prev;                                    \
        !           184:        if ((head) == prev) {                                   \
        !           185:                (head)->next = (queue_entry_t) (elt);           \
        !           186:        }                                                       \
        !           187:        else {                                                  \
        !           188:                ((type)prev)->field.next = (queue_entry_t)(elt);\
        !           189:        }                                                       \
        !           190:        (elt)->field.prev = prev;                               \
        !           191:        (elt)->field.next = head;                               \
        !           192:        (head)->prev = (queue_entry_t) elt;                     \
        !           193: }
        !           194: 
        !           195: /*
        !           196:  *     Macro:          queue_enter_first
        !           197:  *     Function:
        !           198:  *             Insert a new element at the head of the queue.
        !           199:  *     Header:
        !           200:  *             void queue_enter_first(q, elt, type, field)
        !           201:  *                     queue_t q;
        !           202:  *                     <type> elt;
        !           203:  *                     <type> is what's in our queue
        !           204:  *                     <field> is the chain field in (*<type>)
        !           205:  */
        !           206: #define queue_enter_first(head, elt, type, field)              \
        !           207: {                                                              \
        !           208:        register queue_entry_t next;                            \
        !           209:                                                                \
        !           210:        next = (head)->next;                                    \
        !           211:        if ((head) == next) {                                   \
        !           212:                (head)->prev = (queue_entry_t) (elt);           \
        !           213:        }                                                       \
        !           214:        else {                                                  \
        !           215:                ((type)next)->field.prev = (queue_entry_t)(elt);\
        !           216:        }                                                       \
        !           217:        (elt)->field.next = next;                               \
        !           218:        (elt)->field.prev = head;                               \
        !           219:        (head)->next = (queue_entry_t) elt;                     \
        !           220: }
        !           221: 
        !           222: /*
        !           223:  *     Macro:          queue_field [internal use only]
        !           224:  *     Function:
        !           225:  *             Find the queue_chain_t (or queue_t) for the
        !           226:  *             given element (thing) in the given queue (head)
        !           227:  */
        !           228: #define        queue_field(head, thing, type, field)                   \
        !           229:                (((head) == (thing)) ? (head) : &((type)(thing))->field)
        !           230: 
        !           231: /*
        !           232:  *     Macro:          queue_remove
        !           233:  *     Function:
        !           234:  *             Remove an arbitrary item from the queue.
        !           235:  *     Header:
        !           236:  *             void queue_remove(q, qe, type, field)
        !           237:  *                     arguments as in queue_enter
        !           238:  */
        !           239: #define        queue_remove(head, elt, type, field)                    \
        !           240: {                                                              \
        !           241:        register queue_entry_t  next, prev;                     \
        !           242:                                                                \
        !           243:        next = (elt)->field.next;                               \
        !           244:        prev = (elt)->field.prev;                               \
        !           245:                                                                \
        !           246:        if ((head) == next)                                     \
        !           247:                (head)->prev = prev;                            \
        !           248:        else                                                    \
        !           249:                ((type)next)->field.prev = prev;                \
        !           250:                                                                \
        !           251:        if ((head) == prev)                                     \
        !           252:                (head)->next = next;                            \
        !           253:        else                                                    \
        !           254:                ((type)prev)->field.next = next;                \
        !           255: }
        !           256: 
        !           257: /*
        !           258:  *     Macro:          queue_remove_first
        !           259:  *     Function:
        !           260:  *             Remove and return the entry at the head of
        !           261:  *             the queue.
        !           262:  *     Header:
        !           263:  *             queue_remove_first(head, entry, type, field)
        !           264:  *             entry is returned by reference
        !           265:  */
        !           266: #define        queue_remove_first(head, entry, type, field)            \
        !           267: {                                                              \
        !           268:        register queue_entry_t  next;                           \
        !           269:                                                                \
        !           270:        (entry) = (type) ((head)->next);                        \
        !           271:        next = (entry)->field.next;                             \
        !           272:                                                                \
        !           273:        if ((head) == next)                                     \
        !           274:                (head)->prev = (head);                          \
        !           275:        else                                                    \
        !           276:                ((type)(next))->field.prev = (head);            \
        !           277:        (head)->next = next;                                    \
        !           278: }
        !           279: 
        !           280: /*
        !           281:  *     Macro:          queue_remove_last
        !           282:  *     Function:
        !           283:  *             Remove and return the entry at the tail of
        !           284:  *             the queue.
        !           285:  *     Header:
        !           286:  *             queue_remove_last(head, entry, type, field)
        !           287:  *             entry is returned by reference
        !           288:  */
        !           289: #define        queue_remove_last(head, entry, type, field)             \
        !           290: {                                                              \
        !           291:        register queue_entry_t  prev;                           \
        !           292:                                                                \
        !           293:        (entry) = (type) ((head)->prev);                        \
        !           294:        prev = (entry)->field.prev;                             \
        !           295:                                                                \
        !           296:        if ((head) == prev)                                     \
        !           297:                (head)->next = (head);                          \
        !           298:        else                                                    \
        !           299:                ((type)(prev))->field.next = (head);            \
        !           300:        (head)->prev = prev;                                    \
        !           301: }
        !           302: 
        !           303: /*
        !           304:  *     Macro:          queue_assign
        !           305:  */
        !           306: #define        queue_assign(to, from, type, field)                     \
        !           307: {                                                              \
        !           308:        ((type)((from)->prev))->field.next = (to);              \
        !           309:        ((type)((from)->next))->field.prev = (to);              \
        !           310:        *to = *from;                                            \
        !           311: }
        !           312: 
        !           313: /*
        !           314:  *     Macro:          queue_iterate
        !           315:  *     Function:
        !           316:  *             iterate over each item in the queue.
        !           317:  *             Generates a 'for' loop, setting elt to
        !           318:  *             each item in turn (by reference).
        !           319:  *     Header:
        !           320:  *             queue_iterate(q, elt, type, field)
        !           321:  *                     queue_t q;
        !           322:  *                     <type> elt;
        !           323:  *                     <type> is what's in our queue
        !           324:  *                     <field> is the chain field in (*<type>)
        !           325:  */
        !           326: #define queue_iterate(head, elt, type, field)                  \
        !           327:        for ((elt) = (type) queue_first(head);                  \
        !           328:             !queue_end((head), (queue_entry_t)(elt));          \
        !           329:             (elt) = (type) queue_next(&(elt)->field))
        !           330: 
        !           331: 
        !           332: 
        !           333: /*----------------------------------------------------------------*/
        !           334: /*
        !           335:  *     Define macros for queues with locks.
        !           336:  */
        !           337: struct mpqueue_head {
        !           338:        struct queue_entry      head;           /* header for queue */
        !           339:        struct slock            lock;           /* lock for queue */
        !           340: };
        !           341: 
        !           342: typedef struct mpqueue_head    mpqueue_head_t;
        !           343: 
        !           344: #define        round_mpq(size)         (size)
        !           345: 
        !           346: #define mpqueue_init(q) \
        !           347:        { \
        !           348:                queue_init(&(q)->head); \
        !           349:                simple_lock_init(&(q)->lock); \
        !           350:        }
        !           351: 
        !           352: #define mpenqueue_tail(q, elt) \
        !           353:                simple_lock(&(q)->lock); \
        !           354:                enqueue_tail(&(q)->head, elt); \
        !           355:                simple_unlock(&(q)->lock);
        !           356: 
        !           357: #define mpdequeue_head(q, elt) \
        !           358:                simple_lock(&(q)->lock); \
        !           359:                if (queue_empty(&(q)->head)) \
        !           360:                        *(elt) = 0; \
        !           361:                else \
        !           362:                        *(elt) = dequeue_head(&(q)->head); \
        !           363:                simple_unlock(&(q)->lock);
        !           364: 
        !           365: /*
        !           366:  *     Old queue stuff, will go away soon.
        !           367:  */
        !           368: 
        !           369: #endif /* _KERN_QUEUE_H_ */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.