Hash.h

00001 /*
00002 File: Hash.h
00003 
00004 Function: Defines a string-based hash table
00005 
00006 Author: Andrew Willmott
00007 
00008 Copyright: 
00009 */
00010 
00011 #ifndef __Hash__
00012 #define __Hash__
00013 
00014 #include "cl/String.h"
00015 #include "cl/Array.h"
00016 
00017  class HashEntry
00018 {
00019 public:
00020  Char *key;
00021  ULong hash;
00022  Void *data;
00023 };
00024 
00025  class HashIter
00026 {
00027 public:
00028 virtual Void ProcessVoidItem(StrConst s, Void *data) = 0;
00029 };
00030 
00031  class Hash
00032 {
00033 public:
00034 Hash(Int n = 0);
00035 
00036 Void SetVoidItem(StrConst s, Void *data);
00037  Void *GetVoidItem(StrConst s)
00038 {
00039 HashEntry *he = Find(s);
00040 if (he && he->key)
00041 return(he->data);
00042 else
00043 return(0);
00044 };
00045  Bool ItemExists(StrConst s)
00046 { 
00047 HashEntry *he = Find(s);
00048 return(he && he->data);
00049 };
00050 
00051 Void DeleteItem(StrConst s);
00052 // delete item s
00053 Void Iterate(HashIter &iter);
00054 // iterate over all keys
00055 
00056 // low-level functions
00057 
00058 HashEntry *Find(StrConst s);
00059 // returns the entry corresponding to the key if it exists,
00060 // or a new entry if not. if the latter, you must set the
00061 // key field to indicate it's being used.
00062 // returns 0 if we ran out of memory.
00063 Int Init(Int n);
00064 // (re)initialises table, assuming max of n entries
00065 // returns the number of entries in the new table
00066 
00067 // delete s's entry
00068 virtual Void FreeData(Void *data);
00069 
00070 Void FreeKey(Char *key);
00071 Void FreeTable();
00072 
00073 ULong CalcHash(StrConst s);
00074 
00075 protected:
00076 
00077  Array<HashEntry> table;
00078  Int numDeleted;
00079  Bool copyKey;
00080 };
00081 
00082 // This is here both as an example, and the most commonly used hash.
00083 // For any data-specific hash, you will need to override FreeData() to
00084 // correctly dispose of the data (if necessary), and will probably
00085 // want to create your own SetItem/GetItem methods as below.
00086 
00087  class IntHash : public Hash
00088 {
00089 public:
00090  Void SetItem(StrConst s, Int a)
00091 { SetVoidItem(s, (Void *) (a + 1)); };
00092 
00093  Int GetItem(StrConst s) 
00094 { return(((SAddrInt) GetVoidItem(s)) - 1); };
00095 
00096  Void FreeData(Void *data)
00097 {};
00098 };
00099 
00100  class IntHashIter : public HashIter
00101 {
00102 public:
00103 virtual Void ProcessItem(StrConst s, Int a) = 0;
00104  virtual Void ProcessVoidItem(StrConst s, Void *data)
00105 { ProcessItem(s, ((SAddrInt) data) - 1); };
00106 };
00107 
00108 #endif