summaryrefslogtreecommitdiffstats
path: root/media/sphinxbase/src/libsphinxbase/util/listelem_alloc.c
diff options
context:
space:
mode:
Diffstat (limited to 'media/sphinxbase/src/libsphinxbase/util/listelem_alloc.c')
-rw-r--r--media/sphinxbase/src/libsphinxbase/util/listelem_alloc.c294
1 files changed, 0 insertions, 294 deletions
diff --git a/media/sphinxbase/src/libsphinxbase/util/listelem_alloc.c b/media/sphinxbase/src/libsphinxbase/util/listelem_alloc.c
deleted file mode 100644
index 354c4767c..000000000
--- a/media/sphinxbase/src/libsphinxbase/util/listelem_alloc.c
+++ /dev/null
@@ -1,294 +0,0 @@
-/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
-/* ====================================================================
- * Copyright (c) 1999-2004 Carnegie Mellon University. All rights
- * reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- *
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in
- * the documentation and/or other materials provided with the
- * distribution.
- *
- * This work was supported in part by funding from the Defense Advanced
- * Research Projects Agency and the National Science Foundation of the
- * United States of America, and the CMU Sphinx Speech Consortium.
- *
- * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
- * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
- * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
- * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * ====================================================================
- *
- */
-
-#include <stdio.h>
-#include <stdlib.h>
-
-#include "sphinxbase/err.h"
-#include "sphinxbase/ckd_alloc.h"
-#include "sphinxbase/listelem_alloc.h"
-#include "sphinxbase/glist.h"
-
-/**
- * Fast linked list allocator.
- *
- * We keep a separate linked list for each element-size. Element-size
- * must be a multiple of pointer-size.
- *
- * Initially a block of empty elements is allocated, where the first
- * machine word in each element points to the next available element.
- * To allocate, we use this pointer to move the freelist to the next
- * element, then return the current element.
- *
- * The last element in the list starts with a NULL pointer, which is
- * used as a signal to allocate a new block of elements.
- *
- * In order to be able to actually release the memory allocated, we
- * have to add a linked list of block pointers. This shouldn't create
- * much overhead since we never access it except when freeing the
- * allocator.
- */
-struct listelem_alloc_s {
- char **freelist; /**< ptr to first element in freelist */
- glist_t blocks; /**< Linked list of blocks allocated. */
- glist_t blocksize; /**< Number of elements in each block */
- size_t elemsize; /**< Number of (char *) in element */
- size_t blk_alloc; /**< Number of alloc operations before increasing blocksize */
- size_t n_blocks;
- size_t n_alloc;
- size_t n_freed;
-};
-
-#define MIN_ALLOC 50 /**< Minimum number of elements to allocate in one block */
-#define BLKID_SHIFT 16 /**< Bit position of block number in element ID */
-#define BLKID_MASK ((1<<BLKID_SHIFT)-1)
-
-/**
- * Allocate a new block of elements.
- */
-static void listelem_add_block(listelem_alloc_t *list,
- char *caller_file, int caller_line);
-
-listelem_alloc_t *
-listelem_alloc_init(size_t elemsize)
-{
- listelem_alloc_t *list;
-
- if ((elemsize % sizeof(void *)) != 0) {
- size_t rounded = (elemsize + sizeof(void *) - 1) & ~(sizeof(void *)-1);
- E_WARN
- ("List item size (%lu) not multiple of sizeof(void *), rounding to %lu\n",
- (unsigned long)elemsize,
- (unsigned long)rounded);
- elemsize = rounded;
- }
- list = ckd_calloc(1, sizeof(*list));
- list->freelist = NULL;
- list->blocks = NULL;
- list->elemsize = elemsize;
- /* Intent of this is to increase block size once we allocate
- * 256KiB (i.e. 1<<18). If somehow the element size is big enough
- * to overflow that, just fail, people should use malloc anyway. */
- list->blk_alloc = (1 << 18) / (MIN_ALLOC * elemsize);
- if (list->blk_alloc <= 0) {
- E_ERROR("Element size * block size exceeds 256k, use malloc instead.\n");
- ckd_free(list);
- return NULL;
- }
- list->n_alloc = 0;
- list->n_freed = 0;
-
- /* Allocate an initial block to minimize latency. */
- listelem_add_block(list, __FILE__, __LINE__);
- return list;
-}
-
-void
-listelem_alloc_free(listelem_alloc_t *list)
-{
- gnode_t *gn;
- if (list == NULL)
- return;
- for (gn = list->blocks; gn; gn = gnode_next(gn))
- ckd_free(gnode_ptr(gn));
- glist_free(list->blocks);
- glist_free(list->blocksize);
- ckd_free(list);
-}
-
-static void
-listelem_add_block(listelem_alloc_t *list, char *caller_file, int caller_line)
-{
- char **cpp, *cp;
- size_t j;
- int32 blocksize;
-
- blocksize = list->blocksize ? gnode_int32(list->blocksize) : MIN_ALLOC;
- /* Check if block size should be increased (if many requests for this size) */
- if (list->blk_alloc == 0) {
- /* See above. No sense in allocating blocks bigger than
- * 256KiB (well, actually, there might be, but we'll worry
- * about that later). */
- blocksize <<= 1;
- if (blocksize * list->elemsize > (1 << 18))
- blocksize = (1 << 18) / list->elemsize;
- list->blk_alloc = (1 << 18) / (blocksize * list->elemsize);
- }
-
- /* Allocate block */
- cpp = list->freelist =
- (char **) __ckd_calloc__(blocksize, list->elemsize,
- caller_file, caller_line);
- list->blocks = glist_add_ptr(list->blocks, cpp);
- list->blocksize = glist_add_int32(list->blocksize, blocksize);
- cp = (char *) cpp;
- /* Link up the blocks via their first machine word. */
- for (j = blocksize - 1; j > 0; --j) {
- cp += list->elemsize;
- *cpp = cp;
- cpp = (char **) cp;
- }
- /* Make sure the last element's forward pointer is NULL */
- *cpp = NULL;
- --list->blk_alloc;
- ++list->n_blocks;
-}
-
-
-void *
-__listelem_malloc__(listelem_alloc_t *list, char *caller_file, int caller_line)
-{
- char **ptr;
-
- /* Allocate a new block if list empty */
- if (list->freelist == NULL)
- listelem_add_block(list, caller_file, caller_line);
-
- /* Unlink and return first element in freelist */
- ptr = list->freelist;
- list->freelist = (char **) (*(list->freelist));
- (list->n_alloc)++;
-
- return (void *)ptr;
-}
-
-void *
-__listelem_malloc_id__(listelem_alloc_t *list, char *caller_file,
- int caller_line, int32 *out_id)
-{
- char **ptr;
-
- /* Allocate a new block if list empty */
- if (list->freelist == NULL)
- listelem_add_block(list, caller_file, caller_line);
-
- /* Unlink and return first element in freelist */
- ptr = list->freelist;
- list->freelist = (char **) (*(list->freelist));
- (list->n_alloc)++;
-
- if (out_id) {
- int32 blksize, blkidx, ptridx;
- gnode_t *gn, *gn2;
- char **block;
-
- gn2 = list->blocksize;
- block = NULL;
- blkidx = 0;
- for (gn = list->blocks; gn; gn = gnode_next(gn)) {
- block = gnode_ptr(gn);
- blksize = gnode_int32(gn2) * list->elemsize / sizeof(*block);
- if (ptr >= block && ptr < block + blksize)
- break;
- gn2 = gnode_next(gn2);
- ++blkidx;
- }
- if (gn == NULL) {
- E_ERROR("Failed to find block index for pointer %p!\n", ptr);
- }
- ptridx = (ptr - block) / (list->elemsize / sizeof(*block));
- E_DEBUG(4,("ptr %p block %p blkidx %d ptridx %d\n",
- ptr, block, list->n_blocks - blkidx - 1, ptridx));
- *out_id = ((list->n_blocks - blkidx - 1) << BLKID_SHIFT) | ptridx;
- }
-
- return ptr;
-}
-
-void *
-listelem_get_item(listelem_alloc_t *list, int32 id)
-{
- int32 blkidx, ptridx, i;
- gnode_t *gn;
-
- blkidx = (id >> BLKID_SHIFT) & BLKID_MASK;
- ptridx = id & BLKID_MASK;
-
- i = 0;
- blkidx = list->n_blocks - blkidx;
- for (gn = list->blocks; gn; gn = gnode_next(gn)) {
- if (++i == blkidx)
- break;
- }
- if (gn == NULL) {
- E_ERROR("Failed to find block index %d\n", blkidx);
- return NULL;
- }
-
- return (void *)((char **)gnode_ptr(gn)
- + ptridx * (list->elemsize / sizeof(void *)));
-}
-
-void
-__listelem_free__(listelem_alloc_t *list, void *elem,
- char *caller_file, int caller_line)
-{
- char **cpp;
-
- /*
- * Insert freed item at head of list.
- */
- cpp = (char **) elem;
- *cpp = (char *) list->freelist;
- list->freelist = cpp;
- (list->n_freed)++;
-}
-
-
-void
-listelem_stats(listelem_alloc_t *list)
-{
- gnode_t *gn, *gn2;
- char **cpp;
- size_t n;
-
- E_INFO("Linklist stats:\n");
- for (n = 0, cpp = list->freelist; cpp;
- cpp = (char **) (*cpp), n++);
- E_INFO
- ("elemsize %lu, #alloc %lu, #freed %lu, #freelist %lu\n",
- (unsigned long)list->elemsize,
- (unsigned long)list->n_alloc,
- (unsigned long)list->n_freed,
- (unsigned long)n);
- E_INFO("Allocated blocks:\n");
- gn2 = list->blocksize;
- for (gn = list->blocks; gn; gn = gnode_next(gn)) {
- E_INFO("%p (%d * %d bytes)\n", gnode_ptr(gn), gnode_int32(gn2), list->elemsize);
- gn2 = gnode_next(gn2);
- }
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-28 19:13:52 +0000