• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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