2 * Copyright (c) 2004i-2010 Alex Pankratov. All rights reserved.
4 * Hierarchical memory allocator, 1.2.1
5 * http://swapped.cc/halloc
9 * The program is distributed under terms of BSD license.
10 * You can obtain the copy of the license by visiting:
12 * http://www.opensource.org/licenses/bsd-license.php
15 #include <stdlib.h> /* realloc */
16 #include <string.h> /* memset & co */
18 #include "third_party/nestegg/halloc/halloc.h"
23 * block control header
28 #define HH_MAGIC 0x20040518L
31 hlist_item_t siblings; /* 2 pointers */
32 hlist_head_t children; /* 1 pointer */
33 max_align_t data[1]; /* not allocated, see below */
37 #define sizeof_hblock offsetof(hblock_t, data)
42 realloc_t halloc_allocator = NULL;
44 #define allocator halloc_allocator
49 static void _set_allocator(void);
50 static void * _realloc(void * ptr, size_t n);
52 static int _relate(hblock_t * b, hblock_t * p);
53 static void _free_children(hblock_t * p);
58 void * halloc(void * ptr, size_t len)
62 /* set up default allocator */
75 p = allocator(0, len + sizeof_hblock);
81 hlist_init(&p->children);
82 hlist_init_item(&p->siblings);
87 p = structof(ptr, hblock_t, data);
88 assert(p->magic == HH_MAGIC);
93 p = allocator(p, len + sizeof_hblock);
97 hlist_relink(&p->siblings);
98 hlist_relink_head(&p->children);
105 hlist_del(&p->siblings);
111 void hattach(void * block, void * parent)
122 b = structof(block, hblock_t, data);
123 assert(b->magic == HH_MAGIC);
125 hlist_del(&b->siblings);
131 p = structof(parent, hblock_t, data);
132 assert(p->magic == HH_MAGIC);
135 assert(b != p); /* trivial */
136 assert(! _relate(p, b)); /* heavy ! */
138 hlist_add(&p->children, &b->siblings);
144 void * h_malloc(size_t len)
146 return halloc(0, len);
149 void * h_calloc(size_t n, size_t len)
151 void * ptr = halloc(0, len*=n);
152 return ptr ? memset(ptr, 0, len) : NULL;
155 void * h_realloc(void * ptr, size_t len)
157 return halloc(ptr, len);
160 void h_free(void * ptr)
165 char * h_strdup(const char * str)
167 size_t len = strlen(str);
168 char * ptr = halloc(0, len + 1);
169 return ptr ? (ptr[len] = 0, memcpy(ptr, str, len)) : NULL;
175 static void _set_allocator(void)
181 * the purpose of the test below is to check the behaviour
182 * of realloc(ptr, 0), which is defined in the standard
183 * as an implementation-specific. if it returns zero,
184 * then it's equivalent to free(). it can however return
185 * non-zero, in which case it cannot be used for freeing
186 * memory blocks and we'll need to supply our own version
188 * Thanks to Stan Tobias for pointing this tricky part out.
191 if (! (p = malloc(1)))
195 if ((p = realloc(p, 0)))
197 /* realloc cannot be used as free() */
198 allocator = _realloc;
203 static void * _realloc(void * ptr, size_t n)
209 return realloc(ptr, n);
214 static int _relate(hblock_t * b, hblock_t * p)
222 * since there is no 'parent' pointer, which would've allowed
223 * O(log(n)) upward traversal, the check must use O(n) downward
224 * iteration of the entire hierarchy; and this can be VERY SLOW
226 hlist_for_each(i, &p->children)
228 hblock_t * q = structof(i, hblock_t, siblings);
229 if (q == b || _relate(b, q))
235 static void _free_children(hblock_t * p)
237 hlist_item_t * i, * tmp;
241 * this catches loops in hierarchy with almost zero
242 * overhead (compared to _relate() running time)
244 assert(p && p->magic == HH_MAGIC);
247 hlist_for_each_safe(i, tmp, &p->children)
249 hblock_t * q = structof(i, hblock_t, siblings);