Home | History | Annotate | Download | only in src 
      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 
    137