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 */
24typedef struct hlist_head  hlist_head_t;
25typedef struct hlist_item  hlist_item_t;
26
27/*
28 *
29 */
30struct hlist_head
31{
32	hlist_item_t * next;
33};
34
35struct hlist_item
36{
37	hlist_item_t * next;
38	hlist_item_t ** prev;
39};
40
41/*
42 *	shared tail sentinel
43 */
44struct 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
52static_inline void hlist_init(hlist_head_t * h);
53static_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
65static_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
70static_inline void hlist_del(hlist_item_t * i);
71
72static_inline void hlist_relink(hlist_item_t * i);
73static_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 */
86static_inline void hlist_init(hlist_head_t * h)
87{
88	assert(h);
89	h->next = &hlist_null;
90}
91
92static_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
99static_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
110static_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
122static_inline void hlist_relink(hlist_item_t * i)
123{
124	assert(i);
125	*i->prev = i;
126	i->next->prev = &i->next;
127}
128
129static_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