source: src/lib/symtab.cc @ e0cd003

#include "symtab.h"
#include <limits> // numeric_limits
#include <cstdio>
#include <cstdlib>
//---------------------------------------------------------------------------
using namespace UTT;
SymbolTable::SymbolTable(int n, int (*h)(const char*,int), const char* filename)
             : _mx(n), _cnt(0), hash(h)
{
  _sz=first(n);
  _key=new char*[_sz];
  _defind=new int[_sz];
  _hashind=new int[_sz];
  _def=new char*[_mx];
  for(int i=0; i<_sz; i++) _key[i]=NULL;
  if(filename)
    add_from_file(filename);
}

//---------------------------------------------------------------------------

SymbolTable::SymbolTable(int n, const char* filename)
             : _mx(n), _cnt(0), hash(hash1)
{
  _sz=first(n);
  _key=new char*[_sz];
  _defind=new int[_sz];
  _hashind=new int[_sz];
  _def=new char*[_mx];
  for(int i=0; i<_sz; ++i) _key[i]=NULL;
  if(filename)
    add_from_file(filename);
}

//---------------------------------------------------------------------------

SymbolTable::~SymbolTable()
{
  clear();
  delete[] _key;
  delete[] _defind;
  delete[] _hashind;
  delete[] _def;
}

//---------------------------------------------------------------------------

void SymbolTable::clear()
{
  for(int i=0; i<_sz; ++i)
    if(_key[i])
      free(_key[i]);
}

//---------------------------------------------------------------------------

bool SymbolTable::add_from_file(const char* filename)
{
  FILE* in=fopen(filename,"r");
  char buf[MAXKEYLEN+1];

  if(in)
    while(fscanf(in,"%s",buf)==1)
    {
      if(strlen(buf)==MAXKEYLEN || add(buf)<0)
        return false;
    }
  return true;
}

//---------------------------------------------------------------------------

int SymbolTable::add(const char* s)
{
  if(_cnt<_mx)
  {
    int ind=hash(s,_sz);
    while(_key[ind])
      if(strcmp(_key[ind],s))
        ind=++ind%_sz;
      else
        return _defind[ind];
    _key[ind]=strdup(s);
    _defind[ind]=_cnt;
    _hashind[_cnt]=ind;
    _def[_cnt]=_key[ind];
    _cnt++;
    return _cnt-1;
  }
  else
    return -1;
}

//---------------------------------------------------------------------------

int SymbolTable::operator[](const char* s)
{
  int ind=hash(s,_sz);
  while(_key[ind])
    if(strcmp(_key[ind],s)==0)
      return _defind[ind];
    else
      ind=++ind % _sz;
  return -1;
}

//---------------------------------------------------------------------------

int SymbolTable::first(unsigned int n)
{
  int fi=n;
  int bound=(n/2 < MAXKEYLEN)? n/2 : MAXKEYLEN;
  bool found;
  do
  {
    found=true;
    if(fi++ == std::numeric_limits<int>::max) return -1;
    for(int i=2; i<bound; i++)
      if(fi%i==0) { found=false; break; }
  } while(!found);
  return fi;
}

float SymbolTable::search_rate()
{
  long s=0;
  for(int i=0; i<_sz; i++)
    if(_key[i])
      s+=(i+_sz-hash(_key[i],_sz))%_sz+1;
  return _cnt ? (float)s/(float)_cnt : 0;
}

//---------------------------------------------------------------------------

int hash1(const char* s, int _sz)
{
  int l=strlen(s);
  if(l>=4)
    return abs((*((int*)(s+(l/2-2)))+(int)(*s * s[l-1])) % _sz);
  else
  {
    int i=0;
    strcpy((char*)&i,s);
    return abs((i+(int)(*s * s[l-1])) % _sz);
  }
}

//---------------------------------------------------------------------------

int hash2(const char* s, int _sz)
{
  int l=strlen(s);
  if(l>=6)
  {
    unsigned int i1,i2,i3;
    strncpy((char*)&i1,s,sizeof(int));
    strncpy((char*)&i2,s+(l/2-2),sizeof(int));
    strncpy((char*)&i3,s+(l-4),sizeof(int));
    return abs((i1+i2+i3) % _sz);
  }
  else
  {
    int i=0;
    strncpy((char*)&i,s,sizeof(int));
    return abs((i+(int)(*s * s[l-1])) % _sz);
  }
}

//---------------------------------------------------------------------------