[haiku-commits] BRANCH ahenriksson-github.production - headers/private/fs_shell src/add-ons/kernel/file_systems/bfs

added 8 changesets to branch 'refs/remotes/ahenriksson-github/production'
old head: 5cbffd392ebc19ddcecc1ccc64fe20a1c36e370f
new head: f111ce9ecde50daba2af6186c7c606aa4f08a9ca

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

cf389aa: Handle deleted inodes in FileSystemVisitor
  
  This will require some additional work, for instance, we are supposed
  to traverse removed nodes when that flag is set.

93755ec: Can't start transaction with MovedInodesLock write-locked

563d773: Flush transactions with no blocks in _FlushLog()
  
  Since the file system resizing code must reinitialize the block cache,
  it is necessary that it is completely empty.

a6d5f30: Print diagnostic message when disk size is too small

dc436d2: Flush the log before writing the new file system size

77a4fb7: Use RETURN_ERROR in _MoveInode() to facilitate error analysis

acfc9bf: Update the parent pointer of indices as well

f111ce9: Added HashMap to fs_shell

                                      [ ahenriksson <sausageboy@xxxxxxxxx> ]

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

7 files changed, 970 insertions(+), 16 deletions(-)
headers/private/fs_shell/HashMap.h                 |  403 ++++++++++++
headers/private/fs_shell/OpenHashTable.h           |  514 ++++++++++++++++
headers/private/fs_shell/fssh_api_wrapper.h        |    1 +
.../kernel/file_systems/bfs/FileSystemVisitor.cpp  |   29 +-
src/add-ons/kernel/file_systems/bfs/Journal.cpp    |    2 +-
.../kernel/file_systems/bfs/ResizeVisitor.cpp      |   32 +-
src/add-ons/kernel/file_systems/bfs/Volume.cpp     |    5 +-

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

Commit:      cf389aa14e69c2d0340c76d8c6caf99253b6bfb7

Author:      ahenriksson <sausageboy@xxxxxxxxx>
Date:        Tue Aug  7 10:28:15 2012 UTC

Handle deleted inodes in FileSystemVisitor

This will require some additional work, for instance, we are supposed
to traverse removed nodes when that flag is set.

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

diff --git a/src/add-ons/kernel/file_systems/bfs/FileSystemVisitor.cpp 
b/src/add-ons/kernel/file_systems/bfs/FileSystemVisitor.cpp
index 1575a69..a2a759d 100644
--- a/src/add-ons/kernel/file_systems/bfs/FileSystemVisitor.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/FileSystemVisitor.cpp
@@ -59,7 +59,15 @@ FileSystemVisitor::Next()
                        // open inode
                        vnode.SetTo(fVolume, fCurrent);
                        status = vnode.Get(&inode);
+
+                       // release the reference we acquired when pushing the 
node to
+                       // the stack
+                       put_vnode(fVolume->FSVolume(), 
fVolume->ToVnode(fCurrent));
+
                        if (status != B_OK) {
+                               if (inode->IsDeleted())
+                                       continue;
+
                                status = OpenInodeFailed(status, 
fVolume->ToBlock(fCurrent),
                                        NULL, NULL, NULL);
                                if (status == B_OK)
@@ -140,6 +148,10 @@ FileSystemVisitor::Next()
                                // push the directory on the stack, it will be 
visited after
                                // its children
                                fStack.Push(inode->BlockRun());
+
+                               // the inode may be deleted behind our back, we 
keep a
+                               // reference so we can check for this
+                               vnode.Keep();
                                continue;
                        }
 
@@ -187,17 +199,25 @@ FileSystemVisitor::Start(uint32 flags)
 
        fFlags = flags;
 
-       if (fFlags & VISIT_REGULAR)
+       if (fFlags & VISIT_REGULAR) {
+               Vnode vnode(fVolume, fVolume->Root());
+               vnode.Keep();
                fStack.Push(fVolume->Root());
+       }
 
