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 */
hlist_init(hlist_head_t * h)86 static_inline void hlist_init(hlist_head_t * h)
87 {
88 assert(h);
89 h->next = &hlist_null;
90 }
91
hlist_init_item(hlist_item_t * i)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
hlist_add(hlist_head_t * h,hlist_item_t * i)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
hlist_del(hlist_item_t * i)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
hlist_relink(hlist_item_t * i)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
hlist_relink_head(hlist_head_t * h)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
137