[haiku-commits] haiku: hrev53440 - src/add-ons/kernel/file_systems/ramfs

  • From: waddlesplash <waddlesplash@xxxxxxxxx>
  • To: haiku-commits@xxxxxxxxxxxxx
  • Date: Sat, 31 Aug 2019 12:28:32 -0400 (EDT)

hrev53440 adds 4 changesets to branch 'master'
old head: b4e2eff2f63a9d4370194b28cdc1e58d22120487
new head: 91c8637753340bead59f87865c4a4f510b41c095
overview: 
https://git.haiku-os.org/haiku/log/?qt=range&q=91c863775334+%5Eb4e2eff2f63a

----------------------------------------------------------------------------

565c58a52717: ramfs: Adapt NodeTable to use BOpenHashTable.

019d327dce8b: ramfs: Just use the linked list for attributes instead of a hash 
table.
  
  This is what packagefs does; so if it's performant enough for packagefs,
  it's performant enough for us. Greatly simplifies this code (and will
  allow for further simplification of the NodeChildHash.)

e58322127037: ramfs: Replace the NodeChildTable with a DirectoryEntryTable.
  
  Now that Attributes don't use a table, we can replace the generic
  system with a specific DirectoryEntryTable, upgrading to BOpenHashTable
  in the process.

91c863775334: ramfs: Drop OpenTracker OpenHashTable and the custom AreaUtils.
  
  Following removal of NodeChildTable, they aren't used.

                              [ Augustin Cavalier <waddlesplash@xxxxxxxxx> ]

----------------------------------------------------------------------------

15 files changed, 189 insertions(+), 1037 deletions(-)
.../kernel/file_systems/ramfs/AllocationInfo.cpp |  23 -
.../kernel/file_systems/ramfs/AllocationInfo.h   |   6 -
.../kernel/file_systems/ramfs/AreaUtils.cpp      | 138 -----
.../kernel/file_systems/ramfs/AreaUtils.h        |  17 -
.../file_systems/ramfs/DirectoryEntryTable.h     | 153 ++++++
src/add-ons/kernel/file_systems/ramfs/Entry.h    |   3 +
src/add-ons/kernel/file_systems/ramfs/Jamfile    |   1 -
src/add-ons/kernel/file_systems/ramfs/Node.cpp   |   3 -
src/add-ons/kernel/file_systems/ramfs/Node.h     |   3 +
.../kernel/file_systems/ramfs/NodeChildTable.h   | 247 ---------
.../kernel/file_systems/ramfs/NodeTable.cpp      |  42 +-
.../kernel/file_systems/ramfs/NodeTable.h        |  48 +-
.../kernel/file_systems/ramfs/OpenHashTable.h    | 498 -------------------
src/add-ons/kernel/file_systems/ramfs/Volume.cpp |  38 +-
src/add-ons/kernel/file_systems/ramfs/Volume.h   |   6 +-

############################################################################

Commit:      565c58a5271713d8ea3251aecf96cc824579d2df
URL:         https://git.haiku-os.org/haiku/commit/?id=565c58a52717
Author:      Augustin Cavalier <waddlesplash@xxxxxxxxx>
Date:        Sat Aug 31 05:06:50 2019 UTC

ramfs: Adapt NodeTable to use BOpenHashTable.

----------------------------------------------------------------------------

diff --git a/src/add-ons/kernel/file_systems/ramfs/Node.h 
b/src/add-ons/kernel/file_systems/ramfs/Node.h
index 02a81ae7bd..a1b966275e 100644
--- a/src/add-ons/kernel/file_systems/ramfs/Node.h
+++ b/src/add-ons/kernel/file_systems/ramfs/Node.h
@@ -38,6 +38,8 @@ public:
 
        virtual status_t InitCheck() const;
 
+       Node*& HashLink()       { return fHashLink; }
+
        inline void SetVolume(Volume *volume)   { fVolume = volume; }
        inline Volume *GetVolume() const                { return fVolume; }
 
@@ -109,6 +111,7 @@ public:
        virtual void GetAllocationInfo(AllocationInfo &info);
 
 private:
+       Node                                    *fHashLink;
        Volume                                  *fVolume;
        ino_t                                   fID;
        int32                                   fRefCount;
diff --git a/src/add-ons/kernel/file_systems/ramfs/NodeTable.cpp 
b/src/add-ons/kernel/file_systems/ramfs/NodeTable.cpp
index ed729c1ada..aaf97c92fe 100644
--- a/src/add-ons/kernel/file_systems/ramfs/NodeTable.cpp
+++ b/src/add-ons/kernel/file_systems/ramfs/NodeTable.cpp
@@ -8,9 +8,8 @@
 
 // constructor
 NodeTable::NodeTable()
-       : fElementArray(1000),
-         fNodes(1000, &fElementArray)
 {
+       fInitStatus = fNodes.Init(1000);
 }
 
 // destructor
@@ -22,8 +21,7 @@ NodeTable::~NodeTable()
 status_t
 NodeTable::InitCheck() const
 {
-       RETURN_ERROR(fNodes.InitCheck() && fElementArray.InitCheck()
-                                ? B_OK : B_NO_MEMORY);
+       RETURN_ERROR(fInitStatus);
 }
 
 // AddNode
@@ -32,12 +30,9 @@ NodeTable::AddNode(Node *node)
 {
        status_t error = (node ? B_OK : B_BAD_VALUE);
        if (error == B_OK) {
-               NodeHashElement *element
-                       = fNodes.Add(NodeHashElement::HashForID(node));
-               if (element)
-                       element->fNode = node;
-               else
-                       SET_ERROR(error, B_NO_MEMORY);
+               if (fNodes.Lookup(node->GetID()) != nullptr)
+                       fNodes.Remove(node);
+               SET_ERROR(error, fNodes.Insert(node));
        }
        return error;
 }
