nestegg/halloc/src/hlist.h

   1 /*
   2  *      Copyright (c) 2004-2010 Alex Pankratov. All rights reserved.
   3  *
   4  *      Hierarchical memory allocator, 1.2.1
   5  *      http://swapped.cc/halloc
   6  */
   7
   8 /*
   9  *      The program is distributed under terms of BSD license.
  10  *      You can obtain the copy of the license by visiting:
  11  *
  12  *      http://www.opensource.org/licenses/bsd-license.php
  13  */
  14
  15 #ifndef _LIBP_HLIST_H_
  16 #define _LIBP_HLIST_H_
  17
  18 #include <assert.h>
  19 #include "macros.h"  /* static_inline */
  20
  21 /*
  22  *      weak double-linked list w/ tail sentinel
  23  */
  24 typedef struct hlist_head  hlist_head_t;
  25 typedef struct hlist_item  hlist_item_t;
  26
  27 /*
  28  *
  29  */
  30 struct hlist_head
  31 {
  32         hlist_item_t * next;
  33 };
  34
  35 struct hlist_item
  36 {
  37         hlist_item_t * next;
  38         hlist_item_t ** prev;
  39 };
  40
  41 /*
  42  *      shared tail sentinel
  43  */
  44 struct hlist_item hlist_null;
  45
  46 /*
  47  *
  48  */
  49 #define __hlist_init(h)      { &hlist_null }
  50 #define __hlist_init_item(i) { &hlist_null, &(i).next }
  51
  52 static_inline void hlist_init(hlist_head_t * h);
  53 static_inline void hlist_init_item(hlist_item_t * i);
  54
  55 /* static_inline void hlist_purge(hlist_head_t * h); */
  56
  57 /* static_inline bool_t hlist_empty(const hlist_head_t * h); */
  58
  59 /* static_inline hlist_item_t * hlist_head(const hlist_head_t * h); */
  60
  61 /* static_inline hlist_item_t * hlist_next(const hlist_item_t * i); */
  62 /* static_inline hlist_item_t * hlist_prev(const hlist_item_t * i,
  63                                            const hlist_head_t * h); */
  64
  65 static_inline void hlist_add(hlist_head_t * h, hlist_item_t * i);
  66
  67 /* static_inline void hlist_add_prev(hlist_item_t * l, hlist_item_t * i); */
  68 /* static_inline void hlist_add_next(hlist_item_t * l, hlist_item_t * i); */
  69
  70 static_inline void hlist_del(hlist_item_t * i);
  71
  72 static_inline void hlist_relink(hlist_item_t * i);
  73 static_inline void hlist_relink_head(hlist_head_t * h);
  74
  75 #define hlist_for_each(i, h) \
  76         for (i = (h)->next; i != &hlist_null; i = i->next)
  77
  78 #define hlist_for_each_safe(i, tmp, h) \
  79         for (i = (h)->next, tmp = i->next; \
  80              i!= &hlist_null; \
  81              i = tmp, tmp = i->next)
  82
  83 /*
  84  *      static
  85  */
  86 static_inline void hlist_init(hlist_head_t * h)
  87 {
  88         assert(h);
  89         h->next = &hlist_null;
  90 }
  91
  92 static_inline void hlist_init_item(hlist_item_t * i)
  93 {
  94         assert(i);
  95         i->prev = &i->next;
  96         i->next = &hlist_null;
  97 }
  98
  99 static_inline void hlist_add(hlist_head_t * h, hlist_item_t * i)
 100 {
 101         hlist_item_t * next;
 102         assert(h && i);
 103
 104         next = i->next = h->next;
 105         next->prev = &i->next;
 106         h->next = i;
 107         i->prev = &h->next;
 108 }
 109
 110 static_inline void hlist_del(hlist_item_t * i)
 111 {
 112         hlist_item_t * next;
 113         assert(i);
 114
 115         next = i->next;
 116         next->prev = i->prev;
 117         *i->prev = next;
 118
 119         hlist_init_item(i);
 120 }
 121
 122 static_inline void hlist_relink(hlist_item_t * i)
 123 {
 124         assert(i);
 125         *i->prev = i;
 126         i->next->prev = &i->next;
 127 }
 128
 129 static_inline void hlist_relink_head(hlist_head_t * h)
 130 {
 131         assert(h);
 132         h->next->prev = &h->next;
 133 }
 134
 135 #endif
 136