116ed1e1dSAxel Dörfler/*
216ed1e1dSAxel Dörfler * Copyright 2005, Haiku.
316ed1e1dSAxel Dörfler * Distributed under the terms of the MIT License.
416ed1e1dSAxel Dörfler *
516ed1e1dSAxel Dörfler * Authors:
616ed1e1dSAxel Dörfler *		Axel D��rfler, axeld@pinc-software.de
716ed1e1dSAxel Dörfler */
816ed1e1dSAxel Dörfler#ifndef _HASH_TABLE_H_
916ed1e1dSAxel Dörfler#define _HASH_TABLE_H_
1016ed1e1dSAxel Dörfler
1116ed1e1dSAxel Dörfler
1216ed1e1dSAxel Dörfler#include <SupportDefs.h>
1316ed1e1dSAxel Dörfler
1416ed1e1dSAxel Dörfler
1516ed1e1dSAxel Dörflerclass Hashable {
1616ed1e1dSAxel Dörfler	public:
1734bd8bf5SJérôme Duval		virtual ~Hashable() {};
1816ed1e1dSAxel Dörfler		virtual uint32 Hash() const = 0;
1916ed1e1dSAxel Dörfler		virtual bool CompareTo(Hashable& hashable) const = 0;
2016ed1e1dSAxel Dörfler};
2116ed1e1dSAxel Dörfler
2216ed1e1dSAxel Dörflerclass HashTable {
2316ed1e1dSAxel Dörfler	public:
2416ed1e1dSAxel Dörfler		HashTable(bool owning = false, int32 capacity = 100, float loadFactor = 0.75);
2516ed1e1dSAxel Dörfler		~HashTable();
2616ed1e1dSAxel Dörfler
2716ed1e1dSAxel Dörfler		void MakeEmpty(bool deleteValues = true);
2816ed1e1dSAxel Dörfler		bool IsEmpty() const { return fCount == 0; }
2916ed1e1dSAxel Dörfler		bool ContainsKey(Hashable& key) const { return _GetHashEntry(key) != NULL; }
3016ed1e1dSAxel Dörfler		int32 CountItems() const { return fCount; }
3116ed1e1dSAxel Dörfler
3216ed1e1dSAxel Dörfler		Hashable *GetValue(Hashable& key) const;
3316ed1e1dSAxel Dörfler
3416ed1e1dSAxel Dörfler		bool AddItem(Hashable* value);
3516ed1e1dSAxel Dörfler		Hashable *RemoveItem(Hashable& key);
3616ed1e1dSAxel Dörfler
3716ed1e1dSAxel Dörfler	protected:
3816ed1e1dSAxel Dörfler		struct entry;
3916ed1e1dSAxel Dörfler
4016ed1e1dSAxel Dörfler		bool _Rehash();
4116ed1e1dSAxel Dörfler		entry *_GetHashEntry(Hashable& key) const;
4216ed1e1dSAxel Dörfler
4316ed1e1dSAxel Dörfler		entry**	fTable;
4416ed1e1dSAxel Dörfler		int32	fCapacity, fCount, fThreshold;
4516ed1e1dSAxel Dörfler		float	fLoadFactor;
4616ed1e1dSAxel Dörfler		bool	fOwning;
4716ed1e1dSAxel Dörfler};
4816ed1e1dSAxel Dörfler
4916ed1e1dSAxel Dörfler#endif  /* HASHTABLE_H */
50