Return to queue.h CVS log

Up to [Apple Darwin 0.x] / kernel / kern

Annotation of kernel/kern/queue.h, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
        !             3:  *
        !             4:  * @APPLE_LICENSE_HEADER_START@
        !             5:  * 
        !             6:  * Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
        !             7:  * Reserved.  This file contains Original Code and/or Modifications of
        !             8:  * Original Code as defined in and that are subject to the Apple Public
        !             9:  * Source License Version 1.1 (the "License").  You may not use this file
        !            10:  * except in compliance with the License.  Please obtain a copy of the
        !            11:  * License at http://www.apple.com/publicsource and read it before using
        !            12:  * this file.
        !            13:  * 
        !            14:  * The Original Code and all software distributed under the License are
        !            15:  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
        !            16:  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
        !            17:  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
        !            18:  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
        !            19:  * License for the specific language governing rights and limitations
        !            20:  * under the License.
        !            21:  * 
        !            22:  * @APPLE_LICENSE_HEADER_END@
        !            23:  */
        !            24: 
        !            25: /* 
        !            26:  * Mach Operating System
        !            27:  * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
        !            28:  * All Rights Reserved.
        !            29:  * 
        !            30:  * Permission to use, copy, modify and distribute this software and its
        !            31:  * documentation is hereby granted, provided that both the copyright
        !            32:  * notice and this permission notice appear in all copies of the
        !            33:  * software, derivative works or modified versions, and any portions
        !            34:  * thereof, and that both notices appear in supporting documentation.
        !            35:  * 
        !            36:  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
        !            37:  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
        !            38:  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
        !            39:  * 
        !            40:  * Carnegie Mellon requests users of this software to return to
        !            41:  *
        !            42:  *  Software Distribution Coordinator  or  [email protected]
        !            43:  *  School of Computer Science
        !            44:  *  Carnegie Mellon University
        !            45:  *  Pittsburgh PA 15213-3890
        !            46:  *
        !            47:  * any improvements or extensions that they make and grant Carnegie Mellon rights
        !            48:  * to redistribute these changes.
        !            49:  */
        !            50: /*
        !            51:  *     File:   queue.h
        !            52:  *     Author: Avadis Tevanian, Jr.
        !            53:  *     Date:   1985
        !            54:  *
        !            55:  *     Type definitions for generic queues.
        !            56:  *
        !            57:  */
        !            58: 
        !            59: #ifndef        _KERN_QUEUE_H_
        !            60: #define        _KERN_QUEUE_H_
        !            61: 
        !            62: #include <kern/lock.h>
        !            63: #include <kern/macro_help.h>
        !            64: 
        !            65: /*
        !            66:  *     Queue of abstract objects.  Queue is maintained
        !            67:  *     within that object.
        !            68:  *
        !            69:  *     Supports fast removal from within the queue.
        !            70:  *
        !            71:  *     How to declare a queue of elements of type "foo_t":
        !            72:  *             In the "*foo_t" type, you must have a field of
        !            73:  *             type "queue_chain_t" to hold together this queue.
        !            74:  *             There may be more than one chain through a
        !            75:  *             "foo_t", for use by different queues.
        !            76:  *
        !            77:  *             Declare the queue as a "queue_t" type.
        !            78:  *
        !            79:  *             Elements of the queue (of type "foo_t", that is)
        !            80:  *             are referred to by reference, and cast to type
        !            81:  *             "queue_entry_t" within this module.
        !            82:  */
        !            83: 
        !            84: /*
        !            85:  *     A generic doubly-linked list (queue).
        !            86:  */
        !            87: 
        !            88: struct queue_entry {
        !            89:        struct queue_entry      *next;          /* next element */
        !            90:        struct queue_entry      *prev;          /* previous element */
        !            91: };
        !            92: 
        !            93: typedef struct queue_entry     *queue_t;
        !            94: typedef        struct queue_entry      queue_head_t;
        !            95: typedef        struct queue_entry      queue_chain_t;
        !            96: typedef        struct queue_entry      *queue_entry_t;
        !            97: 
        !            98: /*
        !            99:  *     enqueue puts "elt" on the "queue".
        !           100:  *     dequeue returns the first element in the "queue".
        !           101:  *     remqueue removes the specified "elt" from the specified "queue".
        !           102:  */
        !           103: 
        !           104: #define enqueue(queue,elt)     enqueue_tail(queue, elt)
        !           105: #define        dequeue(queue)          dequeue_head(queue)
        !           106: 
        !           107: /*
        !           108:  *     Routines to implement queue package.
        !           109:  */
        !           110:  
        !           111: #ifndef        _KERN_QUEUE_FUNCTION_SCOPE_
        !           112: #define        _KERN_QUEUE_FUNCTION_SCOPE_ static __inline__
        !           113: #define _KERN_QUEUE_H_INTERNAL_SCOPING_
        !           114: #endif
        !           115: 
        !           116: /*
        !           117:  *     Insert element at head of queue.
        !           118:  */
        !           119: _KERN_QUEUE_FUNCTION_SCOPE_
        !           120: void enqueue_head(
        !           121:        register queue_t        que,
        !           122:        register queue_entry_t  elt)
        !           123: {
        !           124:        elt->next = que->next;
        !           125:        elt->prev = que;
        !           126:        elt->next->prev = elt;
        !           127:        que->next = elt;
        !           128: }
        !           129: 
        !           130: /*
        !           131:  *     Insert element at tail of queue.
        !           132:  */
        !           133: _KERN_QUEUE_FUNCTION_SCOPE_
        !           134: void enqueue_tail(
        !           135:        register queue_t        que,
        !           136:        register queue_entry_t  elt)
        !           137: {
        !           138:        elt->next = que;
        !           139:        elt->prev = que->prev;
        !           140:        elt->prev->next = elt;
        !           141:        que->prev = elt;
        !           142: }
        !           143: 
        !           144: /*
        !           145:  *     Remove and return element at head of queue.
        !           146:  */
        !           147: _KERN_QUEUE_FUNCTION_SCOPE_
        !           148: queue_entry_t dequeue_head(
        !           149:        register queue_t        que)
        !           150: {
        !           151:        register queue_entry_t  elt;
        !           152: 
        !           153:        if (que->next == que)
        !           154:                return((queue_entry_t)0);
        !           155: 
        !           156:        elt = que->next;
        !           157:        elt->next->prev = que;
        !           158:        que->next = elt->next;
        !           159:        return(elt);
        !           160: }
        !           161: 
        !           162: /*
        !           163:  *     Remove and return element at tail of queue.
        !           164:  */
        !           165: _KERN_QUEUE_FUNCTION_SCOPE_
        !           166: queue_entry_t dequeue_tail(
        !           167:        register queue_t        que)
        !           168: {
        !           169:        register queue_entry_t  elt;
        !           170: 
        !           171:        if (que->prev == que)
        !           172:                return((queue_entry_t)0);
        !           173: 
        !           174:        elt = que->prev;
        !           175:        elt->prev->next = que;
        !           176:        que->prev = elt->prev;
        !           177:        return(elt);
        !           178: }
        !           179: 
        !           180: /*
        !           181:  *     Remove arbitrary element from queue.
        !           182:  *     Does not check whether element is on queue - the world
        !           183:  *     will go haywire if it isn't.
        !           184:  */
        !           185: 
        !           186: _KERN_QUEUE_FUNCTION_SCOPE_
        !           187: /*ARGSUSED*/
        !           188: void remqueue(
        !           189:        queue_t                 que,
        !           190:        register queue_entry_t  elt)
        !           191: {
        !           192:        elt->next->prev = elt->prev;
        !           193:        elt->prev->next = elt->next;
        !           194: }
        !           195: 
        !           196: /*
        !           197:  *     Routines to directly imitate the VAX hardware queue
        !           198:  *     package.
        !           199:  */
        !           200:  _KERN_QUEUE_FUNCTION_SCOPE_
        !           201: void insque(
        !           202:        register struct queue_entry *entry,
        !           203:        register struct queue_entry *pred)
        !           204: {
        !           205:        entry->next = pred->next;
        !           206:        entry->prev = pred;
        !           207:        (pred->next)->prev = entry;
        !           208:        pred->next = entry;
        !           209: }
        !           210: 
        !           211: _KERN_QUEUE_FUNCTION_SCOPE_
        !           212: struct queue_entry
        !           213: *remque(
        !           214:        register struct queue_entry *elt)
        !           215: {
        !           216:        (elt->next)->prev = elt->prev;
        !           217:        (elt->prev)->next = elt->next;
        !           218:        return(elt);
        !           219: }
        !           220: 
        !           221: #ifdef _KERN_QUEUE_H_INTERNAL_SCOPING_
        !           222: #undef _KERN_QUEUE_H_INTERNAL_SCOPING_
        !           223: #endif
        !           224: 
        !           225: /*
        !           226:  *     Macro:          queue_init
        !           227:  *     Function:
        !           228:  *             Initialize the given queue.
        !           229:  *     Header:
        !           230:  *             void queue_init(q)
        !           231:  *                     queue_t         q;      *MODIFIED*
        !           232:  */
        !           233: #define        queue_init(q)   ((q)->next = (q)->prev = q)
        !           234: 
        !           235: /*
        !           236:  *     Macro:          queue_first
        !           237:  *     Function:
        !           238:  *             Returns the first entry in the queue,
        !           239:  *     Header:
        !           240:  *             queue_entry_t queue_first(q)
        !           241:  *                     queue_t q;              *IN*
        !           242:  */
        !           243: #define        queue_first(q)  ((q)->next)
        !           244: 
        !           245: /*
        !           246:  *     Macro:          queue_next
        !           247:  *     Function:
        !           248:  *             Returns the entry after an item in the queue.
        !           249:  *     Header:
        !           250:  *             queue_entry_t queue_next(qc)
        !           251:  *                     queue_t qc;
        !           252:  */
        !           253: #define        queue_next(qc)  ((qc)->next)
        !           254: 
        !           255: /*
        !           256:  *     Macro:          queue_last
        !           257:  *     Function:
        !           258:  *             Returns the last entry in the queue.
        !           259:  *     Header:
        !           260:  *             queue_entry_t queue_last(q)
        !           261:  *                     queue_t q;               *IN*
        !           262:  */
        !           263: #define        queue_last(q)   ((q)->prev)
        !           264: 
        !           265: /*
        !           266:  *     Macro:          queue_prev
        !           267:  *     Function:
        !           268:  *             Returns the entry before an item in the queue.
        !           269:  *     Header:
        !           270:  *             queue_entry_t queue_prev(qc)
        !           271:  *                     queue_t qc;
        !           272:  */
        !           273: #define        queue_prev(qc)  ((qc)->prev)
        !           274: 
        !           275: /*
        !           276:  *     Macro:          queue_end
        !           277:  *     Function:
        !           278:  *             Tests whether a new entry is really the end of
        !           279:  *             the queue.
        !           280:  *     Header:
        !           281:  *             boolean_t queue_end(q, qe)
        !           282:  *                     queue_t q;
        !           283:  *                     queue_entry_t qe;
        !           284:  */
        !           285: #define        queue_end(q, qe)        ((q) == (qe))
        !           286: 
        !           287: /*
        !           288:  *     Macro:          queue_empty
        !           289:  *     Function:
        !           290:  *             Tests whether a queue is empty.
        !           291:  *     Header:
        !           292:  *             boolean_t queue_empty(q)
        !           293:  *                     queue_t q;
        !           294:  */
        !           295: #define        queue_empty(q)          queue_end((q), queue_first(q))
        !           296: 
        !           297: 
        !           298: /*----------------------------------------------------------------*/
        !           299: /*
        !           300:  * Macros that operate on generic structures.  The queue
        !           301:  * chain may be at any location within the structure, and there
        !           302:  * may be more than one chain.
        !           303:  */
        !           304: 
        !           305: /*
        !           306:  *     Macro:          queue_enter
        !           307:  *     Function:
        !           308:  *             Insert a new element at the tail of the queue.
        !           309:  *     Header:
        !           310:  *             void queue_enter(q, elt, type, field)
        !           311:  *                     queue_t q;
        !           312:  *                     <type> elt;
        !           313:  *                     <type> is what's in our queue
        !           314:  *                     <field> is the chain field in (*<type>)
        !           315:  */
        !           316: #define queue_enter(head, elt, type, field)                    \
        !           317: MACRO_BEGIN                                                    \
        !           318:        register queue_entry_t prev;                            \
        !           319:                                                                \
        !           320:        prev = (head)->prev;                                    \
        !           321:        if ((head) == prev) {                                   \
        !           322:                (head)->next = (queue_entry_t) (elt);           \
        !           323:        }                                                       \
        !           324:        else {                                                  \
        !           325:                ((type)prev)->field.next = (queue_entry_t)(elt);\
        !           326:        }                                                       \
        !           327:        (elt)->field.prev = prev;                               \
        !           328:        (elt)->field.next = head;                               \
        !           329:        (head)->prev = (queue_entry_t) elt;                     \
        !           330: MACRO_END
        !           331: 
        !           332: /*
        !           333:  *     Macro:          queue_enter_first
        !           334:  *     Function:
        !           335:  *             Insert a new element at the head of the queue.
        !           336:  *     Header:
        !           337:  *             void queue_enter_first(q, elt, type, field)
        !           338:  *                     queue_t q;
        !           339:  *                     <type> elt;
        !           340:  *                     <type> is what's in our queue
        !           341:  *                     <field> is the chain field in (*<type>)
        !           342:  */
        !           343: #define queue_enter_first(head, elt, type, field)              \
        !           344: MACRO_BEGIN                                                    \
        !           345:        register queue_entry_t next;                            \
        !           346:                                                                \
        !           347:        next = (head)->next;                                    \
        !           348:        if ((head) == next) {                                   \
        !           349:                (head)->prev = (queue_entry_t) (elt);           \
        !           350:        }                                                       \
        !           351:        else {                                                  \
        !           352:                ((type)next)->field.prev = (queue_entry_t)(elt);\
        !           353:        }                                                       \
        !           354:        (elt)->field.next = next;                               \
        !           355:        (elt)->field.prev = head;                               \
        !           356:        (head)->next = (queue_entry_t) elt;                     \
        !           357: MACRO_END
        !           358: 
        !           359: /*
        !           360:  *     Macro:          queue_field [internal use only]
        !           361:  *     Function:
        !           362:  *             Find the queue_chain_t (or queue_t) for the
        !           363:  *             given element (thing) in the given queue (head)
        !           364:  */
        !           365: #define        queue_field(head, thing, type, field)                   \
        !           366:                (((head) == (thing)) ? (head) : &((type)(thing))->field)
        !           367: 
        !           368: /*
        !           369:  *     Macro:          queue_remove
        !           370:  *     Function:
        !           371:  *             Remove an arbitrary item from the queue.
        !           372:  *     Header:
        !           373:  *             void queue_remove(q, qe, type, field)
        !           374:  *                     arguments as in queue_enter
        !           375:  */
        !           376: #define        queue_remove(head, elt, type, field)                    \
        !           377: MACRO_BEGIN                                                    \
        !           378:        register queue_entry_t  next, prev;                     \
        !           379:                                                                \
        !           380:        next = (elt)->field.next;                               \
        !           381:        prev = (elt)->field.prev;                               \
        !           382:                                                                \
        !           383:        if ((head) == next)                                     \
        !           384:                (head)->prev = prev;                            \
        !           385:        else                                                    \
        !           386:                ((type)next)->field.prev = prev;                \
        !           387:                                                                \
        !           388:        if ((head) == prev)                                     \
        !           389:                (head)->next = next;                            \
        !           390:        else                                                    \
        !           391:                ((type)prev)->field.next = next;                \
        !           392: MACRO_END
        !           393: 
        !           394: /*
        !           395:  *     Macro:          queue_remove_first
        !           396:  *     Function:
        !           397:  *             Remove and return the entry at the head of
        !           398:  *             the queue.
        !           399:  *     Header:
        !           400:  *             queue_remove_first(head, entry, type, field)
        !           401:  *             entry is returned by reference
        !           402:  */
        !           403: #define        queue_remove_first(head, entry, type, field)            \
        !           404: MACRO_BEGIN                                                    \
        !           405:        register queue_entry_t  next;                           \
        !           406:                                                                \
        !           407:        (entry) = (type) ((head)->next);                        \
        !           408:        next = (entry)->field.next;                             \
        !           409:                                                                \
        !           410:        if ((head) == next)                                     \
        !           411:                (head)->prev = (head);                          \
        !           412:        else                                                    \
        !           413:                ((type)(next))->field.prev = (head);            \
        !           414:        (head)->next = next;                                    \
        !           415: MACRO_END
        !           416: 
        !           417: /*
        !           418:  *     Macro:          queue_remove_last
        !           419:  *     Function:
        !           420:  *             Remove and return the entry at the tail of
        !           421:  *             the queue.
        !           422:  *     Header:
        !           423:  *             queue_remove_last(head, entry, type, field)
        !           424:  *             entry is returned by reference
        !           425:  */
        !           426: #define        queue_remove_last(head, entry, type, field)             \
        !           427: MACRO_BEGIN                                                    \
        !           428:        register queue_entry_t  prev;                           \
        !           429:                                                                \
        !           430:        (entry) = (type) ((head)->prev);                        \
        !           431:        prev = (entry)->field.prev;                             \
        !           432:                                                                \
        !           433:        if ((head) == prev)                                     \
        !           434:                (head)->next = (head);                          \
        !           435:        else                                                    \
        !           436:                ((type)(prev))->field.next = (head);            \
        !           437:        (head)->prev = prev;                                    \
        !           438: MACRO_END
        !           439: 
        !           440: /*
        !           441:  *     Macro:          queue_assign
        !           442:  */
        !           443: #define        queue_assign(to, from, type, field)                     \
        !           444: MACRO_BEGIN                                                    \
        !           445:        ((type)((from)->prev))->field.next = (to);              \
        !           446:        ((type)((from)->next))->field.prev = (to);              \
        !           447:        *to = *from;                                            \
        !           448: MACRO_END
        !           449: 
        !           450: /*
        !           451:  *     Macro:          queue_iterate
        !           452:  *     Function:
        !           453:  *             iterate over each item in the queue.
        !           454:  *             Generates a 'for' loop, setting elt to
        !           455:  *             each item in turn (by reference).
        !           456:  *     Header:
        !           457:  *             queue_iterate(q, elt, type, field)
        !           458:  *                     queue_t q;
        !           459:  *                     <type> elt;
        !           460:  *                     <type> is what's in our queue
        !           461:  *                     <field> is the chain field in (*<type>)
        !           462:  */
        !           463: #define queue_iterate(head, elt, type, field)                  \
        !           464:        for ((elt) = (type) queue_first(head);                  \
        !           465:             !queue_end((head), (queue_entry_t)(elt));          \
        !           466:             (elt) = (type) queue_next(&(elt)->field))
        !           467: 
        !           468: #endif /* _KERN_QUEUE_H_ */

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