hrev53968 adds 1 changeset to branch 'master'
old head: 910651da23313caed7fdbe0f9e4fedb0a3d60f8e
new head: 8eaf4427f0ed46dd7ffc2e1b62cc0cfa0274b298
overview:
https://git.haiku-os.org/haiku/log/?qt=range&q=8eaf4427f0ed+%5E910651da2331
----------------------------------------------------------------------------
8eaf4427f0ed: Tracker: Refactor IconCache to use BOpenHashTable.
This removes the last usage of the old OpenTracker OpenHashTable,
and so it can now be removed.
Change-Id: I7a7bceef1d3fc74c7fdfa7b079e53576452703dc
Reviewed-on: https://review.haiku-os.org/c/haiku/+/2339
Reviewed-by: waddlesplash <waddlesplash@xxxxxxxxx>
Reviewed-by: John Scipione <jscipione@xxxxxxxxx>
Reviewed-by: Adrien Destugues <pulkomandy@xxxxxxxxx>
[ Augustin Cavalier <waddlesplash@xxxxxxxxx> ]
----------------------------------------------------------------------------
Revision: hrev53968
Commit: 8eaf4427f0ed46dd7ffc2e1b62cc0cfa0274b298
URL: https://git.haiku-os.org/haiku/commit/?id=8eaf4427f0ed
Author: Augustin Cavalier <waddlesplash@xxxxxxxxx>
Date: Wed Mar 11 23:52:46 2020 UTC
Committer: waddlesplash <waddlesplash@xxxxxxxxx>
Commit-Date: Fri Mar 13 12:39:43 2020 UTC
----------------------------------------------------------------------------
3 files changed, 121 insertions(+), 767 deletions(-)
src/kits/tracker/IconCache.cpp | 258 ++++--------------
src/kits/tracker/IconCache.h | 116 ++++----
src/kits/tracker/OpenHashTable.h | 514 -----------------------------------
----------------------------------------------------------------------------
diff --git a/src/kits/tracker/IconCache.cpp b/src/kits/tracker/IconCache.cpp
index 26d9d0bbc8..7b871138c1 100644
--- a/src/kits/tracker/IconCache.cpp
+++ b/src/kits/tracker/IconCache.cpp
@@ -107,14 +107,14 @@ IconCacheEntry::IconCacheEntry()
fHighlightedLargeIcon(NULL),
fMiniIcon(NULL),
fHighlightedMiniIcon(NULL),
- fAliasForIndex(-1)
+ fAliasTo(NULL)
{
}
IconCacheEntry::~IconCacheEntry()
{
- if (fAliasForIndex < 0) {
+ if (fAliasTo == NULL) {
delete fLargeIcon;
delete fHighlightedLargeIcon;
delete fMiniIcon;
@@ -126,7 +126,7 @@ IconCacheEntry::~IconCacheEntry()
fMiniIcon = NULL;
fHighlightedMiniIcon = NULL;
}
- fAliasForIndex = -1;
+ fAliasTo = NULL;
}
@@ -427,7 +427,7 @@ IconCache::GetIconFromMetaMime(const char* fileType,
IconDrawMode mode,
PRINT_ADD_ITEM(
("File %s; Line %d # adding entry as
alias for type %s\n",
__FILE__, __LINE__, fileType));
- entry = fSharedCache.AddItem(&aliasTo,
fileType);
+ entry = fSharedCache.AddItem(fileType);
entry->SetAliasFor(&fSharedCache, aliasTo);
}
ASSERT(aliasTo->HaveIconBitmap(mode, size));
@@ -531,8 +531,7 @@ IconCache::GetIconFromFileTypes(ModelNodeLazyOpener*
modelOpener,
"preferredApp %s, type %s\n",
__FILE__, __LINE__, nodePreferredApp,
fileType));
IconCacheEntry* aliasedEntry
- =
fSharedCache.AddItem((SharedCacheEntry**)&entry, fileType,
- nodePreferredApp);
+ = fSharedCache.AddItem(fileType,
nodePreferredApp);
aliasedEntry->SetAliasFor(&fSharedCache,
(SharedCacheEntry*)entry);
// OK to cast here, have a runtime check
@@ -840,8 +839,7 @@ IconCache::GetGenericIcon(AutoLock<SimpleIconCache>*
sharedCacheLocker,
__FILE__, __LINE__, model->PreferredAppSignature(),
model->MimeType()));
IconCacheEntry* aliasedEntry = fSharedCache.AddItem(
- (SharedCacheEntry**)&entry, model->MimeType(),
- model->PreferredAppSignature());
+ model->MimeType(), model->PreferredAppSignature());
aliasedEntry->SetAliasFor(&fSharedCache, (SharedCacheEntry*)entry);
source = kMetaMime;
@@ -1223,10 +1221,9 @@ IconCache::IconChanged(const char* mimeType, const char*
appSignature)
entry = (SharedCacheEntry*)fSharedCache.ResolveIfAlias(entry);
ASSERT(entry != NULL);
- int32 index = fSharedCache.EntryIndex(entry);
- fNodeCache.RemoveAliasesTo(index);
- fSharedCache.RemoveAliasesTo(index);
+ fNodeCache.RemoveAliasesTo(entry);
+ fSharedCache.RemoveAliasesTo(entry);
fSharedCache.IconChanged(entry);
}
@@ -1398,24 +1395,13 @@ IconCacheEntry::RetireIcons(BObjectList<BBitmap>*
retiredBitmapList)
// #pragma mark - SharedIconCache
-// In debug mode keep the hash table sizes small so that they grow a lot and
-// execercise the resizing code a lot. In release mode allocate them large
-// up-front for better performance
SharedIconCache::SharedIconCache()
:
-#if DEBUG
- SimpleIconCache("Shared icon cache aka \"The Dead-Locker\""),
- fElementArray(20),
- fHashTable(20),
- fRetiredBitmaps(20, true)
-#else
SimpleIconCache("Tracker shared icon cache"),
- fElementArray(1024),
- fHashTable(1000),
+ fHashTable(),
fRetiredBitmaps(256, true)
-#endif
{
- fHashTable.SetElementVector(&fElementArray);
+ fHashTable.Init(256);
}
@@ -1445,62 +1431,24 @@ SharedIconCache::FindItem(const char* fileType,
if (!fileType)
fileType = B_FILE_MIMETYPE;
- SharedCacheEntry* result
- = fHashTable.FindFirst(SharedCacheEntry::Hash(fileType,
- appSignature));
-
- if (result == NULL)
- return NULL;
-
- for(;;) {
- if (result->fFileType == fileType
- && result->fAppSignature == appSignature) {
- return result;
- }
-
- if (result->fNext < 0)
- break;
-
- result = const_cast<SharedCacheEntry*>(&fElementArray.At(
- result->fNext));
- }
-
- return NULL;
-}
-
-
-SharedCacheEntry*
-SharedIconCache::AddItem(const char* fileType, const char* appSignature)
-{
- ASSERT(fileType != NULL);
- if (fileType == NULL)
- fileType = B_FILE_MIMETYPE;
-
- SharedCacheEntry* result =
fHashTable.Add(SharedCacheEntry::Hash(fileType,
+ return fHashTable.Lookup(SharedCacheEntry::TypeAndSignature(fileType,
appSignature));
- result->SetTo(fileType, appSignature);
-
- return result;
}
SharedCacheEntry*
-SharedIconCache::AddItem(SharedCacheEntry** outstandingEntry,
- const char* fileType, const char* appSignature)
+SharedIconCache::AddItem(const char* fileType, const char* appSignature)
{
- int32 entryToken = fHashTable.ElementIndex(*outstandingEntry);
- ASSERT(entryToken >= 0);
-
ASSERT(fileType != NULL);
if (fileType == NULL)
fileType = B_FILE_MIMETYPE;
- SharedCacheEntry* result =
fHashTable.Add(SharedCacheEntry::Hash(fileType,
- appSignature));
- result->SetTo(fileType, appSignature);
- *outstandingEntry = fHashTable.ElementAt(entryToken);
+ SharedCacheEntry* entry = new SharedCacheEntry(fileType, appSignature);
+ if (fHashTable.Insert(entry) == B_OK)
+ return entry;
- return result;
+ delete entry;
+ return NULL;
}
@@ -1516,13 +1464,13 @@ SharedIconCache::IconChanged(SharedCacheEntry* entry)
void
-SharedIconCache::RemoveAliasesTo(int32 aliasIndex)
+SharedIconCache::RemoveAliasesTo(SharedCacheEntry* alias)
{
- int32 count = fHashTable.VectorSize();
- for (int32 index = 0; index < count; index++) {
- SharedCacheEntry* entry = fHashTable.ElementAt(index);
- if (entry->fAliasForIndex == aliasIndex)
- fHashTable.Remove(entry);
+ EntryHashTable::Iterator it = fHashTable.GetIterator();
+ while (it.HasNext()) {
+ SharedCacheEntry* entry = it.Next();
+ if (entry->fAliasTo == alias)
+ fHashTable.RemoveUnchecked(entry);
}
}
@@ -1531,13 +1479,13 @@ void
SharedIconCache::SetAliasFor(IconCacheEntry* entry,
const SharedCacheEntry* original) const
{
- entry->fAliasForIndex = fHashTable.ElementIndex(original);
+ entry->fAliasTo = original;
}
SharedCacheEntry::SharedCacheEntry()
:
- fNext(-1)
+ fNext(NULL)
{
}
@@ -1545,7 +1493,7 @@ SharedCacheEntry::SharedCacheEntry()
SharedCacheEntry::SharedCacheEntry(const char* fileType,
const char* appSignature)
:
- fNext(-1),
+ fNext(NULL),
fFileType(fileType),
fAppSignature(appSignature)
{
@@ -1591,55 +1539,30 @@ SharedCacheEntry::Draw(BView* view, BPoint where,
IconDrawMode mode,
}
-uint32
-SharedCacheEntry::Hash(const char* fileType, const char* appSignature)
+/* static */ size_t
+SharedCacheEntry::Hash(const TypeAndSignature& typeAndSignature)
{
- uint32 hash = HashString(fileType, 0);
- if (appSignature != NULL && *appSignature != '\0')
- hash = HashString(appSignature, hash);
+ size_t hash = HashString(typeAndSignature.type, 0);
+ if (typeAndSignature.signature != NULL
+ && *typeAndSignature.signature != '\0')
+ hash = HashString(typeAndSignature.signature, hash);
return hash;
}
-uint32
+size_t
SharedCacheEntry::Hash() const
{
- uint32 hash = HashString(fFileType.String(), 0);
- if (fAppSignature.Length() > 0)
- hash = HashString(fAppSignature.String(), hash);
-
- return hash;
+ return Hash(TypeAndSignature(fFileType.String(),
fAppSignature.String()));
}
bool
-SharedCacheEntry::operator==(const SharedCacheEntry &entry) const
+SharedCacheEntry::operator==(const TypeAndSignature& typeAndSignature) const
{
- return fFileType == entry.FileType()
- && fAppSignature == entry.AppSignature();
-}
-
-
-void
-SharedCacheEntry::SetTo(const char* fileType, const char* appSignature)
-{
- fFileType = fileType;
- fAppSignature = appSignature;
-}
-
-
-SharedCacheEntryArray::SharedCacheEntryArray(int32 initialSize)
- :
- OpenHashElementArray<SharedCacheEntry>(initialSize)
-{
-}
-
-
-SharedCacheEntry*
-SharedCacheEntryArray::Add()
-{
- return OpenHashElementArray<SharedCacheEntry>::Add();
+ return fFileType == typeAndSignature.type
+ && fAppSignature == typeAndSignature.signature;
}
@@ -1648,7 +1571,7 @@ SharedCacheEntryArray::Add()
NodeCacheEntry::NodeCacheEntry(bool permanent)
:
- fNext(-1),
+ fNext(NULL),
fPermanent(permanent)
{
}
@@ -1656,7 +1579,7 @@ NodeCacheEntry::NodeCacheEntry(bool permanent)
NodeCacheEntry::NodeCacheEntry(const node_ref* node, bool permanent)
:
- fNext(-1),
+ fNext(NULL),
fRef(*node),
fPermanent(permanent)
{
@@ -1712,14 +1635,14 @@ NodeCacheEntry::Node() const
}
-uint32
+size_t
NodeCacheEntry::Hash() const
{
return Hash(&fRef);
}
-uint32
+/* static */ size_t
NodeCacheEntry::Hash(const node_ref* node)
{
return node->device ^ ((uint32*)&node->node)[0]
@@ -1728,16 +1651,9 @@ NodeCacheEntry::Hash(const node_ref* node)
bool
-NodeCacheEntry::operator==(const NodeCacheEntry &entry) const
-{
- return fRef == entry.fRef;
-}
-
-
-void
-NodeCacheEntry::SetTo(const node_ref* node)
+NodeCacheEntry::operator==(const node_ref* node) const
{
- fRef = *node;
+ return fRef == *node;
}
@@ -1748,29 +1664,14 @@ NodeCacheEntry::Permanent() const
}
-void
-NodeCacheEntry::MakePermanent()
-{
- fPermanent = true;
-}
-
-
// #pragma mark - NodeIconCache
NodeIconCache::NodeIconCache()
:
-#if DEBUG
- SimpleIconCache("Node icon cache aka \"The Dead-Locker\""),
- fElementArray(20),
- fHashTable(20)
-#else
- SimpleIconCache("Tracker node icon cache"),
- fElementArray(100),
- fHashTable(100)
-#endif
+ SimpleIconCache("Tracker node icon cache")
{
- fHashTable.SetElementVector(&fElementArray);
+ fHashTable.Init(100);
}
@@ -1795,47 +1696,19 @@ NodeIconCache::Draw(IconCacheEntry* entry, BView* view,
BPoint where,
NodeCacheEntry*
NodeIconCache::FindItem(const node_ref* node) const
{
- NodeCacheEntry* entry =
fHashTable.FindFirst(NodeCacheEntry::Hash(node));
- if (entry == NULL)
- return NULL;
-
- for(;;) {
- if (*entry->Node() == *node)
- return entry;
-
- if (entry->fNext < 0)
- break;
-
- entry =
const_cast<NodeCacheEntry*>(&fElementArray.At(entry->fNext));
- }
-
- return NULL;
+ return fHashTable.Lookup(node);
}
NodeCacheEntry*
NodeIconCache::AddItem(const node_ref* node, bool permanent)
{
- NodeCacheEntry* entry = fHashTable.Add(NodeCacheEntry::Hash(node));
- entry->SetTo(node);
- if (permanent)
- entry->MakePermanent();
-
- return entry;
-}
-
-
-NodeCacheEntry*
-NodeIconCache::AddItem(NodeCacheEntry** outstandingEntry,
- const node_ref* node)
-{
- int32 entryToken = fHashTable.ElementIndex(*outstandingEntry);
-
- NodeCacheEntry* entry = fHashTable.Add(NodeCacheEntry::Hash(node));
- entry->SetTo(node);
- *outstandingEntry = fHashTable.ElementAt(entryToken);
+ NodeCacheEntry* entry = new NodeCacheEntry(node, permanent);
+ if (fHashTable.Insert(entry) == B_OK)
+ return entry;
- return entry;
+ delete entry;
+ return NULL;
}
@@ -1880,34 +1753,17 @@ NodeIconCache::IconChanged(const Model* model)
void
-NodeIconCache::RemoveAliasesTo(int32 aliasIndex)
+NodeIconCache::RemoveAliasesTo(SharedCacheEntry* alias)
{
- int32 count = fHashTable.VectorSize();
- for (int32 index = 0; index < count; index++) {
- NodeCacheEntry* entry = fHashTable.ElementAt(index);
- if (entry->fAliasForIndex == aliasIndex)
- fHashTable.Remove(entry);
+ EntryHashTable::Iterator it = fHashTable.GetIterator();
+ while (it.HasNext()) {
+ NodeCacheEntry* entry = it.Next();
+ if (entry->fAliasTo == alias)
+ fHashTable.RemoveUnchecked(entry);
}
}
-// #pragma mark - NodeCacheEntryArray
-
-
-NodeCacheEntryArray::NodeCacheEntryArray(int32 initialSize)
- :
- OpenHashElementArray<NodeCacheEntry>(initialSize)
-{
-}
-
-
-NodeCacheEntry*
-NodeCacheEntryArray::Add()
-{
- return OpenHashElementArray<NodeCacheEntry>::Add();
-}
-
-
// #pragma mark - SimpleIconCache
diff --git a/src/kits/tracker/IconCache.h b/src/kits/tracker/IconCache.h
index e14f3fb2e0..2273c586a3 100644
--- a/src/kits/tracker/IconCache.h
+++ b/src/kits/tracker/IconCache.h
@@ -45,7 +45,7 @@ All rights reserved.
#include <String.h>
#include "AutoLock.h"
-#include "OpenHashTable.h"
+#include "HashSet.h"
#include "Utilities.h"
@@ -115,6 +115,33 @@ enum IconSource {
};
+template<typename Class>
+struct SelfHashing {
+ typedef typename Class::HashKeyType KeyType;
+ typedef Class ValueType;
+
+ size_t HashKey(KeyType key) const
+ {
+ return Class::Hash(key);
+ }
+
+ size_t Hash(ValueType* value) const
+ {
+ return value->Hash();
+ }
+
+ bool Compare(KeyType key, ValueType* value) const
+ {
+ return *value == key;
+ }
+
+ ValueType*& GetLink(ValueType* value) const
+ {
+ return value->HashNext();
+ }
+};
+
+
class IconCacheEntry {
// aliased entries don't own their icons, just point
// to some other entry that does
@@ -168,7 +195,8 @@ protected:
BBitmap* fHighlightedLargeIcon;
BBitmap* fMiniIcon;
BBitmap* fHighlightedMiniIcon;
- int32 fAliasForIndex;
+
+ const IconCacheEntry* fAliasTo;
// list of other icon kinds would be added here
@@ -211,14 +239,23 @@ public:
const char* FileType() const;
const char* AppSignature() const;
+public:
// hash table support
- uint32 Hash() const;
- static uint32 Hash(const char* fileType, const char* appSignature = 0);
- bool operator==(const SharedCacheEntry &) const;
- void SetTo(const char* fileType, const char* appSignature = 0);
+ struct TypeAndSignature {
+ const char* type, *signature;
+ TypeAndSignature(const char* t, const char* s)
+ : type(t), signature(s) {}
+ };
+ typedef TypeAndSignature HashKeyType;
+ static size_t Hash(const TypeAndSignature& typeAndSignature);
+
+ size_t Hash() const;
+ SharedCacheEntry*& HashNext() { return fNext; }
+ bool operator==(const TypeAndSignature& typeAndSignature) const;
- int32 fNext;
private:
+ SharedCacheEntry* fNext;
+
BString fFileType;
BString fAppSignature;
@@ -226,14 +263,6 @@ private:
};
-class SharedCacheEntryArray : public OpenHashElementArray<SharedCacheEntry> {
- // SharedIconCache stores all it's elements in this array
-public:
- SharedCacheEntryArray(int32 initialSize);
- SharedCacheEntry* Add();
-};
-
-
class SharedIconCache : public SimpleIconCache {
// SharedIconCache is used for icons that come from the mime database
public:
@@ -248,22 +277,18 @@ public:
const char* appSignature = 0) const;
SharedCacheEntry* AddItem(const char* fileType,
const char* appSignature = 0);
- SharedCacheEntry* AddItem(SharedCacheEntry** outstandingEntry,
- const char* fileType, const char* appSignature = 0);
- // same as previous AddItem, updates the pointer to
outstandingEntry,
- // because adding to the hash table makes any pending pointer
invalid
void IconChanged(SharedCacheEntry*);
void SetAliasFor(IconCacheEntry* entry,
const SharedCacheEntry* original) const;
IconCacheEntry* ResolveIfAlias(IconCacheEntry* entry) const;
- int32 EntryIndex(const SharedCacheEntry* entry) const;
- void RemoveAliasesTo(int32 index);
+ void RemoveAliasesTo(SharedCacheEntry* alias);
private:
- SharedCacheEntryArray fElementArray;
- OpenHashTable<SharedCacheEntry, SharedCacheEntryArray> fHashTable;
+ typedef BOpenHashTable<SelfHashing<SharedCacheEntry> > EntryHashTable;
+ EntryHashTable fHashTable;
+
BObjectList<BBitmap> fRetiredBitmaps;
// icons are drawn asynchronously, can't just delete them right
away,
// instead have to place them onto the retired bitmap list and
wait
@@ -283,15 +308,20 @@ public:
const node_ref* Node() const;
- uint32 Hash() const;
- static uint32 Hash(const node_ref*);
- bool operator==(const NodeCacheEntry&) const;
- void SetTo(const node_ref*);
- void MakePermanent();
bool Permanent() const;
- int32 fNext;
+public:
+ // hash table support
+ typedef const node_ref* HashKeyType;
+ static size_t Hash(const node_ref* node);
+
+ size_t Hash() const;
+ NodeCacheEntry*& HashNext() { return fNext; }
+ bool operator==(const node_ref* ref) const;
+
private:
+ NodeCacheEntry* fNext;
+
node_ref fRef;
bool fPermanent;
// special cache entry that has to be deleted explicitly
@@ -300,14 +330,6 @@ private:
};
-class NodeCacheEntryArray : public OpenHashElementArray<NodeCacheEntry> {
- // NodeIconCache stores all it's elements in this array
-public:
- NodeCacheEntryArray(int32 initialSize);
- NodeCacheEntry* Add();
-};
-
-
class NodeIconCache : public SimpleIconCache {
// NodeIconCache is used for nodes that define their own icons
public:
@@ -321,10 +343,6 @@ public:
NodeCacheEntry* FindItem(const node_ref*) const;
NodeCacheEntry* AddItem(const node_ref*, bool permanent = false);
- NodeCacheEntry* AddItem(NodeCacheEntry** outstandingEntry,
- const node_ref*);
- // same as previous AddItem, updates the pointer to
outstandingEntry,
- // because adding to the hash table makes any pending pointer
invalid
void Deleting(const node_ref*);
// model for this node is getting deleted
// (not necessarily the node itself)
@@ -333,11 +351,11 @@ public:
void Deleting(const BView*);
void IconChanged(const Model*);
- void RemoveAliasesTo(int32 index);
+ void RemoveAliasesTo(SharedCacheEntry* alias);
private:
- NodeCacheEntryArray fElementArray;
- OpenHashTable<NodeCacheEntry, NodeCacheEntryArray> fHashTable;
+ typedef BOpenHashTable<SelfHashing<NodeCacheEntry> > EntryHashTable;
+ EntryHashTable fHashTable;
};
@@ -507,19 +525,13 @@ IconCache::NeedsDeletionNotification(IconSource from)
inline IconCacheEntry*
SharedIconCache::ResolveIfAlias(IconCacheEntry* entry) const
{
- if (entry->fAliasForIndex < 0)
+ if (entry->fAliasTo == NULL)
return entry;
- return fHashTable.ElementAt(entry->fAliasForIndex);
+ return const_cast<IconCacheEntry*>(entry->fAliasTo);
}
-inline int32
-SharedIconCache::EntryIndex(const SharedCacheEntry* entry) const
-{
- return fHashTable.ElementIndex(entry);
-}
-
} // namespace BPrivate
using namespace BPrivate;
diff --git a/src/kits/tracker/OpenHashTable.h b/src/kits/tracker/OpenHashTable.h
deleted file mode 100644
index d7cfb3f467..0000000000
--- a/src/kits/tracker/OpenHashTable.h
+++ /dev/null
@@ -1,514 +0,0 @@
-/*
-Open Tracker License
-
-Terms and Conditions
-
-Copyright (c) 1991-2000, Be Incorporated. All rights reserved.
-
-Permission is hereby granted, free of charge, to any person obtaining a copy of
-this software and associated documentation files (the "Software"), to deal in
-the Software without restriction, including without limitation the rights to
-use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
-of the Software, and to permit persons to whom the Software is furnished to do
-so, subject to the following conditions:
-
-The above copyright notice and this permission notice applies to all licensees
-and shall be included in all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF TITLE, MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
-BE INCORPORATED BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
-AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF, OR IN
CONNECTION
-WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-
-Except as contained in this notice, the name of Be Incorporated shall not be
-used in advertising or otherwise to promote the sale, use or other dealings in
-this Software without prior written authorization from Be Incorporated.
-
-Tracker(TM), Be(R), BeOS(R), and BeIA(TM) are trademarks or registered
trademarks
-of Be Incorporated in the United States and other countries. Other brand
product
-names are registered trademarks or trademarks of their respective holders.
-All rights reserved.
-*/
-
-// bonefish:
-// * removed need for exceptions
-// * fixed warnings
-// * implemented rehashing
-// * added RemoveAll()
-// TODO:
-// * shrinking of element vectors
-
-// Hash table with open addresssing
-
-#ifndef __OPEN_HASH_TABLE__
-#define __OPEN_HASH_TABLE__
-
-#include <stdlib.h>
-#include <new>
-
-// don't include <Debug.h>
-#ifndef _OPEN_HASH_TABLE_ASSERT
-# define _OPEN_HASH_TABLE_ASSERT(E) (void)0
-#endif
-#ifndef _OPEN_HASH_TABLE_TRESPASS
-# define _OPEN_HASH_TABLE_TRESPASS() (void)0
-#endif
-
-namespace BPrivate {
-
-template <class Element>
-class ElementVector {
- // element vector for OpenHashTable needs to implement this
- // interface
-public:
- Element &At(int32 index);
- Element *Add();
- int32 IndexOf(const Element &) const;
- void Remove(int32 index);
-};
-
-class OpenHashElement {
-public:
- uint32 Hash() const;
- bool operator==(const OpenHashElement &) const;
- void Adopt(OpenHashElement &);
- // low overhead copy, original element is in undefined state
- // after call (calls Adopt on BString members, etc.)
- int32 fNext;
-};
-
-const uint32 kPrimes [] = {
- 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139,
- 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393,
67108859,
- 134217689, 268435399, 536870909, 1073741789, 2147483647, 0
-};
-
-template <class Element, class ElementVec = ElementVector<Element> >
-class OpenHashTable {
-public:
- OpenHashTable(int32 minSize, ElementVec *elementVector = 0,
- float maxLoadFactor = 0.8);
- // it is up to the subclass of OpenHashTable to supply
- // elementVector
- ~OpenHashTable();
-
- bool InitCheck() const;
-
- void SetElementVector(ElementVec *elementVector);
-
- Element *FindFirst(uint32 elementHash) const;
- Element *Add(uint32 elementHash);
-
- void Remove(Element *element, bool dontRehash = false);
- void RemoveAll();
-
- // when calling Add, any outstanding element pointer may become
- // invalid; to deal with this, get the element index and restore
- // it after the add
- int32 ElementIndex(const Element *) const;
- Element *ElementAt(int32 index) const;
-
- int32 ArraySize() const;
- int32 VectorSize() const;
- int32 CountElements() const;
-
-protected:
- static int32 OptimalSize(int32 minSize);
-
-private:
- bool _RehashIfNeeded();
- bool _Rehash();
-
- int32 fArraySize;
- int32 fInitialSize;
- int32 fElementCount;
- int32 *fHashArray;
- ElementVec *fElementVector;
- float fMaxLoadFactor;
-};
-
-template <class Element>
-class OpenHashElementArray : public ElementVector<Element> {
- // this is a straightforward implementation of an element vector
- // deleting is handled by linking deleted elements into a free list
- // the vector never shrinks
-public:
- OpenHashElementArray(int32 initialSize);
- ~OpenHashElementArray();
-
- bool InitCheck() const;
-
- Element &At(int32 index);
- const Element &At(int32 index) const;
- Element *Add(const Element &);
- Element *Add();
- void Remove(int32 index);
- int32 IndexOf(const Element &) const;
- int32 Size() const;
-
-private:
- Element *fData;
- int32 fSize;
- int32 fNextFree;
- int32 fNextDeleted;
-};
-
-
-//-----------------------------------
-
-template<class Element, class ElementVec>
-OpenHashTable<Element, ElementVec>::OpenHashTable(int32 minSize,
- ElementVec *elementVector, float maxLoadFactor)
- : fArraySize(OptimalSize(minSize)),
- fInitialSize(fArraySize),
- fElementCount(0),
- fElementVector(elementVector),
- fMaxLoadFactor(maxLoadFactor)
-{
- // sanity check the maximal load factor
- if (fMaxLoadFactor < 0.5)
- fMaxLoadFactor = 0.5;
- // allocate and init the array
- fHashArray = (int32*)calloc(fArraySize, sizeof(int32));
- if (fHashArray) {
- for (int32 index = 0; index < fArraySize; index++)
- fHashArray[index] = -1;
- }
-}
-
-template<class Element, class ElementVec>
-OpenHashTable<Element, ElementVec>::~OpenHashTable()
-{
- RemoveAll();
- free(fHashArray);
-}
-
-template<class Element, class ElementVec>
-bool
-OpenHashTable<Element, ElementVec>::InitCheck() const
-{
- return (fHashArray && fElementVector);
-}
-
-template<class Element, class ElementVec>
-int32
-OpenHashTable<Element, ElementVec>::OptimalSize(int32 minSize)
-{
- for (int32 index = 0; ; index++)
- if (!kPrimes[index] || kPrimes[index] >= (uint32)minSize)
- return (int32)kPrimes[index];
-
- return 0;
-}
-
-template<class Element, class ElementVec>
-Element *
-OpenHashTable<Element, ElementVec>::FindFirst(uint32 hash) const
-{
- _OPEN_HASH_TABLE_ASSERT(fElementVector);
- hash %= fArraySize;
- if (fHashArray[hash] < 0)
- return 0;
-
- return &fElementVector->At(fHashArray[hash]);
-}
-
-template<class Element, class ElementVec>
-int32
-OpenHashTable<Element, ElementVec>::ElementIndex(const Element *element) const
-{
- return fElementVector->IndexOf(*element);
-}
-
-template<class Element, class ElementVec>
-Element *
-OpenHashTable<Element, ElementVec>::ElementAt(int32 index) const
-{
- return &fElementVector->At(index);
-}
-
-template<class Element, class ElementVec>
-int32
-OpenHashTable<Element, ElementVec>::ArraySize() const
-{
- return fArraySize;
-}
-
-template<class Element, class ElementVec>
-int32
-OpenHashTable<Element, ElementVec>::VectorSize() const
-{
- return fElementVector->Size();
-}
-
-template<class Element, class ElementVec>
-int32
-OpenHashTable<Element, ElementVec>::CountElements() const
-{
- return fElementCount;
-}
-
-
-template<class Element, class ElementVec>
-Element *
-OpenHashTable<Element, ElementVec>::Add(uint32 hash)
-{
- _OPEN_HASH_TABLE_ASSERT(fElementVector);
- _RehashIfNeeded();
- hash %= fArraySize;
- Element *result = fElementVector->Add();
- if (result) {
- result->fNext = fHashArray[hash];
- fHashArray[hash] = fElementVector->IndexOf(*result);
- fElementCount++;
- }
- return result;
-}
-
-template<class Element, class ElementVec>
-void
-OpenHashTable<Element, ElementVec>::Remove(Element *element, bool dontRehash)
-{
- if (!dontRehash)
- _RehashIfNeeded();
- uint32 hash = element->Hash() % fArraySize;
- int32 next = fHashArray[hash];
- _OPEN_HASH_TABLE_ASSERT(next >= 0);
-
- if (&fElementVector->At(next) == element) {
- fHashArray[hash] = element->fNext;
- fElementVector->Remove(next);
- fElementCount--;
- return;
- }
-
- for (int32 index = next; index >= 0; ) {
- // look for an existing match in table
- next = fElementVector->At(index).fNext;
- if (next < 0) {
- _OPEN_HASH_TABLE_TRESPASS();
- return;
- }
-
- if (&fElementVector->At(next) == element) {
- fElementVector->At(index).fNext = element->fNext;
- fElementVector->Remove(next);
- fElementCount--;
- return;
- }
- index = next;
- }
-}
-
-template<class Element, class ElementVec>
-void
-OpenHashTable<Element, ElementVec>::RemoveAll()
-{
- for (int32 i = 0; fElementCount > 0 && i < fArraySize; i++) {
- int32 index = fHashArray[i];
- while (index >= 0) {
- Element* element = &fElementVector->At(index);
- int32 next = element->fNext;
- fElementVector->Remove(index);
- fElementCount--;
- index = next;
- }
- fHashArray[i] = -1;
- }
- _RehashIfNeeded();
-}
-
-template<class Element, class ElementVec>
-void
-OpenHashTable<Element, ElementVec>::SetElementVector(ElementVec *elementVector)
-{
- fElementVector = elementVector;
-}
-
-// _RehashIfNeeded
-template<class Element, class ElementVec>
-bool
-OpenHashTable<Element, ElementVec>::_RehashIfNeeded()
-{
- // The load factor range [fMaxLoadFactor / 3, fMaxLoadFactor] is fine,
- // I think. After rehashing the load factor will be about
- // fMaxLoadFactor * 2 / 3, respectively fMaxLoadFactor / 2.
- float loadFactor = (float)fElementCount / (float)fArraySize;
- if (loadFactor > fMaxLoadFactor
- || (fArraySize > fInitialSize && loadFactor < fMaxLoadFactor /
3)) {
- return _Rehash();
- }
- return true;
-}
-
-// _Rehash
-template<class Element, class ElementVec>
-bool
-OpenHashTable<Element, ElementVec>::_Rehash()
-{
- bool result = true;
- int32 newSize = int32(fElementCount * 1.73 * fMaxLoadFactor);
- newSize = (fInitialSize > newSize ? fInitialSize : newSize);
- if (newSize != fArraySize) {
- // allocate a new array
- int32 *newHashArray = (int32*)calloc(newSize, sizeof(int32));
- if (newHashArray) {
- // init the new hash array
- for (int32 index = 0; index < newSize; index++)
- newHashArray[index] = -1;
- // iterate through all elements and put them into the
new
- // hash array
- for (int i = 0; i < fArraySize; i++) {
- int32 index = fHashArray[i];
- while (index >= 0) {
- // insert the element in the new array
- Element &element =
fElementVector->At(index);
- int32 next = element.fNext;
- uint32 hash = (element.Hash() %
newSize);
- element.fNext = newHashArray[hash];
- newHashArray[hash] = index;
- // next element in old list
- index = next;
- }
- }
- // delete the old array and set the new one
- free(fHashArray);
- fHashArray = newHashArray;
- fArraySize = newSize;
- } else
- result = false;
- }
- return result;
-}
-
-
-template<class Element>
-OpenHashElementArray<Element>::OpenHashElementArray(int32 initialSize)
- : fSize(initialSize),
- fNextFree(0),
- fNextDeleted(-1)
-{
- fData = (Element*)calloc((size_t)initialSize, sizeof(Element));
-}
-
-template<class Element>
-OpenHashElementArray<Element>::~OpenHashElementArray()
-{
- free(fData);
-}
-
-template<class Element>
-bool
-OpenHashElementArray<Element>::InitCheck() const
-{
- return fData;
-}
-
-template<class Element>
-Element &
-OpenHashElementArray<Element>::At(int32 index)
-{
- _OPEN_HASH_TABLE_ASSERT(index < fSize);
- return fData[index];
-}
-
-template<class Element>
-const Element &
-OpenHashElementArray<Element>::At(int32 index) const
-{
- _OPEN_HASH_TABLE_ASSERT(index < fSize);
- return fData[index];
-}
-
-template<class Element>
-int32
-OpenHashElementArray<Element>::IndexOf(const Element &element) const
-{
- int32 result = &element - fData;
- if (result < 0 || result > fSize)
- return -1;
-
- return result;
-}
-
-template<class Element>
-int32
-OpenHashElementArray<Element>::Size() const
-{
- return fSize;
-}
-
-
-template<class Element>
-Element *
-OpenHashElementArray<Element>::Add(const Element &newElement)
-{
- Element *element = Add();
- if (element)
- element->Adopt(newElement);
- return element;
-}
-
-#if DEBUG
-const int32 kGrowChunk = 10;
-#else
-const int32 kGrowChunk = 1024;
-#endif
-
-template<class Element>
-Element *
-OpenHashElementArray<Element>::Add()
-{
- int32 index = fNextFree;
- if (fNextDeleted >= 0) {
- index = fNextDeleted;
- fNextDeleted = At(index).fNext;
- } else if (fNextFree >= fSize - 1) {
- int32 newSize = fSize + kGrowChunk;
-/*
- Element *newData = (Element *)calloc((size_t)newSize ,
sizeof(Element));
- if (!newData)
- return NULL;
- memcpy(newData, fData, fSize * sizeof(Element));
- free(fData);
-*/
- Element *newData = (Element*)realloc((void*)fData,
- (size_t)newSize * sizeof(Element));
- if (!newData)
- return NULL;
-
- fData = newData;
- fSize = newSize;
- index = fNextFree;
- fNextFree++;
- } else
- fNextFree++;
-
- new (&At(index)) Element;
- // call placement new to initialize the element properly
- _OPEN_HASH_TABLE_ASSERT(At(index).fNext == -1);
-
- return &At(index);
-}
-
-template<class Element>
-void
-OpenHashElementArray<Element>::Remove(int32 index)
-{
- // delete by chaining empty elements in a single linked
- // list, reusing the next field
- _OPEN_HASH_TABLE_ASSERT(index < fSize);
- At(index).~Element();
- // call the destructor explicitly to destroy the element
- // properly
- At(index).fNext = fNextDeleted;
- fNextDeleted = index;
-}
-
-} // namespace BPrivate
-
-using BPrivate::OpenHashTable;
-
-#endif // __OPEN_HASH_TABLE__
