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 255
