hmem.c

该压缩包为最新版htk的源代码,htk是现在比较流行的语音处理软件,请有兴趣的朋友下载使用

/* ----------------------------------------------------------- */
/*                                                             */
/*                          ___                                */
/*                       |_| | |_/   SPEECH                    */
/*                       | | | | \   RECOGNITION               */
/*                       =========   SOFTWARE                  */ 
/*                                                             */
/*                                                             */
/* ----------------------------------------------------------- */
/*         Copyright: Microsoft Corporation                    */
/*          1995-2000 Redmond, Washington USA                  */
/*                    http://www.microsoft.com                 */
/*                                                             */
/*   Use of this software is governed by a License Agreement   */
/*    ** See the file License for the Conditions of Use  **    */
/*    **     This banner notice must not be removed      **    */
/*                                                             */
/* ----------------------------------------------------------- */
/*         File: HMem.c:   Memory Management Module            */
/* ----------------------------------------------------------- */

char *hmem_version = "!HVER!HMem:   3.3 [CUED 28/04/05]";
char *hmem_vc_id = "$Id: HMem.c,v 1.1.1.1 2005/05/12 10:52:50 jal58 Exp $";

#include "HShell.h"
#include "HMem.h"

int debug_level = 0;               /* For esps linking */

/* --------------------------- Trace Flags ------------------------ */

static int trace = 0;

#define T_TOP  0001       /* Top Level Trace */
#define T_MHP  0002       /* M HEAP alloc/free */
#define T_CHP  0004       /* C HEAP alloc/free */
#define T_STK  0010       /* M STAK alloc/free */

/* ---------------------- Alignment Issues -------------------------- */

#define FWORD 8   /* size of a full word = basic alignment quanta */
/* 
   HMem only guarantees to allocate MSTAK objects on aligned boundaries.
   All MHEAP objects may be any size and they are allocated sequentially.
   However, a heap of math objects is guaranteed to work provided that the
   supplied size routines are used since these round up appropriately.
*/

/* EXPORT->MRound: round up a mem size request to be a multiple of FWORD */
size_t MRound(size_t size)
{
   return ((size % FWORD) == 0)?size : (size/FWORD + 1) * FWORD;
}

/* -------------- General Purpose Memory Management ----------------- */

static ConfParam *cParm[MAXGLOBS];       /* config parameters */
static int numParm = 0;
static Boolean protectStaks = FALSE;    /* enable stack protection */

MemHeap gstack;   /* global MSTAK for general purpose use */
MemHeap gcheap;   /* global CHEAP for general purpose use */

typedef struct _MemHeapRec {
   MemHeap *heap;
   struct _MemHeapRec *next;
} MemHeapRec;

static MemHeapRec *heapList = NULL;

/* RecordHeap: add given heap to list */
static void RecordHeap(MemHeap *x)
{
   MemHeapRec *p;
   
   if ((p=(MemHeapRec *)malloc(sizeof(MemHeapRec))) == NULL)
      HError(5105,"RecordHeap: Cannot allocate memory for MemHeapRec");
   p->heap = x; p->next = heapList;
   heapList = p;
}

/* UnRecordHeap: remove given heap from list */
static void UnRecordHeap(MemHeap *x)
{
   MemHeapRec *p, *q;
   
   p = heapList; q = NULL;
   while (p != NULL && p->heap != x){
      q = p;
      p = p->next;
   }
   if (p == NULL)
      HError(5171,"UnRecordHeap: heap %s not found",x->name);
   if (p==heapList) 
      heapList = p->next;
   else
      q->next = p->next;
   free(p);
}

/* AllocBlock: allocate and initialise a block for num items each of size */
static BlockP AllocBlock(size_t size, size_t num, HeapType type)
{
   BlockP p;
   ByteP c;
   int i;
   
   if (trace&T_TOP)
      printf("HMem: AllocBlock of %u bytes\n",num*size);
   if ((p = (BlockP) malloc(sizeof(Block))) == NULL)
      HError(5105,"AllocBlock: Cannot allocate Block");
   if ((p->data = (void *)malloc(size*num)) == NULL)
      HError(5105,"AllocBlock: Cannot allocate block data of %u bytes",size*num);
   switch (type){
   case MHEAP:
      if ((p->used = (ByteP)malloc((num+7)/8)) == NULL)
         HError(5105,"AllocBlock: Cannot allocate block used array");
      for (i=0,c=p->used; i < (num+7)/8; i++,c++) *c = 0;
      break;
   case MSTAK:
      p->used = NULL;
      break;
   default:
      HError(5190,"AllocBlock: bad type %d",type);
   }
   p->numElem = p->numFree = num; 
   p->firstFree=0; p->next=NULL;
   return p;
}    

