• Main Page
  • Related Pages
  • Data Structures
  • Files
  • File List
  • Globals

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 <err.h>
00042 #include <ckd_alloc.h>
00043 #include <listelem_alloc.h>
00044 #include <glist.h>
00045 
00065 struct listelem_alloc_s {
00066     char **freelist;            
00067     glist_t blocks;             
00068     size_t elemsize;            
00069     size_t blocksize;           
00070     size_t blk_alloc;           
00071     size_t n_alloc;
00072     size_t n_freed;
00073 };
00074 
00075 #define MIN_ALLOC       50      
00079 static void listelem_add_block(listelem_alloc_t *list,
00080                                char *caller_file, int caller_line);
00081 
00082 listelem_alloc_t *
00083 listelem_alloc_init(size_t elemsize)
00084 {
00085     listelem_alloc_t *list;
00086 
00087     if ((elemsize % sizeof(void *)) != 0) {
00088         size_t rounded = (elemsize + sizeof(void *) - 1) & ~(sizeof(void *)-1);
00089         E_WARN
00090             ("List item size (%lu) not multiple of sizeof(void *), rounding to %lu\n",
00091              (unsigned long)elemsize,
00092              (unsigned long)rounded);
00093         elemsize = rounded;
00094     }
00095     list = ckd_calloc(1, sizeof(*list));
00096     list->freelist = NULL;
00097     list->blocks = NULL;
00098     list->elemsize = elemsize;
00099     list->blocksize = MIN_ALLOC;
00100     list->blk_alloc = (1 << 18) / (list->blocksize * sizeof(elemsize));
00101     list->n_alloc = 0;
00102     list->n_freed = 0;
00103 
00104     /* Allocate an initial block to minimize latency. */
00105     listelem_add_block(list, __FILE__, __LINE__);
00106     return list;
00107 }
00108 
00109 void
00110 listelem_alloc_free(listelem_alloc_t *list)
00111 {
00112     gnode_t *gn;
00113     if (list == NULL)
00114         return;
00115     for (gn = list->blocks; gn; gn = gnode_next(gn))
00116         ckd_free(gnode_ptr(gn));
00117     glist_free(list->blocks);
00118     ckd_free(list);
00119 }
00120 
00121 static void
00122 listelem_add_block(listelem_alloc_t *list, char *caller_file, int caller_line)
00123 {
00124     char **cpp, *cp;
00125     size_t j;
00126 
00127     /* Check if block size should be increased (if many requests for this size) */
00128     if (list->blk_alloc == 0) {
00129         list->blocksize <<= 1;
00130         list->blk_alloc =
00131             (1 << 18) / (list->blocksize * sizeof(list->elemsize));
00132         if (list->blk_alloc <= 0)
00133             list->blk_alloc = (size_t) 0x70000000;   /* Limit blocksize to new value */
00134     }
00135 
00136     /* Allocate block */
00137     cpp = list->freelist =
00138         (char **) __ckd_calloc__(list->blocksize, list->elemsize,
00139                                  caller_file, caller_line);
00140     list->blocks = glist_add_ptr(list->blocks, cpp);
00141     cp = (char *) cpp;
00142     /* Link up the blocks via their first machine word. */
00143     for (j = list->blocksize - 1; j > 0; --j) {
00144         cp += list->elemsize;
00145         *cpp = cp;
00146         cpp = (char **) cp;
00147     }
00148     /* Make sure the last element's forward pointer is NULL */
00149     *cpp = NULL;
00150     --(list->blk_alloc);
00151 }
00152 
00153 
00154 void *
00155 __listelem_malloc__(listelem_alloc_t *list, char *caller_file, int caller_line)
00156 {
00157     void *ptr;
00158 
00159     /* Allocate a new block if list empty */
00160     if (list->freelist == NULL)
00161         listelem_add_block(list, caller_file, caller_line);
00162 
00163     /* Unlink and return first element in freelist */
00164     ptr = list->freelist;
00165     list->freelist = (char **) (*(list->freelist));
00166     (list->n_alloc)++;
00167 
00168     return ptr;
00169 }
00170 
00171 
00172 void
00173 __listelem_free__(listelem_alloc_t *list, void *elem,
00174                   char *caller_file, int caller_line)
00175 {
00176     char **cpp;
00177 
00178     /*
00179      * Insert freed item at head of list.
00180      */
00181     cpp = (char **) elem;
00182     *cpp = (char *) list->freelist;
00183     list->freelist = cpp;
00184     (list->n_freed)++;
00185 }
00186 
00187 
00188 void
00189 listelem_stats(listelem_alloc_t *list)
00190 {
00191     gnode_t *gn;
00192     char **cpp;
00193     size_t n;
00194 
00195     E_INFO("Linklist stats:\n");
00196     for (n = 0, cpp = list->freelist; cpp;
00197          cpp = (char **) (*cpp), n++);
00198     E_INFO
00199         ("elemsize %lu, blocksize %lu, #alloc %lu, #freed %lu, #freelist %lu\n",
00200          (unsigned long)list->elemsize,
00201          (unsigned long)list->blocksize,
00202          (unsigned long)list->n_alloc,
00203          (unsigned long)list->n_freed,
00204          (unsigned long)n);
00205     E_INFO("Allocated blocks:\n");
00206     for (gn = list->blocks; gn; gn = gnode_next(gn))
00207         E_INFO("%p\n", gnode_ptr(gn));
00208 }

Generated on Thu Jan 6 2011 for SphinxBase by  doxygen 1.7.1