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