irstlm/src/htable.h

Go to the documentation of this file.

// $Id: htable.h 383 2010-04-23 15:29:28Z 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

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

#ifndef MF_HTABLE_H
#define MF_HTABLE_H

#include <iostream>

#define Prime1                 37
#define Prime2                 1048583
#define BlockSize              100


// Fast arithmetic, relying on powers of 2,
// and on pre-processor concatenation property

typedef struct ENTRY{
  char*                 key;
  ENTRY*                next;  // secret from user
}entry;

typedef unsigned int address;

typedef enum {HT_FIND,    
              HT_ENTER,   
              HT_INIT,    
              HT_CONT     
} HT_ACTION;

typedef enum {
        STR,     
              STRPTR,   
        INT,     
        INTPTR  
}HTYPE;


class htable {
  int        size;            
  int      keylen;            
  HTYPE     htype;            
  entry   **table;            
  int      scan_i;            
  entry   *scan_p;            
  // statistics
  long       keys;            
  long   accesses;            
  long collisions;            

  mempool  *memory;           

  size_t (*keylenfunc)(const char*);          
  address (*hashfunc)(const char*);               
  int (*compfunc)(const char*, const char*);   
  
 public:

  htable(int n,int kl=0,HTYPE ht=STRPTR,size_t (*klf)(const char* )=NULL);

  ~htable();

  address Hash(char *key){
    switch (htype){
      case INT:case INTPTR: return HashInt(key);
        break;
      case STR:case STRPTR: return HashStr(key);
    }
    return 0; //should never happen
  }
  address HashInt(char *key);
  address HashStr(char *key);  
  
  int Comp(char *Key1,char *Key2){
    switch (htype){
      case INT:case INTPTR: return CompInt(Key1,Key2);
        break;
      case STR:case STRPTR: return CompStr(Key1,Key2);
    }    
    return 0; // should never happen
  }

  int CompInt(char *Key1,char *Key2);
  int CompStr(char *Key1,char *Key2);
  
  char *search(char *item, HT_ACTION action);

  char *scan(HT_ACTION action);

  void stat();
  
  void map(std::ostream& co=std::cout, int cols=80);

  int used(){
        return size * sizeof(entry **) + memory->used();
  }
};



#endif

---