Logo Search packages:      
Sourcecode: afnix version File versions

HashTable.cpp

// ---------------------------------------------------------------------------
// - HashTable.cpp                                                           -
// - standard object library - hash table class implementation               -
// ---------------------------------------------------------------------------
// - This program is free software;  you can redistribute it  and/or  modify -
// - it provided that this copyright notice is kept intact.                  -
// -                                                                         -
// - This program  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.  In no event shall -
// - the copyright holder be liable for any  direct, indirect, incidental or -
// - special damages arising in any way out of the use of this software.     -
// ---------------------------------------------------------------------------
// - copyright (c) 1999-2007 amaury darsch                                   -
// ---------------------------------------------------------------------------

#include "Vector.hpp"
#include "Utility.hpp"
#include "Integer.hpp"
#include "Boolean.hpp"
#include "Runnable.hpp"
#include "HashTable.hpp"
#include "QuarkZone.hpp"
#include "Exception.hpp"

namespace afnix {
 
  // -------------------------------------------------------------------------
  // - private section                                                       -
  // -------------------------------------------------------------------------
   
  // the hash table bucket
  struct s_bucket {
    // the object key
    String  d_key;
    // the hash id value
    long    d_hvl;
    // the object 
    Object* p_obj;
    // next record in the list
    s_bucket* p_next;
    // simple constructor
    s_bucket (void) {
      d_hvl  = 0;
      p_obj  = nilp;
      p_next = nilp;
    }
    // simple destructor
    ~s_bucket (void) {
      Object::dref (p_obj);
      delete p_next;
    }
  };
  
  // find a bucket by key given its root bucket
  static inline s_bucket* getbucket (s_bucket* bucket, const String& key) {
    // simple check as fast as we can
    if (bucket == nilp) return nilp;
    // loop until we have a match
    while (bucket != nilp) {
      if (bucket->d_key == key) return bucket;
      bucket = bucket->p_next;
    }
    // no bucket found
    return nilp;
  }
  
  // extract a bucket by key given its root bucket . This procedure remove the
  // bucket if it is found and maintain the link list.
  static inline s_bucket* rmbucket (s_bucket** root, const String& key) {
    s_bucket* bucket = *root;
    // simple check as fast as we can
    if (bucket == nilp) return nilp;
    // first case for the root bucket
    if (bucket->d_key == key) {
      *root = bucket->p_next;
      bucket->p_next = nilp;
      return bucket;
    }
    // loop until we have a match
    while (bucket->p_next != nilp) {
      if (bucket->p_next->d_key == key) {
      s_bucket* result = bucket->p_next;
      bucket->p_next = result->p_next;
      result->p_next = nilp;
      return result;
      }
      bucket = bucket->p_next;
    } 
    // no node found
    return nilp;
  }

  // -------------------------------------------------------------------------
  // - class section                                                         -
  // -------------------------------------------------------------------------
    
  // create a new hash table
  
00100   HashTable::HashTable (void) {
    // build the array
    d_size   = Utility::toprime (0);
    d_thrs   = (d_size * 7) / 10;
    d_count  = 0;
    p_table  = new s_bucket*[d_size];
    // initialize the table with null pointers
    for (long i = 0; i < d_size; i++)
      p_table[i] = nilp;
  }
  
  // create a new hash table with a predefined size
  
00113   HashTable::HashTable (const long size) {
    // build the array - threshold at 70%
    d_size   = Utility::toprime (size);
    d_thrs   = (size * 7) / 10;
    d_count  = 0;
    p_table  = new s_bucket*[d_size];
    // initialize the table with null pointers
    for (long i = 0; i < d_size; i++)
      p_table[i] = nilp;
  }
  
  // delete this hash table 
  
00126   HashTable::~HashTable (void) {
    if (p_table != nilp) {
      for (long i = 0; i < d_size; i++) delete p_table[i];
      delete [] p_table;
    }
  }

  // return the class name

00135   String HashTable::repr (void) const {
    return "HashTable";
  }

  // make this hash table a shared object

00141   void HashTable::mksho (void) {
    if (p_shared != nilp) return;
    Object::mksho ();
    for (long i = 0; i < d_size; i++) {
      s_bucket* bucket = p_table[i];
      while (bucket != nilp) {
      Object* obj = bucket->p_obj;
      if (obj != nilp) obj->mksho ();
      bucket = bucket->p_next;
      }
    }
  }

  // reset this hash table
  
00156   void HashTable::reset (void) {
    wrlock ();
    if (p_table != nilp) {
      for (long i = 0; i < d_size; i++) {
      delete p_table[i];
      p_table[i] = nilp;
      }
    }
    d_count = 0;
    unlock ();
  }  

