1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/media/libnestegg/src/halloc.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,254 @@
1.4 +/*
1.5 + * Copyright (c) 2004i-2010 Alex Pankratov. All rights reserved.
1.6 + *
1.7 + * Hierarchical memory allocator, 1.2.1
1.8 + * http://swapped.cc/halloc
1.9 + */
1.10 +
1.11 +/*
1.12 + * The program is distributed under terms of BSD license.
1.13 + * You can obtain the copy of the license by visiting:
1.14 + *
1.15 + * http://www.opensource.org/licenses/bsd-license.php
1.16 + */
1.17 +
1.18 +#include <stdlib.h> /* realloc */
1.19 +#include <string.h> /* memset & co */
1.20 +
1.21 +#include "halloc.h"
1.22 +#include "align.h"
1.23 +#include "hlist.h"
1.24 +
1.25 +/*
1.26 + * block control header
1.27 + */
1.28 +typedef struct hblock
1.29 +{
1.30 +#ifndef NDEBUG
1.31 +#define HH_MAGIC 0x20040518L
1.32 + long magic;
1.33 +#endif
1.34 + hlist_item_t siblings; /* 2 pointers */
1.35 + hlist_head_t children; /* 1 pointer */
1.36 + max_align_t data[1]; /* not allocated, see below */
1.37 +
1.38 +} hblock_t;
1.39 +
1.40 +#define sizeof_hblock offsetof(hblock_t, data)
1.41 +
1.42 +/*
1.43 + *
1.44 + */
1.45 +realloc_t halloc_allocator = NULL;
1.46 +
1.47 +#define allocator halloc_allocator
1.48 +
1.49 +/*
1.50 + * static methods
1.51 + */
1.52 +static void _set_allocator(void);
1.53 +static void * _realloc(void * ptr, size_t n);
1.54 +
1.55 +static int _relate(hblock_t * b, hblock_t * p);
1.56 +static void _free_children(hblock_t * p);
1.57 +
1.58 +/*
1.59 + * Core API
1.60 + */
1.61 +void * halloc(void * ptr, size_t len)
1.62 +{
1.63 + hblock_t * p;
1.64 +
1.65 + /* set up default allocator */
1.66 + if (! allocator)
1.67 + {
1.68 + _set_allocator();
1.69 + assert(allocator);
1.70 + }
1.71 +
1.72 + /* calloc */
1.73 + if (! ptr)
1.74 + {
1.75 + if (! len)
1.76 + return NULL;
1.77 +
1.78 + p = allocator(0, len + sizeof_hblock);
1.79 + if (! p)
1.80 + return NULL;
1.81 +#ifndef NDEBUG
1.82 + p->magic = HH_MAGIC;
1.83 +#endif
1.84 + hlist_init(&p->children);
1.85 + hlist_init_item(&p->siblings);
1.86 +
1.87 + return p->data;
1.88 + }
1.89 +
1.90 + p = structof(ptr, hblock_t, data);
1.91 + assert(p->magic == HH_MAGIC);
1.92 +
1.93 + /* realloc */
1.94 + if (len)
1.95 + {
1.96 + p = allocator(p, len + sizeof_hblock);
1.97 + if (! p)
1.98 + return NULL;
1.99 +
1.100 + hlist_relink(&p->siblings);
1.101 + hlist_relink_head(&p->children);
1.102 +
1.103 + return p->data;
1.104 + }
1.105 +
1.106 + /* free */
1.107 + _free_children(p);
1.108 + hlist_del(&p->siblings);
1.109 + allocator(p, 0);
1.110 +
1.111 + return NULL;
1.112 +}
1.113 +
1.114 +void hattach(void * block, void * parent)
1.115 +{
1.116 + hblock_t * b, * p;
1.117 +
1.118 + if (! block)
1.119 + {
1.120 + assert(! parent);
1.121 + return;
1.122 + }
1.123 +
1.124 + /* detach */
1.125 + b = structof(block, hblock_t, data);
1.126 + assert(b->magic == HH_MAGIC);
1.127 +
1.128 + hlist_del(&b->siblings);
1.129 +
1.130 + if (! parent)
1.131 + return;
1.132 +
1.133 + /* attach */
1.134 + p = structof(parent, hblock_t, data);
1.135 + assert(p->magic == HH_MAGIC);
1.136 +
1.137 + /* sanity checks */
1.138 + assert(b != p); /* trivial */
1.139 + assert(! _relate(p, b)); /* heavy ! */
1.140 +
1.141 + hlist_add(&p->children, &b->siblings);
1.142 +}
1.143 +
1.144 +/*
1.145 + * malloc/free api
1.146 + */
1.147 +void * h_malloc(size_t len)
1.148 +{
1.149 + return halloc(0, len);
1.150 +}
1.151 +
1.152 +void * h_calloc(size_t n, size_t len)
1.153 +{
1.154 + void * ptr = halloc(0, len*=n);
1.155 + return ptr ? memset(ptr, 0, len) : NULL;
1.156 +}
1.157 +
1.158 +void * h_realloc(void * ptr, size_t len)
1.159 +{
1.160 + return halloc(ptr, len);
1.161 +}
1.162 +
1.163 +void h_free(void * ptr)
1.164 +{
1.165 + halloc(ptr, 0);
1.166 +}
1.167 +
1.168 +char * h_strdup(const char * str)
1.169 +{
1.170 + size_t len = strlen(str);
1.171 + char * ptr = halloc(0, len + 1);
1.172 + return ptr ? (ptr[len] = 0, memcpy(ptr, str, len)) : NULL;
1.173 +}
1.174 +
1.175 +/*
1.176 + * static stuff
1.177 + */
1.178 +static void _set_allocator(void)
1.179 +{
1.180 + void * p;
1.181 + assert(! allocator);
1.182 +
1.183 + /*
1.184 + * the purpose of the test below is to check the behaviour
1.185 + * of realloc(ptr, 0), which is defined in the standard
1.186 + * as an implementation-specific. if it returns zero,
1.187 + * then it's equivalent to free(). it can however return
1.188 + * non-zero, in which case it cannot be used for freeing
1.189 + * memory blocks and we'll need to supply our own version
1.190 + *
1.191 + * Thanks to Stan Tobias for pointing this tricky part out.
1.192 + */
1.193 + allocator = realloc;
1.194 + if (! (p = malloc(1)))
1.195 + /* hmm */
1.196 + return;
1.197 +
1.198 + if ((p = realloc(p, 0)))
1.199 + {
1.200 + /* realloc cannot be used as free() */
1.201 + allocator = _realloc;
1.202 + free(p);
1.203 + }
1.204 +}
1.205 +
1.206 +static void * _realloc(void * ptr, size_t n)
1.207 +{
1.208 + /*
1.209 + * free'ing realloc()
1.210 + */
1.211 + if (n)
1.212 + return realloc(ptr, n);
1.213 + free(ptr);
1.214 + return NULL;
1.215 +}
1.216 +
1.217 +static int _relate(hblock_t * b, hblock_t * p)
1.218 +{
1.219 + hlist_item_t * i;
1.220 +
1.221 + if (!b || !p)
1.222 + return 0;
1.223 +
1.224 + /*
1.225 + * since there is no 'parent' pointer, which would've allowed
1.226 + * O(log(n)) upward traversal, the check must use O(n) downward
1.227 + * iteration of the entire hierarchy; and this can be VERY SLOW
1.228 + */
1.229 + hlist_for_each(i, &p->children)
1.230 + {
1.231 + hblock_t * q = structof(i, hblock_t, siblings);
1.232 + if (q == b || _relate(b, q))
1.233 + return 1;
1.234 + }
1.235 + return 0;
1.236 +}
1.237 +
1.238 +static void _free_children(hblock_t * p)
1.239 +{
1.240 + hlist_item_t * i, * tmp;
1.241 +
1.242 +#ifndef NDEBUG
1.243 + /*
1.244 + * this catches loops in hierarchy with almost zero
1.245 + * overhead (compared to _relate() running time)
1.246 + */
1.247 + assert(p && p->magic == HH_MAGIC);
1.248 + p->magic = 0;
1.249 +#endif
1.250 + hlist_for_each_safe(i, tmp, &p->children)
1.251 + {
1.252 + hblock_t * q = structof(i, hblock_t, siblings);
1.253 + _free_children(q);
1.254 + allocator(q, 0);
1.255 + }
1.256 +}
1.257 +
