SphinxBase 0.6
src/libsphinxbase/util/listelem_alloc.c
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 }