diff options
author | James Zern <jzern@google.com> | 2014-02-20 20:26:53 -0800 |
---|---|---|
committer | James Zern <jzern@google.com> | 2014-02-21 17:16:04 -0800 |
commit | bb3b9aa93f5f699c986d8ac5e6d6f3ceffab41c9 (patch) | |
tree | f88c422d31b2d1f70787e49fa6680a6c5a270b27 /third_party/nestegg/halloc/src/halloc.c | |
parent | a0f0655b5e5739f1acbefb4e4b4fe1f778ecea45 (diff) | |
download | libvpx-bb3b9aa93f5f699c986d8ac5e6d6f3ceffab41c9.tar libvpx-bb3b9aa93f5f699c986d8ac5e6d6f3ceffab41c9.tar.gz libvpx-bb3b9aa93f5f699c986d8ac5e6d6f3ceffab41c9.tar.bz2 libvpx-bb3b9aa93f5f699c986d8ac5e6d6f3ceffab41c9.zip |
move nestegg to third_party
Change-Id: Idf58109195a88dec66c5e1ea6a51c61e6c659ff1
Diffstat (limited to 'third_party/nestegg/halloc/src/halloc.c')
-rw-r--r-- | third_party/nestegg/halloc/src/halloc.c | 254 |
1 files changed, 254 insertions, 0 deletions
diff --git a/third_party/nestegg/halloc/src/halloc.c b/third_party/nestegg/halloc/src/halloc.c new file mode 100644 index 000000000..8860d736a --- /dev/null +++ b/third_party/nestegg/halloc/src/halloc.c @@ -0,0 +1,254 @@ +/* + * Copyright (c) 2004i-2010 Alex Pankratov. All rights reserved. + * + * Hierarchical memory allocator, 1.2.1 + * http://swapped.cc/halloc + */ + +/* + * The program is distributed under terms of BSD license. + * You can obtain the copy of the license by visiting: + * + * http://www.opensource.org/licenses/bsd-license.php + */ + +#include <stdlib.h> /* realloc */ +#include <string.h> /* memset & co */ + +#include "third_party/nestegg/halloc/halloc.h" +#include "align.h" +#include "hlist.h" + +/* + * block control header + */ +typedef struct hblock +{ +#ifndef NDEBUG +#define HH_MAGIC 0x20040518L + long magic; +#endif + hlist_item_t siblings; /* 2 pointers */ + hlist_head_t children; /* 1 pointer */ + max_align_t data[1]; /* not allocated, see below */ + +} hblock_t; + +#define sizeof_hblock offsetof(hblock_t, data) + +/* + * + */ +realloc_t halloc_allocator = NULL; + +#define allocator halloc_allocator + +/* + * static methods + */ +static void _set_allocator(void); +static void * _realloc(void * ptr, size_t n); + +static int _relate(hblock_t * b, hblock_t * p); +static void _free_children(hblock_t * p); + +/* + * Core API + */ +void * halloc(void * ptr, size_t len) +{ + hblock_t * p; + + /* set up default allocator */ + if (! allocator) + { + _set_allocator(); + assert(allocator); + } + + /* calloc */ + if (! ptr) + { + if (! len) + return NULL; + + p = allocator(0, len + sizeof_hblock); + if (! p) + return NULL; +#ifndef NDEBUG + p->magic = HH_MAGIC; +#endif + hlist_init(&p->children); + hlist_init_item(&p->siblings); + + return p->data; + } + + p = structof(ptr, hblock_t, data); + assert(p->magic == HH_MAGIC); + + /* realloc */ + if (len) + { + p = allocator(p, len + sizeof_hblock); + if (! p) + return NULL; + + hlist_relink(&p->siblings); + hlist_relink_head(&p->children); + + return p->data; + } + + /* free */ + _free_children(p); + hlist_del(&p->siblings); + allocator(p, 0); + + return NULL; +} + +void hattach(void * block, void * parent) +{ + hblock_t * b, * p; + + if (! block) + { + assert(! parent); + return; + } + + /* detach */ + b = structof(block, hblock_t, data); + assert(b->magic == HH_MAGIC); + + hlist_del(&b->siblings); + + if (! parent) + return; + + /* attach */ + p = structof(parent, hblock_t, data); + assert(p->magic == HH_MAGIC); + + /* sanity checks */ + assert(b != p); /* trivial */ + assert(! _relate(p, b)); /* heavy ! */ + + hlist_add(&p->children, &b->siblings); +} + +/* + * malloc/free api + */ +void * h_malloc(size_t len) +{ + return halloc(0, len); +} + +void * h_calloc(size_t n, size_t len) +{ + void * ptr = halloc(0, len*=n); + return ptr ? memset(ptr, 0, len) : NULL; +} + +void * h_realloc(void * ptr, size_t len) +{ + return halloc(ptr, len); +} + +void h_free(void * ptr) +{ + halloc(ptr, 0); +} + +char * h_strdup(const char * str) +{ + size_t len = strlen(str); + char * ptr = halloc(0, len + 1); + return ptr ? (ptr[len] = 0, memcpy(ptr, str, len)) : NULL; +} + +/* + * static stuff + */ +static void _set_allocator(void) +{ + void * p; + assert(! allocator); + + /* + * the purpose of the test below is to check the behaviour + * of realloc(ptr, 0), which is defined in the standard + * as an implementation-specific. if it returns zero, + * then it's equivalent to free(). it can however return + * non-zero, in which case it cannot be used for freeing + * memory blocks and we'll need to supply our own version + * + * Thanks to Stan Tobias for pointing this tricky part out. + */ + allocator = realloc; + if (! (p = malloc(1))) + /* hmm */ + return; + + if ((p = realloc(p, 0))) + { + /* realloc cannot be used as free() */ + allocator = _realloc; + free(p); + } +} + +static void * _realloc(void * ptr, size_t n) +{ + /* + * free'ing realloc() + */ + if (n) + return realloc(ptr, n); + free(ptr); + return NULL; +} + +static int _relate(hblock_t * b, hblock_t * p) +{ + hlist_item_t * i; + + if (!b || !p) + return 0; + + /* + * since there is no 'parent' pointer, which would've allowed + * O(log(n)) upward traversal, the check must use O(n) downward + * iteration of the entire hierarchy; and this can be VERY SLOW + */ + hlist_for_each(i, &p->children) + { + hblock_t * q = structof(i, hblock_t, siblings); + if (q == b || _relate(b, q)) + return 1; + } + return 0; +} + +static void _free_children(hblock_t * p) +{ + hlist_item_t * i, * tmp; + +#ifndef NDEBUG + /* + * this catches loops in hierarchy with almost zero + * overhead (compared to _relate() running time) + */ + assert(p && p->magic == HH_MAGIC); + p->magic = 0; +#endif + hlist_for_each_safe(i, tmp, &p->children) + { + hblock_t * q = structof(i, hblock_t, siblings); + _free_children(q); + allocator(q, 0); + } +} + |