SphinxBase 5prealpha
listelem_alloc.c
1/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
2/* ====================================================================
3 * Copyright (c) 1999-2004 Carnegie Mellon University. All rights
4 * reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * This work was supported in part by funding from the Defense Advanced
19 * Research Projects Agency and the National Science Foundation of the
20 * United States of America, and the CMU Sphinx Speech Consortium.
21 *
22 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
23 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
24 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
25 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
26 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 *
34 * ====================================================================
35 *
36 */
37
38#include <stdio.h>
39#include <stdlib.h>
40
41#include "sphinxbase/err.h"
44#include "sphinxbase/glist.h"
45
66 char **freelist;
69 size_t elemsize;
70 size_t blk_alloc;
71 size_t n_blocks;
72 size_t n_alloc;
73 size_t n_freed;
74};
75
76#define MIN_ALLOC 50
77#define BLKID_SHIFT 16
78#define BLKID_MASK ((1<<BLKID_SHIFT)-1)
79
83static void listelem_add_block(listelem_alloc_t *list,
84 char *caller_file, int caller_line);
85
87listelem_alloc_init(size_t elemsize)
88{
89 listelem_alloc_t *list;
90
91 if ((elemsize % sizeof(void *)) != 0) {
92 size_t rounded = (elemsize + sizeof(void *) - 1) & ~(sizeof(void *)-1);
93 E_WARN
94 ("List item size (%lu) not multiple of sizeof(void *), rounding to %lu\n",
95 (unsigned long)elemsize,
96 (unsigned long)rounded);
97 elemsize = rounded;
98 }
99 list = ckd_calloc(1, sizeof(*list));
100 list->freelist = NULL;
101 list->blocks = NULL;
102 list->elemsize = elemsize;
103 /* Intent of this is to increase block size once we allocate
104 * 256KiB (i.e. 1<<18). If somehow the element size is big enough
105 * to overflow that, just fail, people should use malloc anyway. */
106 list->blk_alloc = (1 << 18) / (MIN_ALLOC * elemsize);
107 if (list->blk_alloc <= 0) {
108 E_ERROR("Element size * block size exceeds 256k, use malloc instead.\n");
109 ckd_free(list);
110 return NULL;
111 }
112 list->n_alloc = 0;
113 list->n_freed = 0;
114
115 /* Allocate an initial block to minimize latency. */
116 listelem_add_block(list, __FILE__, __LINE__);
117 return list;
118}
119
120void
122{
123 gnode_t *gn;
124 if (list == NULL)
125 return;
126 for (gn = list->blocks; gn; gn = gnode_next(gn))
127 ckd_free(gnode_ptr(gn));
128 glist_free(list->blocks);
129 glist_free(list->blocksize);
130 ckd_free(list);
131}
132
133static void
134listelem_add_block(listelem_alloc_t *list, char *caller_file, int caller_line)
135{
136 char **cpp, *cp;
137 size_t j;
138 int32 blocksize;
139
140 blocksize = list->blocksize ? gnode_int32(list->blocksize) : MIN_ALLOC;
141 /* Check if block size should be increased (if many requests for this size) */
142 if (list->blk_alloc == 0) {
143 /* See above. No sense in allocating blocks bigger than
144 * 256KiB (well, actually, there might be, but we'll worry
145 * about that later). */
146 blocksize <<= 1;
147 if (blocksize * list->elemsize > (1 << 18))
148 blocksize = (1 << 18) / list->elemsize;
149 list->blk_alloc = (1 << 18) / (blocksize * list->elemsize);
150 }
151
152 /* Allocate block */
153 cpp = list->freelist =
154 (char **) __ckd_calloc__(blocksize, list->elemsize,
155 caller_file, caller_line);
156 list->blocks = glist_add_ptr(list->blocks, cpp);
157 list->blocksize = glist_add_int32(list->blocksize, blocksize);
158 cp = (char *) cpp;
159 /* Link up the blocks via their first machine word. */
160 for (j = blocksize - 1; j > 0; --j) {
161 cp += list->elemsize;
162 *cpp = cp;
163 cpp = (char **) cp;
164 }
165 /* Make sure the last element's forward pointer is NULL */
166 *cpp = NULL;
167 --list->blk_alloc;
168 ++list->n_blocks;
169}
170
171
172void *
173__listelem_malloc__(listelem_alloc_t *list, char *caller_file, int caller_line)
174{
175 char **ptr;
176
177 /* Allocate a new block if list empty */
178 if (list->freelist == NULL)
179 listelem_add_block(list, caller_file, caller_line);
180
181 /* Unlink and return first element in freelist */
182 ptr = list->freelist;
183 list->freelist = (char **) (*(list->freelist));
184 (list->n_alloc)++;
185
186 return (void *)ptr;
187}
188
189void *
190__listelem_malloc_id__(listelem_alloc_t *list, char *caller_file,
191 int caller_line, int32 *out_id)
192{
193 char **ptr;
194
195 /* Allocate a new block if list empty */
196 if (list->freelist == NULL)
197 listelem_add_block(list, caller_file, caller_line);
198
199 /* Unlink and return first element in freelist */
200 ptr = list->freelist;
201 list->freelist = (char **) (*(list->freelist));
202 (list->n_alloc)++;
203
204 if (out_id) {
205 int32 blksize, blkidx, ptridx;
206 gnode_t *gn, *gn2;
207 char **block;
208
209 gn2 = list->blocksize;
210 block = NULL;
211 blkidx = 0;
212 for (gn = list->blocks; gn; gn = gnode_next(gn)) {
213 block = gnode_ptr(gn);
214 blksize = gnode_int32(gn2) * list->elemsize / sizeof(*block);
215 if (ptr >= block && ptr < block + blksize)
216 break;
217 gn2 = gnode_next(gn2);
218 ++blkidx;
219 }
220 if (gn == NULL) {
221 E_ERROR("Failed to find block index for pointer %p!\n", ptr);
222 }
223 ptridx = (ptr - block) / (list->elemsize / sizeof(*block));
224 E_DEBUG(4,("ptr %p block %p blkidx %d ptridx %d\n",
225 ptr, block, list->n_blocks - blkidx - 1, ptridx));
226 *out_id = ((list->n_blocks - blkidx - 1) << BLKID_SHIFT) | ptridx;
227 }
228
229 return ptr;
230}
231
232void *
234{
235 int32 blkidx, ptridx, i;
236 gnode_t *gn;
237
238 blkidx = (id >> BLKID_SHIFT) & BLKID_MASK;
239 ptridx = id & BLKID_MASK;
240
241 i = 0;
242 blkidx = list->n_blocks - blkidx;
243 for (gn = list->blocks; gn; gn = gnode_next(gn)) {
244 if (++i == blkidx)
245 break;
246 }
247 if (gn == NULL) {
248 E_ERROR("Failed to find block index %d\n", blkidx);
249 return NULL;
250 }
251
252 return (void *)((char **)gnode_ptr(gn)
253 + ptridx * (list->elemsize / sizeof(void *)));
254}
255
256void
258 char *caller_file, int caller_line)
259{
260 char **cpp;
261
262 /*
263 * Insert freed item at head of list.
264 */
265 cpp = (char **) elem;
266 *cpp = (char *) list->freelist;
267 list->freelist = cpp;
268 (list->n_freed)++;
269}
270
271
272void
274{
275 gnode_t *gn, *gn2;
276 char **cpp;
277 size_t n;
278
279 E_INFO("Linklist stats:\n");
280 for (n = 0, cpp = list->freelist; cpp;
281 cpp = (char **) (*cpp), n++);
282 E_INFO
283 ("elemsize %lu, #alloc %lu, #freed %lu, #freelist %lu\n",
284 (unsigned long)list->elemsize,
285 (unsigned long)list->n_alloc,
286 (unsigned long)list->n_freed,
287 (unsigned long)n);
288 E_INFO("Allocated blocks:\n");
289 gn2 = list->blocksize;
290 for (gn = list->blocks; gn; gn = gnode_next(gn)) {
291 E_INFO("%p (%d * %d bytes)\n", gnode_ptr(gn), gnode_int32(gn2), list->elemsize);
292 gn2 = gnode_next(gn2);
293 }
294}
Sphinx's memory allocation/deallocation routines.
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
Definition: ckd_alloc.c:244
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Definition: ckd_alloc.h:248
Implementation of logging routines.
#define E_ERROR(...)
Print error message to error log.
Definition: err.h:104
#define E_INFO(...)
Print logging information to standard error stream.
Definition: err.h:114
#define E_WARN(...)
Print warning message to error log.
Definition: err.h:109
#define E_DEBUG(level, x)
Print debugging information to standard error stream.
Definition: err.h:144
Generic linked-lists maintenance.
SPHINXBASE_EXPORT glist_t glist_add_int32(glist_t g, int32 val)
Create and prepend a new list node containing an integer.
Definition: glist.c:86
SPHINXBASE_EXPORT void glist_free(glist_t g)
Free the given generic list; user-defined data contained within is not automatically freed.
Definition: glist.c:133
SPHINXBASE_EXPORT glist_t glist_add_ptr(glist_t g, void *ptr)
Create and prepend a new list node, with the given user-defined data, at the HEAD of the given generi...
Definition: glist.c:74
#define gnode_ptr(g)
Head of a list of gnodes.
Definition: glist.h:109
Fast memory allocator for uniformly sized objects.
SPHINXBASE_EXPORT void listelem_stats(listelem_alloc_t *le)
Print number of allocation, numer of free operation stats.
SPHINXBASE_EXPORT void listelem_alloc_free(listelem_alloc_t *le)
Finalize and release all memory associated with a list element allocator.
SPHINXBASE_EXPORT void * listelem_get_item(listelem_alloc_t *le, int32 id)
Retrieve a list element by its identifier.
SPHINXBASE_EXPORT void __listelem_free__(listelem_alloc_t *le, void *elem, char *file, int line)
Free list element of given size.
SPHINXBASE_EXPORT listelem_alloc_t * listelem_alloc_init(size_t elemsize)
Initialize and return a list element allocator.
A node in a generic list.
Definition: glist.h:100
Fast linked list allocator.
glist_t blocks
Linked list of blocks allocated.
char ** freelist
ptr to first element in freelist
size_t elemsize
Number of (char *) in element.
size_t blk_alloc
Number of alloc operations before increasing blocksize.
glist_t blocksize
Number of elements in each block.