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