hash-tab.cc

可以在ns-2中进行仿真的SPIN路由协议的源码

#include <stdlib.h>
#include <string.h>
#include <mit/rca/meta/hash-tab.h>

int hashstring(char *string);

#define MAXKEY 20
#define MAXELEMENT 30

BucketList::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_;
}