  // get the number of elements

00170   long HashTable::length (void) const {
    rdlock ();
    long result = d_count;
    unlock ();
    return result;
  }

  // return true if the table is empty

00179   bool HashTable::empty (void) const {
    rdlock ();
    bool result = (d_count == 0);
    unlock ();
    return result;
  }

  // get the element key by index

00188   String HashTable::getkey (const long index) const {
    rdlock ();
    long npos = 0;
    for (long i = 0; i < d_size; i++) {
      s_bucket* bucket = p_table[i];
      while (bucket != nilp) {
      if (npos == index) {
        String result = bucket->d_key;
        unlock ();
        return result;
      }
      npos++;
      bucket = bucket->p_next;
      }
    }
    unlock ();
    throw Exception ("index-error", "index is out of range");
  }

  // get the element object by index

00209   Object* HashTable::getobj (const long index) const {
    rdlock ();
    try {
      long npos = 0;
      for (long i = 0; i < d_size; i++) {
      s_bucket* bucket = p_table[i];
      while (bucket != nilp) {
        if (npos == index) {
          Object* result = bucket->p_obj;
          unlock ();
          return result;
        }
        npos++;
        bucket = bucket->p_next;
      }
      }
      throw Exception ("index-error", "index is out of range");
    } catch (...) {
      unlock ();
      throw;
    }
  }

  // set or create an object in this table
  
00234   void HashTable::add (const String& key, Object* object) {
    wrlock ();
    try {
      // protect the object
      Object::iref (object);
      // compute the hash value
      long hvl = key.hashid ();
      long hid = hvl % d_size;
      // look for existing symbol
      s_bucket* bucket = getbucket (p_table[hid],key);
      if (bucket != nilp) {
      Object::dref (bucket->p_obj);
      bucket->p_obj = object;
      unlock ();
      return;
      }
      // the bucket does not exist, create it 
      bucket           = new s_bucket;
      bucket->d_key  = key;
      bucket->d_hvl  = hvl;
      bucket->p_obj  = object;
      bucket->p_next = p_table[hid];
      p_table[hid]   = bucket;
      if (++d_count > d_thrs) resize (Utility::toprime (d_size + 1));
      unlock ();
    } catch (...) {
      unlock ();
      throw;
    }
  }
  
  // get an object by key. If the key is not found, nilp is returned
  
00267   Object* HashTable::get (const String& key) const {
    rdlock ();
    try {
      // compute hash id
      long hid = key.hashid () % d_size;
      // look for the node and find symbol
      s_bucket* bucket = getbucket (p_table[hid],key);
      Object* result = (bucket == nilp) ? nilp : bucket->p_obj;
      unlock ();
      return result;
    } catch (...) {
      unlock ();
      throw;
    }
  }

  // get an object by key. If the key is not found an exception is raised

00285   Object* HashTable::lookup (const String& key) const {
    rdlock ();
    try {
      // compute hash id
      long hid = key.hashid () % d_size;
      // look for the node and find symbol
      s_bucket* bucket = getbucket (p_table[hid],key);
      if (bucket != nilp) {
      Object* result = bucket->p_obj;
      unlock ();
      return result;
      }
      throw Exception ("key-error", "key not found", key);
    } catch (...) {
      unlock ();
      throw;
    }
  }
  
  // return true if a key exists in this table

00306   bool HashTable::exists (const String& key) const {
    rdlock ();
    try {
      // compute hash id
      long hid = key.hashid () % d_size;
      // look for the node and find symbol
      s_bucket* bucket = getbucket (p_table[hid],key);
      bool result = (bucket != nilp) ? true : false;
      unlock ();
      return result;
    } catch (...) {
      unlock ();
      throw;
    }
  }
  
  // remove an object by key. 
  
00324   void HashTable::remove (const String& key) {
    wrlock ();
    try {
      // compute hash id
      long hid = key.hashid () % d_size;   
      // extract the bucket
      s_bucket* bucket = rmbucket (&p_table[hid],key);
      delete bucket;
      d_count--;
      unlock ();
    } catch (...) {
      unlock ();
      throw;
    }
  }

  // return a vector of objects in this hash table

00342   Vector* HashTable::getvobj (void) const {
    rdlock ();
    try {
      Vector* result = new Vector;
      rdlock ();
      for (long i = 0; i < d_size; i++) {
      s_bucket* bucket = p_table[i];
      while (bucket != nilp) {
        Object* obj = bucket->p_obj;
        if (obj != nilp) result->append (obj);
        bucket = bucket->p_next;
      }
      }
      unlock ();
      return result;
    } catch (...) {
      unlock ();
      throw;
    }
  }

