geekos/include/geekos/list2.h

   1 /* (c) 2008, Jack Lange <jarusl@cs.northwestern.edu> */
   2 /* (c) 2008, The V3VEE Project <http://www.v3vee.org> */
   3
   4 #ifndef _LIST2_H
   5 #define _LIST2_H
   6
   7 // JRL FIXME
   8 // #ifdef __V3VEE__
   9
  10 #include <geekos/string.h>
  11
  12 #undef offsetof
  13 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
  14
  15
  16 #define container_of(ptr, type, member) ({                      \
  17         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  18         (type *)( (char *)__mptr - offsetof(type,member) );})
  19
  20
  21 static inline void prefetch(const void *x) {;}
  22
  23 /*
  24  * These are non-NULL pointers that will result in page faults
  25  * under normal circumstances, used to verify that nobody uses
  26  * non-initialized list entries.
  27  */
  28 #define LIST_POISON1  ((void *) 0x00100100)
  29 #define LIST_POISON2  ((void *) 0x00200200)
  30
  31 /*
  32  * Simple doubly linked list implementation.
  33  *
  34  * Some of the internal functions ("__xxx") are useful when
  35  * manipulating whole lists rather than single entries, as
  36  * sometimes we already know the next/prev entries and we can
  37  * generate better code by using them directly rather than
  38  * using the generic single-entry routines.
  39  */
  40
  41 struct list_head {
  42         struct list_head *next, *prev;
  43 };
  44
  45 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  46
  47 #define LIST_HEAD(name) \
  48         struct list_head name = LIST_HEAD_INIT(name)
  49
  50 static inline void INIT_LIST_HEAD(struct list_head *list)
  51 {
  52         list->next = list;
  53         list->prev = list;
  54 }
  55
  56 /*
  57  * Insert a new entry between two known consecutive entries.
  58  *
  59  * This is only for internal list manipulation where we know
  60  * the prev/next entries already!
  61  */
  62 static inline void __list_add(struct list_head *new,
  63                               struct list_head *prev,
  64                               struct list_head *next)
  65 {
  66         next->prev = new;
  67         new->next = next;
  68         new->prev = prev;
  69         prev->next = new;
  70 }
  71
  72 /**
  73  * list_add - add a new entry
  74  * @new: new entry to be added
  75  * @head: list head to add it after
  76  *
  77  * Insert a new entry after the specified head.
  78  * This is good for implementing stacks.
  79  */
  80 static inline void list_add(struct list_head *new, struct list_head *head)
  81 {
  82         __list_add(new, head, head->next);
  83 }
  84
  85 /**
  86  * list_add_tail - add a new entry
  87  * @new: new entry to be added
  88  * @head: list head to add it before
  89  *
  90  * Insert a new entry before the specified head.
  91  * This is useful for implementing queues.
  92  */
  93 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  94 {
  95         __list_add(new, head->prev, head);
  96 }
  97
  98 /*
  99  * Delete a list entry by making the prev/next entries
 100  * point to each other.
 101  *
 102  * This is only for internal list manipulation where we know
 103  * the prev/next entries already!
 104  */
 105 static inline void __list_del(struct list_head * prev, struct list_head * next)
 106 {
 107         next->prev = prev;
 108         prev->next = next;
 109 }
 110
 111 /**
 112  * list_del - deletes entry from list.
 113  * @entry: the element to delete from the list.
 114  * Note: list_empty on entry does not return true after this, the entry is
 115  * in an undefined state.
 116  */
 117 static inline void list_del(struct list_head *entry)
 118 {
 119         __list_del(entry->prev, entry->next);
 120         entry->next = LIST_POISON1;
 121         entry->prev = LIST_POISON2;
 122 }
 123
 124 /**
 125  * list_del_init - deletes entry from list and reinitialize it.
 126  * @entry: the element to delete from the list.
 127  */
 128 static inline void list_del_init(struct list_head *entry)
 129 {
 130         __list_del(entry->prev, entry->next);
 131         INIT_LIST_HEAD(entry);
 132 }
 133
 134 /**
 135  * list_move - delete from one list and add as another's head
 136  * @list: the entry to move
 137  * @head: the head that will precede our entry
 138  */
 139 static inline void list_move(struct list_head *list, struct list_head *head)
 140 {
 141         __list_del(list->prev, list->next);
 142         list_add(list, head);
 143 }
 144
 145 /**
 146  * list_move_tail - delete from one list and add as another's tail
 147  * @list: the entry to move
 148  * @head: the head that will follow our entry
 149  */
 150 static inline void list_move_tail(struct list_head *list,
 151                                   struct list_head *head)
 152 {
 153         __list_del(list->prev, list->next);
 154         list_add_tail(list, head);
 155 }
 156
 157 /**
 158  * list_empty - tests whether a list is empty
 159  * @head: the list to test.
 160  */
 161 static inline int list_empty(const struct list_head *head)
 162 {
 163         return head->next == head;
 164 }
 165
 166 /**
 167  * list_empty_careful - tests whether a list is
 168  * empty _and_ checks that no other CPU might be
 169  * in the process of still modifying either member
 170  *
 171  * NOTE: using list_empty_careful() without synchronization
 172  * can only be safe if the only activity that can happen
 173  * to the list entry is list_del_init(). Eg. it cannot be used
 174  * if another CPU could re-list_add() it.
 175  *
 176  * @head: the list to test.
 177  */
 178 static inline int list_empty_careful(const struct list_head *head)
 179 {
 180         struct list_head *next = head->next;
 181         return (next == head) && (next == head->prev);
 182 }
 183
 184 static inline void __list_splice(struct list_head *list,
 185                                  struct list_head *head)
 186 {
 187         struct list_head *first = list->next;
 188         struct list_head *last = list->prev;
 189         struct list_head *at = head->next;
 190
 191         first->prev = head;
 192         head->next = first;
 193
 194         last->next = at;
 195         at->prev = last;
 196 }
 197
 198 /**
 199  * list_splice - join two lists
 200  * @list: the new list to add.
 201  * @head: the place to add it in the first list.
 202  */
 203 static inline void list_splice(struct list_head *list, struct list_head *head)
 204 {
 205         if (!list_empty(list))
 206                 __list_splice(list, head);
 207 }
 208
 209 /**
 210  * list_splice_init - join two lists and reinitialise the emptied list.
 211  * @list: the new list to add.
 212  * @head: the place to add it in the first list.
 213  *
 214  * The list at @list is reinitialised
 215  */
 216 static inline void list_splice_init(struct list_head *list,
 217                                     struct list_head *head)
 218 {
 219         if (!list_empty(list)) {
 220                 __list_splice(list, head);
 221                 INIT_LIST_HEAD(list);
 222         }
 223 }
 224
 225 /**
 226  * list_entry - get the struct for this entry
 227  * @ptr:        the &struct list_head pointer.
 228  * @type:       the type of the struct this is embedded in.
 229  * @member:     the name of the list_struct within the struct.
 230  */
 231 #define list_entry(ptr, type, member) \
 232         container_of(ptr, type, member)
 233
 234 /**
 235  * list_for_each        -       iterate over a list
 236  * @pos:        the &struct list_head to use as a loop counter.
 237  * @head:       the head for your list.
 238  */
 239 #define list_for_each(pos, head) \
 240         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
 241                 pos = pos->next)
 242
 243 /**
 244  * __list_for_each      -       iterate over a list
 245  * @pos:        the &struct list_head to use as a loop counter.
 246  * @head:       the head for your list.
 247  *
 248  * This variant differs from list_for_each() in that it's the
 249  * simplest possible list iteration code, no prefetching is done.
 250  * Use this for code that knows the list to be very short (empty
 251  * or 1 entry) most of the time.
 252  */
 253 #define __list_for_each(pos, head) \
 254         for (pos = (head)->next; pos != (head); pos = pos->next)
 255
 256 /**
 257  * list_for_each_prev   -       iterate over a list backwards
 258  * @pos:        the &struct list_head to use as a loop counter.
 259  * @head:       the head for your list.
 260  */
 261 #define list_for_each_prev(pos, head) \
 262         for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
 263                 pos = pos->prev)
 264
 265 /**
 266  * list_for_each_safe   -       iterate over a list safe against removal of list entry
 267  * @pos:        the &struct list_head to use as a loop counter.
 268  * @n:          another &struct list_head to use as temporary storage
 269  * @head:       the head for your list.
 270  */
 271 #define list_for_each_safe(pos, n, head) \
 272         for (pos = (head)->next, n = pos->next; pos != (head); \
 273                 pos = n, n = pos->next)
 274
 275 /**
 276  * list_for_each_entry  -       iterate over list of given type
 277  * @pos:        the type * to use as a loop counter.
 278  * @head:       the head for your list.
 279  * @member:     the name of the list_struct within the struct.
 280  */
 281 #define list_for_each_entry(pos, head, member)                          \
 282         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 283              prefetch(pos->member.next), &pos->member != (head);        \
 284              pos = list_entry(pos->member.next, typeof(*pos), member))
 285
 286 /**
 287  * list_for_each_entry_reverse - iterate backwards over list of given type.
 288  * @pos:        the type * to use as a loop counter.
 289  * @head:       the head for your list.
 290  * @member:     the name of the list_struct within the struct.
 291  */
 292 #define list_for_each_entry_reverse(pos, head, member)                  \
 293         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
 294              prefetch(pos->member.prev), &pos->member != (head);        \
 295              pos = list_entry(pos->member.prev, typeof(*pos), member))
 296
 297 /**
 298  * list_prepare_entry - prepare a pos entry for use as a start point in
 299  *                      list_for_each_entry_continue
 300  * @pos:        the type * to use as a start point
 301  * @head:       the head of the list
 302  * @member:     the name of the list_struct within the struct.
 303  */
 304 #define list_prepare_entry(pos, head, member) \
 305         ((pos) ? : list_entry(head, typeof(*pos), member))
 306
 307 /**
 308  * list_for_each_entry_continue -       iterate over list of given type
 309  *                      continuing after existing point
 310  * @pos:        the type * to use as a loop counter.
 311  * @head:       the head for your list.
 312  * @member:     the name of the list_struct within the struct.
 313  */
 314 #define list_for_each_entry_continue(pos, head, member)                 \
 315         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
 316              prefetch(pos->member.next), &pos->member != (head);        \
 317              pos = list_entry(pos->member.next, typeof(*pos), member))
 318
 319 /**
 320  * list_for_each_entry_from -   iterate over list of given type
 321  *                      continuing from existing point
 322  * @pos:        the type * to use as a loop counter.
 323  * @head:       the head for your list.
 324  * @member:     the name of the list_struct within the struct.
 325  */
 326 #define list_for_each_entry_from(pos, head, member)                     \
 327         for (; prefetch(pos->member.next), &pos->member != (head);      \
 328              pos = list_entry(pos->member.next, typeof(*pos), member))
 329
 330 /**
 331  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 332  * @pos:        the type * to use as a loop counter.
 333  * @n:          another type * to use as temporary storage
 334  * @head:       the head for your list.
 335  * @member:     the name of the list_struct within the struct.
 336  */
 337 #define list_for_each_entry_safe(pos, n, head, member)                  \
 338         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 339                 n = list_entry(pos->member.next, typeof(*pos), member); \
 340              &pos->member != (head);                                    \
 341              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 342
 343 /**
 344  * list_for_each_entry_safe_continue -  iterate over list of given type
 345  *                      continuing after existing point safe against removal of list entry
 346  * @pos:        the type * to use as a loop counter.
 347  * @n:          another type * to use as temporary storage
 348  * @head:       the head for your list.
 349  * @member:     the name of the list_struct within the struct.
 350  */
 351 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
 352         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
 353                 n = list_entry(pos->member.next, typeof(*pos), member);         \
 354              &pos->member != (head);                                            \
 355              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 356
 357 /**
 358  * list_for_each_entry_safe_from - iterate over list of given type
 359  *                      from existing point safe against removal of list entry
 360  * @pos:        the type * to use as a loop counter.
 361  * @n:          another type * to use as temporary storage
 362  * @head:       the head for your list.
 363  * @member:     the name of the list_struct within the struct.
 364  */
 365 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
 366         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
 367              &pos->member != (head);                                            \
 368              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 369
 370 /**
 371  * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
 372  *                                    removal of list entry
 373  * @pos:        the type * to use as a loop counter.
 374  * @n:          another type * to use as temporary storage
 375  * @head:       the head for your list.
 376  * @member:     the name of the list_struct within the struct.
 377  */
 378 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 379         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 380                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 381              &pos->member != (head);                                    \
 382              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 383
 384 /*
 385  * Double linked lists with a single pointer list head.
 386  * Mostly useful for hash tables where the two pointer list head is
 387  * too wasteful.
 388  * You lose the ability to access the tail in O(1).
 389  */
 390
 391 struct hlist_head {
 392         struct hlist_node *first;
 393 };
 394
 395 struct hlist_node {
 396         struct hlist_node *next, **pprev;
 397 };
 398
 399 #define HLIST_HEAD_INIT { .first = NULL }
 400 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
 401 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
 402 static inline void INIT_HLIST_NODE(struct hlist_node *h)
 403 {
 404         h->next = NULL;
 405         h->pprev = NULL;
 406 }
 407
 408 static inline int hlist_unhashed(const struct hlist_node *h)
 409 {
 410         return !h->pprev;
 411 }
 412
 413 static inline int hlist_empty(const struct hlist_head *h)
 414 {
 415         return !h->first;
 416 }
 417
 418 static inline void __hlist_del(struct hlist_node *n)
 419 {
 420         struct hlist_node *next = n->next;
 421         struct hlist_node **pprev = n->pprev;
 422         *pprev = next;
 423         if (next)
 424                 next->pprev = pprev;
 425 }
 426
 427 static inline void hlist_del(struct hlist_node *n)
 428 {
 429         __hlist_del(n);
 430         n->next = LIST_POISON1;
 431         n->pprev = LIST_POISON2;
 432 }
 433
 434 static inline void hlist_del_init(struct hlist_node *n)
 435 {
 436         if (!hlist_unhashed(n)) {
 437                 __hlist_del(n);
 438                 INIT_HLIST_NODE(n);
 439         }
 440 }
 441
 442 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 443 {
 444         struct hlist_node *first = h->first;
 445         n->next = first;
 446         if (first)
 447                 first->pprev = &n->next;
 448         h->first = n;
 449         n->pprev = &h->first;
 450 }
 451
 452 /* next must be != NULL */
 453 static inline void hlist_add_before(struct hlist_node *n,
 454                                         struct hlist_node *next)
 455 {
 456         n->pprev = next->pprev;
 457         n->next = next;
 458         next->pprev = &n->next;
 459         *(n->pprev) = n;
 460 }
 461
 462 static inline void hlist_add_after(struct hlist_node *n,
 463                                         struct hlist_node *next)
 464 {
 465         next->next = n->next;
 466         n->next = next;
 467         next->pprev = &n->next;
 468
 469         if(next->next)
 470                 next->next->pprev  = &next->next;
 471 }
 472
 473 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
 474
 475 #define hlist_for_each(pos, head) \
 476         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
 477              pos = pos->next)
 478
 479 #define hlist_for_each_safe(pos, n, head) \
 480         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
 481              pos = n)
 482
 483 /**
 484  * hlist_for_each_entry - iterate over list of given type
 485  * @tpos:       the type * to use as a loop counter.
 486  * @pos:        the &struct hlist_node to use as a loop counter.
 487  * @head:       the head for your list.
 488  * @member:     the name of the hlist_node within the struct.
 489  */
 490 #define hlist_for_each_entry(tpos, pos, head, member)                    \
 491         for (pos = (head)->first;                                        \
 492              pos && ({ prefetch(pos->next); 1;}) &&                      \
 493                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 494              pos = pos->next)
 495
 496 /**
 497  * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
 498  * @tpos:       the type * to use as a loop counter.
 499  * @pos:        the &struct hlist_node to use as a loop counter.
 500  * @member:     the name of the hlist_node within the struct.
 501  */
 502 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
 503         for (pos = (pos)->next;                                          \
 504              pos && ({ prefetch(pos->next); 1;}) &&                      \
 505                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 506              pos = pos->next)
 507
 508 /**
 509  * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
 510  * @tpos:       the type * to use as a loop counter.
 511  * @pos:        the &struct hlist_node to use as a loop counter.
 512  * @member:     the name of the hlist_node within the struct.
 513  */
 514 #define hlist_for_each_entry_from(tpos, pos, member)                     \
 515         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
 516                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 517              pos = pos->next)
 518
 519 /**
 520  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 521  * @tpos:       the type * to use as a loop counter.
 522  * @pos:        the &struct hlist_node to use as a loop counter.
 523  * @n:          another &struct hlist_node to use as temporary storage
 524  * @head:       the head for your list.
 525  * @member:     the name of the hlist_node within the struct.
 526  */
 527 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
 528         for (pos = (head)->first;                                        \
 529              pos && ({ n = pos->next; 1; }) &&                           \
 530                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 531              pos = n)
 532
 533
 534 // JRL FIXME
 535 //#endif // ! __V3VEE__
 536
 537 #endif