/* BlockReorder: reorder blks so that one with n free elems/bytes is 1st */
static void BlockReorder(BlockP *p, int n)
{
   BlockP head,cur,prev;
   
   if (p==NULL) return;
   head = cur = *p; prev=NULL;
   while (cur != NULL) {
      if (cur->numFree >= n) {
         if (prev != NULL) {
            prev->next = cur->next;
            cur->next = head;
         }
         *p = cur;
         return;
      }
      prev = cur;
      cur = cur->next;
   }
}               

/* GetElem: return a pointer to the next free item in the block p */
static void *GetElem(BlockP p, size_t elemSize, HeapType type)
{
   int i,index;
   
   if (p == NULL) return NULL;
   switch (type){
   case MHEAP:
      /* firstFree indexes next free elem to get */
      if (p->numFree == 0) return NULL;
      index=p->firstFree;
      p->used[p->firstFree/8] |= 1<<(p->firstFree&7);
      p->numFree--;
      /* Look thru 'used' bitmap for next free elem */
      if (p->numFree > 0) {
         for (i=p->firstFree+1; i<p->numElem;i++)
            if ((p->used[i/8] & (1 <<(i&7))) == 0) {
               p->firstFree = i;
               break;
            }
      } else
         p->firstFree = p->numElem; /* one over the end */             
      return (void *)((ByteP)p->data+index*elemSize);
   case MSTAK:
      /* take elemSize bytes from top of stack */
      if (p->numFree < elemSize)  return NULL;
      index=p->firstFree;
      p->firstFree += elemSize;
      p->numFree -= elemSize;
      return (void *)((ByteP)p->data + index);
   default:
      HError(5190,"GetElem: bad type %d",type);
   }
   return NULL;  /* just to keep compiler happy */
}

/* EXPORT->InitMem: Initialise the module.  */
void InitMem(void)
{
   int i;
   Boolean b;
   
   Register(hmem_version, hmem_vc_id);
   CreateHeap(&gstack, "Global Stack",  MSTAK, 1, 0.0, 100000, ULONG_MAX ); /* #### should be max size_t */
   CreateHeap(&gcheap, "Global C Heap", CHEAP, 1, 0.0, 0,      0 );
   numParm = GetConfig("HMEM", TRUE, cParm, MAXGLOBS);
   if (numParm>0){
      if (GetConfInt(cParm,numParm,"TRACE",&i)) trace = i;
      if (GetConfBool(cParm,numParm,"PROTECTSTAKS",&b)) protectStaks = b;
   }
}

/* EXPORT->CreateHeap: create a memory heap with given characteristics */
void CreateHeap(MemHeap *x, char *name, HeapType type, size_t elemSize, 
                float growf, size_t numElem, size_t maxElem)
{
   char c=0;

   if (growf<0.0)
      HError(5170,"CreateHeap: -ve grow factor in heap %s",name);
   if (numElem>maxElem)
      HError(5170,"CreateHeap: init num elem > max elem in heap %s",name);
   if (elemSize <= 0)
      HError(5170,"CreateHeap: elem size = %u in heap %s",elemSize,name);
   if (type == MSTAK && elemSize !=1)
      HError(5170,"CreateHeap: elem size = %u in MSTAK heap %s",elemSize,name);
   x->name = (char *)malloc(strlen(name)+1);
   strcpy(x->name,name); /* cant use a MemHeap for this!! */
   x->type  = type; x->growf = growf;
   x->elemSize = elemSize;
   x->maxElem = maxElem;
   x->curElem = x->minElem = numElem;
   x->totUsed = x->totAlloc = 0;
   x->heap = NULL; 
   x->protectStk = (x==&gstack)?FALSE:protectStaks; 
   RecordHeap(x);
   if (trace&T_TOP){
      switch (type){
      case MHEAP: c='M'; break;
      case MSTAK: c='S'; break;
      case CHEAP: c='C'; break;
      }
      printf("HMem: Create Heap %s[%c] %u %.1f %u %u\n",name,c,
             elemSize, growf, numElem, maxElem);
   }
}

