SphinxBase
0.6
|
00001 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */ 00002 /* ==================================================================== 00003 * Copyright (c) 1999-2004 Carnegie Mellon University. All rights 00004 * reserved. 00005 * 00006 * Redistribution and use in source and binary forms, with or without 00007 * modification, are permitted provided that the following conditions 00008 * are met: 00009 * 00010 * 1. Redistributions of source code must retain the above copyright 00011 * notice, this list of conditions and the following disclaimer. 00012 * 00013 * 2. Redistributions in binary form must reproduce the above copyright 00014 * notice, this list of conditions and the following disclaimer in 00015 * the documentation and/or other materials provided with the 00016 * distribution. 00017 * 00018 * This work was supported in part by funding from the Defense Advanced 00019 * Research Projects Agency and the National Science Foundation of the 00020 * United States of America, and the CMU Sphinx Speech Consortium. 00021 * 00022 * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND 00023 * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 00024 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 00025 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY 00026 * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00027 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 00028 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00029 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00030 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00031 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 00032 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00033 * 00034 * ==================================================================== 00035 * 00036 */ 00037 00038 #include <stdio.h> 00039 #include <stdlib.h> 00040 00041 #include "sphinxbase/err.h" 00042 #include "sphinxbase/ckd_alloc.h" 00043 #include "sphinxbase/listelem_alloc.h" 00044 #include "sphinxbase/glist.h" 00045 00065 struct listelem_alloc_s { 00066 char **freelist; 00067 glist_t blocks; 00068 glist_t blocksize; 00069 size_t elemsize; 00070 size_t blk_alloc; 00071 size_t n_blocks; 00072 size_t n_alloc; 00073 size_t n_freed; 00074 }; 00075 00076 #define MIN_ALLOC 50 00077 #define BLKID_SHIFT 16 00078 #define BLKID_MASK ((1<<BLKID_SHIFT)-1) 00079 00083 static void listelem_add_block(listelem_alloc_t *list, 00084 char *caller_file, int caller_line); 00085 00086 listelem_alloc_t * 00087 listelem_alloc_init(size_t elemsize) 00088 { 00089 listelem_alloc_t *list; 00090 00091 if ((elemsize % sizeof(void *)) != 0) { 00092 size_t rounded = (elemsize + sizeof(void *) - 1) & ~(sizeof(void *)-1); 00093 E_WARN 00094 ("List item size (%lu) not multiple of sizeof(void *), rounding to %lu\n", 00095 (unsigned long)elemsize, 00096 (unsigned long)rounded); 00097 elemsize = rounded; 00098 } 00099 list = ckd_calloc(1, sizeof(*list)); 00100 list->freelist = NULL; 00101 list->blocks = NULL; 00102 list->elemsize = elemsize; 00103 /* Intent of this is to increase block size once we allocate 00104 * 256KiB (i.e. 1<<18). If somehow the element size is big enough 00105 * to overflow that, just fail, people should use malloc anyway. */ 00106 list->blk_alloc = (1 << 18) / (MIN_ALLOC * elemsize); 00107 if (list->blk_alloc <= 0) { 00108 E_ERROR("Element size * block size exceeds 256k, use malloc instead.\n"); 00109 ckd_free(list); 00110 return NULL; 00111 } 00112 list->n_alloc = 0; 00113 list->n_freed = 0; 00114 00115 /* Allocate an initial block to minimize latency. */ 00116 listelem_add_block(list, __FILE__, __LINE__); 00117 return list; 00118 } 00119 00120 void 00121 listelem_alloc_free(listelem_alloc_t *list) 00122 { 00123 gnode_t *gn; 00124 if (list == NULL) 00125 return; 00126 for (gn = list->blocks; gn; gn = gnode_next(gn)) 00127 ckd_free(gnode_ptr(gn)); 00128 glist_free(list->blocks); 00129 glist_free(list->blocksize); 00130 ckd_free(list); 00131 } 00132 00133 static void 00134 listelem_add_block(listelem_alloc_t *list, char *caller_file, int caller_line) 00135 { 00136 char **cpp, *cp; 00137 size_t j; 00138 int32 blocksize; 00139 00140 blocksize = list->blocksize ? gnode_int32(list->blocksize) : MIN_ALLOC; 00141 /* Check if block size should be increased (if many requests for this size) */ 00142 if (list->blk_alloc == 0) { 00143 /* See above. No sense in allocating blocks bigger than 00144 * 256KiB (well, actually, there might be, but we'll worry 00145 * about that later). */ 00146 blocksize <<= 1; 00147 if (blocksize * list->elemsize > (1 << 18)) 00148 blocksize = (1 << 18) / list->elemsize; 00149 list->blk_alloc = (1 << 18) / (blocksize * list->elemsize); 00150 } 00151 00152 /* Allocate block */ 00153 cpp = list->freelist = 00154 (char **) __ckd_calloc__(blocksize, list->elemsize, 00155 caller_file, caller_line); 00156 list->blocks = glist_add_ptr(list->blocks, cpp); 00157 list->blocksize = glist_add_int32(list->blocksize, blocksize); 00158 cp = (char *) cpp; 00159 /* Link up the blocks via their first machine word. */ 00160 for (j = blocksize - 1; j > 0; --j) { 00161 cp += list->elemsize; 00162 *cpp = cp; 00163 cpp = (char **) cp; 00164 } 00165 /* Make sure the last element's forward pointer is NULL */ 00166 *cpp = NULL; 00167 --list->blk_alloc; 00168 ++list->n_blocks; 00169 } 00170 00171 00172 void * 00173 __listelem_malloc__(listelem_alloc_t *list, char *caller_file, int caller_line) 00174 { 00175 char **ptr; 00176 00177 /* Allocate a new block if list empty */ 00178 if (list->freelist == NULL) 00179 listelem_add_block(list, caller_file, caller_line); 00180 00181 /* Unlink and return first element in freelist */ 00182 ptr = list->freelist; 00183 list->freelist = (char **) (*(list->freelist)); 00184 (list->n_alloc)++; 00185 00186 return (void *)ptr; 00187 } 00188 00189 void * 00190 __listelem_malloc_id__(listelem_alloc_t *list, char *caller_file, 00191 int caller_line, int32 *out_id) 00192 { 00193 char **ptr; 00194 00195 /* Allocate a new block if list empty */ 00196 if (list->freelist == NULL) 00197 listelem_add_block(list, caller_file, caller_line); 00198 00199 /* Unlink and return first element in freelist */ 00200 ptr = list->freelist; 00201 list->freelist = (char **) (*(list->freelist)); 00202 (list->n_alloc)++; 00203 00204 if (out_id) { 00205 int32 blksize, blkidx, ptridx; 00206 gnode_t *gn, *gn2; 00207 char **block; 00208 00209 gn2 = list->blocksize; 00210 block = NULL; 00211 blkidx = 0; 00212 for (gn = list->blocks; gn; gn = gnode_next(gn)) { 00213 block = gnode_ptr(gn); 00214 blksize = gnode_int32(gn2) * list->elemsize / sizeof(*block); 00215 if (ptr >= block && ptr < block + blksize) 00216 break; 00217 gn2 = gnode_next(gn2); 00218 ++blkidx; 00219 } 00220 if (gn == NULL) { 00221 E_ERROR("Failed to find block index for pointer %p!\n", ptr); 00222 } 00223 ptridx = (ptr - block) / (list->elemsize / sizeof(*block)); 00224 E_DEBUG(4,("ptr %p block %p blkidx %d ptridx %d\n", 00225 ptr, block, list->n_blocks - blkidx - 1, ptridx)); 00226 *out_id = ((list->n_blocks - blkidx - 1) << BLKID_SHIFT) | ptridx; 00227 } 00228 00229 return ptr; 00230 } 00231 00232 void * 00233 listelem_get_item(listelem_alloc_t *list, int32 id) 00234 { 00235 int32 blkidx, ptridx, i; 00236 gnode_t *gn; 00237 00238 blkidx = (id >> BLKID_SHIFT) & BLKID_MASK; 00239 ptridx = id & BLKID_MASK; 00240 00241 i = 0; 00242 blkidx = list->n_blocks - blkidx; 00243 for (gn = list->blocks; gn; gn = gnode_next(gn)) { 00244 if (++i == blkidx) 00245 break; 00246 } 00247 if (gn == NULL) { 00248 E_ERROR("Failed to find block index %d\n", blkidx); 00249 return NULL; 00250 } 00251 00252 return (void *)((char **)gnode_ptr(gn) 00253 + ptridx * (list->elemsize / sizeof(void *))); 00254 } 00255 00256 void 00257 __listelem_free__(listelem_alloc_t *list, void *elem, 00258 char *caller_file, int caller_line) 00259 { 00260 char **cpp; 00261 00262 /* 00263 * Insert freed item at head of list. 00264 */ 00265 cpp = (char **) elem; 00266 *cpp = (char *) list->freelist; 00267 list->freelist = cpp; 00268 (list->n_freed)++; 00269 } 00270 00271 00272 void 00273 listelem_stats(listelem_alloc_t *list) 00274 { 00275 gnode_t *gn, *gn2; 00276 char **cpp; 00277 size_t n; 00278 00279 E_INFO("Linklist stats:\n"); 00280 for (n = 0, cpp = list->freelist; cpp; 00281 cpp = (char **) (*cpp), n++); 00282 E_INFO 00283 ("elemsize %lu, #alloc %lu, #freed %lu, #freelist %lu\n", 00284 (unsigned long)list->elemsize, 00285 (unsigned long)list->n_alloc, 00286 (unsigned long)list->n_freed, 00287 (unsigned long)n); 00288 E_INFO("Allocated blocks:\n"); 00289 gn2 = list->blocksize; 00290 for (gn = list->blocks; gn; gn = gnode_next(gn)) { 00291 E_INFO("%p (%d * %d bytes)\n", gnode_ptr(gn), gnode_int32(gn2), list->elemsize); 00292 gn2 = gnode_next(gn2); 00293 } 00294 }