-       if (fFlags & VISIT_INDICES)
+       if (fFlags & VISIT_INDICES) {
+               Vnode vnode(fVolume, fVolume->Indices());
+               vnode.Keep();
                fStack.Push(fVolume->Indices());
+       }
 
        if (fFlags & VISIT_REMOVED) {
                // Put removed vnodes to the stack -- they are not reachable by
                // traversing the file system anymore.
                InodeList::Iterator iterator = 
fVolume->RemovedInodes().GetIterator();
                while (Inode* inode = iterator.Next()) {
+                       Vnode vnode(fVolume, inode->ID());
+                       vnode.Keep();
                        fStack.Push(inode->BlockRun());
                }
        }
@@ -216,6 +236,11 @@ FileSystemVisitor::Stop()
                // the current directory inode is still locked in memory
                put_vnode(fVolume->FSVolume(), fVolume->ToVnode(fCurrent));
        }
+
+       // release the references to the vnodes on the stack
+       block_run run;
+       while (fStack.Pop(&run))
+               put_vnode(fVolume->FSVolume(), fVolume->ToVnode(run));
 }
 
 

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

Commit:      93755ec98f2bbef0c209551dd8914d234b20f864

Author:      ahenriksson <sausageboy@xxxxxxxxx>
Date:        Tue Aug  7 10:29:42 2012 UTC

Can't start transaction with MovedInodesLock write-locked

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

diff --git a/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp 
b/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
index b3ec05f..10fd5ab 100644
--- a/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
@@ -129,8 +129,6 @@ ResizeVisitor::VisitInode(Inode* inode, const char* 
treeName)
        // start by moving the inode so we can place the stream close to it
        // if possible
        if (inodeBlock < fBeginBlock || inodeBlock >= fEndBlock) {
-               WriteLocker movedInodesLocker(GetVolume()->MovedInodesLock());
-
                status = mark_vnode_busy(GetVolume()->FSVolume(), inode->ID(), 
true);
 
                ino_t oldInodeID = inode->ID();
@@ -659,6 +657,7 @@ ResizeVisitor::_MoveInode(Inode* inode, off_t& newInodeID, 
const char* treeName)
                }
        }
 
