From 3a4838bed13b767132cbdf06364b2658da6cc356 Mon Sep 17 00:00:00 2001 From: chatty Date: Tue, 15 Dec 1992 10:55:33 +0000 Subject: Initial revision --- utils/HashTable.h | 212 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 212 insertions(+) create mode 100644 utils/HashTable.h (limited to 'utils/HashTable.h') diff --git a/utils/HashTable.h b/utils/HashTable.h new file mode 100644 index 0000000..798d7c9 --- /dev/null +++ b/utils/HashTable.h @@ -0,0 +1,212 @@ +/* + * CENA C++ Utilities + * + * by Stephane Chatty + * + * Copyright 1991, 1992 + * Laboratoire de Recherche en Informatique (LRI) + * Centre d'Etudes de la Navigation Aerienne (CENA) + * + * plain and generic hash tables and dictionnaries + * (Original C version by Michel Beaudouin-Lafon) + * + * $Id$ + * $CurLog$ + */ + +#ifndef HashTable_H_ +#define HashTable_H_ + + +#include "cplus_bugs.h" + +class CcuAllocator; + +typedef void CcuHashItem; + +class CcuHashCell { +protected: +friend class CcuHashTable; +friend class CcuHashCellIter; +static CcuAllocator* HashCellMem; +static void ClassInit (); + + const void* Key; /* hash key */ + CcuHashItem* Info; /* data */ + CcuHashCell* Next; /* synonyms */ + +inline CcuHashCell (const void* k, CcuHashCell* n) : Key (k), Info (0), Next (n) {} + +public: +inline void SetInfo (CcuHashItem* p) { Info = p; } +inline CcuHashItem* GetInfo () const { return Info; } +inline const void* GetKey () const { return Key; } + + void* operator new (unsigned int); + void operator delete (void*); +}; + +class CcuHashCellRef { +friend class CcuHashTable; +protected: + const CcuHashTable& Table; + const void* Key; +inline CcuHashCellRef (const CcuHashTable& t, const void* key) : Table (t), Key (key) {} +#ifdef CPLUS_BUG1 +inline CcuHashCellRef (const CcuHashCellRef& t) : Table (t.Table), Key (t.Key) {} +#endif +public: + CcuHashItem* operator = (CcuHashItem*); + operator CcuHashItem* (); +}; + + +typedef int (*HASH_F) (const void*, int); +typedef int (*HCMP_F) (const void*, const void*); +typedef void* (*HCP_F) (const void*); +typedef void (*HDEL_F) (const void*); + +class CcuHashTable { +private: +friend class CcuHashCellIter; +friend class CcuHashCellRef; + +protected : + CcuHashCell** Table; + unsigned int Size; + HASH_F Hash; + HCP_F Copy; + HDEL_F Delete; + HCMP_F Compare; + + CcuHashCell** HashKey (const void*) const; + CcuHashCell* FindCell (CcuHashCell**, const void*) const; + CcuHashCell* AddCell (CcuHashCell**, const void*) const; + +public: + CcuHashTable (unsigned int, HASH_F = 0, HCP_F = 0, HDEL_F = 0, HCMP_F = 0); + CcuHashTable (const CcuHashTable&); + ~CcuHashTable (); + CcuHashCell* Add (const void*, int* = 0); + CcuHashCell* Get (const void*); + CcuHashItem* Remove (const void*, int* = 0); + void Clear (); + void Resize (int); +inline int GetSize () const { return Size; } + CcuHashCellRef operator [] (const void*) const; + +#ifdef TUNE + void HashStats (int fd = 2); + void CollStats (int fd = 2); +#endif +}; + +class CcuDictionnary : public CcuHashTable { +protected: +static void* CopyKey (const void*); +static void DeleteKey (void*); +static int CompareKey (const void*, const void*); +static int HashKey (const void*, int); + +public: + CcuDictionnary (int size, HASH_F = 0); + ~CcuDictionnary (); + + void KeyCopy (int); +}; + + +class CcuHashCellIter { +public: + enum hashiter_status { Normal, StartOfTable, EndOfTable, BadTable }; + +protected: + const CcuHashTable& TheTable; + int CurIndex; + CcuHashCell* CurCell; + +public: +inline CcuHashCellIter (const CcuHashTable& t) : TheTable (t) { CurIndex = -1; CurCell = 0; } +inline ~CcuHashCellIter () {} + +inline void Reset () { CurCell = 0; CurIndex = -1; } + CcuHashCellIter& operator ++ (); +#ifndef CPLUS_BUG16 + CcuHashCellIter operator ++ (int); +#endif +inline CcuHashCell* operator * () const { return CurCell; } + hashiter_status Status () const; +inline operator int () const { return CurCell != 0; } +}; + +class CcuHashIter : public CcuHashCellIter { +public: +inline CcuHashIter (const CcuHashTable& t) : CcuHashCellIter (t) { } +inline ~CcuHashIter () {} + +inline CcuHashIter& operator ++ () { ++((CcuHashCellIter) (*this)); return *this; } +inline CcuHashItem* operator * () const { return CurCell ? CurCell->GetInfo () : 0; } +}; + +#ifndef CPLUS_BUG19 + +template class CcuHashTableOf; +template class CcuDictionnaryOf; + +template class CcuHashCellOf : public CcuHashCell { +protected: +inline CcuHashCellOf (const void* k, CcuHashCellOf* n) : CcuHashCell (k, n) {} +public: +inline void SetInfo (ITEM* p) { CcuHashCell::SetInfo (p); } +inline ITEM* GetInfo () const { return (ITEM*) CcuHashCell::GetInfo (); } +}; + +template class CcuHashCellRefOf : public CcuHashCellRef { +friend class CcuHashTableOf; +friend class CcuDictionnaryOf; +protected: +inline CcuHashCellRefOf (const CcuHashTableOf& t, const void* key) : CcuHashCellRef (t, key) {} +#ifdef CPLUS_BUG1 +inline CcuHashCellRefOf (const CcuHashCellRefOf& t) : CcuHashCellRef (t) {} +#endif +public: +inline ITEM* operator = (ITEM* it) { return (ITEM*) (CcuHashCellRef::operator = (it)); } +inline operator ITEM* () { return (ITEM*) (CcuHashCellRef::operator CcuHashItem* ()); } +}; + + +template class CcuHashTableOf : public CcuHashTable { +public: +inline CcuHashTableOf (unsigned int size, HASH_F hash = 0, HCP_F cp = 0, HDEL_F del = 0, HCMP_F cmp= 0) + : CcuHashTable (size, hash, cp, del, cmp) {} +inline ~CcuHashTableOf () {} +inline CcuHashCellOf* Add (const void* key, int* found = 0) { return (CcuHashCellOf*) CcuHashTable::Add (key, found); } +inline CcuHashCellOf* Get (const void* key) { return (CcuHashCellOf*) CcuHashTable::Get (key); } +inline ITEM* Remove (const void* key, int* found = 0) { return (ITEM*) CcuHashTable::Remove (key, found); } +inline CcuHashCellRefOf operator [] (const void* key) const { return CcuHashCellRefOf (*this, key); } +}; + +template class CcuDictionnaryOf : public CcuDictionnary { +public: +inline CcuDictionnaryOf (unsigned int size, HASH_F hash = 0) : CcuDictionnary (size, hash) {} +inline ~CcuDictionnaryOf () {} +inline CcuHashCellOf* Add (const void* key, int* found = 0) { return (CcuHashCellOf*) CcuDictionnary::Add (key, found); } +inline CcuHashCellOf* Get (const void* key) { return (CcuHashCellOf*) CcuDictionnary::Get (key); } +inline ITEM* Remove (const void* key, int* found = 0) { return (ITEM*) CcuDictionnary::Remove (key, found); } +inline operator const CcuHashTableOf& () const { return *(const CcuHashTableOf*) this; } +inline CcuHashCellRefOf operator [] (const char* key) const { return CcuHashCellRefOf (*(const CcuHashTableOf*)this, key); } +}; + + +template class CcuHashIterOf : public CcuHashIter { +public: +inline CcuHashIterOf (const CcuHashTableOf& t) : CcuHashIter (t) { } +inline ~CcuHashIterOf () {} +inline CcuHashIterOf& operator ++ () { ++((CcuHashIter) (*this)); return *this; } +inline ITEM* operator * () const { return (ITEM*) (CcuHashIter::operator * ()); } +}; + +#endif /* CPLUS_BUG19 */ + +#endif /* HashTable_H_ */ + -- cgit v1.1