irstlm/src/mempool.cpp

Go to the documentation of this file.

// $Id: mempool.cpp 302 2009-08-25 13:04:13Z nicolabertoldi $

/******************************************************************************
 IrstLM: IRST Language Model Toolkit
 Copyright (C) 2006 Marcello Federico, ITC-irst Trento, Italy

 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License as published by the Free Software Foundation; either
 version 2.1 of the License, or (at your option) any later version.

 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 Lesser General Public License for more details.

 You should have received a copy of the GNU Lesser General Public
 License along with this library; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA

******************************************************************************/

// An efficient memory pool manager 
// by M. Federico 
// Copyright Marcello Federico, ITC-irst, 1998

#include <stdio.h>
#include <cstring>
#include <string.h>
#include <cstdlib>
#include <stdlib.h>
#include <iostream>
#include <ostream>
#include <cassert>
#include "mempool.h"

using namespace std;

#ifdef TRACE_ENABLE
#define TRACE_ERR(str) { std::cerr << str; }
#else
#define TRACE_ERR(str) { }
#endif

mempool::mempool(int is, int bs){
  
  // item size must be multiple of memory alignment step (4 bytes)
  // example: is is=9  becomes i=12 (9 + 4 - 9 %4 )
  
  is=(is>(int)sizeof(char *)?is:0);   
  
  is=is + sizeof(char *) - (is % sizeof(char *));  
  
  item_size  = is;
  
  block_size = bs;      
  
  true_size  = is * bs;
  
  block_list = new memnode;
  
  block_list->block = new char[true_size];
  
  memset(block_list->block,'0',true_size);
  
  block_list->next  = 0;
  
  blocknum = 1;
  
  entries  = 0;
  
  // build free list
  
  char *ptr = free_list = block_list->block;
  
  for (int i=0;i<block_size-1;i++) {
    *(char **)ptr= ptr + item_size;
    ptr+=item_size;                     
  }
  *(char **)ptr = NULL; //last item
  
}


char * mempool::allocate(){
  
  char *ptr;
  
  if (free_list==NULL)
  {
    memnode *new_block = new memnode;
    
    new_block->block = new char[true_size];
    
    //memset(new_block->block,'0',true_size);
    
    new_block->next  = block_list;
    
    block_list=new_block; // update block list
    
    /* update  free list */
    
    ptr = free_list = block_list->block;
    
    for (int i=0;i<block_size-1;i++) {
      *(char **)ptr = ptr + item_size;
      ptr = ptr + item_size;                 
    } 
    
    *(char **)ptr=NULL;
    
    blocknum++;
  }
  
  assert(free_list);
  
  ptr = free_list;
  
  free_list=*(char **)ptr;
  
  *(char **)ptr=NULL; // reset the released item
  
  entries++;
  
  return ptr;
  
}


int mempool::free(char* addr){
  
  // do not check if it belongs to this pool !!
  /*
   memnode  *list=block_list;
   while ((list != NULL) &&
          ((addr < list->block) ||
           (addr >= (list->block + true_size))))
   list=list->next;
   
   if ((list==NULL) || (((addr - list->block) % item_size)!=0))
   {
     //cerr << "mempool::free-> addr does not belong to this pool\n";
     return 0;
   }
   */
  
  *(char **)addr=free_list;
  free_list=addr;
  
  entries--;
  
  return 1;
}


mempool::~mempool()
{
  memnode *ptr;
  
  while (block_list !=NULL){
    ptr=block_list->next;    
    delete [] block_list->block;
    delete block_list;
    block_list=ptr;
  } 
  
}

void mempool::map (ostream& co){
  
  co << "mempool memory map:\n";
  //percorri piu` volte la lista libera
  
  memnode *bl=block_list;
  char *fl=free_list;
  
  char* img=new char[block_size+1];
  img[block_size]='\0';
  
  while (bl !=NULL){
    
    memset(img,'#',block_size);
    
    fl=free_list;
    while (fl != NULL){
      if ((fl >= bl->block) 
          && 
          (fl < bl->block + true_size))
      {
        img[(fl-bl->block)/item_size]='-';
      }
      
      fl=*(char **)fl;                     
    }  
    
    co << img << "\n";
    bl=bl->next;    
  } 
        delete [] img;
}

void mempool::stat(){
  
  TRACE_ERR("mempool class statistics\n"
            << "entries " << entries
            << " blocks " << blocknum
            << " used memory " << (blocknum * true_size)/1024 << " Kb\n");
}



strstack::strstack(int bs){
  
  size=bs;
  list=new memnode;
  
  list->block=new char[size];
  
  list->next=0;
  
  memset(list->block,'\0',size);
  idx=0;
  
  waste=0;
  memory=size;
  entries=0;
  blocknum=1;
  
}


void strstack::stat(){
  
  TRACE_ERR("strstack class statistics\n"
            << "entries " << entries
            << " blocks " << blocknum
            << " used memory " << memory/1024 << " Kb\n");
}