@@ -57,7 +52,7 @@ status_t
 NodeTable::RemoveNode(ino_t id)
 {
        status_t error = B_OK;
-       if (NodeHashElement *element = _FindElement(id))
+       if (Node *element = fNodes.Lookup(id))
                fNodes.Remove(element);
        else
                error = B_ERROR;
@@ -68,9 +63,7 @@ NodeTable::RemoveNode(ino_t id)
 Node *
 NodeTable::GetNode(ino_t id)
 {
-       Node *node = NULL;
-       if (NodeHashElement *element = _FindElement(id))
-               node = element->fNode;
+       Node *node = fNodes.Lookup(id);
        return node;
 }
 
@@ -78,23 +71,6 @@ NodeTable::GetNode(ino_t id)
 void
 NodeTable::GetAllocationInfo(AllocationInfo &info)
 {
-       info.AddNodeTableAllocation(fNodes.ArraySize(), fNodes.VectorSize(),
-                                                               
sizeof(NodeHashElement),
-                                                               
fNodes.CountElements());
+       info.AddNodeTableAllocation(0, fNodes.TableSize(),
+               sizeof(Node*), fNodes.CountElements());
 }
-
-// _FindElement
-NodeHashElement *
-NodeTable::_FindElement(ino_t id) const
-{
-       NodeHashElement *element
-               = fNodes.FindFirst(NodeHashElement::HashForID(id));
-       while (element && element->fNode->GetID() != id) {
-               if (element->fNext >= 0)
-                       element = fNodes.ElementAt(element->fNext);
-               else
-                       element = NULL;
-       }
-       return element;
-}
-
diff --git a/src/add-ons/kernel/file_systems/ramfs/NodeTable.h 
b/src/add-ons/kernel/file_systems/ramfs/NodeTable.h
index 33e11d1fa2..5a5c79ec2f 100644
--- a/src/add-ons/kernel/file_systems/ramfs/NodeTable.h
+++ b/src/add-ons/kernel/file_systems/ramfs/NodeTable.h
@@ -5,44 +5,35 @@
 #ifndef NODE_TABLE_H
 #define NODE_TABLE_H
 
+#include <util/OpenHashTable.h>
+
 #include "AllocationInfo.h"
 #include "Node.h"
-#include "OpenHashTable.h"
 
-// NodeHashElement
-class NodeHashElement : public OpenHashElement {
-public:
-       NodeHashElement() : OpenHashElement(), fNode(NULL)
-       {
-               fNext = -1;
-       }
+// NodeHash
+struct NodeHash {
+       typedef ino_t           KeyType;
+       typedef Node            ValueType;
 
-       static inline uint32 HashForID(ino_t id)
+       size_t HashKey(KeyType key) const
        {
-               return uint32(id & 0xffffffff);
+               return uint32(key & 0xffffffff);
        }
 
-       static inline uint32 HashForID(Node *node)
+       size_t Hash(ValueType* value) const
        {
-               return HashForID(node->GetID());
+               return HashKey(value->GetID());
        }
 
-       inline uint32 Hash() const
+       bool Compare(KeyType key, ValueType* value) const
        {
-               return HashForID(fNode);
+               return value->GetID() == key;
        }
 
-       inline bool operator==(const OpenHashElement &element) const
+       ValueType*& GetLink(ValueType* value) const
        {
-               return (static_cast<const NodeHashElement&>(element).fNode == 
fNode);
+               return value->HashLink();
        }
-
-       inline void Adopt(NodeHashElement &element)
-       {
-               fNode = element.fNode;
-       }
-
-       Node    *fNode;
 };
 
 // NodeTable
@@ -62,15 +53,8 @@ public:
        void GetAllocationInfo(AllocationInfo &info);
 
 private:
-       NodeHashElement *_FindElement(ino_t id) const;
-
-private:
-       OpenHashElementArray<NodeHashElement>   fElementArray;
-       OpenHashTable<NodeHashElement, OpenHashElementArray<NodeHashElement> >
-               fNodes;
+       BOpenHashTable<NodeHash> fNodes;
+       status_t fInitStatus;
 };
 
-// undefine the PRINT from <Debug.h>
-//#undef PRINT
-
 #endif // NODE_TABLE_H

############################################################################

Commit:      019d327dce8b1f29774529115800d574674d35c4
URL:         https://git.haiku-os.org/haiku/commit/?id=019d327dce8b
Author:      Augustin Cavalier <waddlesplash@xxxxxxxxx>
Date:        Sat Aug 31 16:04:04 2019 UTC

ramfs: Just use the linked list for attributes instead of a hash table.

This is what packagefs does; so if it's performant enough for packagefs,
it's performant enough for us. Greatly simplifies this code (and will
allow for further simplification of the NodeChildHash.)

----------------------------------------------------------------------------

diff --git a/src/add-ons/kernel/file_systems/ramfs/AllocationInfo.cpp 
b/src/add-ons/kernel/file_systems/ramfs/AllocationInfo.cpp
index d155123689..f1d510102b 100644
--- a/src/add-ons/kernel/file_systems/ramfs/AllocationInfo.cpp
+++ b/src/add-ons/kernel/file_systems/ramfs/AllocationInfo.cpp
@@ -20,9 +20,6 @@ AllocationInfo::AllocationInfo()
          fDirectoryEntryTableArraySize(0),
          fDirectoryEntryTableVectorSize(0),
          fDirectoryEntryTableElementCount(0),
-         fNodeAttributeTableArraySize(0),
-         fNodeAttributeTableVectorSize(0),
-         fNodeAttributeTableElementCount(0),
 
          fAttributeCount(0),
          fAttributeSize(0),
@@ -73,18 +70,6 @@ AllocationInfo::AddDirectoryEntryTableAllocation(size_t 
arraySize,
        fDirectoryEntryTableElementCount += elementCount;
 }
 
-// AddNodeAttributeTableAllocation
-void
-AllocationInfo::AddNodeAttributeTableAllocation(size_t arraySize,
-                                                                               
                size_t vectorSize,
-                                                                               
                size_t elementSize,
-                                                                               
                size_t elementCount)
