OLD | NEW |
| (Empty) |
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 "third_party/nestegg/halloc/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 */ | |
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 | |
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 */ | |
144 void * h_malloc(size_t len) | |
145 { | |
146 return halloc(0, len); | |
147 } | |
148 | |
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 | |
155 void * h_realloc(void * ptr, size_t len) | |
156 { | |
157 return halloc(ptr, len); | |
158 } | |
159 | |
160 void h_free(void * ptr) | |
161 { | |
162 halloc(ptr, 0); | |
163 } | |
164 | |
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 */ | |
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 | |
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 | |
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 | |
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 | |
OLD | NEW |