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"
42 #include "sphinxbase/ckd_alloc.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 
83 static void listelem_add_block(listelem_alloc_t *list,
84  char *caller_file, int caller_line);
85 
87 listelem_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 
120 void
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 
133 static void
134 listelem_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 
172 void *
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 
189 void *
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 
232 void *
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 
256 void
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 
272 void
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 }
#define E_INFO(...)
Print logging information to standard error stream.
Definition: err.h:114
#define ckd_calloc(n, sz)
Macros to simplify the use of above functions.
Definition: ckd_alloc.h:248
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
#define E_ERROR(...)
Print error message to error log.
Definition: err.h:104
#define E_DEBUG(level, x)
Print debugging information to standard error stream.
Definition: err.h:144
Sphinx&#39;s memory allocation/deallocation routines.
A node in a generic list.
Definition: glist.h:100
SPHINXBASE_EXPORT void ckd_free(void *ptr)
Test and free a 1-D array.
Definition: ckd_alloc.c:244
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
glist_t blocks
Linked list of blocks allocated.
Fast linked list allocator.
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 void * listelem_get_item(listelem_alloc_t *le, int32 id)
Retrieve a list element by its identifier.
#define gnode_ptr(g)
Head of a list of gnodes.
Definition: glist.h:109
Fast memory allocator for uniformly sized objects.
Implementation of logging routines.
char ** freelist
ptr to first element in freelist
Generic linked-lists maintenance.
#define E_WARN(...)
Print warning message to error log.
Definition: err.h:109
size_t blk_alloc
Number of alloc operations before increasing blocksize.
SPHINXBASE_EXPORT listelem_alloc_t * listelem_alloc_init(size_t elemsize)
Initialize and return a list element allocator.
glist_t blocksize
Number of elements in each block.
size_t elemsize
Number of (char *) in element.
SPHINXBASE_EXPORT void listelem_stats(listelem_alloc_t *le)
Print number of allocation, numer of free operation stats.
SPHINXBASE_EXPORT void __listelem_free__(listelem_alloc_t *le, void *elem, char *file, int line)
Free list element of given size.
SPHINXBASE_EXPORT void listelem_alloc_free(listelem_alloc_t *le)
Finalize and release all memory associated with a list element allocator.