-{
-       fNodeAttributeTableArraySize += arraySize;
-       fNodeAttributeTableVectorSize += vectorSize * elementSize;
-       fNodeAttributeTableElementCount += elementCount;
-}
-
 // AddAttributeAllocation
 void
 AllocationInfo::AddAttributeAllocation(size_t size)
@@ -187,14 +172,6 @@ AllocationInfo::Dump() const
        areaSize += fDirectoryEntryTableArraySize * sizeof(int32)
                                + fDirectoryEntryTableVectorSize;
 
-       PRINT("  attribute table:\n");
-       PRINT("    array size:  %9lu\n", fNodeAttributeTableArraySize);
-       PRINT("    vector size: %9lu\n", fNodeAttributeTableVectorSize);
-       PRINT("    elements:    %9lu\n", fNodeAttributeTableElementCount);
-       areaCount += 2;
-       areaSize += fNodeAttributeTableArraySize * sizeof(int32)
-                               + fNodeAttributeTableVectorSize;
-
        PRINT("  attributes:  %9lu, size: %9lu\n", fAttributeCount, 
fAttributeSize);
        heapCount += fAttributeCount;
        heapSize += fAttributeCount * sizeof(Attribute);
diff --git a/src/add-ons/kernel/file_systems/ramfs/AllocationInfo.h 
b/src/add-ons/kernel/file_systems/ramfs/AllocationInfo.h
index d2bf764bc9..b0c81cff66 100644
--- a/src/add-ons/kernel/file_systems/ramfs/AllocationInfo.h
+++ b/src/add-ons/kernel/file_systems/ramfs/AllocationInfo.h
@@ -17,9 +17,6 @@ public:
        void AddDirectoryEntryTableAllocation(size_t arraySize, size_t 
vectorSize,
                                                                                
  size_t elementSize,
                                                                                
  size_t elementCount);
-       void AddNodeAttributeTableAllocation(size_t arraySize, size_t 
vectorSize,
-                                                                               
 size_t elementSize,
-                                                                               
 size_t elementCount);
 
        void AddAttributeAllocation(size_t size);
        void AddDirectoryAllocation();
@@ -42,9 +39,6 @@ private:
        size_t  fDirectoryEntryTableArraySize;
        size_t  fDirectoryEntryTableVectorSize;
        size_t  fDirectoryEntryTableElementCount;
-       size_t  fNodeAttributeTableArraySize;
-       size_t  fNodeAttributeTableVectorSize;
-       size_t  fNodeAttributeTableElementCount;
 
        size_t  fAttributeCount;
        size_t  fAttributeSize;
diff --git a/src/add-ons/kernel/file_systems/ramfs/Node.cpp 
b/src/add-ons/kernel/file_systems/ramfs/Node.cpp
index f2187b8e12..20d2610e69 100644
--- a/src/add-ons/kernel/file_systems/ramfs/Node.cpp
+++ b/src/add-ons/kernel/file_systems/ramfs/Node.cpp
@@ -274,7 +274,6 @@ Node::FindAttribute(const char *name, Attribute 
**_attribute) const
 {
        status_t error = (name && _attribute ? B_OK : B_BAD_VALUE);
        if (error == B_OK) {
-/*
                Attribute *attribute = NULL;
                while (GetNextAttribute(&attribute) == B_OK) {
                        if (!strcmp(attribute->GetName(), name)) {
@@ -283,8 +282,6 @@ Node::FindAttribute(const char *name, Attribute 
**_attribute) const
                        }
                }
                error = B_ENTRY_NOT_FOUND;
-*/
-               error = GetVolume()->FindNodeAttribute(GetID(), name, 
_attribute);
        }
        return error;
 }
diff --git a/src/add-ons/kernel/file_systems/ramfs/Volume.cpp 
b/src/add-ons/kernel/file_systems/ramfs/Volume.cpp
index 6e8c08d3a8..c1b374ff3b 100644
--- a/src/add-ons/kernel/file_systems/ramfs/Volume.cpp
+++ b/src/add-ons/kernel/file_systems/ramfs/Volume.cpp
@@ -136,7 +136,6 @@ Volume::Volume(fs_volume* volume)
        fNextNodeID(kRootParentID + 1),
        fNodeTable(NULL),
        fDirectoryEntryTable(NULL),
-       fNodeAttributeTable(NULL),
        fIndexDirectory(NULL),
        fRootDirectory(NULL),
        fName(kDefaultVolumeName),
@@ -213,14 +212,6 @@ Volume::Mount(uint32 flags)
                else
                        SET_ERROR(error, B_NO_MEMORY);
        }
-       // create the node attribute table
-       if (error == B_OK) {
-               fNodeAttributeTable = new(nothrow) NodeAttributeTable;
-               if (fNodeAttributeTable)
-                       error = fNodeAttributeTable->InitCheck();
-               else
-                       SET_ERROR(error, B_NO_MEMORY);
-       }
        // create the index directory
        if (error == B_OK) {
                fIndexDirectory = new(nothrow) IndexDirectory(this);
@@ -272,10 +263,6 @@ Volume::Unmount()
                fNodeListeners = NULL;
        }
        // delete the tables
