Initial revision

1 files changed, 212 insertions, 0 deletions

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 ITEM> class CcuHashTableOf;
+template <class ITEM> class CcuDictionnaryOf;
+
+template <class ITEM> class CcuHashCellOf : public CcuHashCell {
+protected:
+inline		CcuHashCellOf (const void* k, CcuHashCellOf<ITEM>* n) : CcuHashCell (k, n)	{}
+public:
+inline	void	SetInfo (ITEM* p)			{ CcuHashCell::SetInfo (p); }
+inline	ITEM*	GetInfo () const			{ return (ITEM*) CcuHashCell::GetInfo (); }
+};
+
+template <class ITEM> class CcuHashCellRefOf : public CcuHashCellRef {
+friend	class	CcuHashTableOf<ITEM>;
+friend	class	CcuDictionnaryOf<ITEM>;
+protected:
+inline	CcuHashCellRefOf (const CcuHashTableOf<ITEM>& t, const void* key) : CcuHashCellRef (t, key)	{}
+#ifdef CPLUS_BUG1
+inline	CcuHashCellRefOf (const CcuHashCellRefOf<ITEM>& 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 ITEM> 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<ITEM>*	Add (const void* key, int* found = 0)	{ return (CcuHashCellOf<ITEM>*) CcuHashTable::Add (key, found); }
+inline	CcuHashCellOf<ITEM>*	Get (const void* key)		{ return (CcuHashCellOf<ITEM>*) CcuHashTable::Get (key); }
+inline	ITEM*	Remove (const void* key, int* found = 0)	{ return (ITEM*) CcuHashTable::Remove (key, found); }
+inline	CcuHashCellRefOf<ITEM> operator [] (const void* key) const	{ return CcuHashCellRefOf<ITEM> (*this, key); }
+};
+
+template <class ITEM> class CcuDictionnaryOf : public CcuDictionnary {
+public:
+inline		CcuDictionnaryOf (unsigned int size, HASH_F hash = 0) : CcuDictionnary (size, hash)	{}
+inline		~CcuDictionnaryOf ()	{}
+inline	CcuHashCellOf<ITEM>*	Add (const void* key, int* found = 0)	{ return (CcuHashCellOf<ITEM>*) CcuDictionnary::Add (key, found); }
+inline	CcuHashCellOf<ITEM>*	Get (const void* key)		{ return (CcuHashCellOf<ITEM>*) CcuDictionnary::Get (key); }
+inline	ITEM*	Remove (const void* key, int* found = 0)	{ return (ITEM*) CcuDictionnary::Remove (key, found); }
+inline		operator const CcuHashTableOf<ITEM>& () const	{ return *(const CcuHashTableOf<ITEM>*) this; }
+inline	CcuHashCellRefOf<ITEM> operator [] (const char* key) const	{ return CcuHashCellRefOf<ITEM> (*(const CcuHashTableOf<ITEM>*)this, key); }
+};
+
+
+template <class ITEM> class CcuHashIterOf : public CcuHashIter {
+public:
+inline		CcuHashIterOf (const CcuHashTableOf<ITEM>& t) : CcuHashIter (t) { }
+inline		~CcuHashIterOf () {}
+inline	CcuHashIterOf<ITEM>&	operator ++ ()	{ ++((CcuHashIter) (*this)); return *this; }
+inline	ITEM*	operator * () const	{ return (ITEM*) (CcuHashIter::operator  * ()); }
+};
+
+#endif	/* CPLUS_BUG19 */
+
+#endif	/* HashTable_H_ */
+