+       WriteLocker movedInodesLocker(GetVolume()->MovedInodesLock());
        status = GetVolume()->AddMovedInode(inode->ID(), newInodeID);
        if (status != B_OK) {
                FATAL(("_MoveInode: Could not add inode to vnodeID -> inodeID 
map!\n"));

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

Commit:      563d77322815364e26abaeb505a8632c0f049fa4

Author:      ahenriksson <sausageboy@xxxxxxxxx>
Date:        Tue Aug  7 14:36:18 2012 UTC

Flush transactions with no blocks in _FlushLog()

Since the file system resizing code must reinitialize the block cache,
it is necessary that it is completely empty.

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

diff --git a/src/add-ons/kernel/file_systems/bfs/Journal.cpp 
b/src/add-ons/kernel/file_systems/bfs/Journal.cpp
index bacfde1..ad2b91c 100644
--- a/src/add-ons/kernel/file_systems/bfs/Journal.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/Journal.cpp
@@ -920,7 +920,7 @@ Journal::_FlushLog(bool canWait, bool flushBlocks, bool 
alreadyLocked)
 
        // write the current log entry to disk
 
-       if (fUnwrittenTransactions != 0 && _TransactionSize() != 0) {
+       if (fUnwrittenTransactions != 0) {
                status = _WriteTransactionToLog();
                if (status < B_OK)
                        FATAL(("writing current log entry failed: %s\n", 
strerror(status)));

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

Commit:      a6d5f30cb73928a971226fc82903306dee4712a0

Author:      ahenriksson <sausageboy@xxxxxxxxx>
Date:        Tue Aug  7 16:22:21 2012 UTC

Print diagnostic message when disk size is too small

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

diff --git a/src/add-ons/kernel/file_systems/bfs/Volume.cpp 
b/src/add-ons/kernel/file_systems/bfs/Volume.cpp
index 7021b27..48a6b5f 100644
--- a/src/add-ons/kernel/file_systems/bfs/Volume.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/Volume.cpp
@@ -365,8 +365,11 @@ Volume::Mount(const char* deviceName, uint32 flags)
        off_t diskSize;
        if (opener.GetSize(&diskSize, &fDeviceBlockSize) != B_OK)
                RETURN_ERROR(B_ERROR);
-       if (diskSize < (NumBlocks() << BlockShift()))
+       if (diskSize < (NumBlocks() << BlockShift())) {
+               FATAL(("Disk size (%" B_PRIdOFF " bytes) < file system size (%"
+                       B_PRIdOFF " bytes)!\n", diskSize, NumBlocks() << 
BlockShift()));
                RETURN_ERROR(B_BAD_VALUE);
+       }
 
        // set the current log pointers, so that journaling will work correctly
        fLogStart = fSuperBlock.LogStart();

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

Commit:      dc436d20b3b9438d39e500b5ac6fa7e57ee81865

Author:      ahenriksson <sausageboy@xxxxxxxxx>
Date:        Tue Aug  7 17:02:50 2012 UTC

Flush the log before writing the new file system size

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

diff --git a/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp 
b/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
index 10fd5ab..5853e27 100644
--- a/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
@@ -310,6 +310,12 @@ ResizeVisitor::_ResizeVolume()
        if (status != B_OK)
                return status;
 
+       // we flush the log before updating file system size, so nothing
+       // on the disk remains unmoved 
+       status = GetVolume()->GetJournal(0)->FlushLogAndBlocks();
+       if (status != B_OK)
+               return status;
+
        // update superblock and volume information
        disk_super_block& superBlock = GetVolume()->SuperBlock();
 

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

Commit:      77a4fb7f9f7f66e141640f0035e2addd28006b26

Author:      ahenriksson <sausageboy@xxxxxxxxx>
Date:        Tue Aug  7 17:03:26 2012 UTC

Use RETURN_ERROR in _MoveInode() to facilitate error analysis

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

diff --git a/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp 
b/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
index 5853e27..0a0e174 100644
--- a/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
@@ -607,52 +607,52 @@ ResizeVisitor::_MoveInode(Inode* inode, off_t& 
newInodeID, const char* treeName)
                //       stuff that originally was in the beginning should 
probably
                //       stay close to it
        if (status != B_OK)
-               return status;
+               RETURN_ERROR(status);
 
        newInodeID = GetVolume()->ToBlock(run);
 
        status = inode->Copy(transaction, newInodeID);
        if (status != B_OK)
-               return status;
+               RETURN_ERROR(status);
 
        if (!rootOrIndexDir) {
                status = _UpdateParent(transaction, inode, newInodeID, 
treeName);
                if (status != B_OK)
-                       return status;
+                       RETURN_ERROR(status);
        }
 
        // update parent reference in attribute directory if we have one
        if (!inode->Attributes().IsZero()) {
                status = _UpdateAttributeDirectory(transaction, inode, run);
                if (status != B_OK)
-                       return status;
+                       RETURN_ERROR(status);
        }
 
        status = _UpdateIndexReferences(transaction, inode, newInodeID,
                rootOrIndexDir);
        if (status != B_OK)
-               return status;
+               RETURN_ERROR(status);
 
        // update "." and ".." tree entries if we are a directory
        if (inode->IsDirectory()) {
                status = _UpdateTree(transaction, inode, newInodeID);
                if (status != B_OK)
-                       return status;
+                       RETURN_ERROR(status);
        }
 
        if (inode->IsDirectory() || inode->IsAttributeDirectory()) {
                status = _UpdateChildren(transaction, inode, newInodeID);
                if (status != B_OK)
-                       return status;
+                       RETURN_ERROR(status);
        }
 
        status = GetVolume()->Free(transaction, inode->BlockRun());
        if (status != B_OK)
-               return status;
+               RETURN_ERROR(status);
 
        status = transaction.Done();
        if (status != B_OK)
-               return status;
+               RETURN_ERROR(status);
 
        if (rootOrIndexDir) {
                status = _UpdateSuperBlock(inode, newInodeID);

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

Commit:      acfc9bf1808590fc0f2f831f7b214e7386916e2f

Author:      ahenriksson <sausageboy@xxxxxxxxx>
Date:        Tue Aug  7 20:16:32 2012 UTC

Update the parent pointer of indices as well

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

diff --git a/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp 
b/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
index 0a0e174..cb9483f 100644
--- a/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
+++ b/src/add-ons/kernel/file_systems/bfs/ResizeVisitor.cpp
@@ -640,7 +640,10 @@ ResizeVisitor::_MoveInode(Inode* inode, off_t& newInodeID, 
const char* treeName)
                        RETURN_ERROR(status);
        }
 
-       if (inode->IsDirectory() || inode->IsAttributeDirectory()) {
+       // update the parent reference if we have children, this applies to
+       // regular directories, attribute directories and the index directory
+       // (not the indices themselves though)
+       if (inode->IsContainer() && !inode->IsIndex()) {
                status = _UpdateChildren(transaction, inode, newInodeID);
                if (status != B_OK)
                        RETURN_ERROR(status);

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

Commit:      f111ce9ecde50daba2af6186c7c606aa4f08a9ca

Author:      ahenriksson <sausageboy@xxxxxxxxx>
Date:        Tue Aug  7 20:22:55 2012 UTC

Added HashMap to fs_shell

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

diff --git a/headers/private/fs_shell/HashMap.h 
b/headers/private/fs_shell/HashMap.h
new file mode 100644
index 0000000..3660705
--- /dev/null
+++ b/headers/private/fs_shell/HashMap.h
@@ -0,0 +1,403 @@
+// HashMap.h
+//
+// Copyright (c) 2004-2007, Ingo Weinhold (bonefish@xxxxxxxxxxxxxxx)
+//
+// 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 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 MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+// THE AUTHORS OR COPYRIGHT HOLDERS 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 a copyright holder shall
+// not be used in advertising or otherwise to promote the sale, use or other
+// dealings in this Software without prior written authorization of the
+// copyright holder.
+
+#ifndef HASH_MAP_H
+#define HASH_MAP_H
+
+
+#include "fssh_types.h"
+
+#include "OpenHashTable.h"
+
+
+namespace FSShell {
+
+// HashMapElement
+template<typename Key, typename Value>
+class HashMapElement : public OpenHashElement {
+private:
+       typedef HashMapElement<Key, Value> Element;
+public:
+
+       HashMapElement() : OpenHashElement(), fKey(), fValue()
+       {
+               fNext = -1;
+       }
+
+       inline uint32_t Hash() const
+       {
+               return fKey.GetHashCode();
+       }
+
+       inline bool operator==(const OpenHashElement &_element) const
+       {
+               const Element &element = static_cast<const Element&>(_element);
+               return (fKey == element.fKey);
+       }
+
+       inline void Adopt(Element &element)
+       {
+               fKey = element.fKey;
+               fValue = element.fValue;
+       }
+
+       Key             fKey;
+       Value   fValue;
+};
+
+// HashMap
+template<typename Key, typename Value>
+class HashMap {
+public:
+       class Entry {
+       public:
+               Entry() {}
+               Entry(const Key& key, Value value) : key(key), value(value) {}
+
+               Key             key;
+               Value   value;
+       };
+
+       class Iterator {
+       private:
+               typedef HashMapElement<Key, Value>      Element;
+       public:
+               Iterator(const Iterator& other)
+                       :
+                       fMap(other.fMap),
+                       fIndex(other.fIndex),
+                       fElement(other.fElement),
+                       fLastElement(other.fElement)
+               {
+               }
+
+               bool HasNext() const
+               {
+                       return fElement;
+               }
+
+               Entry Next()
+               {
+                       if (!fElement)
+                               return Entry();
+                       Entry result(fElement->fKey, fElement->fValue);
+                       _FindNext();
+                       return result;
+               }
+
+               Value* NextValue()
+               {
+                       if (fElement == NULL)
+                               return NULL;
+
+                       Value* value = &fElement->fValue;
+                       _FindNext();
+                       return value;
+               }
+
+               Entry Remove()
+               {
+                       if (!fLastElement)
+                               return Entry();
+                       Entry result(fLastElement->fKey, fLastElement->fValue);
+                       fMap->fTable.Remove(fLastElement, true);
+                       fLastElement = NULL;
+                       return result;
+               }
+
+               Iterator& operator=(const Iterator& other)
+               {
+                       fMap = other.fMap;
+                       fIndex = other.fIndex;
+                       fElement = other.fElement;
+                       fLastElement = other.fLastElement;
+                       return *this;
+               }
+
+       private:
+               Iterator(const HashMap<Key, Value>* map)
+                       :
+                       fMap(const_cast<HashMap<Key, Value>*>(map)),
+                       fIndex(0),
+                       fElement(NULL),
+                       fLastElement(NULL)
+               {
+                       // find first
+                       _FindNext();
+               }
+
+               void _FindNext()
+               {
+                       fLastElement = fElement;
+                       if (fElement && fElement->fNext >= 0) {
+                               fElement = 
fMap->fTable.ElementAt(fElement->fNext);
+                               return;
+                       }
+                       fElement = NULL;
+                       int32_t arraySize = fMap->fTable.ArraySize();
+                       for (; !fElement && fIndex < arraySize; fIndex++)
+                               fElement = fMap->fTable.FindFirst(fIndex);
+               }
+
+       private:
+               friend class HashMap<Key, Value>;
+
+               HashMap<Key, Value>*    fMap;
+               int32_t                                 fIndex;
+               Element*                                fElement;
+               Element*                                fLastElement;
+       };
+
+       HashMap();
+       ~HashMap();
+
+       fssh_status_t InitCheck() const;
+
+       fssh_status_t Put(const Key& key, Value value);
+       Value Remove(const Key& key);
+       void Clear();
+       Value Get(const Key& key) const;
+       bool Get(const Key& key, Value*& _value) const;
+
+       bool ContainsKey(const Key& key) const;
+
+       int32_t Size() const;
+
+       Iterator GetIterator() const;
+
+protected:
+       typedef HashMapElement<Key, Value>      Element;
+       friend class Iterator;
+
+private:
+       Element *_FindElement(const Key& key) const;
+
+protected:
+       OpenHashElementArray<Element>                                           
        fElementArray;
+       OpenHashTable<Element, OpenHashElementArray<Element> >  fTable;
+};
+
+
+// HashKey32
+template<typename Value>
+struct HashKey32 {
+       HashKey32() {}
+       HashKey32(const Value& value) : value(value) {}
+
+       uint32_t GetHashCode() const
+       {
+               return (uint32_t)value;
+       }
+
+       HashKey32<Value> operator=(const HashKey32<Value>& other)
+       {
+               value = other.value;
+               return *this;
+       }
+
+       bool operator==(const HashKey32<Value>& other) const
+       {
+               return (value == other.value);
+       }
+
+       bool operator!=(const HashKey32<Value>& other) const
+       {
+               return (value != other.value);
+       }
+
+       Value   value;
+};
+
+
+// HashKey64
+template<typename Value>
+struct HashKey64 {
+       HashKey64() {}
+       HashKey64(const Value& value) : value(value) {}
+
+       uint32_t GetHashCode() const
+       {
+               uint64_t v = (uint64_t)value;
+               return (uint32_t)(v >> 32) ^ (uint32_t)v;
+       }
+
+       HashKey64<Value> operator=(const HashKey64<Value>& other)
+       {
+               value = other.value;
+               return *this;
+       }
+
+       bool operator==(const HashKey64<Value>& other) const
+       {
+               return (value == other.value);
+       }
+
+       bool operator!=(const HashKey64<Value>& other) const
+       {
+               return (value != other.value);
+       }
+
+       Value   value;
+};
+
+
+// HashMap
+
+// constructor
+template<typename Key, typename Value>
+HashMap<Key, Value>::HashMap()
+       :
+       fElementArray(1000),
+       fTable(1000, &fElementArray)
+{
+}
+
+// destructor
+template<typename Key, typename Value>
+HashMap<Key, Value>::~HashMap()
+{
+}
+
+// InitCheck
+template<typename Key, typename Value>
+fssh_status_t
+HashMap<Key, Value>::InitCheck() const
+{
+       return (fTable.InitCheck() && fElementArray.InitCheck()
+                       ? FSSH_B_OK : FSSH_B_NO_MEMORY);
+}
+
+// Put
+template<typename Key, typename Value>
+fssh_status_t
+HashMap<Key, Value>::Put(const Key& key, Value value)
+{
+       Element* element = _FindElement(key);
+       if (element) {
+               // already contains the key: just set the new value
+               element->fValue = value;
+               return FSSH_B_OK;
+       }
+       // does not contain the key yet: add an element
+       element = fTable.Add(key.GetHashCode());
+       if (!element)
+               return FSSH_B_NO_MEMORY;
+       element->fKey = key;
+       element->fValue = value;
+       return FSSH_B_OK;
+}
+
+// Remove
+template<typename Key, typename Value>
+Value
+HashMap<Key, Value>::Remove(const Key& key)
+{
+       Value value = Value();
+       if (Element* element = _FindElement(key)) {
+               value = element->fValue;
+               fTable.Remove(element);
+       }
+       return value;
+}
+
+// Clear
+template<typename Key, typename Value>
+void
+HashMap<Key, Value>::Clear()
+{
+       fTable.RemoveAll();
+}
+
+// Get
+template<typename Key, typename Value>
+Value
+HashMap<Key, Value>::Get(const Key& key) const
+{
+       if (Element* element = _FindElement(key))
+               return element->fValue;
+       return Value();
+}
+
+// Get
+template<typename Key, typename Value>
+bool
+HashMap<Key, Value>::Get(const Key& key, Value*& _value) const
+{
+       if (Element* element = _FindElement(key)) {
+               _value = &element->fValue;
+               return true;
+       }
+
+       return false;
+}
+
+// ContainsKey
+template<typename Key, typename Value>
+bool
+HashMap<Key, Value>::ContainsKey(const Key& key) const
+{
+       return _FindElement(key);
+}
+
+// Size
+template<typename Key, typename Value>
+int32_t
+HashMap<Key, Value>::Size() const
+{
+       return fTable.CountElements();
+}
+
+// GetIterator
+template<typename Key, typename Value>
+struct HashMap<Key, Value>::Iterator
+HashMap<Key, Value>::GetIterator() const
+{
+       return Iterator(this);
+}
+
+// _FindElement
+template<typename Key, typename Value>
+typename HashMap<Key, Value>::Element *
+HashMap<Key, Value>::_FindElement(const Key& key) const
+{
+       Element* element = fTable.FindFirst(key.GetHashCode());
+       while (element && element->fKey != key) {
+               if (element->fNext >= 0)
+                       element = fTable.ElementAt(element->fNext);
+               else
+                       element = NULL;
+       }
+       return element;
+}
+
+}      // namespace FSShell
+
+using FSShell::HashMap;
+using FSShell::HashKey32;
+using FSShell::HashKey64;
+
+#endif // HASH_MAP_H
diff --git a/headers/private/fs_shell/OpenHashTable.h 
b/headers/private/fs_shell/OpenHashTable.h
new file mode 100644
index 0000000..daa178e
--- /dev/null
+++ b/headers/private/fs_shell/OpenHashTable.h
@@ -0,0 +1,514 @@
+/*
+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 FSShell {
+
+template <class Element>
+class ElementVector {
+       // element vector for OpenHashTable needs to implement this
+       // interface
+public:
+       Element &At(int32_t index);
+       Element *Add();
+       int32_t IndexOf(const Element &) const;
+       void Remove(int32_t index);
+};
+
+class OpenHashElement {
+public:
+       uint32_t 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_t fNext;
+};
+
+const uint32_t 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_t 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_t elementHash) const;
+       Element *Add(uint32_t 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_t ElementIndex(const Element *) const;
+       Element *ElementAt(int32_t index) const;
+
+       int32_t ArraySize() const;
+       int32_t VectorSize() const;
+       int32_t CountElements() const;
+
+protected:
+       static int32_t OptimalSize(int32_t minSize);
+
+private:
+       bool _RehashIfNeeded();
+       bool _Rehash();
+
+       int32_t fArraySize;
+       int32_t fInitialSize;
+       int32_t fElementCount;
+       int32_t *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_t initialSize);
+       ~OpenHashElementArray();
+
+       bool InitCheck() const;
+
+       Element &At(int32_t index);
+       const Element &At(int32_t index) const;
+       Element *Add(const Element &);
+       Element *Add();
+       void Remove(int32_t index);
+       int32_t IndexOf(const Element &) const;
+       int32_t Size() const;
+
+private:
+       Element *fData;
+       int32_t fSize;
+       int32_t fNextFree;
+       int32_t fNextDeleted;
+};
+
+
+//-----------------------------------
+
+template<class Element, class ElementVec>
+OpenHashTable<Element, ElementVec>::OpenHashTable(int32_t 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_t*)calloc(fArraySize, sizeof(int32_t));
+       if (fHashArray) {
+               for (int32_t 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_t
+OpenHashTable<Element, ElementVec>::OptimalSize(int32_t minSize)
+{
+       for (int32_t index = 0; ; index++)
+               if (!kPrimes[index] || kPrimes[index] >= (uint32_t)minSize)
+                       return (int32_t)kPrimes[index];
+
+       return 0;
+}
+
+template<class Element, class ElementVec>
+Element *
+OpenHashTable<Element, ElementVec>::FindFirst(uint32_t 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_t
+OpenHashTable<Element, ElementVec>::ElementIndex(const Element *element) const
+{
+       return fElementVector->IndexOf(*element);
+}
+
+template<class Element, class ElementVec>
+Element *
+OpenHashTable<Element, ElementVec>::ElementAt(int32_t index) const
+{
+       return &fElementVector->At(index);
+}
+
+template<class Element, class ElementVec>
+int32_t
+OpenHashTable<Element, ElementVec>::ArraySize() const
+{
+        return fArraySize;
+}
+
+template<class Element, class ElementVec>
+int32_t
+OpenHashTable<Element, ElementVec>::VectorSize() const
+{
+        return fElementVector->Size();
+}
+
+template<class Element, class ElementVec>
+int32_t
+OpenHashTable<Element, ElementVec>::CountElements() const
+{
+        return fElementCount;
+}
+
+
+template<class Element, class ElementVec>
+Element *
+OpenHashTable<Element, ElementVec>::Add(uint32_t 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_t hash = element->Hash() % fArraySize;
+       int32_t 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_t 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_t i = 0; fElementCount > 0 && i < fArraySize; i++) {
+               int32_t index = fHashArray[i];
+               while (index >= 0) {
+                       Element* element = &fElementVector->At(index);
+                       int32_t 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_t newSize = int32_t(fElementCount * 1.73 * fMaxLoadFactor);
+       newSize = (fInitialSize > newSize ? fInitialSize : newSize);
+       if (newSize != fArraySize) {
+               // allocate a new array
+               int32_t *newHashArray = (int32_t*)calloc(newSize, 
sizeof(int32_t));
+               if (newHashArray) {
+                       // init the new hash array
+                       for (int32_t 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_t index = fHashArray[i];
+                               while (index >= 0) {
+                                       // insert the element in the new array
+                                       Element &element = 
fElementVector->At(index);
+                                       int32_t next = element.fNext;
+                                       uint32_t 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_t 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_t index)
+{
+       _OPEN_HASH_TABLE_ASSERT(index < fSize);
+       return fData[index];
+}
+
+template<class Element>
+const Element &
+OpenHashElementArray<Element>::At(int32_t index) const
+{
+       _OPEN_HASH_TABLE_ASSERT(index < fSize);
+       return fData[index];
+}
+
+template<class Element>
+int32_t
+OpenHashElementArray<Element>::IndexOf(const Element &element) const
+{
+       int32_t result = &element - fData;
+       if (result < 0 || result > fSize)
+               return -1;
+
+       return result;
+}
+
+template<class Element>
+int32_t
+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_t kGrowChunk = 10;
+#else
+const int32_t kGrowChunk = 1024;
+#endif
+
+template<class Element>
+Element *
+OpenHashElementArray<Element>::Add()
+{
+       int32_t index = fNextFree;
+       if (fNextDeleted >= 0) {
+               index = fNextDeleted;
+               fNextDeleted = At(index).fNext;
+       } else if (fNextFree >= fSize - 1) {
+               int32_t 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(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_t 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 FSShell
+
+using FSShell::OpenHashTable;
+
+#endif // __OPEN_HASH_TABLE__
diff --git a/headers/private/fs_shell/fssh_api_wrapper.h 
b/headers/private/fs_shell/fssh_api_wrapper.h
index 2338ba7..92c6240 100644
--- a/headers/private/fs_shell/fssh_api_wrapper.h
+++ b/headers/private/fs_shell/fssh_api_wrapper.h
@@ -42,6 +42,7 @@
 #include "fssh_types.h"
 
 #include "DoublyLinkedList.h"
+#include "HashMap.h"
 #include "SinglyLinkedList.h"
 #include "Stack.h"
 


Other related posts: