[haiku-commits] BRANCH ahenriksson-github.production - headers/private/fs_shell src/add-ons/kernel/file_systems/bfs
- From: ahenriksson-github.production <community@xxxxxxxxxxxx>
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Tue, 7 Aug 2012 22:49:22 +0200 (CEST)
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:
