![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to queue.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / Gnu-Mach / kern|
Return to queue.h CVS log | Up to [GnuMach] / Gnu-Mach / kern |
1.1.1.2 ! root 1: /* 1.1 root 2: * Mach Operating System 3: * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University 4: * All Rights Reserved. 1.1.1.2 ! root 5: * 1.1 root 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. 1.1.1.2 ! root 11: * 1.1 root 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. 1.1.1.2 ! root 15: * 1.1 root 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: 1.1.1.2 ! root 369: #endif /* _KERN_QUEUE_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.