  // resize the hash table by creating a new one
  
00365   void HashTable::resize (const long size) {
    wrlock ();
    try {
      // check for the size
      if (size < d_size) return;
      // initialize the new table
      s_bucket** table = new s_bucket*[size];
      for (long i = 0; i < size; i++) table[i] = nilp;
      // rebuild the table
      for (long i = 0; i < d_size; i++) {
      s_bucket* bucket = p_table[i];
      while (bucket != nilp) {
        s_bucket* next = bucket->p_next;
        bucket->p_next = nilp;
        long hid = bucket->d_hvl  % size;
        bucket->p_next = table[hid];
        table[hid]     = bucket;
        bucket = next;
      }
      }
      // clean the old table
      delete [] p_table;
      // restore the new table
      d_size  = size;
      d_thrs  = (d_size * 7) / 10;
      p_table = table;
      // done
      unlock ();
    } catch (...) {
      unlock ();
      throw;
    }
  }

  // -------------------------------------------------------------------------
  // - object section                                                        -
  // -------------------------------------------------------------------------

  // the quark zone
  static const long QUARK_ZONE_LENGTH = 10;
  static QuarkZone  zone (QUARK_ZONE_LENGTH);

  // the object supported quarks
  static const long QUARK_ADD    = zone.intern ("add");
  static const long QUARK_GET    = zone.intern ("get");
  static const long QUARK_RESET  = zone.intern ("reset");
  static const long QUARK_LENGTH = zone.intern ("length");
  static const long QUARK_LOOKUP = zone.intern ("lookup");
  static const long QUARK_REMOVE = zone.intern ("remove");
  static const long QUARK_EXISTP = zone.intern ("exists-p");
  static const long QUARK_EMPTYP = zone.intern ("empty-p");
  static const long QUARK_GETKEY = zone.intern ("get-key");
  static const long QUARK_GETOBJ = zone.intern ("get-object");

  // create a new object in a generic way

00421   Object* HashTable::mknew (Vector* argv) {
    // get tne number of arguments
    long argc = (argv == nilp) ? 0 : argv->length ();
    // check 0 argument
    if (argc == 0) return new HashTable;
    // check 1 argument
    if (argc == 1) {
      long size = argv->getint (0);
      return new HashTable (size);
    }
    throw Exception ("argument-error", "too many argument for hash table");
  }

  // return true if the given quark is defined

00436   bool HashTable::isquark (const long quark, const bool hflg) const {
    rdlock ();
    if (zone.exists (quark) == true) {
      unlock ();
      return true;
    }
    bool result = hflg ? Object::isquark (quark, hflg) : false;
    unlock ();
    return result;
  }
  
  // apply this object with a set of arguments and a quark
  
00449   Object* HashTable::apply (Runnable* robj, Nameset* nset, const long quark,
                      Vector* argv) {
    // get the number of arguments
    long argc = (argv == nilp) ? 0 : argv->length ();

    // dispatch 0 argument
    if (argc == 0) {
      if (quark == QUARK_EMPTYP) return new Boolean (empty  ());
      if (quark == QUARK_LENGTH) return new Integer (length ());
      if (quark == QUARK_RESET) {
      reset ();
      return nilp;
      }
    }
    // dispatch 1 argument
    if (argc == 1) {
      if (quark == QUARK_EXISTP) {
      String key = argv->getstring (0);
      return new Boolean (exists (key));
      }
      if (quark == QUARK_GET) {
      String key = argv->getstring (0);
      rdlock();
      try {
        Object* result = get (key);
        robj->post (result);
        unlock ();          
        return result;
      } catch (...) {
        unlock ();
        throw;
      }
      }
      if (quark == QUARK_LOOKUP) {
      String key = argv->getstring (0);
      rdlock();
      try {
        Object* result = lookup (key);
        robj->post (result);
        unlock ();          
        return result;
      } catch (...) {
        unlock ();
        throw;
      }
      }
      if (quark == QUARK_GETKEY) {
      long index = argv->getint (0);
      return new String (getkey (index));
      }
      if (quark == QUARK_GETOBJ) {
      long index = argv->getint (0);
      rdlock();
      try {
        Object* result = getobj (index);
        robj->post (result);
        unlock ();          
        return result;
      } catch (...) {
        unlock ();
        throw;
      }
      }
      if (quark == QUARK_REMOVE) {
      String key = argv->getstring (0);
      remove (key);
      return nilp;
      }
    }
    // dispatch 2 arguments
    if (argc == 2) {
      if (quark == QUARK_ADD) {
      String  key = argv->getstring (0);
      Object* obj  = argv->get (1);
      add (key, obj);
      return nilp;
      }
    }
    // call the object method
    return Object::apply (robj, nset, quark, argv);
  }
}

Generated by  Doxygen 1.6.0   Back to index