Home | History | Annotate | Download | only in src
      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