1 /*
   2  * Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  *
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS
  17  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
  20  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28 
  29 /*
  30   tre-mem.c - TRE memory allocator
  31 */
  32 
  33 /*
  34   This memory allocator is for allocating small memory blocks efficiently
  35   in terms of memory overhead and execution speed.  The allocated blocks
  36   cannot be freed individually, only all at once.  There can be multiple
  37   allocators, though.
  38 */
  39 
  40 #include <stdlib.h>
  41 #include <string.h>
  42 
  43 #include "tre-internal.h"
  44 #include "tre-mem.h"
  45 
  46 /* Returns a new memory allocator or NULL if out of memory. */
  47 tre_mem_t
  48 tre_mem_new_impl(int provided, void *provided_block)
  49 {
  50   tre_mem_t mem;
  51   if (provided)
  52     {
  53       mem = provided_block;
  54       memset(mem, 0, sizeof(*mem));
  55     }
  56   else
  57     mem = calloc(1, sizeof(*mem));
  58   if (mem == NULL)
  59     return NULL;
  60   return mem;
  61 }
  62 
  63 /* Frees the memory allocator and all memory allocated with it. */
  64 void
  65 tre_mem_destroy(tre_mem_t mem)
  66 {
  67   tre_list_t *tmp, *l = mem->blocks;
  68 
  69   while (l != NULL)
  70     {
  71       free(l->data);
  72       tmp = l->next;
  73       free(l);
  74       l = tmp;
  75     }
  76   free(mem);
  77 }
  78 
  79 /* Allocates a block of `size' bytes from `mem'.  Returns a pointer to the
  80    allocated block or NULL if an underlying malloc() failed. */
  81 void *
  82 tre_mem_alloc_impl(tre_mem_t mem, int provided, void *provided_block,
  83                    int zero, size_t size)
  84 {
  85   void *ptr;
  86 
  87   if (mem->failed)
  88     {
  89       DPRINT(("tre_mem_alloc: oops, called after failure?!\n"));
  90       return NULL;
  91     }
  92 
  93   if (mem->n < size)
  94     {
  95       /* We need more memory than is available in the current block.
  96          Allocate a new block. */
  97       tre_list_t *l;
  98       if (provided)
  99         {
 100           DPRINT(("tre_mem_alloc: using provided block\n"));
 101           if (provided_block == NULL)
 102             {
 103               DPRINT(("tre_mem_alloc: provided block was NULL\n"));
 104               mem->failed = 1;
 105               return NULL;
 106             }
 107           mem->ptr = provided_block;
 108           mem->n = TRE_MEM_BLOCK_SIZE;
 109         }
 110       else
 111         {
 112           int block_size;
 113           if (size * 8 > TRE_MEM_BLOCK_SIZE)
 114             block_size = size * 8;
 115           else
 116             block_size = TRE_MEM_BLOCK_SIZE;
 117           DPRINT(("tre_mem_alloc: allocating new %d byte block\n",
 118                   block_size));
 119           l = malloc(sizeof(*l));
 120           if (l == NULL)
 121             {
 122               mem->failed = 1;
 123               return NULL;
 124             }
 125           l->data = malloc(block_size);
 126           if (l->data == NULL)
 127             {
 128               free(l);
 129               mem->failed = 1;
 130               return NULL;
 131             }
 132           l->next = NULL;
 133           if (mem->current != NULL)
 134             mem->current->next = l;
 135           if (mem->blocks == NULL)
 136             mem->blocks = l;
 137           mem->current = l;
 138           mem->ptr = l->data;
 139           mem->n = block_size;
 140         }
 141     }
 142 
 143   /* Make sure the next pointer will be aligned. */
 144   size += ALIGN(mem->ptr + size, long);
 145 
 146   /* Allocate from current block. */
 147   ptr = mem->ptr;
 148   mem->ptr += size;
 149   mem->n -= size;
 150 
 151   /* Set to zero if needed. */
 152   if (zero)
 153     memset(ptr, 0, size);
 154 
 155   return ptr;
 156 }