#include <stdlib.h>#include <string.h>#include <mit/rca/meta/hash-tab.h>int hashstring(char *string);#define MAXKEY 20#define MAXELEMENT 30BucketList::BucketList(char *key){  next_ = NULL;  key_ = new char[strlen(key)+1];  element_ = NULL;  strcpy(key_,key);}BucketList::~BucketList(){  delete key_;  if (element_ != NULL)    {      delete element_;    }  return;}void BucketList::DeleteList(){  BucketList *p = next_;    if (p != NULL)    {      p->DeleteList();    }  delete this;  return;}BucketList *BucketList::Lookup(char *key){  BucketList *p;  for(p = this ; p != NULL ; p = p->next_)    {      if (strcmp(p->key_, key) == 0)	{	  return p;	}    }    return NULL;}int BucketList::Length(){  BucketList *p;  int i = 0;  for(p = this ; p != NULL ; p = p->next_)    {      i++;    }    return i;}BucketList *BucketList::Delete(char *key){  BucketList *next;  BucketList *last;  BucketList *first = this;  for(last = first ; last != NULL ; last = last->next_)    {      next = last->next_;            if ((next != NULL) && (strcmp(next->key_ , key) == 0))	{	  last->next_ = next->next_;	  delete next;	  	  return first;	}    }  if (strcmp(this->key_,key) == 0)    {      delete this;      first = NULL;    }  return first;}static class HashTabClass : public TclClass {public:  HashTabClass() : TclClass("HashTable") {}  TclObject* create(int, const char*const*) {    return (new HashTab);  }} class_HashTab;HashTab::HashTab(int buckets = DEFAULT_BUCKETS){  htab_ = new BucketList*[buckets];  buckets_ = buckets;  elements_ = 0;  if (htab_ != NULL)    memset(htab_, '\0', sizeof(BucketList *) * buckets_);}HashTab::~HashTab(){  register i;  BucketList *p;  for (i = 0; i < buckets_; i++) {    p = htab_[i];    if (p != NULL)      {	p->DeleteList();      }  }  delete htab_;}BucketList *HashTab::LookupInsertNotFound(char *key, char *element){  int intkey = hashstring(key);  int index = intkey % buckets_;    BucketList *p = htab_[index];  p = p->Lookup(key);  if (p != NULL)    {      return p;    }  p = new BucketList(key);  p->next_ = htab_[index];  if( element != NULL)    {      p->element_ = new char[strlen(element)+1];      strcpy(p->element_,element);    }  htab_[index] = p;  elements_++;  return p;}BucketList *HashTab::Lookup(char *key){  int intkey = hashstring(key);  int index = intkey % buckets_;    BucketList *p = htab_[index];  if (p == NULL)    {      return NULL;    }  p = p->Lookup(key);  return p;}void HashTab::Delete(char *key){  int intkey = hashstring(key);  int index = intkey % buckets_;  BucketList *p = htab_[index];  if (p == NULL)    {      return;    }  int oldlistsize = p->Length();  BucketList *newp = p->Delete(key);  htab_[index] = newp;  int newsize = newp->Length();  int delta = oldlistsize - newsize ;  elements_ = elements_ - delta;  return;}int hashstring(char *string){  if (string == NULL)    {      return 0;    }  char firstchar = string[0];  return (int) firstchar;}char *HashTab::FindElement(char *key){  BucketList *p = Lookup(key);  if ((p == NULL) || (p->element_ == NULL))    {      return NULL;    }  return p->element_;}