const char *strstack::push(const char *s){
  int len=strlen(s);
  
  if ((len+1) >= size){
    cerr << "strstack::push string is too long\n";
    exit(1);
  };
  
  if ((idx+len+1) >= size){
    //append a new block
    //there must be space to 
    //put the index after 
    //the word
    
    waste+=size-idx;
    blocknum++;
    memory+=size;
    
    memnode* nd=new memnode;
    nd->block=new char[size];
    nd->next=list;
    
    list=nd;
    
    memset(list->block,'\0',size);
    
    idx=0;
    
  }
  
  // append in current block
  
  strcpy(&list->block[idx],s);
  
  idx+=len+1;
  
  entries++;
  
  return &list->block[idx-len-1];
  
}


const char *strstack::pop(){
  
  if (list==0) return 0;
  
  if (idx==0){
    
    // free this block and go to next
    
    memnode *ptr=list->next;
    
    delete [] list->block;
    delete list;
    
    list=ptr;
    
    if (list==0) 
      return 0;
    else
      idx=size-1;
  }
  
  //go back to first non \0
  while (idx>0) 
    if (list->block[idx--]!='\0')
      break;
  
  //go back to first \0
  while (idx>0) 
    if (list->block[idx--]=='\0')
      break;
  
  entries--;
  
  if (list->block[idx+1]=='\0')
  {
    idx+=2;
    memset(&list->block[idx],'\0',size-idx);
    return &list->block[idx];
  }
  else{
    idx=0;
    memset(&list->block[idx],'\0',size);
    return &list->block[0];
  }
}


const char *strstack::top(){
  
  int tidx=idx;
  memnode *tlist=list;
  
  if (tlist==0) return 0;
  
  if (idx==0){
    
    tlist=tlist->next;
    
    if (tlist==0) return 0;
    
    tidx=size-1;
  }
  
  //go back to first non \0
  while (tidx>0) 
    if (tlist->block[tidx--]!='\0')
      break;
  
  //aaa\0bbb\0\0\0\0
  
  //go back to first \0
  while (tidx>0) 
    if (tlist->block[tidx--]=='\0')
      break;
  
  if (tlist->block[tidx+1]=='\0')
  {
    tidx+=2;
    return &tlist->block[tidx];
  }
  else{
    tidx=0;
    return &tlist->block[0];
  }
  
}


strstack::~strstack(){
  memnode *ptr;
  while (list !=NULL){
    ptr=list->next;    
    delete [] list->block;
    delete list;
    list=ptr;
  } 
}


storage::storage(int maxsize,int blocksize)
{
  newmemory=0;
  newcalls=0;
  setsize=maxsize;
  poolsize=blocksize; //in bytes
  poolset=new mempool* [setsize+1];
  for (int i=0;i<=setsize;i++)
    poolset[i]=NULL;
}


storage::~storage(){
  for (int i=0;i<=setsize;i++)
    if (poolset[i])
      delete poolset[i];
  delete [] poolset;
}

char *storage::allocate(int size){
  
  if (size<=setsize){
    if (!poolset[size]){
      poolset[size]=new mempool(size,poolsize/size);
    }
    return poolset[size]->allocate();
  }
  else{
    
    newmemory+=size+8;
    newcalls++;
    char* p=(char *)calloc(sizeof(char),size);
    if (p==NULL){
      cerr << "storage::alloc insufficient memory\n";
      exit(1);
    }
    return p;
  }
}

char *storage::reallocate(char *oldptr,int oldsize,int newsize){
  
  char *newptr;
  
  assert(newsize>oldsize);
  
  if (oldsize<=setsize){
    if (newsize<=setsize){
      if (!poolset[newsize])
        poolset[newsize]=new mempool(newsize,poolsize/newsize);
      newptr=poolset[newsize]->allocate();
      memset((char*)newptr,0,newsize);
    }
    else
      newptr=(char *)calloc(sizeof(char),newsize);
    
    if (oldptr && oldsize){
      memcpy(newptr,oldptr,oldsize);
      poolset[oldsize]->free(oldptr);
    }
  }
  else{
    newptr=(char *)realloc(oldptr,newsize);
    if (newptr==oldptr) 
      cerr << "r\b";
    else
      cerr << "a\b";
  }
  if (newptr==NULL){
    cerr << "storage::realloc insufficient memory\n";
    exit(1);
  }
  
  return newptr;
}

int storage::free(char *addr,int size){
  
  /*
   while(size<=setsize){
     if (poolset[size] && poolset[size]->free(addr))
       break;
     size++;
   }
   */
  
  if (size>setsize)
    return free(addr),1;
  else{
    poolset[size] && poolset[size]->free(addr);
  }
  return 1;
}


void storage::stat(){
  int used=0;
  int memory=sizeof(char *) * setsize;
  int waste=0;
  
  for (int i=0;i<=setsize;i++)
    if (poolset[i]){
      used++;
      memory+=poolset[i]->used();
      waste+=poolset[i]->wasted();
    }
      
      TRACE_ERR("storage class statistics\n"
                << "alloc entries " << newcalls 
                << " used memory " << newmemory/1024 << "Kb\n"
                << "mpools " << setsize
                << " active  " << used 
                << " used memory " << memory/1024 << "Kb"
                << " wasted " << waste/1024 << "Kb\n");
}

---