00001 /*- 00002 * See the file LICENSE for redistribution information. 00003 * 00004 * Copyright (c) 1996, 1997, 1998, 1999, 2000 00005 * Sleepycat Software. All rights reserved. 00006 * 00007 * $Id: shqueue_8h-source.html,v 1.1 2008年06月08日 10:22:10 sebdiaz Exp $ 00008 */ 00009 #ifndef _SYS_SHQUEUE_H_ 00010 #define _SYS_SHQUEUE_H_ 00011 00012 /* 00013 * This file defines three types of data structures: lists, tail queues, and 00014 * circular queues, similarly to the include file <sys/queue.h>. 00015 * 00016 * The difference is that this set of macros can be used for structures that 00017 * reside in shared memory that may be mapped at different addresses in each 00018 * process. In most cases, the macros for shared structures exactly mirror 00019 * the normal macros, although the macro calls require an additional type 00020 * parameter, only used by the HEAD and ENTRY macros of the standard macros. 00021 * 00022 * For details on the use of these macros, see the queue(3) manual page. 00023 */ 00024 00025 #if defined(__cplusplus) 00026 extern "C" { 00027 #endif 00028 00029 /* 00030 * Shared list definitions. 00031 */ 00032 #define SH_LIST_HEAD(name) \ 00033 struct name { \ 00034 ssize_t slh_first; /* first element */ \ 00035 } 00036 00037 #define SH_LIST_ENTRY \ 00038 struct { \ 00039 ssize_t sle_next; /* relative offset next element */ \ 00040 ssize_t sle_prev; /* relative offset of prev element */ \ 00041 } 00042 00043 /* 00044 * Shared list functions. Since we use relative offsets for pointers, 00045 * 0 is a valid offset. Therefore, we use -1 to indicate end of list. 00046 * The macros ending in "P" return pointers without checking for end 00047 * of list, the others check for end of list and evaluate to either a 00048 * pointer or NULL. 00049 */ 00050 00051 #define SH_LIST_FIRSTP(head, type) \ 00052 ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first)) 00053 00054 #define SH_LIST_FIRST(head, type) \ 00055 ((head)->slh_first == -1 ? NULL : \ 00056 ((struct type *)(((u_int8_t *)(head)) + (head)->slh_first))) 00057 00058 #define SH_LIST_NEXTP(elm, field, type) \ 00059 ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next)) 00060 00061 #define SH_LIST_NEXT(elm, field, type) \ 00062 ((elm)->field.sle_next == -1 ? NULL : \ 00063 ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.sle_next))) 00064 00065 #define SH_LIST_PREV(elm, field) \ 00066 ((ssize_t *)(((u_int8_t *)(elm)) + (elm)->field.sle_prev)) 00067 00068 #define SH_PTR_TO_OFF(src, dest) \ 00069 ((ssize_t)(((u_int8_t *)(dest)) - ((u_int8_t *)(src)))) 00070 00071 #define SH_LIST_END(head) NULL 00072 00073 /* 00074 * Take the element's next pointer and calculate what the corresponding 00075 * Prev pointer should be -- basically it is the negation plus the offset 00076 * of the next field in the structure. 00077 */ 00078 #define SH_LIST_NEXT_TO_PREV(elm, field) \ 00079 (-(elm)->field.sle_next + SH_PTR_TO_OFF(elm, &(elm)->field.sle_next)) 00080 00081 #define SH_LIST_INIT(head) (head)->slh_first = -1 00082 00083 #define SH_LIST_INSERT_AFTER(listelm, elm, field, type) do { \ 00084 if ((listelm)->field.sle_next != -1) { \ 00085 (elm)->field.sle_next = SH_PTR_TO_OFF(elm, \ 00086 SH_LIST_NEXTP(listelm, field, type)); \ 00087 SH_LIST_NEXTP(listelm, field, type)->field.sle_prev = \ 00088 SH_LIST_NEXT_TO_PREV(elm, field); \ 00089 } else \ 00090 (elm)->field.sle_next = -1; \ 00091 (listelm)->field.sle_next = SH_PTR_TO_OFF(listelm, elm); \ 00092 (elm)->field.sle_prev = SH_LIST_NEXT_TO_PREV(listelm, field); \ 00093 } while (0) 00094 00095 #define SH_LIST_INSERT_HEAD(head, elm, field, type) do { \ 00096 if ((head)->slh_first != -1) { \ 00097 (elm)->field.sle_next = \ 00098 (head)->slh_first - SH_PTR_TO_OFF(head, elm); \ 00099 SH_LIST_FIRSTP(head, type)->field.sle_prev = \ 00100 SH_LIST_NEXT_TO_PREV(elm, field); \ 00101 } else \ 00102 (elm)->field.sle_next = -1; \ 00103 (head)->slh_first = SH_PTR_TO_OFF(head, elm); \ 00104 (elm)->field.sle_prev = SH_PTR_TO_OFF(elm, &(head)->slh_first); \ 00105 } while (0) 00106 00107 #define SH_LIST_REMOVE(elm, field, type) do { \ 00108 if ((elm)->field.sle_next != -1) { \ 00109 SH_LIST_NEXTP(elm, field, type)->field.sle_prev = \ 00110 (elm)->field.sle_prev - (elm)->field.sle_next; \ 00111 *SH_LIST_PREV(elm, field) += (elm)->field.sle_next; \ 00112 } else \ 00113 *SH_LIST_PREV(elm, field) = -1; \ 00114 } while (0) 00115 00116 /* 00117 * Shared tail queue definitions. 00118 */ 00119 #define SH_TAILQ_HEAD(name) \ 00120 struct name { \ 00121 ssize_t stqh_first; /* relative offset of first element */ \ 00122 ssize_t stqh_last; /* relative offset of last's next */ \ 00123 } 00124 00125 #define SH_TAILQ_ENTRY \ 00126 struct { \ 00127 ssize_t stqe_next; /* relative offset of next element */ \ 00128 ssize_t stqe_prev; /* relative offset of prev's next */ \ 00129 } 00130 00131 /* 00132 * Shared tail queue functions. 00133 */ 00134 #define SH_TAILQ_FIRSTP(head, type) \ 00135 ((struct type *)((u_int8_t *)(head) + (head)->stqh_first)) 00136 00137 #define SH_TAILQ_FIRST(head, type) \ 00138 ((head)->stqh_first == -1 ? NULL : SH_TAILQ_FIRSTP(head, type)) 00139 00140 #define SH_TAILQ_NEXTP(elm, field, type) \ 00141 ((struct type *)((u_int8_t *)(elm) + (elm)->field.stqe_next)) 00142 00143 #define SH_TAILQ_NEXT(elm, field, type) \ 00144 ((elm)->field.stqe_next == -1 ? NULL : SH_TAILQ_NEXTP(elm, field, type)) 00145 00146 #define SH_TAILQ_PREVP(elm, field) \ 00147 ((ssize_t *)((u_int8_t *)(elm) + (elm)->field.stqe_prev)) 00148 00149 #define SH_TAILQ_LAST(head) \ 00150 ((ssize_t *)(((u_int8_t *)(head)) + (head)->stqh_last)) 00151 00152 #define SH_TAILQ_NEXT_TO_PREV(elm, field) \ 00153 (-(elm)->field.stqe_next + SH_PTR_TO_OFF(elm, &(elm)->field.stqe_next)) 00154 00155 #define SH_TAILQ_END(head) NULL 00156 00157 #define SH_TAILQ_INIT(head) { \ 00158 (head)->stqh_first = -1; \ 00159 (head)->stqh_last = SH_PTR_TO_OFF(head, &(head)->stqh_first); \ 00160 } 00161 00162 #define SH_TAILQ_INSERT_HEAD(head, elm, field, type) do { \ 00163 if ((head)->stqh_first != -1) { \ 00164 (elm)->field.stqe_next = \ 00165 (head)->stqh_first - SH_PTR_TO_OFF(head, elm); \ 00166 SH_TAILQ_FIRSTP(head, type)->field.stqe_prev = \ 00167 SH_TAILQ_NEXT_TO_PREV(elm, field); \ 00168 } else { \ 00169 (elm)->field.stqe_next = -1; \ 00170 (head)->stqh_last = \ 00171 SH_PTR_TO_OFF(head, &(elm)->field.stqe_next); \ 00172 } \ 00173 (head)->stqh_first = SH_PTR_TO_OFF(head, elm); \ 00174 (elm)->field.stqe_prev = \ 00175 SH_PTR_TO_OFF(elm, &(head)->stqh_first); \ 00176 } while (0) 00177 00178 #define SH_TAILQ_INSERT_TAIL(head, elm, field) do { \ 00179 (elm)->field.stqe_next = -1; \ 00180 (elm)->field.stqe_prev = \ 00181 -SH_PTR_TO_OFF(head, elm) + (head)->stqh_last; \ 00182 if ((head)->stqh_last == \ 00183 SH_PTR_TO_OFF((head), &(head)->stqh_first)) \ 00184 (head)->stqh_first = SH_PTR_TO_OFF(head, elm); \ 00185 else \ 00186 *SH_TAILQ_LAST(head) = -(head)->stqh_last + \ 00187 SH_PTR_TO_OFF((elm), &(elm)->field.stqe_next) + \ 00188 SH_PTR_TO_OFF(head, elm); \ 00189 (head)->stqh_last = \ 00190 SH_PTR_TO_OFF(head, &((elm)->field.stqe_next)); \ 00191 } while (0) 00192 00193 #define SH_TAILQ_INSERT_AFTER(head, listelm, elm, field, type) do { \ 00194 if ((listelm)->field.stqe_next != -1) { \ 00195 (elm)->field.stqe_next = (listelm)->field.stqe_next - \ 00196 SH_PTR_TO_OFF(listelm, elm); \ 00197 SH_TAILQ_NEXTP(listelm, field, type)->field.stqe_prev = \ 00198 SH_TAILQ_NEXT_TO_PREV(elm, field); \ 00199 } else { \ 00200 (elm)->field.stqe_next = -1; \ 00201 (head)->stqh_last = \ 00202 SH_PTR_TO_OFF(head, &elm->field.stqe_next); \ 00203 } \ 00204 (listelm)->field.stqe_next = SH_PTR_TO_OFF(listelm, elm); \ 00205 (elm)->field.stqe_prev = SH_TAILQ_NEXT_TO_PREV(listelm, field); \ 00206 } while (0) 00207 00208 #define SH_TAILQ_REMOVE(head, elm, field, type) do { \ 00209 if ((elm)->field.stqe_next != -1) { \ 00210 SH_TAILQ_NEXTP(elm, field, type)->field.stqe_prev = \ 00211 (elm)->field.stqe_prev + \ 00212 SH_PTR_TO_OFF(SH_TAILQ_NEXTP(elm, \ 00213 field, type), elm); \ 00214 *SH_TAILQ_PREVP(elm, field) += elm->field.stqe_next; \ 00215 } else { \ 00216 (head)->stqh_last = (elm)->field.stqe_prev + \ 00217 SH_PTR_TO_OFF(head, elm); \ 00218 *SH_TAILQ_PREVP(elm, field) = -1; \ 00219 } \ 00220 } while (0) 00221 00222 /* 00223 * Shared circular queue definitions. 00224 */ 00225 #define SH_CIRCLEQ_HEAD(name) \ 00226 struct name { \ 00227 ssize_t scqh_first; /* first element */ \ 00228 ssize_t scqh_last; /* last element */ \ 00229 } 00230 00231 #define SH_CIRCLEQ_ENTRY \ 00232 struct { \ 00233 ssize_t scqe_next; /* next element */ \ 00234 ssize_t scqe_prev; /* previous element */ \ 00235 } 00236 00237 /* 00238 * Shared circular queue functions. 00239 */ 00240 #define SH_CIRCLEQ_FIRSTP(head, type) \ 00241 ((struct type *)(((u_int8_t *)(head)) + (head)->scqh_first)) 00242 00243 #define SH_CIRCLEQ_FIRST(head, type) \ 00244 ((head)->scqh_first == -1 ? \ 00245 (void *)head : SH_CIRCLEQ_FIRSTP(head, type)) 00246 00247 #define SH_CIRCLEQ_LASTP(head, type) \ 00248 ((struct type *)(((u_int8_t *)(head)) + (head)->scqh_last)) 00249 00250 #define SH_CIRCLEQ_LAST(head, type) \ 00251 ((head)->scqh_last == -1 ? (void *)head : SH_CIRCLEQ_LASTP(head, type)) 00252 00253 #define SH_CIRCLEQ_NEXTP(elm, field, type) \ 00254 ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.scqe_next)) 00255 00256 #define SH_CIRCLEQ_NEXT(head, elm, field, type) \ 00257 ((elm)->field.scqe_next == SH_PTR_TO_OFF(elm, head) ? \ 00258 (void *)head : SH_CIRCLEQ_NEXTP(elm, field, type)) 00259 00260 #define SH_CIRCLEQ_PREVP(elm, field, type) \ 00261 ((struct type *)(((u_int8_t *)(elm)) + (elm)->field.scqe_prev)) 00262 00263 #define SH_CIRCLEQ_PREV(head, elm, field, type) \ 00264 ((elm)->field.scqe_prev == SH_PTR_TO_OFF(elm, head) ? \ 00265 (void *)head : SH_CIRCLEQ_PREVP(elm, field, type)) 00266 00267 #define SH_CIRCLEQ_END(head) ((void *)(head)) 00268 00269 #define SH_CIRCLEQ_INIT(head) { \ 00270 (head)->scqh_first = 0; \ 00271 (head)->scqh_last = 0; \ 00272 } 00273 00274 #define SH_CIRCLEQ_INSERT_AFTER(head, listelm, elm, field, type) do { \ 00275 (elm)->field.scqe_prev = SH_PTR_TO_OFF(elm, listelm); \ 00276 (elm)->field.scqe_next = (listelm)->field.scqe_next + \ 00277 (elm)->field.scqe_prev; \ 00278 if (SH_CIRCLEQ_NEXTP(listelm, field, type) == (void *)head) \ 00279 (head)->scqh_last = SH_PTR_TO_OFF(head, elm); \ 00280 else \ 00281 SH_CIRCLEQ_NEXTP(listelm, \ 00282 field, type)->field.scqe_prev = \ 00283 SH_PTR_TO_OFF(SH_CIRCLEQ_NEXTP(listelm, \ 00284 field, type), elm); \ 00285 (listelm)->field.scqe_next = -(elm)->field.scqe_prev; \ 00286 } while (0) 00287 00288 #define SH_CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field, type) do { \ 00289 (elm)->field.scqe_next = SH_PTR_TO_OFF(elm, listelm); \ 00290 (elm)->field.scqe_prev = (elm)->field.scqe_next - \ 00291 SH_CIRCLEQ_PREVP(listelm, field, type)->field.scqe_next;\ 00292 if (SH_CIRCLEQ_PREVP(listelm, field, type) == (void *)(head)) \ 00293 (head)->scqh_first = SH_PTR_TO_OFF(head, elm); \ 00294 else \ 00295 SH_CIRCLEQ_PREVP(listelm, \ 00296 field, type)->field.scqe_next = \ 00297 SH_PTR_TO_OFF(SH_CIRCLEQ_PREVP(listelm, \ 00298 field, type), elm); \ 00299 (listelm)->field.scqe_prev = -(elm)->field.scqe_next; \ 00300 } while (0) 00301 00302 #define SH_CIRCLEQ_INSERT_HEAD(head, elm, field, type) do { \ 00303 (elm)->field.scqe_prev = SH_PTR_TO_OFF(elm, head); \ 00304 (elm)->field.scqe_next = (head)->scqh_first + \ 00305 (elm)->field.scqe_prev; \ 00306 if ((head)->scqh_last == 0) \ 00307 (head)->scqh_last = -(elm)->field.scqe_prev; \ 00308 else \ 00309 SH_CIRCLEQ_FIRSTP(head, type)->field.scqe_prev = \ 00310 SH_PTR_TO_OFF(SH_CIRCLEQ_FIRSTP(head, type), elm); \ 00311 (head)->scqh_first = -(elm)->field.scqe_prev; \ 00312 } while (0) 00313 00314 #define SH_CIRCLEQ_INSERT_TAIL(head, elm, field, type) do { \ 00315 (elm)->field.scqe_next = SH_PTR_TO_OFF(elm, head); \ 00316 (elm)->field.scqe_prev = (head)->scqh_last + \ 00317 (elm)->field.scqe_next; \ 00318 if ((head)->scqh_first == 0) \ 00319 (head)->scqh_first = -(elm)->field.scqe_next; \ 00320 else \ 00321 SH_CIRCLEQ_LASTP(head, type)->field.scqe_next = \ 00322 SH_PTR_TO_OFF(SH_CIRCLEQ_LASTP(head, type), elm); \ 00323 (head)->scqh_last = -(elm)->field.scqe_next; \ 00324 } while (0) 00325 00326 #define SH_CIRCLEQ_REMOVE(head, elm, field, type) do { \ 00327 if (SH_CIRCLEQ_NEXTP(elm, field, type) == (void *)(head)) \ 00328 (head)->scqh_last += (elm)->field.scqe_prev; \ 00329 else \ 00330 SH_CIRCLEQ_NEXTP(elm, field, type)->field.scqe_prev += \ 00331 (elm)->field.scqe_prev; \ 00332 if (SH_CIRCLEQ_PREVP(elm, field, type) == (void *)(head)) \ 00333 (head)->scqh_first += (elm)->field.scqe_next; \ 00334 else \ 00335 SH_CIRCLEQ_PREVP(elm, field, type)->field.scqe_next += \ 00336 (elm)->field.scqe_next; \ 00337 } while (0) 00338 00339 #if defined(__cplusplus) 00340 } 00341 #endif 00342 00343 #endif /* !_SYS_SHQUEUE_H_ */