/* EXPORT->ResetHeap: Free all items from heap x */
void ResetHeap(MemHeap *x)
{
   BlockP cur,next;

   switch(x->type){
   case MHEAP:
      if (trace&T_TOP)
         printf("HMem: ResetHeap %s[M]\n",x->name);
      cur=x->heap;
      /* delete all blocks */
      while (cur != NULL) {
         next = cur->next;
         free(cur->data); free(cur->used);
         free(cur); cur = next;
      }
      x->curElem = x->minElem;
      x->totAlloc = 0; x->heap = NULL;
      break;
   case MSTAK:    
      if (trace&T_TOP)
         printf("HMem: ResetHeap %s[S]\n",x->name);
      cur=x->heap;       
      if (cur != NULL) {
         /* delete all blocks but first */
         while (cur->next != NULL) { 
            next = cur->next;
            x->totAlloc -= cur->numElem;
            free(cur->data); free(cur);
            cur = next;
         }
         x->heap = cur;
      }
      x->curElem = x->minElem;
      if (cur != NULL){
         cur->numFree = cur->numElem;
         cur->firstFree = 0;
      }
      break;
   case CHEAP:
      HError(5172,"ResetHeap: cannot reset C heap");
   }
   x->totUsed = 0;
}

/* EXPORT->DeleteHeap: delete given heap */
void DeleteHeap(MemHeap *x)
{
   if (x->type == CHEAP) 
      HError(5172,"DeleteHeap: cant delete C Heap %s",x->name);
   if (trace&T_TOP)
      printf("HMem: DeleteHeap %s\n",x->name);
   /* free all data blocks */
   ResetHeap(x);
   if (x->heap != NULL){
      free(x->heap->data);
      free(x->heap);
   }
   /* expunge all trace of it */
   UnRecordHeap(x);
   /* free name */
   free(x->name);
}

/* EXPORT->New: create a new element from heap x  */
void *New(MemHeap *x,size_t size)
{
   void *q;
   BlockP newp;
   size_t num,bytes,*ip,chdr;
   Boolean noSpace;
   Ptr *pp;
  
   if (x->elemSize <= 0)
      HError(5174,"New: heap %s not initialised",
             (x->name==NULL)? "Unnamed":x->name);
   switch(x->type){
   case MHEAP:
      /* Element is taken from first available slot in block list.  
         If none found a new block is allocated with num elems
         determined by the curElem, the grow factor growf and the
         upper limit maxElem. */
      if (size != 0 && size != x->elemSize)
         HError(5173,"New: MHEAP req for %u size elem from heap %s size %u",
                size,x->name,x->elemSize);

      noSpace = x->totUsed == x->totAlloc;
      if (noSpace || (q=GetElem(x->heap,x->elemSize,x->type)) == NULL) {
         if (!noSpace) BlockReorder(&(x->heap),1);
         if (noSpace || (q=GetElem(x->heap,x->elemSize,x->type)) == NULL) {
            num = (size_t) ((double)x->curElem * (x->growf + 1.0) + 0.5);
            if (num>x->maxElem) num = x->maxElem;
            newp = AllocBlock(x->elemSize, num, x->type);
            x->totAlloc += num; x->curElem = num;
            newp->next = x->heap;
            x->heap = newp;
            if ((q=GetElem(x->heap,x->elemSize,x->type)) == NULL)
               HError(5191,"New: null elem but just made block in heap %s",
                      x->name);
         }
      }
      x->totUsed++;
      if (trace&T_MHP)
         printf("HMem: %s[M] %u bytes at %p allocated\n",x->name,size,q);
      return q;
   case CHEAP:
      chdr = MRound(sizeof(size_t));
      q = malloc(size+chdr);
      if (q==NULL)
         HError(5105,"New: memory exhausted");
      x->totUsed += size; 
      x->totAlloc += size+chdr;
      ip = (size_t *)q; *ip = size;
      if (trace&T_CHP)
         printf("HMem: %s[C] %u+%u bytes at %p allocated\n",x->name,chdr,size,q);
      return (Ptr)((ByteP)q+chdr);
   case MSTAK:
      /* set required size - must alloc on double boundaries */
      if (x->protectStk) size += sizeof(Ptr);
      size = MRound(size);
      /* get elem from current block if possible */
      if ((q=GetElem(x->heap,size,x->type)) == NULL) {
         /* no space - so add a new (maybe bigger) block */
         bytes = (size_t)((double)x->curElem * (x->growf + 1.0) + 0.5);
         if (bytes > x->maxElem) bytes = x->maxElem;
         x->curElem = bytes;
         if (bytes < size) bytes = size;
         bytes = MRound(bytes);
         newp = AllocBlock(1, bytes, x->type);
         x->totAlloc += bytes; 
         newp->next = x->heap;
         x->heap = newp;
         if ((q=GetElem(x->heap,size,x->type)) == NULL)
            HError(5191,"New: null elem but just made block in heap %s",
                   x->name);
      }
      x->totUsed += size;
      if (trace&T_STK)
         printf("HMem: %s[S] %u bytes at %p allocated\n",x->name,size,q);
      if (x->protectStk) {
         pp = (Ptr *)((long)q + size - sizeof(Ptr)); /* #### fix this! */
         *pp = q;
      }
      return q;
   }
   return NULL;  /* just to keep compiler happy */
}


