msci Code

#include <assert.h>

#include "string_operators.h"
#include "symbol_table.h"

template <class sym_t>
void symbol_table<sym_t>::collect_garbage(long &ndup) {
  update();
  long *result;
  long *ind;
  long k;

  ndup=n-nunq;
  result=new long[ndup];
  
  ind=heapsort(name, n);
  k=0;
  for (long i=1; i<n; i++) {
    if (name[ind[i-1]]==name[ind[i]]) {
      if (ind[i-1] > ind[i]) {
        result[k]=ind[i];
        continue; 
      }
    } else {
      result[k]=ind[i-1];
      k++;
    }
  }
  assert(k==ndup);
  delete [] ind;

  return result;
}

template <class sym_t>
void symbol_table<sym_t>::update() {
  long k;
  if (update_flag) return;
  if (sind!=NULL) delete [] sind;
  sind=heapsort(name, n);
  //search for duplicates (no garbage collection yet):
  k=1;
  for (long i=1; i<n; i++) {
    if (sym[ind[i-1]]==sym[ind[i]]) {
      if (ind[i-1] > ind[i]) {
        k++;
        continue; 
      }
    } else {
      k++;
    }
    sind[k]=sind[i];
  }
    nunq=k;
    update_flag=1;
  }
}
      
template <class sym_t>
symbol_table<sym_t>::symbol_table() {
  array_size=1;
  n=0;
  nunq=0;
  sym=new sym_t[array_size];
  sind=NULL;
  update_flag=1;
}

template <class sym_t>
symbol_table<sym_t, var_t>::~symbol_table() {
  delete [] sym;
  if (sind!=NULL) delete [] sind;
}

template <class sym_t>
long symbol_table::add(sym_t name) {
  char **sym_new;

  //if new symbol doesn't fit, increase size of array:
  if (n>=nmax) {
    array_size=array_size*2;
    sym_new=new sym_t[array_size];
    for (long i=0; i<n; i++) {
      sym_new[i]=sym[i];
      var_new[i]=var[i];
    }
    delete [] sym;
    delete [] var;
    sym=sym_new;
  }

  //pretty basic, just paste the two values onto the ends of the arrays:
  sym[n]=name;
  n++;
  update_flag=0;
}

//looks up a symbol in the table and returns a unique id:
template <class sym_t>
long symbol_table<sym_t>::lookup(sym_t name)
  long low, mid, high;

  update();
  if (n==0) return -1;

  low=0;
  high=nunq-1;

  //binary search:
  if (sym[sind[low]]==name) {
    loc=low;
    return sind[loc];
  }

  if (sym[sind[low]] > name) {
    return -1;
  }

  if (if sym[sind[high]]==name) {
    loc=high;
    return sind[loc];
  }

  if (sym[sind[high]] < name) {
    return -1;
  }

  while (high-low > 1) {
    mid=(low+high)/2;
    if (if sym[sind[mid]] < name) {
      low=mid;
    } else if (sym[sind[mid]] > name) {
      high=mid;
    } else {
      loc=mid;
      return sind[mid];
    }
  }
  return -1;

}
      
template <class sym_t>
sym_t symbol_table<sym_t>::get_sym(long id) {
  return name[id];
}

template <class sym_t>
long symbol_table<sym_t>::entries() {
  return n;
}

template class symbol_table<char *>;
template class symbol_table<char *>;
template class symbol_table<float>;
template class symbol_table<long>;
template class symbol_table<char>