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 */ 25typedef 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 */ 42realloc_t halloc_allocator = NULL; 43 44#define allocator halloc_allocator 45 46/* 47 * static methods 48 */ 49static void _set_allocator(void); 50static void * _realloc(void * ptr, size_t n); 51 52static int _relate(hblock_t * b, hblock_t * p); 53static void _free_children(hblock_t * p); 54 55/* 56 * Core API 57 */ 58void * 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 111void 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 */ 144void * h_malloc(size_t len) 145{ 146 return halloc(0, len); 147} 148 149void * 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 155void * h_realloc(void * ptr, size_t len) 156{ 157 return halloc(ptr, len); 158} 159 160void h_free(void * ptr) 161{ 162 halloc(ptr, 0); 163} 164 165char * 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 */ 175static 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 203static 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 214static 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 235static 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