1 /*
2 * Copyright (c) 2004i-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 #include <stdlib.h> /* realloc */
16 #include <string.h> /* memset & co */
17
18 #include "../halloc.h"
19 #include "align.h"
20 #include "hlist.h"
21
22 /*
23 * block control header
24 */
25 typedef struct hblock
26 {
27 #ifndef NDEBUG
28 #define HH_MAGIC 0x20040518L
29 long magic;
30 #endif
31 hlist_item_t siblings; /* 2 pointers */
32 hlist_head_t children; /* 1 pointer */
33 max_align_t data[1]; /* not allocated, see below */
34
35 } hblock_t;
36
37 #define sizeof_hblock offsetof(hblock_t, data)
38
39 /*
40 *
41 */
42 realloc_t halloc_allocator = NULL;
43
44 #define allocator halloc_allocator
45
46 /*
47 * static methods
48 */
49 static void _set_allocator(void);
50 static void * _realloc(void * ptr, size_t n);
51
52 static int _relate(hblock_t * b, hblock_t * p);
53 static void _free_children(hblock_t * p);
54
55 /*
56 * Core API
57 */
halloc(void * ptr,size_t len)58 void * halloc(void * ptr, size_t len)
59 {
60 hblock_t * p;
61
62 /* set up default allocator */
63 if (! allocator)
64 {
65 _set_allocator();
66 assert(allocator);
67 }
68
69 /* calloc */
70 if (! ptr)
71 {
72 if (! len)
73 return NULL;
74
75 p = allocator(0, len + sizeof_hblock);
76 if (! p)
77 return NULL;
78 #ifndef NDEBUG
79 p->magic = HH_MAGIC;
80 #endif
81 hlist_init(&p->children);
82 hlist_init_item(&p->siblings);
83
84 return p->data;
85 }
86
87 p = structof(ptr, hblock_t, data);
88 assert(p->magic == HH_MAGIC);
89
90 /* realloc */
91 if (len)
92 {
93 p = allocator(p, len + sizeof_hblock);
94 if (! p)
95 return NULL;
96
97 hlist_relink(&p->siblings);
98 hlist_relink_head(&p->children);
99
100 return p->data;
101 }
102
103 /* free */
104 _free_children(p);
105 hlist_del(&p->siblings);
106 allocator(p, 0);
107
108 return NULL;
109 }
110
hattach(void * block,void * parent)111 void hattach(void * block, void * parent)
112 {
113 hblock_t * b, * p;
114
115 if (! block)
116 {
117 assert(! parent);
118 return;
119 }
120
121 /* detach */
122 b = structof(block, hblock_t, data);
123 assert(b->magic == HH_MAGIC);
124
125 hlist_del(&b->siblings);
126
127 if (! parent)
128 return;
129
130 /* attach */
131 p = structof(parent, hblock_t, data);
132 assert(p->magic == HH_MAGIC);
133
134 /* sanity checks */
135 assert(b != p); /* trivial */
136 assert(! _relate(p, b)); /* heavy ! */
137
138 hlist_add(&p->children, &b->siblings);
139 }
140
141 /*
142 * malloc/free api
143 */
h_malloc(size_t len)144 void * h_malloc(size_t len)
145 {
146 return halloc(0, len);
147 }
148
h_calloc(size_t n,size_t len)149 void * h_calloc(size_t n, size_t len)
150 {
151 void * ptr = halloc(0, len*=n);
152 return ptr ? memset(ptr, 0, len) : NULL;
153 }
154
h_realloc(void * ptr,size_t len)155 void * h_realloc(void * ptr, size_t len)
156 {
157 return halloc(ptr, len);
158 }
159
h_free(void * ptr)160 void h_free(void * ptr)
161 {
162 halloc(ptr, 0);
163 }
164
h_strdup(const char * str)165 char * h_strdup(const char * str)
166 {
167 size_t len = strlen(str);
168 char * ptr = halloc(0, len + 1);
169 return ptr ? (ptr[len] = 0, memcpy(ptr, str, len)) : NULL;
170 }
171
172 /*
173 * static stuff
174 */
_set_allocator(void)175 static void _set_allocator(void)
176 {
177 void * p;
178 assert(! allocator);
179
180 /*
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
187 *
188 * Thanks to Stan Tobias for pointing this tricky part out.
189 */
190 allocator = realloc;
191 if (! (p = malloc(1)))
192 /* hmm */
193 return;
194
195 if ((p = realloc(p, 0)))
196 {
197 /* realloc cannot be used as free() */
198 allocator = _realloc;
199 free(p);
200 }
201 }
202
_realloc(void * ptr,size_t n)203 static void * _realloc(void * ptr, size_t n)
204 {
205 /*
206 * free'ing realloc()
207 */
208 if (n)
209 return realloc(ptr, n);
210 free(ptr);
211 return NULL;
212 }
213
_relate(hblock_t * b,hblock_t * p)214 static int _relate(hblock_t * b, hblock_t * p)
215 {
216 hlist_item_t * i;
217
218 if (!b || !p)
219 return 0;
220
221 /*
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
225 */
226 hlist_for_each(i, &p->children)
227 {
228 hblock_t * q = structof(i, hblock_t, siblings);
229 if (q == b || _relate(b, q))
230 return 1;
231 }
232 return 0;
233 }
234
_free_children(hblock_t * p)235 static void _free_children(hblock_t * p)
236 {
237 hlist_item_t * i, * tmp;
238
239 #ifndef NDEBUG
240 /*
241 * this catches loops in hierarchy with almost zero
242 * overhead (compared to _relate() running time)
243 */
244 assert(p && p->magic == HH_MAGIC);
245 p->magic = 0;
246 #endif
247 hlist_for_each_safe(i, tmp, &p->children)
248 {
249 hblock_t * q = structof(i, hblock_t, siblings);
250 _free_children(q);
251 allocator(q, 0);
252 }
253 }
254
255