-       if (fNodeAttributeTable) {
-               delete fNodeAttributeTable;
-               fNodeAttributeTable = NULL;
-       }
        if (fDirectoryEntryTable) {
                delete fDirectoryEntryTable;
                fDirectoryEntryTable = NULL;
@@ -660,7 +647,6 @@ Volume::NodeAttributeAdded(ino_t id, Attribute *attribute)
 {
        status_t error = (attribute ? B_OK : B_BAD_VALUE);
        if (error == B_OK) {
-               error = fNodeAttributeTable->AddNodeChild(id, attribute);
                // notify the respective attribute index
                if (error == B_OK) {
                        if (AttributeIndex *index = FindAttributeIndex(
@@ -678,7 +664,6 @@ Volume::NodeAttributeRemoved(ino_t id, Attribute *attribute)
 {
        status_t error = (attribute ? B_OK : B_BAD_VALUE);
        if (error == B_OK) {
-               error = fNodeAttributeTable->RemoveNodeChild(id, attribute);
                // notify the respective attribute index
                if (error == B_OK) {
                        if (AttributeIndex *index = FindAttributeIndex(
@@ -699,19 +684,6 @@ Volume::NodeAttributeRemoved(ino_t id, Attribute 
*attribute)
        return error;
 }
 
-// FindNodeAttribute
-status_t
-Volume::FindNodeAttribute(ino_t id, const char *name, Attribute **attribute)
-{
-       status_t error = (attribute ? B_OK : B_BAD_VALUE);
-       if (error == B_OK) {
-               *attribute = fNodeAttributeTable->GetNodeChild(id, name);
-               if (!*attribute)
-                       error = B_ENTRY_NOT_FOUND;
-       }
-       return error;
-}
-
 // GetNameIndex
 NameIndex *
 Volume::GetNameIndex() const
@@ -841,8 +813,6 @@ Volume::GetAllocationInfo(AllocationInfo &info)
        fNodeTable->GetAllocationInfo(info);
        info.AddOtherAllocation(sizeof(DirectoryEntryTable));
        fDirectoryEntryTable->GetAllocationInfo(info);
-       info.AddOtherAllocation(sizeof(NodeAttributeTable));
-       fNodeAttributeTable->GetAllocationInfo(info);
        // node hierarchy
        fRootDirectory->GetAllocationInfo(info);
        // name
diff --git a/src/add-ons/kernel/file_systems/ramfs/Volume.h 
b/src/add-ons/kernel/file_systems/ramfs/Volume.h
index 05af40653c..1cbec3c129 100644
--- a/src/add-ons/kernel/file_systems/ramfs/Volume.h
+++ b/src/add-ons/kernel/file_systems/ramfs/Volume.h
@@ -47,7 +47,6 @@ class IndexDirectory;
 class LastModifiedIndex;
 class NameIndex;
 class Node;
-class NodeAttributeTable;
 class NodeListener;
 class NodeListenerTree;
 class NodeTable;
@@ -136,11 +135,9 @@ public:
                                                          uint32 flags);
        status_t RemoveEntryListener(EntryListener *listener, Entry *entry);
 
-       // node attribute table
+       // node attributes
        status_t NodeAttributeAdded(ino_t id, Attribute *attribute);
        status_t NodeAttributeRemoved(ino_t id, Attribute *attribute);
-       status_t FindNodeAttribute(ino_t id, const char *name,
-                                                          Attribute 
**attribute);
 
        // indices
        IndexDirectory *GetIndexDirectory() const       { return 
fIndexDirectory; }
@@ -186,7 +183,6 @@ private:
        ino_t                                   fNextNodeID;
        NodeTable                               *fNodeTable;
        DirectoryEntryTable             *fDirectoryEntryTable;
-       NodeAttributeTable              *fNodeAttributeTable;
        IndexDirectory                  *fIndexDirectory;
        Directory                               *fRootDirectory;
        String                                  fName;

############################################################################

Commit:      e58322127037e91a4190fb1fde4f60bff9970dae
URL:         https://git.haiku-os.org/haiku/commit/?id=e58322127037
Author:      Augustin Cavalier <waddlesplash@xxxxxxxxx>
Date:        Sat Aug 31 16:25:39 2019 UTC

ramfs: Replace the NodeChildTable with a DirectoryEntryTable.

Now that Attributes don't use a table, we can replace the generic
system with a specific DirectoryEntryTable, upgrading to BOpenHashTable
in the process.

----------------------------------------------------------------------------

diff --git a/src/add-ons/kernel/file_systems/ramfs/DirectoryEntryTable.h 
b/src/add-ons/kernel/file_systems/ramfs/DirectoryEntryTable.h
new file mode 100644
index 0000000000..71ea63779e
--- /dev/null
+++ b/src/add-ons/kernel/file_systems/ramfs/DirectoryEntryTable.h
@@ -0,0 +1,153 @@
+/*
+ * Copyright 2019, Haiku, Inc. All rights reserved.
+ * Distributed under the terms of the MIT license.
+ */
+#ifndef DIRECTORY_ENTRY_TABLE_H
+#define DIRECTORY_ENTRY_TABLE_H
+
+#include <util/OpenHashTable.h>
+
+#include "AllocationInfo.h"
+#include "DebugSupport.h"
+#include "Misc.h"
+#include "Node.h"
+
+// DirectoryEntryHash
+struct DirectoryEntryHash {
+       struct Key {
+               ino_t id;
+               const char* name;
+
+               Key(ino_t i, const char* n) : id(i), name(n) {}
+       };
+       typedef Key                     KeyType;
+       typedef Entry           ValueType;
+
+       size_t HashKey(KeyType key) const
+       {
+               return node_child_hash(key.id, key.name);
+       }
+
+       size_t Hash(ValueType* value) const
+       {
+               return HashKey(Key(value->GetParent()->GetID(), 
value->GetName()));
+       }
+
+       bool Compare(KeyType key, ValueType* value) const
+       {
+               return (value->GetParent()->GetID() == key.id
+                       && !strcmp(value->GetName(), key.name));
+       }
+
+       ValueType*& GetLink(ValueType* value) const
+       {
+               return value->HashLink();
+       }
+};
+
+// DirectoryEntryTable
+class DirectoryEntryTable {
+public:
+       DirectoryEntryTable();
+       ~DirectoryEntryTable();
+
+       status_t InitCheck() const;
+
+       status_t AddEntry(Directory *node, Entry *child);
+       status_t AddEntry(ino_t, Entry *child);
+       status_t RemoveEntry(Directory *node, Entry *child);
+       status_t RemoveEntry(ino_t id, Entry *child);
+       status_t RemoveEntry(ino_t id, const char *name);
+       Entry *GetEntry(ino_t id, const char *name);
+
+       void GetAllocationInfo(AllocationInfo &info)
+       {
+               info.AddDirectoryEntryTableAllocation(0, fTable.TableSize(),
+                       sizeof(void*), fTable.CountElements());
+       }
+
+protected:
+       BOpenHashTable<DirectoryEntryHash> fTable;
+       status_t fInitStatus;
+};
+
+// constructor
+DirectoryEntryTable::DirectoryEntryTable()
+{
+       fInitStatus = fTable.Init(1000);
+}
+
+// destructor
+DirectoryEntryTable::~DirectoryEntryTable()
+{
+}
+
+// InitCheck
+status_t
+DirectoryEntryTable::InitCheck() const
+{
+       RETURN_ERROR(fInitStatus);
+}
+
+// AddEntry
+status_t
+DirectoryEntryTable::AddEntry(Directory *node, Entry *child)
+{
+       status_t error = (node && child ? B_OK : B_BAD_VALUE);
+       if (error == B_OK)
+               error = AddEntry(node->GetID(), child);
+       return error;
+}
+
+// AddEntry
+status_t
+DirectoryEntryTable::AddEntry(ino_t id, Entry *child)
+{
+       status_t error = (child ? B_OK : B_BAD_VALUE);
+       if (error == B_OK) {
+               RemoveEntry(id, child);
+               SET_ERROR(error, fTable.Insert(child));
+       }
+       return error;
+}
+
+// RemoveEntry
+status_t
+DirectoryEntryTable::RemoveEntry(Directory *node, Entry *child)
+{
+       status_t error = (node && child ? B_OK : B_BAD_VALUE);
+       if (error == B_OK)
+               error = RemoveEntry(node->GetID(), child->GetName());
+       return error;
+}
+
+// RemoveEntry
+status_t
+DirectoryEntryTable::RemoveEntry(ino_t id, Entry *child)
+{
+       status_t error = (child ? B_OK : B_BAD_VALUE);
+       if (error == B_OK)
+               error = RemoveEntry(id, child->GetName());
+       return error;
+}
+
+// RemoveEntry
+status_t
+DirectoryEntryTable::RemoveEntry(ino_t id, const char *name)
+{
+       Entry* child = fTable.Lookup(typename DirectoryEntryHash::Key(id, 
name));
+       if (!child)
+               return B_NAME_NOT_FOUND;
+       status_t error = fTable.Remove(child);
+       return error;
+}
+
+// GetEntry
+Entry *
+DirectoryEntryTable::GetEntry(ino_t id, const char *name)
+{
+       Entry *child = fTable.Lookup(typename DirectoryEntryHash::Key(id, 
name));
+       return child;
+}
+
+#endif // DIRECTORY_ENTRY_TABLE_H
diff --git a/src/add-ons/kernel/file_systems/ramfs/Entry.h 
b/src/add-ons/kernel/file_systems/ramfs/Entry.h
index 6e6ffbaf53..6fb55517e0 100644
--- a/src/add-ons/kernel/file_systems/ramfs/Entry.h
+++ b/src/add-ons/kernel/file_systems/ramfs/Entry.h
@@ -24,6 +24,8 @@ public:
 
        status_t InitCheck() const;
 
+       Entry*& HashLink()      { return fHashLink; }
+
        inline void SetParent(Directory *parent)        { fParent = parent; }
        Directory *GetParent() const                            { return 
fParent; }
 
@@ -50,6 +52,7 @@ public:
        void GetAllocationInfo(AllocationInfo &info);
 
 private:
+       Entry                                   *fHashLink;
        Directory                               *fParent;
        Node                                    *fNode;
        String                                  fName;
diff --git a/src/add-ons/kernel/file_systems/ramfs/Volume.cpp 
b/src/add-ons/kernel/file_systems/ramfs/Volume.cpp
index c1b374ff3b..95c0795598 100644
--- a/src/add-ons/kernel/file_systems/ramfs/Volume.cpp
+++ b/src/add-ons/kernel/file_systems/ramfs/Volume.cpp
@@ -30,6 +30,7 @@
 #include "BlockAllocator.h"
 #include "DebugSupport.h"
 #include "Directory.h"
+#include "DirectoryEntryTable.h"
 #include "Entry.h"
 #include "EntryListener.h"
 #include "IndexDirectory.h"
@@ -37,7 +38,6 @@
 #include "Misc.h"
 #include "NameIndex.h"
 #include "Node.h"
-#include "NodeChildTable.h"
 #include "NodeListener.h"
 #include "NodeTable.h"
 #include "TwoKeyAVLTree.h"
@@ -535,7 +535,7 @@ Volume::EntryAdded(ino_t id, Entry *entry)
 {
        status_t error = (entry ? B_OK : B_BAD_VALUE);
        if (error == B_OK) {
-               error = fDirectoryEntryTable->AddNodeChild(id, entry);
+               error = fDirectoryEntryTable->AddEntry(id, entry);
                if (error == B_OK) {
                        // notify listeners
                        // listeners interested in that entry
@@ -566,7 +566,7 @@ Volume::EntryRemoved(ino_t id, Entry *entry)
 {
        status_t error = (entry ? B_OK : B_BAD_VALUE);
        if (error == B_OK) {
-               error = fDirectoryEntryTable->RemoveNodeChild(id, entry);
+               error = fDirectoryEntryTable->RemoveEntry(id, entry);
                if (error == B_OK) {
                        // notify listeners
                        // listeners interested in that entry
@@ -597,7 +597,7 @@ Volume::FindEntry(ino_t id, const char *name, Entry **entry)
 {
        status_t error = (entry ? B_OK : B_BAD_VALUE);
        if (error == B_OK) {
-               *entry = fDirectoryEntryTable->GetNodeChild(id, name);
+               *entry = fDirectoryEntryTable->GetEntry(id, name);
                if (!*entry)
                        error = B_ENTRY_NOT_FOUND;
        }

############################################################################

Revision:    hrev53440
Commit:      91c8637753340bead59f87865c4a4f510b41c095
URL:         https://git.haiku-os.org/haiku/commit/?id=91c863775334
Author:      Augustin Cavalier <waddlesplash@xxxxxxxxx>
Date:        Sat Aug 31 16:26:10 2019 UTC

ramfs: Drop OpenTracker OpenHashTable and the custom AreaUtils.

Following removal of NodeChildTable, they aren't used.

----------------------------------------------------------------------------

diff --git a/src/add-ons/kernel/file_systems/ramfs/AreaUtils.cpp 
b/src/add-ons/kernel/file_systems/ramfs/AreaUtils.cpp
deleted file mode 100644
index 31838533b9..0000000000
--- a/src/add-ons/kernel/file_systems/ramfs/AreaUtils.cpp
+++ /dev/null
@@ -1,138 +0,0 @@
-/*
- * Copyright 2003, Ingo Weinhold, ingo_weinhold@xxxxxx.
- * All rights reserved. Distributed under the terms of the MIT license.
- */
-
-#include <OS.h>
-
-#include "AreaUtils.h"
-#include "DebugSupport.h"
-#include "Misc.h"
-
-#ifndef USE_STANDARD_FUNCTIONS
-#define USE_STANDARD_FUNCTIONS 0
-#endif
-
-
-// area_info_for
-static
-status_t
-area_info_for(void *address, area_info *info)
-{
-       status_t error = B_OK;
-       if (address) {
-               // get the area ID for the ptr
-               area_id area = area_for(address);
-               // check if supplied pointer points to the beginning of the area
-               if (area >= 0)
-                       error = get_area_info(area, info);
-               else
-                       error = area;
-       } else
-               error = B_BAD_VALUE;
-       return error;
-}
-
-// calloc
-void *
-AreaUtils::calloc(size_t nmemb, size_t size)
-{
-//PRINT(("AreaUtils::calloc(%lu, %lu)\n", nmemb, size));
-       return AreaUtils::malloc(nmemb * size);
-}
-
-// free
-void
-AreaUtils::free(void *ptr)
-{
-//PRINT(("AreaUtils::free(%p)\n", ptr));
-#if USE_STANDARD_FUNCTIONS
-       return ::free(ptr);
-#else
-       if (ptr) {
-               // get the area for the pointer
-               area_info info;
-               if (area_info_for(ptr, &info) == B_OK) {
-                       if (ptr == info.address) {
-                               // everything is fine, delete the area
-                               delete_area(info.area);
-                       } else {
-                               INFORM("WARNING: AreaUtils::free(%p): area 
begin is %p."
-                                               "Ignored.\n", ptr, 
info.address);
-                       }
-               }
-       }
-#endif
-}
-
-// malloc
-void *
-AreaUtils::malloc(size_t size)
-{
-//PRINT(("AreaUtils::malloc(%lu)\n", size));
-#if USE_STANDARD_FUNCTIONS
-       return ::malloc(size);
-#else
-       void *address = NULL;
-       if (size > 0) {
-               // round to multiple of page size
-               size = (size + B_PAGE_SIZE - 1) / B_PAGE_SIZE * B_PAGE_SIZE;
-               // create an area
-#if USER
-               area_id area = create_area("AreaUtils::malloc", &address,
-                                                                  
B_ANY_ADDRESS, size, B_NO_LOCK,
-                                                                  B_WRITE_AREA 
| B_READ_AREA);
-#else
-               area_id area = create_area("AreaUtils::malloc", &address,
-                                                                  
B_ANY_KERNEL_ADDRESS, size, B_FULL_LOCK,
-                                                                  B_READ_AREA 
| B_WRITE_AREA);
-#endif
-               if (area < 0)
-                       address = NULL;
-       }
-       return address;
-#endif
-}
-
-// realloc
-void *
-AreaUtils::realloc(void * ptr, size_t size)
-{
-//PRINT(("AreaUtils::realloc(%p, %lu)\n", ptr, size))
-#if USE_STANDARD_FUNCTIONS
-       return ::realloc(ptr, size);
-#else
-       void *newAddress = NULL;
-       if (size == 0) {
-               AreaUtils::free(ptr);
-       } else if (ptr) {
-               // get the area for the pointer
-               area_info info;
-               if (area_info_for(ptr, &info) == B_OK) {
-                       if (ptr == info.address) {
-                               // round to multiple of page size
-                               size = (size + B_PAGE_SIZE - 1) / B_PAGE_SIZE * 
B_PAGE_SIZE;
-                               if (size == info.size) {
-                                       // nothing to do
-                                       newAddress = ptr;
-                               } else if (resize_area(info.area, size) == 
B_OK) {
-                                       // resizing the area went fine
-                                       newAddress = ptr;
-                               } else {
-                                       // resizing the area failed: we need to 
allocate a new one
-                                       newAddress = AreaUtils::malloc(size);
-                                       if (newAddress) {
-                                               memcpy(newAddress, ptr, 
min(size, info.size));
-                                               delete_area(info.area);
-                                       }
-                               }
-                       } else {
-                               INFORM("WARNING: AreaUtils::realloc(%p): area 
begin is %p."
-                                               "Ignored.\n", ptr, 
info.address);
-                       }
-               }
-       }
-       return newAddress;
-#endif
-}
-
diff --git a/src/add-ons/kernel/file_systems/ramfs/AreaUtils.h 
b/src/add-ons/kernel/file_systems/ramfs/AreaUtils.h
deleted file mode 100644
index 539c8387a7..0000000000
--- a/src/add-ons/kernel/file_systems/ramfs/AreaUtils.h
+++ /dev/null
@@ -1,17 +0,0 @@
-/*
- * Copyright 2003, Ingo Weinhold, ingo_weinhold@xxxxxx.
- * All rights reserved. Distributed under the terms of the MIT license.
- */
-#ifndef AREA_UTILS_H
-#define AREA_UTILS_H
-
-namespace AreaUtils {
-
-       void *calloc(size_t nmemb, size_t size);
-       void free(void *ptr);
-       void *malloc(size_t size);
-       void *realloc(void * ptr, size_t size);
-
-};
-
-#endif // AREA_UTILS_H
diff --git a/src/add-ons/kernel/file_systems/ramfs/Jamfile 
b/src/add-ons/kernel/file_systems/ramfs/Jamfile
index 9d14961e76..c5920f53c8 100644
--- a/src/add-ons/kernel/file_systems/ramfs/Jamfile
+++ b/src/add-ons/kernel/file_systems/ramfs/Jamfile
@@ -8,7 +8,6 @@ DEFINES += DEBUG_APP="\\\"ramfs\\\"" ;
 KernelAddon ramfs
        :
        AllocationInfo.cpp
-       AreaUtils.cpp
        Attribute.cpp
        AttributeIndex.cpp
        AttributeIndexImpl.cpp
diff --git a/src/add-ons/kernel/file_systems/ramfs/NodeChildTable.h 
b/src/add-ons/kernel/file_systems/ramfs/NodeChildTable.h
deleted file mode 100644
index 987ea32b96..0000000000
--- a/src/add-ons/kernel/file_systems/ramfs/NodeChildTable.h
+++ /dev/null
@@ -1,247 +0,0 @@
-/*
- * Copyright 2007, Ingo Weinhold, ingo_weinhold@xxxxxx.
- * All rights reserved. Distributed under the terms of the MIT license.
- */
-#ifndef NODE_CHILD_TABLE_H
-#define NODE_CHILD_TABLE_H
-
-#include "AllocationInfo.h"
-#include "DebugSupport.h"
-#include "Misc.h"
-#include "Node.h"
-#include "OpenHashTable.h"
-
-// NodeChildHashElement
-template<typename ParentNode, typename NodeChild>
-class NodeChildHashElement : public OpenHashElement {
-private:
-       typedef NodeChildHashElement<ParentNode, NodeChild> Element;
-public:
-
-       NodeChildHashElement() : OpenHashElement(), fID(-1), fChild(NULL)
-       {
-               fNext = -1;
-       }
-
-       static inline uint32 HashFor(ino_t id, const char *name)
-       {
-               return node_child_hash(id, name);
-       }
-
-       static inline uint32 HashFor(ParentNode *parent, NodeChild *child)
-       {
-               return node_child_hash(parent->GetID(), child->GetName());
-       }
-
-       inline uint32 Hash() const
-       {
-               return HashFor(fID, fChild->GetName());
-       }
-
-       inline bool Equals(ino_t id, const char *name)
-       {
-               return (fID == id && !strcmp(fChild->GetName(), name));
-       }
-
-       inline bool operator==(const OpenHashElement &_element) const
-       {
-               const Element &element = static_cast<const Element&>(_element);
-               return Equals(element.fID, element.fChild->GetName());
-       }
-
-       inline void Adopt(Element &element)
-       {
-               fID = element.fID;
-               fChild = element.fChild;
-       }
-
-       ino_t           fID;
-       NodeChild       *fChild;
-};
-
-// NodeChildTable
-template<typename ParentNode, typename NodeChild>
-class NodeChildTable {
-public:
-       NodeChildTable();
-       ~NodeChildTable();
-
-       status_t InitCheck() const;
-
-       status_t AddNodeChild(ParentNode *node, NodeChild *child);
-       status_t AddNodeChild(ino_t, NodeChild *child);
-       status_t RemoveNodeChild(ParentNode *node, NodeChild *child);
-       status_t RemoveNodeChild(ino_t id, NodeChild *child);
-       status_t RemoveNodeChild(ino_t id, const char *name);
-       NodeChild *GetNodeChild(ino_t id, const char *name);
-
-protected:
-       typedef NodeChildHashElement<ParentNode, NodeChild>     Element;
-
-private:
-       Element *_FindElement(ino_t id, const char *name) const;
-
-protected:
-       OpenHashElementArray<Element>                                           
        fElementArray;
-       OpenHashTable<Element, OpenHashElementArray<Element> >  fTable;
-};
-
-// define convenient instantiation types
-
-// DirectoryEntryTable
-class DirectoryEntryTable : public NodeChildTable<Directory, Entry> {
-public:
-       DirectoryEntryTable()   {}
-       ~DirectoryEntryTable()  {}
-
-       void GetAllocationInfo(AllocationInfo &info)
-       {
-               info.AddDirectoryEntryTableAllocation(fTable.ArraySize(),
-                                                                               
          fTable.VectorSize(),
-                                                                               
          sizeof(Element),
-                                                                               
          fTable.CountElements());
-       }
-};
-
-// NodeAttributeTable
-class NodeAttributeTable : public NodeChildTable<Node, Attribute> {
-public:
-       NodeAttributeTable()    {}
-       ~NodeAttributeTable()   {}
-
-       void GetAllocationInfo(AllocationInfo &info)
-       {
-               info.AddNodeAttributeTableAllocation(fTable.ArraySize(),
-                                                                               
         fTable.VectorSize(),
-                                                                               
         sizeof(Element),
-                                                                               
         fTable.CountElements());
-       }
-};
-
-
-// NodeChildTable implementation
-
-// constructor
-template<typename ParentNode, typename NodeChild>
-NodeChildTable<ParentNode, NodeChild>::NodeChildTable()
-       : fElementArray(1000),
-         fTable(1000, &fElementArray)
-{
-}
-
-// destructor
-template<typename ParentNode, typename NodeChild>
-NodeChildTable<ParentNode, NodeChild>::~NodeChildTable()
-{
-}
-
-// InitCheck
-template<typename ParentNode, typename NodeChild>
-status_t
-NodeChildTable<ParentNode, NodeChild>::InitCheck() const
-{
-       RETURN_ERROR(fTable.InitCheck() && fElementArray.InitCheck()
-                                ? B_OK : B_NO_MEMORY);
-}
-
-// AddNodeChild
-template<typename ParentNode, typename NodeChild>
-status_t
-NodeChildTable<ParentNode, NodeChild>::AddNodeChild(ParentNode *node,
-                                                                               
                        NodeChild *child)
-{
-       status_t error = (node && child ? B_OK : B_BAD_VALUE);
-       if (error == B_OK)
-               error = AddNodeChild(node->GetID(), child);
-       return error;
-}
-
-// AddNodeChild
-template<typename ParentNode, typename NodeChild>
-status_t
-NodeChildTable<ParentNode, NodeChild>::AddNodeChild(ino_t id,
-                                                                               
                        NodeChild *child)
-{
-       status_t error = (child ? B_OK : B_BAD_VALUE);
-       if (error == B_OK) {
-               Element *element = fTable.Add(Element::HashFor(id, 
child->GetName()));
-               if (element) {
-                       element->fID = id;
-                       element->fChild = child;
-               } else
-                       SET_ERROR(error, B_NO_MEMORY);
-       }
-       return error;
-}
-
-// RemoveNodeChild
-template<typename ParentNode, typename NodeChild>
-status_t
-NodeChildTable<ParentNode, NodeChild>::RemoveNodeChild(ParentNode *node,
-                                                                               
                           NodeChild *child)
-{
-       status_t error = (node && child ? B_OK : B_BAD_VALUE);
-       if (error == B_OK)
-               error = RemoveNodeChild(node->GetID(), child->GetName());
-       return error;
-}
-
-// RemoveNodeChild
-template<typename ParentNode, typename NodeChild>
-status_t
-NodeChildTable<ParentNode, NodeChild>::RemoveNodeChild(ino_t id,
-                                                                               
                           NodeChild *child)
-{
-       status_t error = (child ? B_OK : B_BAD_VALUE);
-       if (error == B_OK)
-               error = RemoveNodeChild(id, child->GetName());
-       return error;
-}
-
-// RemoveNodeChild
-template<typename ParentNode, typename NodeChild>
-status_t
-NodeChildTable<ParentNode, NodeChild>::RemoveNodeChild(ino_t id,
-                                                                               
                           const char *name)
-{
-       status_t error = B_OK;
-       if (Element *element = _FindElement(id, name))
-               fTable.Remove(element);
-       else
-               error = B_ERROR;
-       return error;
-}
-
-// GetNodeChild
-template<typename ParentNode, typename NodeChild>
-NodeChild *
-NodeChildTable<ParentNode, NodeChild>::GetNodeChild(ino_t id,
-                                                                               
                        const char *name)
-{
-       NodeChild *child = NULL;
-       if (Element *element = _FindElement(id, name))
-               child = element->fChild;
-       return child;
-}
-
-// _FindElement
-template<typename ParentNode, typename NodeChild>
-typename NodeChildTable<ParentNode, NodeChild>::Element *
-NodeChildTable<ParentNode, NodeChild>::_FindElement(ino_t id,
-                                                                               
                        const char *name) const
-{
-       Element *element = fTable.FindFirst(Element::HashFor(id, name));
-       while (element && !element->Equals(id, name)) {
-               if (element->fNext >= 0)
-                       element = fTable.ElementAt(element->fNext);
-               else
-                       element = NULL;
-       }
-       return element;
-}
-
-
-// undefine the PRINT from <Debug.h>
-//#undef PRINT
-
-#endif // NODE_CHILD_TABLE_H
diff --git a/src/add-ons/kernel/file_systems/ramfs/OpenHashTable.h 
b/src/add-ons/kernel/file_systems/ramfs/OpenHashTable.h
deleted file mode 100644
index df4685e153..0000000000
--- a/src/add-ons/kernel/file_systems/ramfs/OpenHashTable.h
+++ /dev/null
@@ -1,498 +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
-// * hash array and element vector use areas for allocations
-// TODO:
-// * shrinking of element vectors
-
-// Hash table with open addresssing
-
-#ifndef __OPEN_HASH_TABLE__
-#define __OPEN_HASH_TABLE__
-
-#include <malloc.h>
-#include <new>
-
-#include "AreaUtils.h"
-#include "Misc.h"
-
-// don't include <Debug.h>
-#ifndef ASSERT
-#      define ASSERT(E)               (void)0
-#endif
-#define TRESPASS()              (void)0
-
-//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 *);
-
-       // 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*)AreaUtils::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()
-{
-       AreaUtils::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
-{
-       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)
-{
-       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)
-{
-       _RehashIfNeeded();
-       uint32 hash = element->Hash() % fArraySize;
-       int32 next = fHashArray[hash];
-       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) {
-                       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>::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 = max(fInitialSize,
-                                               int32(fElementCount * 1.73 * 
fMaxLoadFactor));
-       newSize = OptimalSize(newSize);
-       if (newSize != fArraySize) {
-PRINT(("_Rehash(): %lu -> %lu (currently %lu entries)\n", fArraySize, newSize,
-fElementCount));
-               // allocate a new array
-               int32 *newHashArray
-                       = (int32*)AreaUtils::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
-                       AreaUtils::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*)AreaUtils::calloc((size_t)initialSize, 
sizeof(Element));
-}
-
-template<class Element>
-OpenHashElementArray<Element>::~OpenHashElementArray()
-{
-       AreaUtils::free(fData);
-}
-
-template<class Element>
-bool
-OpenHashElementArray<Element>::InitCheck() const
-{
-       return fData;
-}
-
-template<class Element>
-Element &
-OpenHashElementArray<Element>::At(int32 index)
-{
-       ASSERT(index < fSize);
-       return fData[index];
-}
-
-template<class Element>
-const Element &
-OpenHashElementArray<Element>::At(int32 index) const
-{
-       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*)AreaUtils::realloc(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
-       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
-       ASSERT(index < fSize);
-       At(index).~Element();
-               // call the destructor explicitly to destroy the element
-               // properly
-       At(index).fNext = fNextDeleted;
-       fNextDeleted = index;
-}
-
-//} // namespace BPrivate
-
-//using namespace BPrivate;
-
-#endif



Other related posts:

  • » [haiku-commits] haiku: hrev53440 - src/add-ons/kernel/file_systems/ramfs - waddlesplash