1/* 2 * Copyright 2005, Haiku. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Axel D��rfler, axeld@pinc-software.de 7 */ 8#ifndef _HASH_TABLE_H_ 9#define _HASH_TABLE_H_ 10 11 12#include <SupportDefs.h> 13 14 15class Hashable { 16 public: 17 virtual ~Hashable() {}; 18 virtual uint32 Hash() const = 0; 19 virtual bool CompareTo(Hashable& hashable) const = 0; 20}; 21 22class HashTable { 23 public: 24 HashTable(bool owning = false, int32 capacity = 100, float loadFactor = 0.75); 25 ~HashTable(); 26 27 void MakeEmpty(bool deleteValues = true); 28 bool IsEmpty() const { return fCount == 0; } 29 bool ContainsKey(Hashable& key) const { return _GetHashEntry(key) != NULL; } 30 int32 CountItems() const { return fCount; } 31 32 Hashable *GetValue(Hashable& key) const; 33 34 bool AddItem(Hashable* value); 35 Hashable *RemoveItem(Hashable& key); 36 37 protected: 38 struct entry; 39 40 bool _Rehash(); 41 entry *_GetHashEntry(Hashable& key) const; 42 43 entry** fTable; 44 int32 fCapacity, fCount, fThreshold; 45 float fLoadFactor; 46 bool fOwning; 47}; 48 49#endif /* HASHTABLE_H */ 50