/* EXPORT->CNew: create a new element from heap x and initialise to zero */
Ptr CNew (MemHeap *x, size_t size)
{
   void *ptr;

   ptr = New (x, size);
   if (x->type == MHEAP && size ==0)
      size = x->elemSize;
   memset (ptr, 0, size);

   return ptr;
}

/* EXPORT->Dispose: Free item p from memory heap x */
void Dispose(MemHeap *x, void *p)
{
   BlockP head,cur,prev;
   Boolean found=FALSE;
   ByteP bp;
   size_t size,chdr;
   size_t num,index, *ip;
   Ptr *pp;
   
   if (x->totUsed == 0)
      HError(5105,"Dispose: heap %s is empty",x->name);
   switch(x->type){
   case MHEAP:
      head = x->heap; cur=head; prev=NULL;
      size = x->elemSize;
      while (cur != NULL && !found) {
         num = cur->numElem;
         found = cur->data <= p && 
            (((void*)((ByteP)cur->data+(num-1)*size)) >= p);
         if (!found) {
            prev=cur; cur=cur->next;
         }   
      }
      if (cur == NULL)
         HError(5175,"Dispose: Item to free in MHEAP %s not found",x->name);
      index = ((size_t)p-(size_t)cur->data)/size;
      cur->used[index/8] &= ~(1 <<(index&7));
      if (index < cur->firstFree) cur->firstFree = index;
      cur->numFree++; x->totUsed--;
      if (cur->numFree == cur->numElem) { 
         if (cur != head)                /* free the whole block */
            prev->next = cur->next;
         else
            head = cur->next;
         x->heap = head; x->totAlloc -= cur->numElem;
         free(cur->data); free(cur->used); free(cur);
      }
      if (trace&T_MHP)
         printf("HMem: %s[M] %u bytes at %p de-allocated\n",x->name,size,p);
      return;
   case MSTAK:
      /* search for item to dispose */
      cur = x->heap;
      if (x->protectStk){
         if (cur->firstFree > 0 ) /* s-top in current block */
            pp = (Ptr *)((size_t)cur->data+cur->firstFree-sizeof(Ptr));
         else{                      /* s-top in previous block */
            if (cur->next == NULL)
               HError(5175,"Dispose: empty stack");
            pp = (Ptr *)((size_t)cur->next->data+cur->next->firstFree-sizeof(Ptr));
         }
         if (*pp != p)
            HError(-5175,"Dispose: violation of stack discipline in %s [%p != %p]",
                   x->name, *pp, p);
      }
      while (cur != NULL && !found){
         /* check current block */
         num = cur->numElem;
         found = cur->data <= p && 
            (((void*)((ByteP)cur->data+num)) > p);
         if (!found) {     /* item not in cur block so delete it */
            x->heap = cur->next;
            x->totAlloc -= cur->numElem;
            x->totUsed -= cur->firstFree;
            free(cur->data);
            free(cur);
            cur = x->heap;
            if (trace&T_STK)
               printf("HMem: deleleting block in %s[S]\n",x->name);
         }
      }
      if (!found) 
         HError(5175,"Dispose: Item to free in MSTAK %s not found",x->name);
      /* finally cut back the stack in the current block */
      size = ((ByteP)cur->data + cur->firstFree) - (ByteP)p;
      if (((ByteP)cur->data + cur->firstFree) < (ByteP)p)
         HError(5175,"Dispose: item to free in MSTAK %s is above stack top",
                x->name);
      cur->firstFree -= size;
      cur->numFree += size; x->totUsed -= size;
      if (trace&T_STK)
         printf("HMem: %s[S] %u bytes at %p de-allocated\n",x->name,size,p);
      return;
   case CHEAP:
      chdr = MRound(sizeof(size_t));
      bp = (ByteP)p-chdr;
      ip = (size_t *)bp;
      x->totAlloc -= (*ip + chdr); x->totUsed -= *ip;
      if (trace&T_CHP)
         printf("HMem: %s[C] %u+%u bytes at %p de-allocated\n",
                x->name,chdr,*ip,bp);
      free(bp);
      return;
   }
}