nestegg/halloc/src/halloc.c

   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  */
  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