Move most headers containing generic template classes out of kernel/util.
This follows on the move of BitUtils. Many of these headers were
already used in userspace.
Fixes #19849.
Diff
headers/private/shared/HashMap.h | 2 +-
headers/private/shared/HashSet.h | 2 +-
headers/private/shared/OpenHashTable.h | 1 -
headers/private/util/AtomicsHashTable.h | 79 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
headers/private/util/BumpAllocator.h | 112 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
headers/private/util/DoublyLinkedList.h | 681 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
headers/private/util/DoublyLinkedQueue.h | 368 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
headers/private/util/MultiHashTable.h | 183 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
headers/private/util/OpenHashTable.h | 497 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
headers/private/util/SimpleAllocator.h | 389 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
headers/private/util/SinglyLinkedList.h | 317 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
headers/private/util/SplayTree.h | 623 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
headers/private/util/Stack.h | 111 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
src/apps/showimage/ImageCache.h | 2 +-
src/apps/sudoku/Stack.h | 79 -------------------------------------------------------------------------------
src/apps/sudoku/SudokuSolver.cpp | 4 ++--
src/kits/media/Jamfile | 2 +-
src/kits/media/RealtimeAlloc.cpp | 2 +-
headers/build/private/util/BumpAllocator.h | 1 +
headers/build/private/util/DoublyLinkedList.h | 1 +
headers/build/private/util/OpenHashTable.h | 1 +
headers/build/private/util/SinglyLinkedList.h | 1 +
headers/private/kernel/util/AtomicsHashTable.h | 79 -------------------------------------------------------------------------------
headers/private/kernel/util/BumpAllocator.h | 112 --------------------------------------------------------------------------------
headers/private/kernel/util/DoublyLinkedList.h | 681 --------------------------------------------------------------------------------
headers/private/kernel/util/DoublyLinkedQueue.h | 368 --------------------------------------------------------------------------------
headers/private/kernel/util/MultiHashTable.h | 183 --------------------------------------------------------------------------------
headers/private/kernel/util/OpenHashTable.h | 497 --------------------------------------------------------------------------------
headers/private/kernel/util/SimpleAllocator.h | 389 --------------------------------------------------------------------------------
headers/private/kernel/util/SinglyLinkedList.h | 317 --------------------------------------------------------------------------------
headers/private/kernel/util/SplayTree.h | 623 --------------------------------------------------------------------------------
headers/private/kernel/util/Stack.h | 111 --------------------------------------------------------------------------------
src/add-ons/translators/rtf/RTF.h | 3 +--
src/add-ons/translators/rtf/Stack.h | 70 ----------------------------------------------------------------------
src/add-ons/translators/rtf/convert.cpp | 2 --
headers/build/private/kernel/util/BumpAllocator.h | 1 -
headers/build/private/kernel/util/DoublyLinkedList.h | 1 -
headers/build/private/kernel/util/OpenHashTable.h | 1 -
headers/build/private/kernel/util/SinglyLinkedList.h | 1 -
src/add-ons/kernel/file_systems/exfat/Inode.h | 3 ++-
src/add-ons/kernel/file_systems/exfat/Jamfile | 3 +--
src/add-ons/kernel/file_systems/exfat/Volume.h | 2 +-
src/add-ons/kernel/file_systems/userlandfs/server/FileSystem.h | 2 +-
src/add-ons/kernel/file_systems/userlandfs/server/Volume.h | 2 +-
44 files changed, 3378 insertions(+), 3531 deletions(-)
@@ -6,8 +6,8 @@
#ifndef HASH_MAP_H
#define HASH_MAP_H
#include <OpenHashTable.h>
#include <Locker.h>
#include <util/OpenHashTable.h>
#include "AutoLocker.h"
@@ -6,8 +6,8 @@
#ifndef HASH_SET_H
#define HASH_SET_H
#include <OpenHashTable.h>
#include <Locker.h>
#include <util/OpenHashTable.h>
#include "AutoLocker.h"
@@ -1,1 +1,0 @@
#include <../kernel/util/OpenHashTable.h>
@@ -1,0 +1,79 @@
/*
* Copyright 2025, Haiku, Inc. All rights reserved.
* Distributed under the terms of the MIT License.
*/
#ifndef _KERNEL_UTIL_ATOMICS_HASH_TABLE_H
#define _KERNEL_UTIL_ATOMICS_HASH_TABLE_H
#include <util/OpenHashTable.h>
#include <util/atomic.h>
template<typename Definition, bool AutoExpand = true,
bool CheckDuplicates = false>
class AtomicsHashTable : public BOpenHashTable<Definition,
AutoExpand, CheckDuplicates> {
public:
typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
typedef typename Definition::KeyType KeyType;
typedef typename Definition::ValueType ValueType;
AtomicsHashTable()
: HashTable() {}
AtomicsHashTable(const Definition& definition)
: HashTable(definition) {}
/*! \brief Inserts a value atomically.
If there's another item with an identical key, the new value will not
be inserted, and that value will be returned instead. If there's no
other value with the same key, the passed value will be inserted,
and NULL will be returned.
The caller is responsible for ensuring that no Remove()s or Resize()s
are invoked concurrently with this method.
*/
ValueType* InsertAtomic(ValueType* value)
{
KeyType key = HashTable::fDefinition.Key(value);
size_t index = HashTable::fDefinition.Hash(value) & (HashTable::fTableSize - 1);
HashTable::_Link(value) = NULL;
ValueType** link = &HashTable::fTable[index];
while (true) {
ValueType* existing = atomic_pointer_get(link);
if (existing == NULL) {
existing = atomic_pointer_test_and_set(link, value, existing);
if (existing == NULL) {
size_t& count = HashTable::fItemCount;
sizeof(size_t) == 4 ?
atomic_add((int32*)&count, 1) :
atomic_add64((int64*)&count, 1);
return NULL;
}
}
if (HashTable::fDefinition.Compare(key, existing))
return existing;
link = &HashTable::_Link(existing);
}
}
bool ResizeIfNeeded()
{
size_t resizeNeeded = HashTable::ResizeNeeded();
if (resizeNeeded == 0)
return true;
return HashTable::_Resize(resizeNeeded);
}
};
#endif
@@ -1,0 +1,112 @@
/*
* Copyright 2024, Haiku, Inc. All rights reserved.
* Distributed under the terms of the MIT License.
*/
#ifndef _BUMP_ALLOCATOR_H
#define _BUMP_ALLOCATOR_H
#include <stdlib.h>
#include <OS.h>
#include <SupportDefs.h>
template<size_t InlineDataSize = (16 * sizeof(void*)), size_t SlabSize = 4096>
class BumpAllocator {
public:
BumpAllocator()
:
fCurrentSlab((Slab*)fInlineData)
{
fCurrentSlab->previous = NULL;
fCurrentSlab->total = sizeof(fInlineData) - sizeof(Slab);
fCurrentSlab->remaining = fCurrentSlab->total;
}
~BumpAllocator()
{
if (fCurrentSlab != (Slab*)fInlineData)
Free(NULL);
if (!IsEmpty())
debugger("BumpAllocator: deleted with allocations still active!");
}
bool IsEmpty() const
{
return fCurrentSlab == (Slab*)fInlineData
&& fCurrentSlab->remaining == fCurrentSlab->total;
}
void* Allocate(size_t _size)
{
const size_t size = _size + sizeof(Allocation);
if (size > SlabSize)
debugger("BumpAllocator: can't allocate larger than the slab size");
if (fCurrentSlab->remaining < size) {
Slab* newSlab = (Slab*)malloc(SlabSize);
if (newSlab == NULL)
return NULL;
newSlab->previous = fCurrentSlab;
newSlab->total = SlabSize - sizeof(Slab);
newSlab->remaining = newSlab->total;
fCurrentSlab = newSlab;
}
fCurrentSlab->remaining -= size;
uint8* pointer = fCurrentSlab->data + fCurrentSlab->remaining;
Allocation* allocation = (Allocation*)pointer;
allocation->size = size;
return allocation->data;
}
void Free(void* _pointer)
{
if (fCurrentSlab->remaining == fCurrentSlab->total) {
Slab* previous = fCurrentSlab->previous;
free(fCurrentSlab);
fCurrentSlab = previous;
}
if (_pointer == NULL)
return;
Allocation* allocation = (((Allocation*)_pointer) - 1);
uint8* last = fCurrentSlab->data + fCurrentSlab->remaining;
if ((uint8*)allocation != last) {
debugger("BumpAllocator: out-of-order free");
return;
}
fCurrentSlab->remaining += allocation->size;
}
private:
#if __cplusplus >= 201103L
# define FLA_SIZE
#else
# define FLA_SIZE 0
#endif
struct Slab {
Slab* previous;
uint32 total;
uint32 remaining;
uint8 data[FLA_SIZE];
};
struct Allocation {
uint32 size;
uint32 _pad;
uint8 data[FLA_SIZE];
#undef FLA_SIZE
};
Slab* fCurrentSlab;
uint8 fInlineData[InlineDataSize - sizeof(Slab*)];
};
#endif
@@ -1,0 +1,681 @@
/*
* Copyright 2005-2009, Ingo Weinhold, bonefish@users.sf.net.
* Copyright 2006-2009, Axel Dörfler, axeld@pinc-software.de.
*
* Distributed under the terms of the MIT License.
*/
#ifndef KERNEL_UTIL_DOUBLY_LINKED_LIST_H
#define KERNEL_UTIL_DOUBLY_LINKED_LIST_H
#include <SupportDefs.h>
#ifdef _KERNEL_MODE
# include <debug.h>
# include <util/kernel_cpp.h>
# if !defined(_BOOT_MODE) && KDEBUG
# define DEBUG_DOUBLY_LINKED_LIST KDEBUG
# endif
#endif
#ifdef __cplusplus
template<typename Element>
class DoublyLinkedListLink {
public:
Element* next;
Element* previous;
};
template<typename Element>
class DoublyLinkedListLinkImpl {
private:
typedef DoublyLinkedListLink<Element> DLL_Link;
public:
DLL_Link* GetDoublyLinkedListLink()
{ return &fDoublyLinkedListLink; }
const DLL_Link* GetDoublyLinkedListLink() const
{ return &fDoublyLinkedListLink; }
private:
DLL_Link fDoublyLinkedListLink;
};
template<typename Element>
class DoublyLinkedListStandardGetLink {
private:
typedef DoublyLinkedListLink<Element> Link;
public:
inline Link* operator()(Element* element) const
{
return element->GetDoublyLinkedListLink();
}
inline const Link* operator()(const Element* element) const
{
return element->GetDoublyLinkedListLink();
}
};
template<typename Element,
DoublyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
class DoublyLinkedListMemberGetLink {
private:
typedef DoublyLinkedListLink<Element> Link;
public:
inline Link* operator()(Element* element) const
{
return &(element->*LinkMember);
}
inline const Link* operator()(const Element* element) const
{
return &(element->*LinkMember);
}
};
template<typename Element>
class DoublyLinkedListCLink {
private:
typedef DoublyLinkedListLink<Element> Link;
public:
inline Link* operator()(Element* element) const
{
return (Link*)&element->link;
}
inline const Link* operator()(const Element* element) const
{
return (const Link*)&element->link;
}
};
#define DOUBLY_LINKED_LIST_TEMPLATE_LIST \
template<typename Element, typename GetLink>
#define DOUBLY_LINKED_LIST_CLASS_NAME DoublyLinkedList<Element, GetLink>
template<typename Element,
typename GetLink = DoublyLinkedListStandardGetLink<Element> >
class DoublyLinkedList {
private:
typedef DoublyLinkedList<Element, GetLink> List;
typedef DoublyLinkedListLink<Element> Link;
public:
class Iterator {
public:
Iterator(List* list)
:
fList(list)
{
Rewind();
}
Iterator()
{
}
Iterator(const Iterator &other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element* Next()
{
fCurrent = fNext;
if (fNext)
fNext = fList->GetNext(fNext);
return fCurrent;
}
Element* Current()
{
return fCurrent;
}
Element* Remove()
{
Element* element = fCurrent;
if (fCurrent) {
fList->Remove(fCurrent);
fCurrent = NULL;
}
return element;
}
Iterator &operator=(const Iterator& other)
{
fList = other.fList;
fCurrent = other.fCurrent;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fCurrent = NULL;
fNext = fList->First();
}
private:
List* fList;
Element* fCurrent;
Element* fNext;
};
class ConstIterator {
public:
ConstIterator(const List* list)
:
fList(list)
{
Rewind();
}
ConstIterator(const ConstIterator& other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element* Next()
{
Element* element = fNext;
if (fNext)
fNext = fList->GetNext(fNext);
return element;
}
ConstIterator& operator=(const ConstIterator& other)
{
fList = other.fList;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fNext = fList->First();
}
private:
const List* fList;
Element* fNext;
};
class ReverseIterator {
public:
ReverseIterator(List* list)
:
fList(list)
{
Rewind();
}
ReverseIterator(const ReverseIterator& other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element* Next()
{
fCurrent = fNext;
if (fNext)
fNext = fList->GetPrevious(fNext);
return fCurrent;
}
Element* Remove()
{
Element* element = fCurrent;
if (fCurrent) {
fList->Remove(fCurrent);
fCurrent = NULL;
}
return element;
}
ReverseIterator &operator=(const ReverseIterator& other)
{
fList = other.fList;
fCurrent = other.fCurrent;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fCurrent = NULL;
fNext = fList->Last();
}
private:
List* fList;
Element* fCurrent;
Element* fNext;
};
class ConstReverseIterator {
public:
ConstReverseIterator(const List* list)
:
fList(list)
{
Rewind();
}
ConstReverseIterator(const ConstReverseIterator& other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element* Next()
{
Element* element = fNext;
if (fNext)
fNext = fList->GetPrevious(fNext);
return element;
}
ConstReverseIterator& operator=(const ConstReverseIterator& other)
{
fList = other.fList;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fNext = fList->Last();
}
private:
const List* fList;
Element* fNext;
};
public:
DoublyLinkedList() : fFirst(NULL), fLast(NULL) {}
~DoublyLinkedList() {}
inline bool IsEmpty() const { return (fFirst == NULL); }
inline void InsertBefore(Element* insertBefore, Element* element);
inline void InsertAfter(Element* insertAfter, Element* element);
inline void Insert(Element* element, bool back = true);
inline void Add(Element* element, bool back = true);
inline void Remove(Element* element);
inline void Swap(Element* a, Element* b);
inline void TakeFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList);
inline void RemoveAll();
inline void MakeEmpty() { RemoveAll(); }
inline Element* First() const { return fFirst; }
inline Element* Last() const { return fLast; }
inline Element* Head() const { return fFirst; }
inline Element* Tail() const { return fLast; }
inline Element* RemoveHead();
inline Element* RemoveTail();
static inline Element* GetPrevious(Element* element);
static inline Element* GetNext(Element* element);
inline bool Contains(Element* element) const;
inline int32 Count() const;
template<typename Less>
void Sort(const Less& less);
inline Iterator GetIterator() { return Iterator(this); }
inline ConstIterator GetIterator() const { return ConstIterator(this); }
inline ReverseIterator GetReverseIterator()
{ return ReverseIterator(this); }
inline ConstReverseIterator GetReverseIterator() const
{ return ConstReverseIterator(this); }
private:
inline void Insert(Element* before, Element* element);
private:
Element* fFirst;
Element* fLast;
static GetLink sGetLink;
};
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* element, bool back)
{
if (element) {
#if DEBUG_DOUBLY_LINKED_LIST
ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
"list: %p\n", this);
#endif
Link* elLink = sGetLink(element);
if (back) {
elLink->previous = fLast;
elLink->next = NULL;
if (fLast)
sGetLink(fLast)->next = element;
else
fFirst = element;
fLast = element;
} else {
elLink->previous = NULL;
elLink->next = fFirst;
if (fFirst)
sGetLink(fFirst)->previous = element;
else
fLast = element;
fFirst = element;
}
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::InsertBefore(Element* before, Element* element)
{
ASSERT(element != NULL);
if (before == NULL) {
Insert(element);
return;
}
#if DEBUG_DOUBLY_LINKED_LIST
ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
"list: %p\n", this);
#endif
Link* beforeLink = sGetLink(before);
Link* link = sGetLink(element);
link->next = before;
link->previous = beforeLink->previous;
beforeLink->previous = element;
if (link->previous != NULL)
sGetLink(link->previous)->next = element;
else
fFirst = element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::InsertAfter(Element* after, Element* element)
{
ASSERT(element != NULL);
if (after == NULL) {
Insert(element, false);
return;
}
#if DEBUG_DOUBLY_LINKED_LIST
ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
"list: %p\n", this);
#endif
Link* afterLink = sGetLink(after);
Link* link = sGetLink(element);
link->previous = after;
link->next = afterLink->next;
afterLink->next = element;
if (link->next != NULL)
sGetLink(link->next)->previous = element;
else
fLast = element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element)
{
InsertBefore(before, element);
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element* element, bool back)
{
Insert(element, back);
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element* element)
{
if (element == NULL)
return;
#if DEBUG_DOUBLY_LINKED_LIST
ASSERT_PRINT(fFirst != NULL && fLast != NULL
&& (fFirst != fLast || element == fFirst),
"list: %p, element: %p\n", this, element);
#endif
Link* elLink = sGetLink(element);
if (element == fFirst)
fFirst = elLink->next;
else
sGetLink(elLink->previous)->next = elLink->next;
if (element == fLast)
fLast = elLink->previous;
else
sGetLink(elLink->next)->previous = elLink->previous;
elLink->next = elLink->previous = NULL;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element* a, Element* b)
{
if (a && b && a != b) {
Element* aNext = sGetLink(a)->next;
Element* bNext = sGetLink(b)->next;
if (a == bNext) {
Remove(a);
Insert(b, a);
} else if (b == aNext) {
Remove(b);
Insert(a, b);
} else {
Remove(a);
Remove(b);
Insert(aNext, b);
Insert(bNext, a);
}
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::TakeFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList)
{
if (fromList && fromList->fFirst) {
if (fFirst) {
sGetLink(fLast)->next = fromList->fFirst;
sGetLink(fromList->fFirst)->previous = fLast;
fLast = fromList->fLast;
} else {
fFirst = fromList->fFirst;
fLast = fromList->fLast;
}
fromList->fFirst = NULL;
fromList->fLast = NULL;
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll()
{
fFirst = NULL;
fLast = NULL;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element*
DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
{
Element* element = Head();
Remove(element);
return element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element*
DOUBLY_LINKED_LIST_CLASS_NAME::RemoveTail()
{
Element* element = Tail();
Remove(element);
return element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element*
DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element* element)
{
Element* result = NULL;
if (element)
result = sGetLink(element)->previous;
return result;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element*
DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element)
{
Element* result = NULL;
if (element)
result = sGetLink(element)->next;
return result;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
bool
DOUBLY_LINKED_LIST_CLASS_NAME::Contains(Element* _element) const
{
for (Element* element = First(); element; element = GetNext(element)) {
if (element == _element)
return true;
}
return false;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
int32
DOUBLY_LINKED_LIST_CLASS_NAME::Count() const
{
int32 count = 0;
for (Element* element = First(); element; element = GetNext(element))
count++;
return count;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
template<typename Less>
void
DOUBLY_LINKED_LIST_CLASS_NAME::Sort(const Less& less)
{
Element* tail = Head();
while (tail != NULL) {
Element* leastElement = tail;
Element* element = tail;
while ((element = GetNext(element)) != NULL) {
if (less(element, leastElement))
leastElement = element;
}
if (leastElement != tail) {
Remove(leastElement);
InsertBefore(tail, leastElement);
} else
tail = GetNext(tail);
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
#endif
#endif
@@ -1,0 +1,368 @@
/*
* Copyright 2007, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
* Copyright 2005-2006, Ingo Weinhold, bonefish@users.sf.net. All rights reserved.
*
* Distributed under the terms of the MIT License.
*/
#ifndef KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H
#define KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H
#include <util/DoublyLinkedList.h>
/*!
A doubly linked queue is like a doubly linked list, but only has a pointer
to the head of the list, none to its tail.
*/
#ifdef __cplusplus
#define DOUBLY_LINKED_QUEUE_CLASS_NAME DoublyLinkedQueue<Element, GetLink>
template<typename Element,
typename GetLink = DoublyLinkedListStandardGetLink<Element> >
class DoublyLinkedQueue {
private:
typedef DoublyLinkedQueue<Element, GetLink> Queue;
typedef DoublyLinkedListLink<Element> Link;
public:
class Iterator {
public:
Iterator(Queue *queue)
:
fQueue(queue)
{
Rewind();
}
Iterator(const Iterator &other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element *Next()
{
fCurrent = fNext;
if (fNext)
fNext = fQueue->GetNext(fNext);
return fCurrent;
}
Element *Remove()
{
Element *element = fCurrent;
if (fCurrent) {
fQueue->Remove(fCurrent);
fCurrent = NULL;
}
return element;
}
Iterator &operator=(const Iterator &other)
{
fQueue = other.fQueue;
fCurrent = other.fCurrent;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fCurrent = NULL;
fNext = fQueue->First();
}
private:
Queue *fQueue;
Element *fCurrent;
Element *fNext;
};
class ConstIterator {
public:
ConstIterator(const Queue *queue)
:
fQueue(queue)
{
Rewind();
}
ConstIterator(const ConstIterator &other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element *Next()
{
Element *element = fNext;
if (fNext)
fNext = fQueue->GetNext(fNext);
return element;
}
ConstIterator &operator=(const ConstIterator &other)
{
fQueue = other.fQueue;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fNext = fQueue->First();
}
private:
const Queue *fQueue;
Element *fNext;
};
public:
DoublyLinkedQueue() : fFirst(NULL) {}
~DoublyLinkedQueue() {}
inline bool IsEmpty() const { return (fFirst == NULL); }
inline void Insert(Element *element);
inline void InsertBefore(Element *before, Element *element);
inline void Add(Element *element);
inline void Remove(Element *element);
inline void Swap(Element *a, Element *b);
inline void TakeFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList);
inline void RemoveAll();
inline void MakeEmpty() { RemoveAll(); }
inline Element *First() const { return fFirst; }
inline Element *Head() const { return fFirst; }
inline Element *RemoveHead();
inline Element *GetPrevious(Element *element) const;
inline Element *GetNext(Element *element) const;
inline int32 Size() const;
inline Iterator GetIterator() { return Iterator(this); }
inline ConstIterator GetIterator() const { return ConstIterator(this); }
private:
Element *fFirst;
static GetLink sGetLink;
};
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Insert(Element *element)
{
if (element) {
Link *elLink = sGetLink(element);
elLink->previous = NULL;
elLink->next = fFirst;
if (fFirst)
sGetLink(fFirst)->previous = element;
fFirst = element;
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::InsertBefore(Element *before, Element *element)
{
if (before == NULL) {
Insert(element);
return;
}
if (element == NULL)
return;
Link *beforeLink = sGetLink(before);
Link *link = sGetLink(element);
link->next = before;
link->previous = beforeLink->previous;
if (link->previous != NULL)
sGetLink(link->previous)->next = element;
beforeLink->previous = element;
if (fFirst == before)
fFirst = element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Add(Element *element)
{
Insert(element);
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Remove(Element *element)
{
if (element == NULL)
return;
#if DEBUG_DOUBLY_LINKED_LIST
ASSERT_PRINT(fFirst != NULL,
"queue: %p, element: %p\n", this, element);
#endif
Link *elLink = sGetLink(element);
if (element == fFirst)
fFirst = elLink->next;
else
sGetLink(elLink->previous)->next = elLink->next;
if (elLink->next)
sGetLink(elLink->next)->previous = elLink->previous;
elLink->next = elLink->previous = NULL;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Swap(Element *a, Element *b)
{
if (a && b && a != b) {
Link *aLink = sGetLink(a);
Link *bLink = sGetLink(b);
Element *aPrev = aLink->previous;
Element *bPrev = bLink->previous;
Element *aNext = aLink->next;
Element *bNext = bLink->next;
if (bPrev)
sGetLink(bPrev)->next = a;
else
fFirst = a;
if (bNext)
sGetLink(bNext)->previous = a;
aLink->previous = bPrev;
aLink->next = bNext;
if (aPrev)
sGetLink(aPrev)->next = b;
else
fFirst = b;
if (aNext)
sGetLink(aNext)->previous = b;
bLink->previous = aPrev;
bLink->next = aNext;
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::TakeFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList)
{
if (fromList && fromList->fFirst) {
if (fFirst) {
Element *element = fFirst;
Link *elLink;
while ((elLink = sGetLink(element))->next) {
element = elLink->next;
}
elLink->next = fromList->fFirst;
} else {
fFirst = fromList->fFirst;
}
fromList->fFirst = NULL;
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveAll()
{
Element *element = fFirst;
while (element) {
Link *elLink = sGetLink(element);
element = elLink->next;
elLink->previous = NULL;
elLink->next = NULL;
}
fFirst = NULL;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element *
DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveHead()
{
Element *element = Head();
Remove(element);
return element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element *
DOUBLY_LINKED_QUEUE_CLASS_NAME::GetPrevious(Element *element) const
{
Element *result = NULL;
if (element)
result = sGetLink(element)->previous;
return result;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element *
DOUBLY_LINKED_QUEUE_CLASS_NAME::GetNext(Element *element) const
{
Element *result = NULL;
if (element)
result = sGetLink(element)->next;
return result;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
int32
DOUBLY_LINKED_QUEUE_CLASS_NAME::Size() const
{
int32 count = 0;
for (Element* element = First(); element; element = GetNext(element))
count++;
return count;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
GetLink DOUBLY_LINKED_QUEUE_CLASS_NAME::sGetLink;
#endif
#endif
@@ -1,0 +1,183 @@
/*
* Copyright 2007, Hugo Santos. All Rights Reserved.
* Distributed under the terms of the MIT License.
*
* Authors:
* Hugo Santos, hugosantos@gmail.com
*/
#ifndef _KERNEL_UTIL_MULTI_HASH_TABLE_H
#define _KERNEL_UTIL_MULTI_HASH_TABLE_H
#include <KernelExport.h>
#include <util/kernel_cpp.h>
#include <util/OpenHashTable.h>
template<typename Definition, bool AutoExpand = true,
bool CheckDuplicates = false>
class MultiHashTable : private BOpenHashTable<Definition,
AutoExpand, CheckDuplicates> {
public:
typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
typedef MultiHashTable<Definition, AutoExpand, CheckDuplicates> MultiTable;
typedef typename HashTable::Iterator Iterator;
typedef typename Definition::KeyType KeyType;
typedef typename Definition::ValueType ValueType;
MultiHashTable()
: HashTable() {}
MultiHashTable(const Definition& definition)
: HashTable(definition) {}
status_t Init(size_t initialSize = HashTable::kMinimumSize)
{
return HashTable::Init(initialSize);
}
void Insert(ValueType *value)
{
if (AutoExpand
&& HashTable::fItemCount >= (HashTable::fTableSize * 200 / 256))
_Resize(HashTable::fTableSize * 2);
InsertUnchecked(value);
}
void InsertUnchecked(ValueType *value)
{
_Insert(HashTable::fTable, HashTable::fTableSize, value);
HashTable::fItemCount++;
}
bool Remove(ValueType *value)
{
if (!HashTable::RemoveUnchecked(value))
return false;
if (AutoExpand && HashTable::fTableSize > HashTable::kMinimumSize
&& HashTable::fItemCount < (HashTable::fTableSize * 50 / 256))
_Resize(HashTable::fTableSize / 2);
return true;
}
Iterator GetIterator() const { return HashTable::GetIterator(); }
class ValueIterator : protected Iterator {
public:
ValueIterator(const HashTable *table, size_t index, ValueType *value)
: fOriginalIndex(index), fOriginalValue(value)
{
Iterator::fTable = table;
Rewind();
}
bool HasNext() const
{
if (Iterator::fNext == NULL)
return false;
if (Iterator::fNext == fOriginalValue)
return true;
return ((const MultiTable *)Iterator::fTable)->_Definition().CompareValues(
fOriginalValue, Iterator::fNext);
}
void Rewind()
{
Iterator::fIndex = fOriginalIndex + 1;
Iterator::fNext = fOriginalValue;
}
ValueType *Next() { return Iterator::Next(); }
private:
size_t fOriginalIndex;
ValueType *fOriginalValue;
};
ValueIterator Lookup(const KeyType &key) const
{
size_t index = 0;
ValueType *slot = NULL;
if (HashTable::fTableSize > 0) {
index = HashTable::fDefinition.HashKey(key)
& (HashTable::fTableSize - 1);
slot = HashTable::fTable[index];
}
while (slot) {
if (HashTable::fDefinition.Compare(key, slot))
break;
slot = HashTable::_Link(slot);
}
if (slot == NULL)
return ValueIterator(this, HashTable::fTableSize, NULL);
return ValueIterator(this, index, slot);
}
private:
friend class ValueIterator;
const Definition &_Definition() const { return HashTable::fDefinition; }
void _Insert(ValueType **table, size_t tableSize, ValueType *value)
{
size_t index = HashTable::fDefinition.Hash(value) & (tableSize - 1);
ValueType *previous;
for (previous = table[index]; previous
&& !HashTable::fDefinition.CompareValues(previous, value);
previous = HashTable::_Link(previous));
if (previous) {
HashTable::_Link(value) = HashTable::_Link(previous);
HashTable::_Link(previous) = value;
} else {
HashTable::_Link(value) = table[index];
table[index] = value;
}
}
bool _Resize(size_t newSize)
{
ValueType **newTable = new ValueType *[newSize];
if (newTable == NULL)
return false;
for (size_t i = 0; i < newSize; i++)
newTable[i] = NULL;
if (HashTable::fTable) {
for (size_t i = 0; i < HashTable::fTableSize; i++) {
ValueType *bucket = HashTable::fTable[i];
while (bucket) {
ValueType *next = HashTable::_Link(bucket);
_Insert(newTable, newSize, bucket);
bucket = next;
}
}
delete [] HashTable::fTable;
}
HashTable::fTableSize = newSize;
HashTable::fTable = newTable;
return true;
}
};
#endif
@@ -1,0 +1,497 @@
/*
* Copyright 2007, Hugo Santos. All Rights Reserved.
* Distributed under the terms of the MIT License.
*/
#ifndef _KERNEL_UTIL_OPEN_HASH_TABLE_H
#define _KERNEL_UTIL_OPEN_HASH_TABLE_H
#include <OS.h>
#include <stdlib.h>
#include <string.h>
#ifdef _KERNEL_MODE
# include <KernelExport.h>
# include <util/kernel_cpp.h>
# include <util/TypeOperation.h>
#else
# include <new>
# include <TypeOperation.h>
#endif
/*!
The Definition template must have four methods: `HashKey', `Hash',
`Compare' and `GetLink;. It must also define several types as shown in the
following example:
struct Foo {
int bar;
Foo* fNext;
};
struct HashTableDefinition {
typedef int KeyType;
typedef Foo ValueType;
size_t HashKey(KeyType key) const
{
return key >> 1;
}
size_t Hash(ValueType* value) const
{
return HashKey(value->bar);
}
bool Compare(KeyType key, ValueType* value) const
{
return value->bar == key;
}
ValueType*& GetLink(ValueType* value) const
{
return value->fNext;
}
};
*/
struct MallocAllocator {
void* Allocate(size_t size) const
{
return malloc(size);
}
void Free(void* memory) const
{
free(memory);
}
};
/** Implements an hash table with open hashing, that is, colliding entries are
* stored in a linked list. The table may be made to adjust its number of slots
* depending on the load factor (this should be enabled unless the object is to
* be used at times where memory allocations aren't possible, such as code
* called by the memory allocator).
*
* The link between entries is part of the ValueType stored items, which makes
* sure the table can always accept new items and will never fail because it is
* out of memory (except at Init time).
*/
template<typename Definition, bool AutoExpand = true,
bool CheckDuplicates = false, typename Allocator = MallocAllocator>
class BOpenHashTable {
public:
typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
typedef typename Definition::KeyType KeyType;
typedef typename Definition::ValueType ValueType;
static const size_t kMinimumSize = 8;
BOpenHashTable()
:
fTableSize(0),
fItemCount(0),
fTable(NULL)
{
}
BOpenHashTable(const Definition& definition)
:
fDefinition(definition),
fTableSize(0),
fItemCount(0),
fTable(NULL)
{
}
BOpenHashTable(const Definition& definition, const Allocator& allocator)
:
fDefinition(definition),
fAllocator(allocator),
fTableSize(0),
fItemCount(0),
fTable(NULL)
{
}
~BOpenHashTable()
{
fAllocator.Free(fTable);
}
status_t Init(size_t initialSize = kMinimumSize)
{
if (initialSize > 0 && !_Resize(initialSize))
return B_NO_MEMORY;
return B_OK;
}
size_t TableSize() const
{
return fTableSize;
}
bool IsEmpty() const
{
return fItemCount == 0;
}
size_t CountElements() const
{
return fItemCount;
}
ValueType* Lookup(typename TypeOperation<KeyType>::ConstRefT key) const
{
if (fTableSize == 0)
return NULL;
size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
ValueType* slot = fTable[index];
while (slot) {
if (fDefinition.Compare(key, slot))
break;
slot = _Link(slot);
}
return slot;
}
status_t Insert(ValueType* value)
{
if (fTableSize == 0) {
if (!_Resize(kMinimumSize))
return B_NO_MEMORY;
} else if (AutoExpand && fItemCount >= (fTableSize * 200 / 256))
_Resize(fTableSize * 2);
InsertUnchecked(value);
return B_OK;
}
/*! \brief Inserts a value without resizing the table.
Use this method if you need to insert a value into the table while
iterating it, as regular insertion can invalidate iterators.
*/
void InsertUnchecked(ValueType* value)
{
if (CheckDuplicates && _ExhaustiveSearch(value)) {
#ifdef _KERNEL_MODE
panic("Hash Table: value already in table.");
#else
debugger("Hash Table: value already in table.");
#endif
}
_Insert(fTable, fTableSize, value);
fItemCount++;
}
bool Remove(ValueType* value)
{
if (!RemoveUnchecked(value))
return false;
if (AutoExpand && fTableSize > kMinimumSize
&& fItemCount < (fTableSize * 50 / 256))
_Resize(fTableSize / 2);
return true;
}
/*! \brief Removes a value without resizing the table.
Use this method if you need to remove a value from the table while
iterating it, as Remove can invalidate iterators.
Also use this method if you know you are going to reinsert the item soon
(possibly with a different hash) to avoid shrinking then growing the
table again.
*/
bool RemoveUnchecked(ValueType* value)
{
size_t index = fDefinition.Hash(value) & (fTableSize - 1);
ValueType* previous = NULL;
ValueType* slot = fTable[index];
while (slot) {
ValueType* next = _Link(slot);
if (value == slot) {
if (previous)
_Link(previous) = next;
else
fTable[index] = next;
break;
}
previous = slot;
slot = next;
}
if (slot == NULL)
return false;
if (CheckDuplicates && _ExhaustiveSearch(value)) {
#ifdef _KERNEL_MODE
panic("Hash Table: duplicate detected.");
#else
debugger("Hash Table: duplicate detected.");
#endif
}
fItemCount--;
return true;
}
/*! \brief Removes all elements from the hash table.
No resizing happens. The elements are not deleted. If \a returnElements
is \c true, the method returns all elements chained via their hash table
link.
*/
ValueType* Clear(bool returnElements = false)
{
if (fItemCount == 0)
return NULL;
ValueType* result = NULL;
if (returnElements) {
ValueType** nextPointer = &result;
for (size_t i = 0; i < fTableSize; i++) {
ValueType* element = fTable[i];
if (element != NULL) {
*nextPointer = element;
while (element != NULL) {
nextPointer = &_Link(element);
element = *nextPointer;
}
}
}
}
memset(this->fTable, 0, sizeof(ValueType*) * this->fTableSize);
fItemCount = 0;
return result;
}
/*! If the table needs resizing, the number of bytes for the required
allocation is returned. If no resizing is needed, 0 is returned.
*/
size_t ResizeNeeded() const
{
size_t size = fTableSize;
if (size == 0 || fItemCount >= (size * 200 / 256)) {
if (size == 0)
size = kMinimumSize;
while (fItemCount >= size * 200 / 256)
size <<= 1;
} else if (size > kMinimumSize && fItemCount < size * 50 / 256) {
while (fItemCount < size * 50 / 256)
size >>= 1;
if (size < kMinimumSize)
size = kMinimumSize;
}
if (size == fTableSize)
return 0;
return size * sizeof(ValueType*);
}
/*! Resizes the table using the given allocation. The allocation must not
be \c NULL. It must be of size \a size, which must be a value returned
earlier by ResizeNeeded(). If the size requirements have changed in the
meantime, the method free()s the given allocation and returns \c false,
unless \a force is \c true, in which case the supplied allocation is
used in any event.
Otherwise \c true is returned.
If \a oldTable is non-null and resizing is successful, the old table
will not be freed, but will be returned via this parameter instead.
*/
bool Resize(void* allocation, size_t size, bool force = false,
void** oldTable = NULL)
{
if (!force && size != ResizeNeeded()) {
fAllocator.Free(allocation);
return false;
}
_Resize((ValueType**)allocation, size / sizeof(ValueType*), oldTable);
return true;
}
/*! \brief Iterator for BOpenHashTable
The iterator is not invalidated when removing the current element from
the table, unless the removal triggers a resize.
*/
class Iterator {
public:
Iterator(const HashTable* table)
: fTable(table)
{
Rewind();
}
Iterator(const HashTable* table, size_t index, ValueType* value)
: fTable(table), fIndex(index), fNext(value) {}
bool HasNext() const { return fNext != NULL; }
ValueType* Next()
{
ValueType* current = fNext;
_GetNext();
return current;
}
void Rewind()
{
fIndex = 0;
fNext = NULL;
_GetNext();
}
protected:
Iterator() {}
void _GetNext()
{
if (fNext)
fNext = fTable->_Link(fNext);
while (fNext == NULL && fIndex < fTable->fTableSize)
fNext = fTable->fTable[fIndex++];
}
const HashTable* fTable;
size_t fIndex;
ValueType* fNext;
};
Iterator GetIterator() const
{
return Iterator(this);
}
Iterator GetIterator(typename TypeOperation<KeyType>::ConstRefT key) const
{
if (fTableSize == 0)
return Iterator(this, fTableSize, NULL);
size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
ValueType* slot = fTable[index];
while (slot) {
if (fDefinition.Compare(key, slot))
break;
slot = _Link(slot);
}
if (slot == NULL)
return Iterator(this, fTableSize, NULL);
return Iterator(this, index + 1, slot);
}
protected:
friend class Iterator;
void _Insert(ValueType** table, size_t tableSize, ValueType* value)
{
size_t index = fDefinition.Hash(value) & (tableSize - 1);
_Link(value) = table[index];
table[index] = value;
}
bool _Resize(size_t newSize)
{
ValueType** newTable
= (ValueType**)fAllocator.Allocate(sizeof(ValueType*) * newSize);
if (newTable == NULL)
return false;
_Resize(newTable, newSize);
return true;
}
void _Resize(ValueType** newTable, size_t newSize, void** _oldTable = NULL)
{
for (size_t i = 0; i < newSize; i++)
newTable[i] = NULL;
if (fTable) {
for (size_t i = 0; i < fTableSize; i++) {
ValueType* bucket = fTable[i];
while (bucket) {
ValueType* next = _Link(bucket);
_Insert(newTable, newSize, bucket);
bucket = next;
}
}
if (_oldTable != NULL)
*_oldTable = fTable;
else
fAllocator.Free(fTable);
} else if (_oldTable != NULL)
*_oldTable = NULL;
fTableSize = newSize;
fTable = newTable;
}
ValueType*& _Link(ValueType* bucket) const
{
return fDefinition.GetLink(bucket);
}
bool _ExhaustiveSearch(ValueType* value) const
{
for (size_t i = 0; i < fTableSize; i++) {
ValueType* bucket = fTable[i];
while (bucket) {
if (bucket == value)
return true;
bucket = _Link(bucket);
}
}
return false;
}
Definition fDefinition;
Allocator fAllocator;
size_t fTableSize;
size_t fItemCount;
ValueType** fTable;
};
#endif
@@ -1,0 +1,389 @@
/*
* Copyright 2003-2013, Axel Dörfler, axeld@pinc-software.de.
* Copyright 2005-2013, Ingo Weinhold, ingo_weinhold@gmx.de.
* Copyright 2025, Haiku, Inc. All rights reserved.
* Distributed under the terms of the MIT License.
*/
#ifndef _SIMPLE_ALLOCATOR_H
#define _SIMPLE_ALLOCATOR_H
#include <SupportDefs.h>
#include <util/SplayTree.h>
/*! This is a very simple malloc()/free() implementation - it only
manages a free list using a splay tree.
After heap_init() is called, all free memory is contained in one
big chunk, the only entry in the free chunk tree.
When memory is allocated, the smallest free chunk that contains
the requested size is split (or taken as a whole if it can't be
splitted anymore), and its lower half will be removed from the
free list.
The free list is ordered by size, starting with the smallest
free chunk available. When a chunk is freed, it will be joined
with its predecessor or successor, if possible.
*/
template<uint32 Alignment = 8>
class SimpleAllocator {
class Chunk {
public:
size_t CompleteSize() const
{
return fSize;
}
protected:
union {
uint32 fSize;
char fAlignment[Alignment];
};
};
class FreeChunk;
struct FreeChunkData : SplayTreeLink<FreeChunk> {
FreeChunk* Next() const
{
return fNext;
}
FreeChunk** NextLink()
{
return &fNext;
}
protected:
FreeChunk* fNext;
};
class FreeChunk : public Chunk, public FreeChunkData {
public:
void SetTo(size_t size)
{
Chunk::fSize = size;
FreeChunkData::fNext = NULL;
}
/*! Returns the amount of bytes that can be allocated
in this chunk.
*/
size_t Size() const
{
return (addr_t)this + Chunk::fSize - (addr_t)AllocatedAddress();
}
/*! Splits the upper half at the requested location and returns it. This chunk
will no longer be a valid FreeChunk object; only its fSize will be valid.
*/
FreeChunk* Split(size_t splitSize)
{
splitSize = Align(splitSize);
FreeChunk* chunk = (FreeChunk*)((addr_t)AllocatedAddress() + splitSize);
size_t newSize = (addr_t)chunk - (addr_t)this;
chunk->fSize = Chunk::fSize - newSize;
chunk->fNext = NULL;
Chunk::fSize = newSize;
return chunk;
}
/*! Checks if the specified chunk touches this chunk, so
that they could be joined.
*/
bool IsTouching(FreeChunk* chunk)
{
return chunk
&& (((uint8*)this + Chunk::fSize == (uint8*)chunk)
|| (uint8*)chunk + chunk->fSize == (uint8*)this);
}
/*! Joins the chunk to this chunk and returns the pointer
to the new chunk - which will either be one of the
two chunks.
Note, the chunks must be joinable, or else this method
doesn't work correctly. Use FreeChunk::IsTouching()
to check if this method can be applied.
*/
FreeChunk* Join(FreeChunk* chunk)
{
if (chunk < this) {
chunk->fSize += Chunk::fSize;
chunk->fNext = FreeChunkData::fNext;
return chunk;
}
Chunk::fSize += chunk->fSize;
FreeChunkData::fNext = chunk->fNext;
return this;
}
void* AllocatedAddress() const
{
return (void*)static_cast<const FreeChunkData*>(this);
}
static FreeChunk* SetToAllocated(void* allocated)
{
return static_cast<FreeChunk*>((FreeChunkData*)allocated);
}
};
struct FreeChunkKey {
FreeChunkKey(size_t size)
:
fSize(size),
fChunk(NULL)
{
}
FreeChunkKey(const FreeChunk* chunk)
:
fSize(chunk->Size()),
fChunk(chunk)
{
}
int Compare(const FreeChunk* chunk) const
{
size_t chunkSize = chunk->Size();
if (chunkSize != fSize)
return fSize < chunkSize ? -1 : 1;
if (fChunk == chunk)
return 0;
return fChunk < chunk ? -1 : 1;
}
private:
size_t fSize;
const FreeChunk* fChunk;
};
struct FreeChunkTreeDefinition {
typedef FreeChunkKey KeyType;
typedef FreeChunk NodeType;
static FreeChunkKey GetKey(const FreeChunk* node)
{
return FreeChunkKey(node);
}
static SplayTreeLink<FreeChunk>* GetLink(FreeChunk* node)
{
return node;
}
static int Compare(const FreeChunkKey& key, const FreeChunk* node)
{
return key.Compare(node);
}
static FreeChunk** GetListLink(FreeChunk* node)
{
return node->NextLink();
}
};
typedef IteratableSplayTree<FreeChunkTreeDefinition> FreeChunkTree;
public:
static inline size_t Align(size_t size, size_t alignment = Alignment)
{
return (size + alignment - 1) & ~(alignment - 1);
}
public:
SimpleAllocator()
:
fAvailable(0)
{
#ifdef DEBUG_MAX_HEAP_USAGE
fMaxHeapSize = fMaxHeapUsage = 0;
#endif
}
~SimpleAllocator()
{
}
void AddChunk(void* base, uint32 size)
{
FreeChunk* chunk = (FreeChunk*)base;
chunk->SetTo(size);
#ifdef DEBUG_MAX_HEAP_USAGE
fMaxHeapSize += chunk->Size();
#endif
_InsertChunk(chunk);
}
uint32 Available() const { return fAvailable; }
void* Allocate(uint32 size)
{
if (size == 0)
return NULL;
if (size < sizeof(FreeChunkData))
size = sizeof(FreeChunkData);
size = Align(size);
if (size > fAvailable)
return NULL;
FreeChunk* chunk = fFreeChunkTree.FindClosest(FreeChunkKey(size), true, true);
if (chunk == NULL) {
return NULL;
}
fFreeChunkTree.Remove(chunk);
fAvailable -= chunk->Size();
void* allocated = chunk->AllocatedAddress();
if (chunk->Size() >= (size + Align(sizeof(FreeChunk)))) {
FreeChunk* freeChunk = chunk->Split(size);
fFreeChunkTree.Insert(freeChunk);
fAvailable += freeChunk->Size();
}
#ifdef DEBUG_MAX_HEAP_USAGE
fMaxHeapUsage = std::max(fMaxHeapUsage, fMaxHeapSize - fAvailable);
#endif
#ifdef DEBUG_ALLOCATIONS
memset(allocated, 0xcc, chunk->Size());
#endif
return allocated;
}
uint32 UsableSize(void* allocated)
{
FreeChunk* chunk = FreeChunk::SetToAllocated(allocated);
return chunk->Size();
}
void* Reallocate(void* oldBuffer, uint32 newSize)
{
size_t oldSize = 0;
if (oldBuffer != NULL) {
oldSize = UsableSize(oldBuffer);
if (oldSize >= newSize && (oldSize < 128 || newSize > (oldSize / 3)))
return oldBuffer;
}
void* newBuffer = Allocate(newSize);
if (newBuffer == NULL)
return NULL;
if (oldBuffer != NULL) {
memcpy(newBuffer, oldBuffer, (oldSize < newSize) ? oldSize : newSize);
Free(oldBuffer);
}
return newBuffer;
}
void Free(void* allocated)
{
if (allocated == NULL)
return;
FreeChunk* freedChunk = FreeChunk::SetToAllocated(allocated);
#ifdef DEBUG_VALIDATE_HEAP_ON_FREE
if (freedChunk->Size() > (fMaxHeapSize - fAvailable)) {
panic("freed chunk %p clobbered (%#zx)!\n", freedChunk,
freedChunk->Size());
}
{
FreeChunk* chunk = fFreeChunkTree.FindMin();
while (chunk) {
if (chunk->Size() > fAvailable || freedChunk == chunk)
panic("invalid chunk in free list (%p (%zu)), or double free\n",
chunk, chunk->Size());
chunk = chunk->Next();
}
}
#endif
#ifdef DEBUG_ALLOCATIONS
for (uint32 i = 0; i < (freedChunk->Size() / 4); i++)
((uint32*)allocated)[i] = 0xdeadbeef;
#endif
_InsertChunk(freedChunk);
}
#ifdef DEBUG_MAX_HEAP_USAGE
uint32 MaxHeapSize() const { return fMaxHeapSize; }
uint32 MaxHeapUsage() const { return fMaxHeapUsage; }
#endif
void DumpChunks()
{
FreeChunk* chunk = fFreeChunkTree.FindMin();
while (chunk != NULL) {
printf("\t%p: chunk size = %ld, end = %p, next = %p\n", chunk,
chunk->Size(), (uint8*)chunk + chunk->CompleteSize(),
chunk->Next());
chunk = chunk->Next();
}
}
private:
void _InsertChunk(FreeChunk* freedChunk)
{
FreeChunk* chunk = fFreeChunkTree.FindMin();
int32 joinCount = 0;
while (chunk != NULL) {
FreeChunk* nextChunk = chunk->Next();
if (chunk->IsTouching(freedChunk)) {
fFreeChunkTree.Remove(chunk);
fAvailable -= chunk->Size();
freedChunk = chunk->Join(freedChunk);
if (++joinCount == 2)
break;
}
chunk = nextChunk;
}
fFreeChunkTree.Insert(freedChunk);
fAvailable += freedChunk->Size();
#ifdef DEBUG_MAX_HEAP_USAGE
fMaxHeapUsage = std::max(fMaxHeapUsage, fMaxHeapSize - fAvailable);
#endif
}
private:
FreeChunkTree fFreeChunkTree;
uint32 fAvailable;
#ifdef DEBUG_MAX_HEAP_USAGE
uint32 fMaxHeapSize, fMaxHeapUsage;
#endif
};
#endif
@@ -1,0 +1,317 @@
/*
* Copyright 2008, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
* Copyright 2005-2010, Ingo Weinhold, ingo_weinhold@gmx.de.
*
* Distributed under the terms of the MIT License.
*/
#ifndef KERNEL_UTIL_SINGLY_LINKED_LIST_H
#define KERNEL_UTIL_SINGLY_LINKED_LIST_H
#include <SupportDefs.h>
#ifdef __cplusplus
template<typename Element>
class SinglyLinkedListLink {
public:
SinglyLinkedListLink() : next(NULL) {}
~SinglyLinkedListLink() {}
Element* next;
};
template<typename Element>
class SinglyLinkedListLinkImpl {
private:
typedef SinglyLinkedListLink<Element> SLL_Link;
public:
SinglyLinkedListLinkImpl() : fSinglyLinkedListLink() {}
~SinglyLinkedListLinkImpl() {}
SLL_Link* GetSinglyLinkedListLink()
{ return &fSinglyLinkedListLink; }
const SLL_Link* GetSinglyLinkedListLink() const
{ return &fSinglyLinkedListLink; }
private:
SLL_Link fSinglyLinkedListLink;
};
template<typename Element>
class SinglyLinkedListStandardGetLink {
private:
typedef SinglyLinkedListLink<Element> Link;
public:
inline Link* operator()(Element* element) const
{
return element->GetSinglyLinkedListLink();
}
inline const Link* operator()(const Element* element) const
{
return element->GetSinglyLinkedListLink();
}
};
template<typename Element,
SinglyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
class SinglyLinkedListMemberGetLink {
private:
typedef SinglyLinkedListLink<Element> Link;
public:
inline Link* operator()(Element* element) const
{
return &(element->*LinkMember);
}
inline const Link* operator()(const Element* element) const
{
return &(element->*LinkMember);
}
};
#define SINGLY_LINKED_LIST_TEMPLATE_LIST \
template<typename Element, typename GetLink>
#define SINGLY_LINKED_LIST_CLASS_NAME SinglyLinkedList<Element, GetLink>
template<typename Element,
typename GetLink = SinglyLinkedListStandardGetLink<Element> >
class SinglyLinkedList {
private:
typedef SinglyLinkedList<Element, GetLink> List;
typedef SinglyLinkedListLink<Element> Link;
public:
class ConstIterator {
public:
ConstIterator(const List* list)
:
fList(list)
{
Rewind();
}
ConstIterator(const ConstIterator& other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element* Next()
{
Element* element = fNext;
if (fNext)
fNext = fList->GetNext(fNext);
return element;
}
ConstIterator& operator=(const ConstIterator& other)
{
fList = other.fList;
fNext = other.fNext;
return* this;
}
void Rewind()
{
fNext = fList->First();
}
private:
const List* fList;
Element* fNext;
};
public:
SinglyLinkedList() : fFirst(NULL) {}
~SinglyLinkedList() {}
inline bool IsEmpty() const { return (fFirst == NULL); }
inline void Add(Element* element);
inline bool Remove(Element* element);
inline void Remove(Element* previous, Element* element);
inline void TakeFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList);
inline void RemoveAll();
inline void MakeEmpty() { RemoveAll(); }
inline Element* First() const { return fFirst; }
inline Element* Head() const { return fFirst; }
inline Element* RemoveHead();
inline Element* GetNext(Element* element) const;
inline int32 Count() const;
inline ConstIterator GetIterator() const { return ConstIterator(this); }
private:
Element *fFirst;
static GetLink sGetLink;
};
SINGLY_LINKED_LIST_TEMPLATE_LIST
void
SINGLY_LINKED_LIST_CLASS_NAME::Add(Element* element)
{
if (element != NULL) {
sGetLink(element)->next = fFirst;
fFirst = element;
}
}
/*! Removes \a element from the list.
It is safe to call the list with a \c NULL element or an element that isn't
in the list.
\param element The element to be removed.
\return \c true, if the element was in the list and has been removed,
\c false otherwise.
*/
SINGLY_LINKED_LIST_TEMPLATE_LIST
bool
SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* element)
{
if (element == NULL)
return false;
Element* next = fFirst;
Element* last = NULL;
while (element != next) {
if (next == NULL)
return false;
last = next;
next = sGetLink(next)->next;
}
Link* elementLink = sGetLink(element);
if (last == NULL)
fFirst = elementLink->next;
else
sGetLink(last)->next = elementLink->next;
elementLink->next = NULL;
return true;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
void
SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* previous, Element* element)
{
Link* elementLink = sGetLink(element);
if (previous == NULL)
fFirst = elementLink->next;
else
sGetLink(previous)->next = elementLink->next;
elementLink->next = NULL;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
void
SINGLY_LINKED_LIST_CLASS_NAME::TakeFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList)
{
if (fromList->fFirst == NULL)
return;
if (fFirst == NULL) {
fFirst = fromList->fFirst;
fromList->fFirst = NULL;
return;
}
Element* tail = fFirst;
while (Element* next = sGetLink(tail)->next)
tail = next;
sGetLink(tail)->next = fromList->fFirst;
fromList->fFirst = NULL;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
void
SINGLY_LINKED_LIST_CLASS_NAME::RemoveAll()
{
Element* element = fFirst;
while (element) {
Link* elLink = sGetLink(element);
element = elLink->next;
elLink->next = NULL;
}
fFirst = NULL;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
Element*
SINGLY_LINKED_LIST_CLASS_NAME::RemoveHead()
{
Element* element = Head();
Remove(element);
return element;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
Element*
SINGLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const
{
Element* result = NULL;
if (element)
result = sGetLink(element)->next;
return result;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
int32
SINGLY_LINKED_LIST_CLASS_NAME::Count() const
{
int32 count = 0;
for (Element* element = First(); element; element = GetNext(element))
count++;
return count;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
GetLink SINGLY_LINKED_LIST_CLASS_NAME::sGetLink;
#endif
#endif
@@ -1,0 +1,623 @@
/*
* Copyright 2008-2009, Ingo Weinhold <ingo_weinhold@gmx.de>.
* Distributed under the terms of the MIT License.
*
* Original Java implementation:
* Available at http:
* Author: Danny Sleator <sleator@cs.cmu.edu>
* This code is in the public domain.
*/
#ifndef KERNEL_UTIL_SPLAY_TREE_H
#define KERNEL_UTIL_SPLAY_TREE_H
/*! Implements two classes:
SplayTree: A top-down splay tree.
IteratableSplayTree: Extends SplayTree by a singly-linked list to make it
cheaply iteratable (requires another pointer per node).
Both classes are templatized over a definition parameter with the following
(or a compatible) interface:
struct SplayTreeDefinition {
typedef xxx KeyType;
typedef yyy NodeType;
static const KeyType& GetKey(const NodeType* node);
static SplayTreeLink<NodeType>* GetLink(NodeType* node);
static int Compare(const KeyType& key, const NodeType* node);
static NodeType** GetListLink(NodeType* node);
};
*/
template<typename Node>
struct SplayTreeLink {
Node* left;
Node* right;
};
template<typename Definition>
class SplayTree {
protected:
typedef typename Definition::KeyType Key;
typedef typename Definition::NodeType Node;
typedef SplayTreeLink<Node> Link;
public:
SplayTree()
:
fRoot(NULL)
{
}
/*!
Insert into the tree.
\param node the item to insert.
*/
bool Insert(Node* node)
{
Link* nodeLink = Definition::GetLink(node);
if (fRoot == NULL) {
fRoot = node;
nodeLink->left = NULL;
nodeLink->right = NULL;
return true;
}
Key key = Definition::GetKey(node);
_Splay(key);
int c = Definition::Compare(key, fRoot);
if (c == 0)
return false;
Link* rootLink = Definition::GetLink(fRoot);
if (c < 0) {
nodeLink->left = rootLink->left;
nodeLink->right = fRoot;
rootLink->left = NULL;
} else {
nodeLink->right = rootLink->right;
nodeLink->left = fRoot;
rootLink->right = NULL;
}
fRoot = node;
return true;
}
Node* Remove(const Key& key)
{
if (fRoot == NULL)
return NULL;
_Splay(key);
if (Definition::Compare(key, fRoot) != 0)
return NULL;
Node* node = fRoot;
Link* rootLink = Definition::GetLink(fRoot);
if (rootLink->left == NULL) {
fRoot = rootLink->right;
} else {
Node* temp = rootLink->right;
fRoot = rootLink->left;
_Splay(key);
Definition::GetLink(fRoot)->right = temp;
}
return node;
}
/*!
Remove from the tree.
\param node the item to remove.
*/
bool Remove(Node* node)
{
Key key = Definition::GetKey(node);
_Splay(key);
if (node != fRoot)
return false;
Link* rootLink = Definition::GetLink(fRoot);
if (rootLink->left == NULL) {
fRoot = rootLink->right;
} else {
Node* temp = rootLink->right;
fRoot = rootLink->left;
_Splay(key);
Definition::GetLink(fRoot)->right = temp;
}
return true;
}
/*!
Find the smallest item in the tree.
*/
Node* FindMin()
{
if (fRoot == NULL)
return NULL;
Node* node = fRoot;
while (Node* left = Definition::GetLink(node)->left)
node = left;
_Splay(Definition::GetKey(node));
return node;
}
/*!
Find the largest item in the tree.
*/
Node* FindMax()
{
if (fRoot == NULL)
return NULL;
Node* node = fRoot;
while (Node* right = Definition::GetLink(node)->right)
node = right;
_Splay(Definition::GetKey(node));
return node;
}
/*!
Find an item in the tree.
*/
Node* Lookup(const Key& key)
{
if (fRoot == NULL)
return NULL;
_Splay(key);
return Definition::Compare(key, fRoot) == 0 ? fRoot : NULL;
}
Node* Root() const
{
return fRoot;
}
/*!
Test if the tree is logically empty.
\return true if empty, false otherwise.
*/
bool IsEmpty() const
{
return fRoot == NULL;
}
Node* PreviousDontSplay(const Key& key) const
{
Node* closestNode = NULL;
Node* node = fRoot;
while (node != NULL) {
if (Definition::Compare(key, node) > 0) {
closestNode = node;
node = Definition::GetLink(node)->right;
} else
node = Definition::GetLink(node)->left;
}
return closestNode;
}
Node* FindClosest(const Key& key, bool greater, bool orEqual)
{
if (fRoot == NULL)
return NULL;
_Splay(key);
Node* closestNode = NULL;
Node* node = fRoot;
while (node != NULL) {
int compare = Definition::Compare(key, node);
if (compare == 0 && orEqual)
return node;
if (greater) {
if (compare < 0) {
closestNode = node;
node = Definition::GetLink(node)->left;
} else
node = Definition::GetLink(node)->right;
} else {
if (compare > 0) {
closestNode = node;
node = Definition::GetLink(node)->right;
} else
node = Definition::GetLink(node)->left;
}
}
return closestNode;
}
SplayTree& operator=(const SplayTree& other)
{
fRoot = other.fRoot;
return *this;
}
private:
/*!
Internal method to perform a top-down splay.
_Splay(key) does the splay operation on the given key.
If key is in the tree, then the node containing
that key becomes the root. If key is not in the tree,
then after the splay, key.root is either the greatest key
< key in the tree, or the least key > key in the tree.
This means, among other things, that if you splay with
a key that's larger than any in the tree, the rightmost
node of the tree becomes the root. This property is used
in the Remove() method.
*/
void _Splay(const Key& key) {
Link headerLink;
headerLink.left = headerLink.right = NULL;
Link* lLink = &headerLink;
Link* rLink = &headerLink;
Node* l = NULL;
Node* r = NULL;
Node* t = fRoot;
for (;;) {
int c = Definition::Compare(key, t);
if (c < 0) {
Node*& left = Definition::GetLink(t)->left;
if (left == NULL)
break;
if (Definition::Compare(key, left) < 0) {
Node* y = left;
Link* yLink = Definition::GetLink(y);
left = yLink->right;
yLink->right = t;
t = y;
if (yLink->left == NULL)
break;
}
rLink->left = t;
r = t;
rLink = Definition::GetLink(r);
t = rLink->left;
} else if (c > 0) {
Node*& right = Definition::GetLink(t)->right;
if (right == NULL)
break;
if (Definition::Compare(key, right) > 0) {
Node* y = right;
Link* yLink = Definition::GetLink(y);
right = yLink->left;
yLink->left = t;
t = y;
if (yLink->right == NULL)
break;
}
lLink->right = t;
l = t;
lLink = Definition::GetLink(l);
t = lLink->right;
} else
break;
}
Link* tLink = Definition::GetLink(t);
lLink->right = tLink->left;
rLink->left = tLink->right;
tLink->left = headerLink.right;
tLink->right = headerLink.left;
fRoot = t;
}
protected:
Node* fRoot;
};
template<typename Definition>
class IteratableSplayTree {
protected:
typedef typename Definition::KeyType Key;
typedef typename Definition::NodeType Node;
typedef SplayTreeLink<Node> Link;
typedef IteratableSplayTree<Definition> Tree;
public:
class Iterator {
public:
Iterator()
{
}
Iterator(const Iterator& other)
{
*this = other;
}
Iterator(Tree* tree)
:
fTree(tree)
{
Rewind();
}
Iterator(Tree* tree, Node* next)
:
fTree(tree),
fCurrent(NULL),
fNext(next)
{
}
bool HasNext() const
{
return fNext != NULL;
}
Node* Next()
{
fCurrent = fNext;
if (fNext != NULL)
fNext = *Definition::GetListLink(fNext);
return fCurrent;
}
Node* Current()
{
return fCurrent;
}
Node* Remove()
{
Node* element = fCurrent;
if (fCurrent) {
fTree->Remove(fCurrent);
fCurrent = NULL;
}
return element;
}
Iterator &operator=(const Iterator &other)
{
fTree = other.fTree;
fCurrent = other.fCurrent;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fCurrent = NULL;
fNext = fTree->fFirst;
}
private:
Tree* fTree;
Node* fCurrent;
Node* fNext;
};
class ConstIterator {
public:
ConstIterator()
{
}
ConstIterator(const ConstIterator& other)
{
*this = other;
}
ConstIterator(const Tree* tree)
:
fTree(tree)
{
Rewind();
}
ConstIterator(const Tree* tree, Node* next)
:
fTree(tree),
fNext(next)
{
}
bool HasNext() const
{
return fNext != NULL;
}
Node* Next()
{
Node* node = fNext;
if (fNext != NULL)
fNext = *Definition::GetListLink(fNext);
return node;
}
ConstIterator &operator=(const ConstIterator &other)
{
fTree = other.fTree;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fNext = fTree->fFirst;
}
private:
const Tree* fTree;
Node* fNext;
};
IteratableSplayTree()
:
fTree(),
fFirst(NULL)
{
}
bool Insert(Node* node)
{
if (!fTree.Insert(node))
return false;
Node** previousNext;
if (Node* previous = fTree.PreviousDontSplay(Definition::GetKey(node)))
previousNext = Definition::GetListLink(previous);
else
previousNext = &fFirst;
*Definition::GetListLink(node) = *previousNext;
*previousNext = node;
return true;
}
Node* Remove(const Key& key)
{
Node* node = fTree.Remove(key);
if (node == NULL)
return NULL;
Node** previousNext;
if (Node* previous = fTree.PreviousDontSplay(key))
previousNext = Definition::GetListLink(previous);
else
previousNext = &fFirst;
*previousNext = *Definition::GetListLink(node);
return node;
}
bool Remove(Node* node)
{
if (!fTree.Remove(node))
return false;
Node** previousNext;
if (Node* previous = fTree.PreviousDontSplay(Definition::GetKey(node)))
previousNext = Definition::GetListLink(previous);
else
previousNext = &fFirst;
*previousNext = *Definition::GetListLink(node);
return true;
}
Node* Lookup(const Key& key)
{
return fTree.Lookup(key);
}
Node* Root() const
{
return fTree.Root();
}
/*!
Test if the tree is logically empty.
\return true if empty, false otherwise.
*/
bool IsEmpty() const
{
return fTree.IsEmpty();
}
Node* PreviousDontSplay(const Key& key)
{
return fTree.PreviousDontSplay(key);
}
Node* FindClosest(const Key& key, bool greater, bool orEqual)
{
return fTree.FindClosest(key, greater, orEqual);
}
Node* FindMin()
{
return fTree.FindMin();
}
Node* FindMax()
{
return fTree.FindMax();
}
Iterator GetIterator()
{
return Iterator(this);
}
ConstIterator GetIterator() const
{
return ConstIterator(this);
}
Iterator GetIterator(const Key& key, bool greater, bool orEqual)
{
return Iterator(this, fTree.FindClosest(key, greater, orEqual));
}
ConstIterator GetIterator(const Key& key, bool greater, bool orEqual) const
{
return ConstIterator(this, FindClosest(key, greater, orEqual));
}
IteratableSplayTree& operator=(const IteratableSplayTree& other)
{
fTree = other.fTree;
fFirst = other.fFirst;
return *this;
}
protected:
friend class Iterator;
friend class ConstIterator;
SplayTree<Definition> fTree;
Node* fFirst;
};
#endif
@@ -1,0 +1,111 @@
/*
* Copyright 2001-2008, Axel Dörfler, axeld@pinc-software.de.
* This file may be used under the terms of the MIT License.
*/
#ifndef KERNEL_UTIL_STACK_H
#define KERNEL_UTIL_STACK_H
#include <stdlib.h>
#include <SupportDefs.h>
#include <AutoDeleter.h>
template<class T> class Stack {
public:
Stack()
:
fArray(NULL),
fUsed(0),
fMax(0)
{
}
~Stack()
{
free(fArray);
}
bool IsEmpty() const
{
return fUsed == 0;
}
void MakeEmpty()
{
fUsed = 0;
}
status_t Push(T value)
{
if (fUsed >= fMax) {
fMax += 16;
T *newArray = (T *)realloc(fArray, fMax * sizeof(T));
if (newArray == NULL)
return B_NO_MEMORY;
fArray = newArray;
}
fArray[fUsed++] = value;
return B_OK;
}
bool Pop(T *value)
{
if (fUsed == 0)
return false;
*value = fArray[--fUsed];
return true;
}
T *Array()
{
return fArray;
}
int32 CountItems() const
{
return fUsed;
}
private:
T *fArray;
int32 fUsed;
int32 fMax;
};
template<typename T> class StackDelete {
public:
inline void operator()(Stack<T>* stack)
{
if (stack == NULL)
return;
T item;
while (stack->Pop(&item)) {
delete item;
}
delete stack;
}
};
template<typename T> class StackDeleter
: public BPrivate::AutoDeleter<Stack<T>, StackDelete<T> > {
public:
StackDeleter()
{
}
StackDeleter(Stack<T>* stack)
: BPrivate::AutoDeleter<Stack<T>, StackDelete<T> >(stack)
{
}
};
#endif
@@ -14,8 +14,8 @@
#include <Locker.h>
#include <String.h>
#include <kernel/util/DoublyLinkedList.h>
#include <Referenceable.h>
#include <util/DoublyLinkedList.h>
class BBitmap;
@@ -1,79 +1,0 @@
/* Stack - a template stack class (plus some handy methods)
*
* Copyright 2001-2005, Axel Dörfler, axeld@pinc-software.de.
* This file may be used under the terms of the MIT License.
*/
#ifndef KERNEL_UTIL_STACK_H
#define KERNEL_UTIL_STACK_H
#include <SupportDefs.h>
#include <stdlib.h>
template<class T> class Stack {
public:
Stack()
:
fArray(NULL),
fUsed(0),
fMax(0)
{
}
~Stack()
{
free(fArray);
}
bool IsEmpty() const
{
return fUsed == 0;
}
void MakeEmpty()
{
fUsed = 0;
}
status_t Push(T value)
{
if (fUsed >= fMax) {
fMax += 16;
T *newArray = (T *)realloc(fArray, fMax * sizeof(T));
if (newArray == NULL)
return B_NO_MEMORY;
fArray = newArray;
}
fArray[fUsed++] = value;
return B_OK;
}
bool Pop(T *value)
{
if (fUsed == 0)
return false;
*value = fArray[--fUsed];
return true;
}
T *Array()
{
return fArray;
}
int32 CountItems() const
{
return fUsed;
}
private:
T *fArray;
int32 fUsed;
int32 fMax;
};
#endif
@@ -1,13 +1,13 @@
/*
* Copyright 2007, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
* Distributed under the terms of the MIT License.
*/
#include "SudokuSolver.h"
#include <util/Stack.h>
#include "SudokuField.h"
#include "Stack.h"
struct SolutionStep {
@@ -1,8 +1,8 @@
SubDir HAIKU_TOP src kits media ;
AddResources libmedia.so : libmedia.rdef ;
UsePrivateHeaders app media kernel shared ;
UsePrivateHeaders app media shared ;
UsePrivateHeaders [ FDirName media experimental ] ;
UsePrivateHeaders [ FDirName interface ] ;
@@ -19,7 +19,7 @@
#include <OS.h>
#include <locks.h>
#include <kernel/util/DoublyLinkedList.h>
#include <util/DoublyLinkedList.h>
@@ -1,0 +1,1 @@
#include <../private/util/BumpAllocator.h>
@@ -1,0 +1,1 @@
#include <../private/util/DoublyLinkedList.h>
@@ -1,0 +1,1 @@
#include <../private/util/OpenHashTable.h>
@@ -1,0 +1,1 @@
#include <../private/util/SinglyLinkedList.h>
@@ -1,79 +1,0 @@
/*
* Copyright 2025, Haiku, Inc. All rights reserved.
* Distributed under the terms of the MIT License.
*/
#ifndef _KERNEL_UTIL_ATOMICS_HASH_TABLE_H
#define _KERNEL_UTIL_ATOMICS_HASH_TABLE_H
#include <util/OpenHashTable.h>
#include <util/atomic.h>
template<typename Definition, bool AutoExpand = true,
bool CheckDuplicates = false>
class AtomicsHashTable : public BOpenHashTable<Definition,
AutoExpand, CheckDuplicates> {
public:
typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
typedef typename Definition::KeyType KeyType;
typedef typename Definition::ValueType ValueType;
AtomicsHashTable()
: HashTable() {}
AtomicsHashTable(const Definition& definition)
: HashTable(definition) {}
/*! \brief Inserts a value atomically.
If there's another item with an identical key, the new value will not
be inserted, and that value will be returned instead. If there's no
other value with the same key, the passed value will be inserted,
and NULL will be returned.
The caller is responsible for ensuring that no Remove()s or Resize()s
are invoked concurrently with this method.
*/
ValueType* InsertAtomic(ValueType* value)
{
KeyType key = HashTable::fDefinition.Key(value);
size_t index = HashTable::fDefinition.Hash(value) & (HashTable::fTableSize - 1);
HashTable::_Link(value) = NULL;
ValueType** link = &HashTable::fTable[index];
while (true) {
ValueType* existing = atomic_pointer_get(link);
if (existing == NULL) {
existing = atomic_pointer_test_and_set(link, value, existing);
if (existing == NULL) {
size_t& count = HashTable::fItemCount;
sizeof(size_t) == 4 ?
atomic_add((int32*)&count, 1) :
atomic_add64((int64*)&count, 1);
return NULL;
}
}
if (HashTable::fDefinition.Compare(key, existing))
return existing;
link = &HashTable::_Link(existing);
}
}
bool ResizeIfNeeded()
{
size_t resizeNeeded = HashTable::ResizeNeeded();
if (resizeNeeded == 0)
return true;
return HashTable::_Resize(resizeNeeded);
}
};
#endif
@@ -1,112 +1,0 @@
/*
* Copyright 2024, Haiku, Inc. All rights reserved.
* Distributed under the terms of the MIT License.
*/
#ifndef _BUMP_ALLOCATOR_H
#define _BUMP_ALLOCATOR_H
#include <stdlib.h>
#include <OS.h>
#include <SupportDefs.h>
template<size_t InlineDataSize = (16 * sizeof(void*)), size_t SlabSize = 4096>
class BumpAllocator {
public:
BumpAllocator()
:
fCurrentSlab((Slab*)fInlineData)
{
fCurrentSlab->previous = NULL;
fCurrentSlab->total = sizeof(fInlineData) - sizeof(Slab);
fCurrentSlab->remaining = fCurrentSlab->total;
}
~BumpAllocator()
{
if (fCurrentSlab != (Slab*)fInlineData)
Free(NULL);
if (!IsEmpty())
debugger("BumpAllocator: deleted with allocations still active!");
}
bool IsEmpty() const
{
return fCurrentSlab == (Slab*)fInlineData
&& fCurrentSlab->remaining == fCurrentSlab->total;
}
void* Allocate(size_t _size)
{
const size_t size = _size + sizeof(Allocation);
if (size > SlabSize)
debugger("BumpAllocator: can't allocate larger than the slab size");
if (fCurrentSlab->remaining < size) {
Slab* newSlab = (Slab*)malloc(SlabSize);
if (newSlab == NULL)
return NULL;
newSlab->previous = fCurrentSlab;
newSlab->total = SlabSize - sizeof(Slab);
newSlab->remaining = newSlab->total;
fCurrentSlab = newSlab;
}
fCurrentSlab->remaining -= size;
uint8* pointer = fCurrentSlab->data + fCurrentSlab->remaining;
Allocation* allocation = (Allocation*)pointer;
allocation->size = size;
return allocation->data;
}
void Free(void* _pointer)
{
if (fCurrentSlab->remaining == fCurrentSlab->total) {
Slab* previous = fCurrentSlab->previous;
free(fCurrentSlab);
fCurrentSlab = previous;
}
if (_pointer == NULL)
return;
Allocation* allocation = (((Allocation*)_pointer) - 1);
uint8* last = fCurrentSlab->data + fCurrentSlab->remaining;
if ((uint8*)allocation != last) {
debugger("BumpAllocator: out-of-order free");
return;
}
fCurrentSlab->remaining += allocation->size;
}
private:
#if __cplusplus >= 201103L
# define FLA_SIZE
#else
# define FLA_SIZE 0
#endif
struct Slab {
Slab* previous;
uint32 total;
uint32 remaining;
uint8 data[FLA_SIZE];
};
struct Allocation {
uint32 size;
uint32 _pad;
uint8 data[FLA_SIZE];
#undef FLA_SIZE
};
Slab* fCurrentSlab;
uint8 fInlineData[InlineDataSize - sizeof(Slab*)];
};
#endif
@@ -1,681 +1,0 @@
/*
* Copyright 2005-2009, Ingo Weinhold, bonefish@users.sf.net.
* Copyright 2006-2009, Axel Dörfler, axeld@pinc-software.de.
*
* Distributed under the terms of the MIT License.
*/
#ifndef KERNEL_UTIL_DOUBLY_LINKED_LIST_H
#define KERNEL_UTIL_DOUBLY_LINKED_LIST_H
#include <SupportDefs.h>
#ifdef _KERNEL_MODE
# include <debug.h>
# include <util/kernel_cpp.h>
# if !defined(_BOOT_MODE) && KDEBUG
# define DEBUG_DOUBLY_LINKED_LIST KDEBUG
# endif
#endif
#ifdef __cplusplus
template<typename Element>
class DoublyLinkedListLink {
public:
Element* next;
Element* previous;
};
template<typename Element>
class DoublyLinkedListLinkImpl {
private:
typedef DoublyLinkedListLink<Element> DLL_Link;
public:
DLL_Link* GetDoublyLinkedListLink()
{ return &fDoublyLinkedListLink; }
const DLL_Link* GetDoublyLinkedListLink() const
{ return &fDoublyLinkedListLink; }
private:
DLL_Link fDoublyLinkedListLink;
};
template<typename Element>
class DoublyLinkedListStandardGetLink {
private:
typedef DoublyLinkedListLink<Element> Link;
public:
inline Link* operator()(Element* element) const
{
return element->GetDoublyLinkedListLink();
}
inline const Link* operator()(const Element* element) const
{
return element->GetDoublyLinkedListLink();
}
};
template<typename Element,
DoublyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
class DoublyLinkedListMemberGetLink {
private:
typedef DoublyLinkedListLink<Element> Link;
public:
inline Link* operator()(Element* element) const
{
return &(element->*LinkMember);
}
inline const Link* operator()(const Element* element) const
{
return &(element->*LinkMember);
}
};
template<typename Element>
class DoublyLinkedListCLink {
private:
typedef DoublyLinkedListLink<Element> Link;
public:
inline Link* operator()(Element* element) const
{
return (Link*)&element->link;
}
inline const Link* operator()(const Element* element) const
{
return (const Link*)&element->link;
}
};
#define DOUBLY_LINKED_LIST_TEMPLATE_LIST \
template<typename Element, typename GetLink>
#define DOUBLY_LINKED_LIST_CLASS_NAME DoublyLinkedList<Element, GetLink>
template<typename Element,
typename GetLink = DoublyLinkedListStandardGetLink<Element> >
class DoublyLinkedList {
private:
typedef DoublyLinkedList<Element, GetLink> List;
typedef DoublyLinkedListLink<Element> Link;
public:
class Iterator {
public:
Iterator(List* list)
:
fList(list)
{
Rewind();
}
Iterator()
{
}
Iterator(const Iterator &other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element* Next()
{
fCurrent = fNext;
if (fNext)
fNext = fList->GetNext(fNext);
return fCurrent;
}
Element* Current()
{
return fCurrent;
}
Element* Remove()
{
Element* element = fCurrent;
if (fCurrent) {
fList->Remove(fCurrent);
fCurrent = NULL;
}
return element;
}
Iterator &operator=(const Iterator& other)
{
fList = other.fList;
fCurrent = other.fCurrent;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fCurrent = NULL;
fNext = fList->First();
}
private:
List* fList;
Element* fCurrent;
Element* fNext;
};
class ConstIterator {
public:
ConstIterator(const List* list)
:
fList(list)
{
Rewind();
}
ConstIterator(const ConstIterator& other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element* Next()
{
Element* element = fNext;
if (fNext)
fNext = fList->GetNext(fNext);
return element;
}
ConstIterator& operator=(const ConstIterator& other)
{
fList = other.fList;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fNext = fList->First();
}
private:
const List* fList;
Element* fNext;
};
class ReverseIterator {
public:
ReverseIterator(List* list)
:
fList(list)
{
Rewind();
}
ReverseIterator(const ReverseIterator& other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element* Next()
{
fCurrent = fNext;
if (fNext)
fNext = fList->GetPrevious(fNext);
return fCurrent;
}
Element* Remove()
{
Element* element = fCurrent;
if (fCurrent) {
fList->Remove(fCurrent);
fCurrent = NULL;
}
return element;
}
ReverseIterator &operator=(const ReverseIterator& other)
{
fList = other.fList;
fCurrent = other.fCurrent;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fCurrent = NULL;
fNext = fList->Last();
}
private:
List* fList;
Element* fCurrent;
Element* fNext;
};
class ConstReverseIterator {
public:
ConstReverseIterator(const List* list)
:
fList(list)
{
Rewind();
}
ConstReverseIterator(const ConstReverseIterator& other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element* Next()
{
Element* element = fNext;
if (fNext)
fNext = fList->GetPrevious(fNext);
return element;
}
ConstReverseIterator& operator=(const ConstReverseIterator& other)
{
fList = other.fList;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fNext = fList->Last();
}
private:
const List* fList;
Element* fNext;
};
public:
DoublyLinkedList() : fFirst(NULL), fLast(NULL) {}
~DoublyLinkedList() {}
inline bool IsEmpty() const { return (fFirst == NULL); }
inline void InsertBefore(Element* insertBefore, Element* element);
inline void InsertAfter(Element* insertAfter, Element* element);
inline void Insert(Element* element, bool back = true);
inline void Add(Element* element, bool back = true);
inline void Remove(Element* element);
inline void Swap(Element* a, Element* b);
inline void TakeFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList);
inline void RemoveAll();
inline void MakeEmpty() { RemoveAll(); }
inline Element* First() const { return fFirst; }
inline Element* Last() const { return fLast; }
inline Element* Head() const { return fFirst; }
inline Element* Tail() const { return fLast; }
inline Element* RemoveHead();
inline Element* RemoveTail();
static inline Element* GetPrevious(Element* element);
static inline Element* GetNext(Element* element);
inline bool Contains(Element* element) const;
inline int32 Count() const;
template<typename Less>
void Sort(const Less& less);
inline Iterator GetIterator() { return Iterator(this); }
inline ConstIterator GetIterator() const { return ConstIterator(this); }
inline ReverseIterator GetReverseIterator()
{ return ReverseIterator(this); }
inline ConstReverseIterator GetReverseIterator() const
{ return ConstReverseIterator(this); }
private:
inline void Insert(Element* before, Element* element);
private:
Element* fFirst;
Element* fLast;
static GetLink sGetLink;
};
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* element, bool back)
{
if (element) {
#if DEBUG_DOUBLY_LINKED_LIST
ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
"list: %p\n", this);
#endif
Link* elLink = sGetLink(element);
if (back) {
elLink->previous = fLast;
elLink->next = NULL;
if (fLast)
sGetLink(fLast)->next = element;
else
fFirst = element;
fLast = element;
} else {
elLink->previous = NULL;
elLink->next = fFirst;
if (fFirst)
sGetLink(fFirst)->previous = element;
else
fLast = element;
fFirst = element;
}
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::InsertBefore(Element* before, Element* element)
{
ASSERT(element != NULL);
if (before == NULL) {
Insert(element);
return;
}
#if DEBUG_DOUBLY_LINKED_LIST
ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
"list: %p\n", this);
#endif
Link* beforeLink = sGetLink(before);
Link* link = sGetLink(element);
link->next = before;
link->previous = beforeLink->previous;
beforeLink->previous = element;
if (link->previous != NULL)
sGetLink(link->previous)->next = element;
else
fFirst = element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::InsertAfter(Element* after, Element* element)
{
ASSERT(element != NULL);
if (after == NULL) {
Insert(element, false);
return;
}
#if DEBUG_DOUBLY_LINKED_LIST
ASSERT_PRINT(fFirst == NULL ? fLast == NULL : fLast != NULL,
"list: %p\n", this);
#endif
Link* afterLink = sGetLink(after);
Link* link = sGetLink(element);
link->previous = after;
link->next = afterLink->next;
afterLink->next = element;
if (link->next != NULL)
sGetLink(link->next)->previous = element;
else
fLast = element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::Insert(Element* before, Element* element)
{
InsertBefore(before, element);
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::Add(Element* element, bool back)
{
Insert(element, back);
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::Remove(Element* element)
{
if (element == NULL)
return;
#if DEBUG_DOUBLY_LINKED_LIST
ASSERT_PRINT(fFirst != NULL && fLast != NULL
&& (fFirst != fLast || element == fFirst),
"list: %p, element: %p\n", this, element);
#endif
Link* elLink = sGetLink(element);
if (element == fFirst)
fFirst = elLink->next;
else
sGetLink(elLink->previous)->next = elLink->next;
if (element == fLast)
fLast = elLink->previous;
else
sGetLink(elLink->next)->previous = elLink->previous;
elLink->next = elLink->previous = NULL;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::Swap(Element* a, Element* b)
{
if (a && b && a != b) {
Element* aNext = sGetLink(a)->next;
Element* bNext = sGetLink(b)->next;
if (a == bNext) {
Remove(a);
Insert(b, a);
} else if (b == aNext) {
Remove(b);
Insert(a, b);
} else {
Remove(a);
Remove(b);
Insert(aNext, b);
Insert(bNext, a);
}
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::TakeFrom(DOUBLY_LINKED_LIST_CLASS_NAME* fromList)
{
if (fromList && fromList->fFirst) {
if (fFirst) {
sGetLink(fLast)->next = fromList->fFirst;
sGetLink(fromList->fFirst)->previous = fLast;
fLast = fromList->fLast;
} else {
fFirst = fromList->fFirst;
fLast = fromList->fLast;
}
fromList->fFirst = NULL;
fromList->fLast = NULL;
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_LIST_CLASS_NAME::RemoveAll()
{
fFirst = NULL;
fLast = NULL;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element*
DOUBLY_LINKED_LIST_CLASS_NAME::RemoveHead()
{
Element* element = Head();
Remove(element);
return element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element*
DOUBLY_LINKED_LIST_CLASS_NAME::RemoveTail()
{
Element* element = Tail();
Remove(element);
return element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element*
DOUBLY_LINKED_LIST_CLASS_NAME::GetPrevious(Element* element)
{
Element* result = NULL;
if (element)
result = sGetLink(element)->previous;
return result;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element*
DOUBLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element)
{
Element* result = NULL;
if (element)
result = sGetLink(element)->next;
return result;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
bool
DOUBLY_LINKED_LIST_CLASS_NAME::Contains(Element* _element) const
{
for (Element* element = First(); element; element = GetNext(element)) {
if (element == _element)
return true;
}
return false;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
int32
DOUBLY_LINKED_LIST_CLASS_NAME::Count() const
{
int32 count = 0;
for (Element* element = First(); element; element = GetNext(element))
count++;
return count;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
template<typename Less>
void
DOUBLY_LINKED_LIST_CLASS_NAME::Sort(const Less& less)
{
Element* tail = Head();
while (tail != NULL) {
Element* leastElement = tail;
Element* element = tail;
while ((element = GetNext(element)) != NULL) {
if (less(element, leastElement))
leastElement = element;
}
if (leastElement != tail) {
Remove(leastElement);
InsertBefore(tail, leastElement);
} else
tail = GetNext(tail);
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
GetLink DOUBLY_LINKED_LIST_CLASS_NAME::sGetLink;
#endif
#endif
@@ -1,368 +1,0 @@
/*
* Copyright 2007, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
* Copyright 2005-2006, Ingo Weinhold, bonefish@users.sf.net. All rights reserved.
*
* Distributed under the terms of the MIT License.
*/
#ifndef KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H
#define KERNEL_UTIL_DOUBLY_LINKED_QUEUE_H
#include <util/DoublyLinkedList.h>
/*!
A doubly linked queue is like a doubly linked list, but only has a pointer
to the head of the list, none to its tail.
*/
#ifdef __cplusplus
#define DOUBLY_LINKED_QUEUE_CLASS_NAME DoublyLinkedQueue<Element, GetLink>
template<typename Element,
typename GetLink = DoublyLinkedListStandardGetLink<Element> >
class DoublyLinkedQueue {
private:
typedef DoublyLinkedQueue<Element, GetLink> Queue;
typedef DoublyLinkedListLink<Element> Link;
public:
class Iterator {
public:
Iterator(Queue *queue)
:
fQueue(queue)
{
Rewind();
}
Iterator(const Iterator &other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element *Next()
{
fCurrent = fNext;
if (fNext)
fNext = fQueue->GetNext(fNext);
return fCurrent;
}
Element *Remove()
{
Element *element = fCurrent;
if (fCurrent) {
fQueue->Remove(fCurrent);
fCurrent = NULL;
}
return element;
}
Iterator &operator=(const Iterator &other)
{
fQueue = other.fQueue;
fCurrent = other.fCurrent;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fCurrent = NULL;
fNext = fQueue->First();
}
private:
Queue *fQueue;
Element *fCurrent;
Element *fNext;
};
class ConstIterator {
public:
ConstIterator(const Queue *queue)
:
fQueue(queue)
{
Rewind();
}
ConstIterator(const ConstIterator &other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element *Next()
{
Element *element = fNext;
if (fNext)
fNext = fQueue->GetNext(fNext);
return element;
}
ConstIterator &operator=(const ConstIterator &other)
{
fQueue = other.fQueue;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fNext = fQueue->First();
}
private:
const Queue *fQueue;
Element *fNext;
};
public:
DoublyLinkedQueue() : fFirst(NULL) {}
~DoublyLinkedQueue() {}
inline bool IsEmpty() const { return (fFirst == NULL); }
inline void Insert(Element *element);
inline void InsertBefore(Element *before, Element *element);
inline void Add(Element *element);
inline void Remove(Element *element);
inline void Swap(Element *a, Element *b);
inline void TakeFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList);
inline void RemoveAll();
inline void MakeEmpty() { RemoveAll(); }
inline Element *First() const { return fFirst; }
inline Element *Head() const { return fFirst; }
inline Element *RemoveHead();
inline Element *GetPrevious(Element *element) const;
inline Element *GetNext(Element *element) const;
inline int32 Size() const;
inline Iterator GetIterator() { return Iterator(this); }
inline ConstIterator GetIterator() const { return ConstIterator(this); }
private:
Element *fFirst;
static GetLink sGetLink;
};
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Insert(Element *element)
{
if (element) {
Link *elLink = sGetLink(element);
elLink->previous = NULL;
elLink->next = fFirst;
if (fFirst)
sGetLink(fFirst)->previous = element;
fFirst = element;
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::InsertBefore(Element *before, Element *element)
{
if (before == NULL) {
Insert(element);
return;
}
if (element == NULL)
return;
Link *beforeLink = sGetLink(before);
Link *link = sGetLink(element);
link->next = before;
link->previous = beforeLink->previous;
if (link->previous != NULL)
sGetLink(link->previous)->next = element;
beforeLink->previous = element;
if (fFirst == before)
fFirst = element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Add(Element *element)
{
Insert(element);
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Remove(Element *element)
{
if (element == NULL)
return;
#if DEBUG_DOUBLY_LINKED_LIST
ASSERT_PRINT(fFirst != NULL,
"queue: %p, element: %p\n", this, element);
#endif
Link *elLink = sGetLink(element);
if (element == fFirst)
fFirst = elLink->next;
else
sGetLink(elLink->previous)->next = elLink->next;
if (elLink->next)
sGetLink(elLink->next)->previous = elLink->previous;
elLink->next = elLink->previous = NULL;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::Swap(Element *a, Element *b)
{
if (a && b && a != b) {
Link *aLink = sGetLink(a);
Link *bLink = sGetLink(b);
Element *aPrev = aLink->previous;
Element *bPrev = bLink->previous;
Element *aNext = aLink->next;
Element *bNext = bLink->next;
if (bPrev)
sGetLink(bPrev)->next = a;
else
fFirst = a;
if (bNext)
sGetLink(bNext)->previous = a;
aLink->previous = bPrev;
aLink->next = bNext;
if (aPrev)
sGetLink(aPrev)->next = b;
else
fFirst = b;
if (aNext)
sGetLink(aNext)->previous = b;
bLink->previous = aPrev;
bLink->next = aNext;
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::TakeFrom(DOUBLY_LINKED_QUEUE_CLASS_NAME *fromList)
{
if (fromList && fromList->fFirst) {
if (fFirst) {
Element *element = fFirst;
Link *elLink;
while ((elLink = sGetLink(element))->next) {
element = elLink->next;
}
elLink->next = fromList->fFirst;
} else {
fFirst = fromList->fFirst;
}
fromList->fFirst = NULL;
}
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
void
DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveAll()
{
Element *element = fFirst;
while (element) {
Link *elLink = sGetLink(element);
element = elLink->next;
elLink->previous = NULL;
elLink->next = NULL;
}
fFirst = NULL;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element *
DOUBLY_LINKED_QUEUE_CLASS_NAME::RemoveHead()
{
Element *element = Head();
Remove(element);
return element;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element *
DOUBLY_LINKED_QUEUE_CLASS_NAME::GetPrevious(Element *element) const
{
Element *result = NULL;
if (element)
result = sGetLink(element)->previous;
return result;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
Element *
DOUBLY_LINKED_QUEUE_CLASS_NAME::GetNext(Element *element) const
{
Element *result = NULL;
if (element)
result = sGetLink(element)->next;
return result;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
int32
DOUBLY_LINKED_QUEUE_CLASS_NAME::Size() const
{
int32 count = 0;
for (Element* element = First(); element; element = GetNext(element))
count++;
return count;
}
DOUBLY_LINKED_LIST_TEMPLATE_LIST
GetLink DOUBLY_LINKED_QUEUE_CLASS_NAME::sGetLink;
#endif
#endif
@@ -1,183 +1,0 @@
/*
* Copyright 2007, Hugo Santos. All Rights Reserved.
* Distributed under the terms of the MIT License.
*
* Authors:
* Hugo Santos, hugosantos@gmail.com
*/
#ifndef _KERNEL_UTIL_MULTI_HASH_TABLE_H
#define _KERNEL_UTIL_MULTI_HASH_TABLE_H
#include <KernelExport.h>
#include <util/kernel_cpp.h>
#include <util/OpenHashTable.h>
template<typename Definition, bool AutoExpand = true,
bool CheckDuplicates = false>
class MultiHashTable : private BOpenHashTable<Definition,
AutoExpand, CheckDuplicates> {
public:
typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
typedef MultiHashTable<Definition, AutoExpand, CheckDuplicates> MultiTable;
typedef typename HashTable::Iterator Iterator;
typedef typename Definition::KeyType KeyType;
typedef typename Definition::ValueType ValueType;
MultiHashTable()
: HashTable() {}
MultiHashTable(const Definition& definition)
: HashTable(definition) {}
status_t Init(size_t initialSize = HashTable::kMinimumSize)
{
return HashTable::Init(initialSize);
}
void Insert(ValueType *value)
{
if (AutoExpand
&& HashTable::fItemCount >= (HashTable::fTableSize * 200 / 256))
_Resize(HashTable::fTableSize * 2);
InsertUnchecked(value);
}
void InsertUnchecked(ValueType *value)
{
_Insert(HashTable::fTable, HashTable::fTableSize, value);
HashTable::fItemCount++;
}
bool Remove(ValueType *value)
{
if (!HashTable::RemoveUnchecked(value))
return false;
if (AutoExpand && HashTable::fTableSize > HashTable::kMinimumSize
&& HashTable::fItemCount < (HashTable::fTableSize * 50 / 256))
_Resize(HashTable::fTableSize / 2);
return true;
}
Iterator GetIterator() const { return HashTable::GetIterator(); }
class ValueIterator : protected Iterator {
public:
ValueIterator(const HashTable *table, size_t index, ValueType *value)
: fOriginalIndex(index), fOriginalValue(value)
{
Iterator::fTable = table;
Rewind();
}
bool HasNext() const
{
if (Iterator::fNext == NULL)
return false;
if (Iterator::fNext == fOriginalValue)
return true;
return ((const MultiTable *)Iterator::fTable)->_Definition().CompareValues(
fOriginalValue, Iterator::fNext);
}
void Rewind()
{
Iterator::fIndex = fOriginalIndex + 1;
Iterator::fNext = fOriginalValue;
}
ValueType *Next() { return Iterator::Next(); }
private:
size_t fOriginalIndex;
ValueType *fOriginalValue;
};
ValueIterator Lookup(const KeyType &key) const
{
size_t index = 0;
ValueType *slot = NULL;
if (HashTable::fTableSize > 0) {
index = HashTable::fDefinition.HashKey(key)
& (HashTable::fTableSize - 1);
slot = HashTable::fTable[index];
}
while (slot) {
if (HashTable::fDefinition.Compare(key, slot))
break;
slot = HashTable::_Link(slot);
}
if (slot == NULL)
return ValueIterator(this, HashTable::fTableSize, NULL);
return ValueIterator(this, index, slot);
}
private:
friend class ValueIterator;
const Definition &_Definition() const { return HashTable::fDefinition; }
void _Insert(ValueType **table, size_t tableSize, ValueType *value)
{
size_t index = HashTable::fDefinition.Hash(value) & (tableSize - 1);
ValueType *previous;
for (previous = table[index]; previous
&& !HashTable::fDefinition.CompareValues(previous, value);
previous = HashTable::_Link(previous));
if (previous) {
HashTable::_Link(value) = HashTable::_Link(previous);
HashTable::_Link(previous) = value;
} else {
HashTable::_Link(value) = table[index];
table[index] = value;
}
}
bool _Resize(size_t newSize)
{
ValueType **newTable = new ValueType *[newSize];
if (newTable == NULL)
return false;
for (size_t i = 0; i < newSize; i++)
newTable[i] = NULL;
if (HashTable::fTable) {
for (size_t i = 0; i < HashTable::fTableSize; i++) {
ValueType *bucket = HashTable::fTable[i];
while (bucket) {
ValueType *next = HashTable::_Link(bucket);
_Insert(newTable, newSize, bucket);
bucket = next;
}
}
delete [] HashTable::fTable;
}
HashTable::fTableSize = newSize;
HashTable::fTable = newTable;
return true;
}
};
#endif
@@ -1,497 +1,0 @@
/*
* Copyright 2007, Hugo Santos. All Rights Reserved.
* Distributed under the terms of the MIT License.
*/
#ifndef _KERNEL_UTIL_OPEN_HASH_TABLE_H
#define _KERNEL_UTIL_OPEN_HASH_TABLE_H
#include <OS.h>
#include <stdlib.h>
#include <string.h>
#ifdef _KERNEL_MODE
# include <KernelExport.h>
# include <util/kernel_cpp.h>
# include <util/TypeOperation.h>
#else
# include <new>
# include <TypeOperation.h>
#endif
/*!
The Definition template must have four methods: `HashKey', `Hash',
`Compare' and `GetLink;. It must also define several types as shown in the
following example:
struct Foo {
int bar;
Foo* fNext;
};
struct HashTableDefinition {
typedef int KeyType;
typedef Foo ValueType;
size_t HashKey(KeyType key) const
{
return key >> 1;
}
size_t Hash(ValueType* value) const
{
return HashKey(value->bar);
}
bool Compare(KeyType key, ValueType* value) const
{
return value->bar == key;
}
ValueType*& GetLink(ValueType* value) const
{
return value->fNext;
}
};
*/
struct MallocAllocator {
void* Allocate(size_t size) const
{
return malloc(size);
}
void Free(void* memory) const
{
free(memory);
}
};
/** Implements an hash table with open hashing, that is, colliding entries are
* stored in a linked list. The table may be made to adjust its number of slots
* depending on the load factor (this should be enabled unless the object is to
* be used at times where memory allocations aren't possible, such as code
* called by the memory allocator).
*
* The link between entries is part of the ValueType stored items, which makes
* sure the table can always accept new items and will never fail because it is
* out of memory (except at Init time).
*/
template<typename Definition, bool AutoExpand = true,
bool CheckDuplicates = false, typename Allocator = MallocAllocator>
class BOpenHashTable {
public:
typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
typedef typename Definition::KeyType KeyType;
typedef typename Definition::ValueType ValueType;
static const size_t kMinimumSize = 8;
BOpenHashTable()
:
fTableSize(0),
fItemCount(0),
fTable(NULL)
{
}
BOpenHashTable(const Definition& definition)
:
fDefinition(definition),
fTableSize(0),
fItemCount(0),
fTable(NULL)
{
}
BOpenHashTable(const Definition& definition, const Allocator& allocator)
:
fDefinition(definition),
fAllocator(allocator),
fTableSize(0),
fItemCount(0),
fTable(NULL)
{
}
~BOpenHashTable()
{
fAllocator.Free(fTable);
}
status_t Init(size_t initialSize = kMinimumSize)
{
if (initialSize > 0 && !_Resize(initialSize))
return B_NO_MEMORY;
return B_OK;
}
size_t TableSize() const
{
return fTableSize;
}
bool IsEmpty() const
{
return fItemCount == 0;
}
size_t CountElements() const
{
return fItemCount;
}
ValueType* Lookup(typename TypeOperation<KeyType>::ConstRefT key) const
{
if (fTableSize == 0)
return NULL;
size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
ValueType* slot = fTable[index];
while (slot) {
if (fDefinition.Compare(key, slot))
break;
slot = _Link(slot);
}
return slot;
}
status_t Insert(ValueType* value)
{
if (fTableSize == 0) {
if (!_Resize(kMinimumSize))
return B_NO_MEMORY;
} else if (AutoExpand && fItemCount >= (fTableSize * 200 / 256))
_Resize(fTableSize * 2);
InsertUnchecked(value);
return B_OK;
}
/*! \brief Inserts a value without resizing the table.
Use this method if you need to insert a value into the table while
iterating it, as regular insertion can invalidate iterators.
*/
void InsertUnchecked(ValueType* value)
{
if (CheckDuplicates && _ExhaustiveSearch(value)) {
#ifdef _KERNEL_MODE
panic("Hash Table: value already in table.");
#else
debugger("Hash Table: value already in table.");
#endif
}
_Insert(fTable, fTableSize, value);
fItemCount++;
}
bool Remove(ValueType* value)
{
if (!RemoveUnchecked(value))
return false;
if (AutoExpand && fTableSize > kMinimumSize
&& fItemCount < (fTableSize * 50 / 256))
_Resize(fTableSize / 2);
return true;
}
/*! \brief Removes a value without resizing the table.
Use this method if you need to remove a value from the table while
iterating it, as Remove can invalidate iterators.
Also use this method if you know you are going to reinsert the item soon
(possibly with a different hash) to avoid shrinking then growing the
table again.
*/
bool RemoveUnchecked(ValueType* value)
{
size_t index = fDefinition.Hash(value) & (fTableSize - 1);
ValueType* previous = NULL;
ValueType* slot = fTable[index];
while (slot) {
ValueType* next = _Link(slot);
if (value == slot) {
if (previous)
_Link(previous) = next;
else
fTable[index] = next;
break;
}
previous = slot;
slot = next;
}
if (slot == NULL)
return false;
if (CheckDuplicates && _ExhaustiveSearch(value)) {
#ifdef _KERNEL_MODE
panic("Hash Table: duplicate detected.");
#else
debugger("Hash Table: duplicate detected.");
#endif
}
fItemCount--;
return true;
}
/*! \brief Removes all elements from the hash table.
No resizing happens. The elements are not deleted. If \a returnElements
is \c true, the method returns all elements chained via their hash table
link.
*/
ValueType* Clear(bool returnElements = false)
{
if (fItemCount == 0)
return NULL;
ValueType* result = NULL;
if (returnElements) {
ValueType** nextPointer = &result;
for (size_t i = 0; i < fTableSize; i++) {
ValueType* element = fTable[i];
if (element != NULL) {
*nextPointer = element;
while (element != NULL) {
nextPointer = &_Link(element);
element = *nextPointer;
}
}
}
}
memset(this->fTable, 0, sizeof(ValueType*) * this->fTableSize);
fItemCount = 0;
return result;
}
/*! If the table needs resizing, the number of bytes for the required
allocation is returned. If no resizing is needed, 0 is returned.
*/
size_t ResizeNeeded() const
{
size_t size = fTableSize;
if (size == 0 || fItemCount >= (size * 200 / 256)) {
if (size == 0)
size = kMinimumSize;
while (fItemCount >= size * 200 / 256)
size <<= 1;
} else if (size > kMinimumSize && fItemCount < size * 50 / 256) {
while (fItemCount < size * 50 / 256)
size >>= 1;
if (size < kMinimumSize)
size = kMinimumSize;
}
if (size == fTableSize)
return 0;
return size * sizeof(ValueType*);
}
/*! Resizes the table using the given allocation. The allocation must not
be \c NULL. It must be of size \a size, which must be a value returned
earlier by ResizeNeeded(). If the size requirements have changed in the
meantime, the method free()s the given allocation and returns \c false,
unless \a force is \c true, in which case the supplied allocation is
used in any event.
Otherwise \c true is returned.
If \a oldTable is non-null and resizing is successful, the old table
will not be freed, but will be returned via this parameter instead.
*/
bool Resize(void* allocation, size_t size, bool force = false,
void** oldTable = NULL)
{
if (!force && size != ResizeNeeded()) {
fAllocator.Free(allocation);
return false;
}
_Resize((ValueType**)allocation, size / sizeof(ValueType*), oldTable);
return true;
}
/*! \brief Iterator for BOpenHashTable
The iterator is not invalidated when removing the current element from
the table, unless the removal triggers a resize.
*/
class Iterator {
public:
Iterator(const HashTable* table)
: fTable(table)
{
Rewind();
}
Iterator(const HashTable* table, size_t index, ValueType* value)
: fTable(table), fIndex(index), fNext(value) {}
bool HasNext() const { return fNext != NULL; }
ValueType* Next()
{
ValueType* current = fNext;
_GetNext();
return current;
}
void Rewind()
{
fIndex = 0;
fNext = NULL;
_GetNext();
}
protected:
Iterator() {}
void _GetNext()
{
if (fNext)
fNext = fTable->_Link(fNext);
while (fNext == NULL && fIndex < fTable->fTableSize)
fNext = fTable->fTable[fIndex++];
}
const HashTable* fTable;
size_t fIndex;
ValueType* fNext;
};
Iterator GetIterator() const
{
return Iterator(this);
}
Iterator GetIterator(typename TypeOperation<KeyType>::ConstRefT key) const
{
if (fTableSize == 0)
return Iterator(this, fTableSize, NULL);
size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
ValueType* slot = fTable[index];
while (slot) {
if (fDefinition.Compare(key, slot))
break;
slot = _Link(slot);
}
if (slot == NULL)
return Iterator(this, fTableSize, NULL);
return Iterator(this, index + 1, slot);
}
protected:
friend class Iterator;
void _Insert(ValueType** table, size_t tableSize, ValueType* value)
{
size_t index = fDefinition.Hash(value) & (tableSize - 1);
_Link(value) = table[index];
table[index] = value;
}
bool _Resize(size_t newSize)
{
ValueType** newTable
= (ValueType**)fAllocator.Allocate(sizeof(ValueType*) * newSize);
if (newTable == NULL)
return false;
_Resize(newTable, newSize);
return true;
}
void _Resize(ValueType** newTable, size_t newSize, void** _oldTable = NULL)
{
for (size_t i = 0; i < newSize; i++)
newTable[i] = NULL;
if (fTable) {
for (size_t i = 0; i < fTableSize; i++) {
ValueType* bucket = fTable[i];
while (bucket) {
ValueType* next = _Link(bucket);
_Insert(newTable, newSize, bucket);
bucket = next;
}
}
if (_oldTable != NULL)
*_oldTable = fTable;
else
fAllocator.Free(fTable);
} else if (_oldTable != NULL)
*_oldTable = NULL;
fTableSize = newSize;
fTable = newTable;
}
ValueType*& _Link(ValueType* bucket) const
{
return fDefinition.GetLink(bucket);
}
bool _ExhaustiveSearch(ValueType* value) const
{
for (size_t i = 0; i < fTableSize; i++) {
ValueType* bucket = fTable[i];
while (bucket) {
if (bucket == value)
return true;
bucket = _Link(bucket);
}
}
return false;
}
Definition fDefinition;
Allocator fAllocator;
size_t fTableSize;
size_t fItemCount;
ValueType** fTable;
};
#endif
@@ -1,389 +1,0 @@
/*
* Copyright 2003-2013, Axel Dörfler, axeld@pinc-software.de.
* Copyright 2005-2013, Ingo Weinhold, ingo_weinhold@gmx.de.
* Copyright 2025, Haiku, Inc. All rights reserved.
* Distributed under the terms of the MIT License.
*/
#ifndef _SIMPLE_ALLOCATOR_H
#define _SIMPLE_ALLOCATOR_H
#include <SupportDefs.h>
#include <util/SplayTree.h>
/*! This is a very simple malloc()/free() implementation - it only
manages a free list using a splay tree.
After heap_init() is called, all free memory is contained in one
big chunk, the only entry in the free chunk tree.
When memory is allocated, the smallest free chunk that contains
the requested size is split (or taken as a whole if it can't be
splitted anymore), and its lower half will be removed from the
free list.
The free list is ordered by size, starting with the smallest
free chunk available. When a chunk is freed, it will be joined
with its predecessor or successor, if possible.
*/
template<uint32 Alignment = 8>
class SimpleAllocator {
class Chunk {
public:
size_t CompleteSize() const
{
return fSize;
}
protected:
union {
uint32 fSize;
char fAlignment[Alignment];
};
};
class FreeChunk;
struct FreeChunkData : SplayTreeLink<FreeChunk> {
FreeChunk* Next() const
{
return fNext;
}
FreeChunk** NextLink()
{
return &fNext;
}
protected:
FreeChunk* fNext;
};
class FreeChunk : public Chunk, public FreeChunkData {
public:
void SetTo(size_t size)
{
Chunk::fSize = size;
FreeChunkData::fNext = NULL;
}
/*! Returns the amount of bytes that can be allocated
in this chunk.
*/
size_t Size() const
{
return (addr_t)this + Chunk::fSize - (addr_t)AllocatedAddress();
}
/*! Splits the upper half at the requested location and returns it. This chunk
will no longer be a valid FreeChunk object; only its fSize will be valid.
*/
FreeChunk* Split(size_t splitSize)
{
splitSize = Align(splitSize);
FreeChunk* chunk = (FreeChunk*)((addr_t)AllocatedAddress() + splitSize);
size_t newSize = (addr_t)chunk - (addr_t)this;
chunk->fSize = Chunk::fSize - newSize;
chunk->fNext = NULL;
Chunk::fSize = newSize;
return chunk;
}
/*! Checks if the specified chunk touches this chunk, so
that they could be joined.
*/
bool IsTouching(FreeChunk* chunk)
{
return chunk
&& (((uint8*)this + Chunk::fSize == (uint8*)chunk)
|| (uint8*)chunk + chunk->fSize == (uint8*)this);
}
/*! Joins the chunk to this chunk and returns the pointer
to the new chunk - which will either be one of the
two chunks.
Note, the chunks must be joinable, or else this method
doesn't work correctly. Use FreeChunk::IsTouching()
to check if this method can be applied.
*/
FreeChunk* Join(FreeChunk* chunk)
{
if (chunk < this) {
chunk->fSize += Chunk::fSize;
chunk->fNext = FreeChunkData::fNext;
return chunk;
}
Chunk::fSize += chunk->fSize;
FreeChunkData::fNext = chunk->fNext;
return this;
}
void* AllocatedAddress() const
{
return (void*)static_cast<const FreeChunkData*>(this);
}
static FreeChunk* SetToAllocated(void* allocated)
{
return static_cast<FreeChunk*>((FreeChunkData*)allocated);
}
};
struct FreeChunkKey {
FreeChunkKey(size_t size)
:
fSize(size),
fChunk(NULL)
{
}
FreeChunkKey(const FreeChunk* chunk)
:
fSize(chunk->Size()),
fChunk(chunk)
{
}
int Compare(const FreeChunk* chunk) const
{
size_t chunkSize = chunk->Size();
if (chunkSize != fSize)
return fSize < chunkSize ? -1 : 1;
if (fChunk == chunk)
return 0;
return fChunk < chunk ? -1 : 1;
}
private:
size_t fSize;
const FreeChunk* fChunk;
};
struct FreeChunkTreeDefinition {
typedef FreeChunkKey KeyType;
typedef FreeChunk NodeType;
static FreeChunkKey GetKey(const FreeChunk* node)
{
return FreeChunkKey(node);
}
static SplayTreeLink<FreeChunk>* GetLink(FreeChunk* node)
{
return node;
}
static int Compare(const FreeChunkKey& key, const FreeChunk* node)
{
return key.Compare(node);
}
static FreeChunk** GetListLink(FreeChunk* node)
{
return node->NextLink();
}
};
typedef IteratableSplayTree<FreeChunkTreeDefinition> FreeChunkTree;
public:
static inline size_t Align(size_t size, size_t alignment = Alignment)
{
return (size + alignment - 1) & ~(alignment - 1);
}
public:
SimpleAllocator()
:
fAvailable(0)
{
#ifdef DEBUG_MAX_HEAP_USAGE
fMaxHeapSize = fMaxHeapUsage = 0;
#endif
}
~SimpleAllocator()
{
}
void AddChunk(void* base, uint32 size)
{
FreeChunk* chunk = (FreeChunk*)base;
chunk->SetTo(size);
#ifdef DEBUG_MAX_HEAP_USAGE
fMaxHeapSize += chunk->Size();
#endif
_InsertChunk(chunk);
}
uint32 Available() const { return fAvailable; }
void* Allocate(uint32 size)
{
if (size == 0)
return NULL;
if (size < sizeof(FreeChunkData))
size = sizeof(FreeChunkData);
size = Align(size);
if (size > fAvailable)
return NULL;
FreeChunk* chunk = fFreeChunkTree.FindClosest(FreeChunkKey(size), true, true);
if (chunk == NULL) {
return NULL;
}
fFreeChunkTree.Remove(chunk);
fAvailable -= chunk->Size();
void* allocated = chunk->AllocatedAddress();
if (chunk->Size() >= (size + Align(sizeof(FreeChunk)))) {
FreeChunk* freeChunk = chunk->Split(size);
fFreeChunkTree.Insert(freeChunk);
fAvailable += freeChunk->Size();
}
#ifdef DEBUG_MAX_HEAP_USAGE
fMaxHeapUsage = std::max(fMaxHeapUsage, fMaxHeapSize - fAvailable);
#endif
#ifdef DEBUG_ALLOCATIONS
memset(allocated, 0xcc, chunk->Size());
#endif
return allocated;
}
uint32 UsableSize(void* allocated)
{
FreeChunk* chunk = FreeChunk::SetToAllocated(allocated);
return chunk->Size();
}
void* Reallocate(void* oldBuffer, uint32 newSize)
{
size_t oldSize = 0;
if (oldBuffer != NULL) {
oldSize = UsableSize(oldBuffer);
if (oldSize >= newSize && (oldSize < 128 || newSize > (oldSize / 3)))
return oldBuffer;
}
void* newBuffer = Allocate(newSize);
if (newBuffer == NULL)
return NULL;
if (oldBuffer != NULL) {
memcpy(newBuffer, oldBuffer, (oldSize < newSize) ? oldSize : newSize);
Free(oldBuffer);
}
return newBuffer;
}
void Free(void* allocated)
{
if (allocated == NULL)
return;
FreeChunk* freedChunk = FreeChunk::SetToAllocated(allocated);
#ifdef DEBUG_VALIDATE_HEAP_ON_FREE
if (freedChunk->Size() > (fMaxHeapSize - fAvailable)) {
panic("freed chunk %p clobbered (%#zx)!\n", freedChunk,
freedChunk->Size());
}
{
FreeChunk* chunk = fFreeChunkTree.FindMin();
while (chunk) {
if (chunk->Size() > fAvailable || freedChunk == chunk)
panic("invalid chunk in free list (%p (%zu)), or double free\n",
chunk, chunk->Size());
chunk = chunk->Next();
}
}
#endif
#ifdef DEBUG_ALLOCATIONS
for (uint32 i = 0; i < (freedChunk->Size() / 4); i++)
((uint32*)allocated)[i] = 0xdeadbeef;
#endif
_InsertChunk(freedChunk);
}
#ifdef DEBUG_MAX_HEAP_USAGE
uint32 MaxHeapSize() const { return fMaxHeapSize; }
uint32 MaxHeapUsage() const { return fMaxHeapUsage; }
#endif
void DumpChunks()
{
FreeChunk* chunk = fFreeChunkTree.FindMin();
while (chunk != NULL) {
printf("\t%p: chunk size = %ld, end = %p, next = %p\n", chunk,
chunk->Size(), (uint8*)chunk + chunk->CompleteSize(),
chunk->Next());
chunk = chunk->Next();
}
}
private:
void _InsertChunk(FreeChunk* freedChunk)
{
FreeChunk* chunk = fFreeChunkTree.FindMin();
int32 joinCount = 0;
while (chunk != NULL) {
FreeChunk* nextChunk = chunk->Next();
if (chunk->IsTouching(freedChunk)) {
fFreeChunkTree.Remove(chunk);
fAvailable -= chunk->Size();
freedChunk = chunk->Join(freedChunk);
if (++joinCount == 2)
break;
}
chunk = nextChunk;
}
fFreeChunkTree.Insert(freedChunk);
fAvailable += freedChunk->Size();
#ifdef DEBUG_MAX_HEAP_USAGE
fMaxHeapUsage = std::max(fMaxHeapUsage, fMaxHeapSize - fAvailable);
#endif
}
private:
FreeChunkTree fFreeChunkTree;
uint32 fAvailable;
#ifdef DEBUG_MAX_HEAP_USAGE
uint32 fMaxHeapSize, fMaxHeapUsage;
#endif
};
#endif
@@ -1,317 +1,0 @@
/*
* Copyright 2008, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
* Copyright 2005-2010, Ingo Weinhold, ingo_weinhold@gmx.de.
*
* Distributed under the terms of the MIT License.
*/
#ifndef KERNEL_UTIL_SINGLY_LINKED_LIST_H
#define KERNEL_UTIL_SINGLY_LINKED_LIST_H
#include <SupportDefs.h>
#ifdef __cplusplus
template<typename Element>
class SinglyLinkedListLink {
public:
SinglyLinkedListLink() : next(NULL) {}
~SinglyLinkedListLink() {}
Element* next;
};
template<typename Element>
class SinglyLinkedListLinkImpl {
private:
typedef SinglyLinkedListLink<Element> SLL_Link;
public:
SinglyLinkedListLinkImpl() : fSinglyLinkedListLink() {}
~SinglyLinkedListLinkImpl() {}
SLL_Link* GetSinglyLinkedListLink()
{ return &fSinglyLinkedListLink; }
const SLL_Link* GetSinglyLinkedListLink() const
{ return &fSinglyLinkedListLink; }
private:
SLL_Link fSinglyLinkedListLink;
};
template<typename Element>
class SinglyLinkedListStandardGetLink {
private:
typedef SinglyLinkedListLink<Element> Link;
public:
inline Link* operator()(Element* element) const
{
return element->GetSinglyLinkedListLink();
}
inline const Link* operator()(const Element* element) const
{
return element->GetSinglyLinkedListLink();
}
};
template<typename Element,
SinglyLinkedListLink<Element> Element::* LinkMember = &Element::fLink>
class SinglyLinkedListMemberGetLink {
private:
typedef SinglyLinkedListLink<Element> Link;
public:
inline Link* operator()(Element* element) const
{
return &(element->*LinkMember);
}
inline const Link* operator()(const Element* element) const
{
return &(element->*LinkMember);
}
};
#define SINGLY_LINKED_LIST_TEMPLATE_LIST \
template<typename Element, typename GetLink>
#define SINGLY_LINKED_LIST_CLASS_NAME SinglyLinkedList<Element, GetLink>
template<typename Element,
typename GetLink = SinglyLinkedListStandardGetLink<Element> >
class SinglyLinkedList {
private:
typedef SinglyLinkedList<Element, GetLink> List;
typedef SinglyLinkedListLink<Element> Link;
public:
class ConstIterator {
public:
ConstIterator(const List* list)
:
fList(list)
{
Rewind();
}
ConstIterator(const ConstIterator& other)
{
*this = other;
}
bool HasNext() const
{
return fNext;
}
Element* Next()
{
Element* element = fNext;
if (fNext)
fNext = fList->GetNext(fNext);
return element;
}
ConstIterator& operator=(const ConstIterator& other)
{
fList = other.fList;
fNext = other.fNext;
return* this;
}
void Rewind()
{
fNext = fList->First();
}
private:
const List* fList;
Element* fNext;
};
public:
SinglyLinkedList() : fFirst(NULL) {}
~SinglyLinkedList() {}
inline bool IsEmpty() const { return (fFirst == NULL); }
inline void Add(Element* element);
inline bool Remove(Element* element);
inline void Remove(Element* previous, Element* element);
inline void TakeFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList);
inline void RemoveAll();
inline void MakeEmpty() { RemoveAll(); }
inline Element* First() const { return fFirst; }
inline Element* Head() const { return fFirst; }
inline Element* RemoveHead();
inline Element* GetNext(Element* element) const;
inline int32 Count() const;
inline ConstIterator GetIterator() const { return ConstIterator(this); }
private:
Element *fFirst;
static GetLink sGetLink;
};
SINGLY_LINKED_LIST_TEMPLATE_LIST
void
SINGLY_LINKED_LIST_CLASS_NAME::Add(Element* element)
{
if (element != NULL) {
sGetLink(element)->next = fFirst;
fFirst = element;
}
}
/*! Removes \a element from the list.
It is safe to call the list with a \c NULL element or an element that isn't
in the list.
\param element The element to be removed.
\return \c true, if the element was in the list and has been removed,
\c false otherwise.
*/
SINGLY_LINKED_LIST_TEMPLATE_LIST
bool
SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* element)
{
if (element == NULL)
return false;
Element* next = fFirst;
Element* last = NULL;
while (element != next) {
if (next == NULL)
return false;
last = next;
next = sGetLink(next)->next;
}
Link* elementLink = sGetLink(element);
if (last == NULL)
fFirst = elementLink->next;
else
sGetLink(last)->next = elementLink->next;
elementLink->next = NULL;
return true;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
void
SINGLY_LINKED_LIST_CLASS_NAME::Remove(Element* previous, Element* element)
{
Link* elementLink = sGetLink(element);
if (previous == NULL)
fFirst = elementLink->next;
else
sGetLink(previous)->next = elementLink->next;
elementLink->next = NULL;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
void
SINGLY_LINKED_LIST_CLASS_NAME::TakeFrom(SINGLY_LINKED_LIST_CLASS_NAME* fromList)
{
if (fromList->fFirst == NULL)
return;
if (fFirst == NULL) {
fFirst = fromList->fFirst;
fromList->fFirst = NULL;
return;
}
Element* tail = fFirst;
while (Element* next = sGetLink(tail)->next)
tail = next;
sGetLink(tail)->next = fromList->fFirst;
fromList->fFirst = NULL;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
void
SINGLY_LINKED_LIST_CLASS_NAME::RemoveAll()
{
Element* element = fFirst;
while (element) {
Link* elLink = sGetLink(element);
element = elLink->next;
elLink->next = NULL;
}
fFirst = NULL;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
Element*
SINGLY_LINKED_LIST_CLASS_NAME::RemoveHead()
{
Element* element = Head();
Remove(element);
return element;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
Element*
SINGLY_LINKED_LIST_CLASS_NAME::GetNext(Element* element) const
{
Element* result = NULL;
if (element)
result = sGetLink(element)->next;
return result;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
int32
SINGLY_LINKED_LIST_CLASS_NAME::Count() const
{
int32 count = 0;
for (Element* element = First(); element; element = GetNext(element))
count++;
return count;
}
SINGLY_LINKED_LIST_TEMPLATE_LIST
GetLink SINGLY_LINKED_LIST_CLASS_NAME::sGetLink;
#endif
#endif
@@ -1,623 +1,0 @@
/*
* Copyright 2008-2009, Ingo Weinhold <ingo_weinhold@gmx.de>.
* Distributed under the terms of the MIT License.
*
* Original Java implementation:
* Available at http:
* Author: Danny Sleator <sleator@cs.cmu.edu>
* This code is in the public domain.
*/
#ifndef KERNEL_UTIL_SPLAY_TREE_H
#define KERNEL_UTIL_SPLAY_TREE_H
/*! Implements two classes:
SplayTree: A top-down splay tree.
IteratableSplayTree: Extends SplayTree by a singly-linked list to make it
cheaply iteratable (requires another pointer per node).
Both classes are templatized over a definition parameter with the following
(or a compatible) interface:
struct SplayTreeDefinition {
typedef xxx KeyType;
typedef yyy NodeType;
static const KeyType& GetKey(const NodeType* node);
static SplayTreeLink<NodeType>* GetLink(NodeType* node);
static int Compare(const KeyType& key, const NodeType* node);
static NodeType** GetListLink(NodeType* node);
};
*/
template<typename Node>
struct SplayTreeLink {
Node* left;
Node* right;
};
template<typename Definition>
class SplayTree {
protected:
typedef typename Definition::KeyType Key;
typedef typename Definition::NodeType Node;
typedef SplayTreeLink<Node> Link;
public:
SplayTree()
:
fRoot(NULL)
{
}
/*!
Insert into the tree.
\param node the item to insert.
*/
bool Insert(Node* node)
{
Link* nodeLink = Definition::GetLink(node);
if (fRoot == NULL) {
fRoot = node;
nodeLink->left = NULL;
nodeLink->right = NULL;
return true;
}
Key key = Definition::GetKey(node);
_Splay(key);
int c = Definition::Compare(key, fRoot);
if (c == 0)
return false;
Link* rootLink = Definition::GetLink(fRoot);
if (c < 0) {
nodeLink->left = rootLink->left;
nodeLink->right = fRoot;
rootLink->left = NULL;
} else {
nodeLink->right = rootLink->right;
nodeLink->left = fRoot;
rootLink->right = NULL;
}
fRoot = node;
return true;
}
Node* Remove(const Key& key)
{
if (fRoot == NULL)
return NULL;
_Splay(key);
if (Definition::Compare(key, fRoot) != 0)
return NULL;
Node* node = fRoot;
Link* rootLink = Definition::GetLink(fRoot);
if (rootLink->left == NULL) {
fRoot = rootLink->right;
} else {
Node* temp = rootLink->right;
fRoot = rootLink->left;
_Splay(key);
Definition::GetLink(fRoot)->right = temp;
}
return node;
}
/*!
Remove from the tree.
\param node the item to remove.
*/
bool Remove(Node* node)
{
Key key = Definition::GetKey(node);
_Splay(key);
if (node != fRoot)
return false;
Link* rootLink = Definition::GetLink(fRoot);
if (rootLink->left == NULL) {
fRoot = rootLink->right;
} else {
Node* temp = rootLink->right;
fRoot = rootLink->left;
_Splay(key);
Definition::GetLink(fRoot)->right = temp;
}
return true;
}
/*!
Find the smallest item in the tree.
*/
Node* FindMin()
{
if (fRoot == NULL)
return NULL;
Node* node = fRoot;
while (Node* left = Definition::GetLink(node)->left)
node = left;
_Splay(Definition::GetKey(node));
return node;
}
/*!
Find the largest item in the tree.
*/
Node* FindMax()
{
if (fRoot == NULL)
return NULL;
Node* node = fRoot;
while (Node* right = Definition::GetLink(node)->right)
node = right;
_Splay(Definition::GetKey(node));
return node;
}
/*!
Find an item in the tree.
*/
Node* Lookup(const Key& key)
{
if (fRoot == NULL)
return NULL;
_Splay(key);
return Definition::Compare(key, fRoot) == 0 ? fRoot : NULL;
}
Node* Root() const
{
return fRoot;
}
/*!
Test if the tree is logically empty.
\return true if empty, false otherwise.
*/
bool IsEmpty() const
{
return fRoot == NULL;
}
Node* PreviousDontSplay(const Key& key) const
{
Node* closestNode = NULL;
Node* node = fRoot;
while (node != NULL) {
if (Definition::Compare(key, node) > 0) {
closestNode = node;
node = Definition::GetLink(node)->right;
} else
node = Definition::GetLink(node)->left;
}
return closestNode;
}
Node* FindClosest(const Key& key, bool greater, bool orEqual)
{
if (fRoot == NULL)
return NULL;
_Splay(key);
Node* closestNode = NULL;
Node* node = fRoot;
while (node != NULL) {
int compare = Definition::Compare(key, node);
if (compare == 0 && orEqual)
return node;
if (greater) {
if (compare < 0) {
closestNode = node;
node = Definition::GetLink(node)->left;
} else
node = Definition::GetLink(node)->right;
} else {
if (compare > 0) {
closestNode = node;
node = Definition::GetLink(node)->right;
} else
node = Definition::GetLink(node)->left;
}
}
return closestNode;
}
SplayTree& operator=(const SplayTree& other)
{
fRoot = other.fRoot;
return *this;
}
private:
/*!
Internal method to perform a top-down splay.
_Splay(key) does the splay operation on the given key.
If key is in the tree, then the node containing
that key becomes the root. If key is not in the tree,
then after the splay, key.root is either the greatest key
< key in the tree, or the least key > key in the tree.
This means, among other things, that if you splay with
a key that's larger than any in the tree, the rightmost
node of the tree becomes the root. This property is used
in the Remove() method.
*/
void _Splay(const Key& key) {
Link headerLink;
headerLink.left = headerLink.right = NULL;
Link* lLink = &headerLink;
Link* rLink = &headerLink;
Node* l = NULL;
Node* r = NULL;
Node* t = fRoot;
for (;;) {
int c = Definition::Compare(key, t);
if (c < 0) {
Node*& left = Definition::GetLink(t)->left;
if (left == NULL)
break;
if (Definition::Compare(key, left) < 0) {
Node* y = left;
Link* yLink = Definition::GetLink(y);
left = yLink->right;
yLink->right = t;
t = y;
if (yLink->left == NULL)
break;
}
rLink->left = t;
r = t;
rLink = Definition::GetLink(r);
t = rLink->left;
} else if (c > 0) {
Node*& right = Definition::GetLink(t)->right;
if (right == NULL)
break;
if (Definition::Compare(key, right) > 0) {
Node* y = right;
Link* yLink = Definition::GetLink(y);
right = yLink->left;
yLink->left = t;
t = y;
if (yLink->right == NULL)
break;
}
lLink->right = t;
l = t;
lLink = Definition::GetLink(l);
t = lLink->right;
} else
break;
}
Link* tLink = Definition::GetLink(t);
lLink->right = tLink->left;
rLink->left = tLink->right;
tLink->left = headerLink.right;
tLink->right = headerLink.left;
fRoot = t;
}
protected:
Node* fRoot;
};
template<typename Definition>
class IteratableSplayTree {
protected:
typedef typename Definition::KeyType Key;
typedef typename Definition::NodeType Node;
typedef SplayTreeLink<Node> Link;
typedef IteratableSplayTree<Definition> Tree;
public:
class Iterator {
public:
Iterator()
{
}
Iterator(const Iterator& other)
{
*this = other;
}
Iterator(Tree* tree)
:
fTree(tree)
{
Rewind();
}
Iterator(Tree* tree, Node* next)
:
fTree(tree),
fCurrent(NULL),
fNext(next)
{
}
bool HasNext() const
{
return fNext != NULL;
}
Node* Next()
{
fCurrent = fNext;
if (fNext != NULL)
fNext = *Definition::GetListLink(fNext);
return fCurrent;
}
Node* Current()
{
return fCurrent;
}
Node* Remove()
{
Node* element = fCurrent;
if (fCurrent) {
fTree->Remove(fCurrent);
fCurrent = NULL;
}
return element;
}
Iterator &operator=(const Iterator &other)
{
fTree = other.fTree;
fCurrent = other.fCurrent;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fCurrent = NULL;
fNext = fTree->fFirst;
}
private:
Tree* fTree;
Node* fCurrent;
Node* fNext;
};
class ConstIterator {
public:
ConstIterator()
{
}
ConstIterator(const ConstIterator& other)
{
*this = other;
}
ConstIterator(const Tree* tree)
:
fTree(tree)
{
Rewind();
}
ConstIterator(const Tree* tree, Node* next)
:
fTree(tree),
fNext(next)
{
}
bool HasNext() const
{
return fNext != NULL;
}
Node* Next()
{
Node* node = fNext;
if (fNext != NULL)
fNext = *Definition::GetListLink(fNext);
return node;
}
ConstIterator &operator=(const ConstIterator &other)
{
fTree = other.fTree;
fNext = other.fNext;
return *this;
}
void Rewind()
{
fNext = fTree->fFirst;
}
private:
const Tree* fTree;
Node* fNext;
};
IteratableSplayTree()
:
fTree(),
fFirst(NULL)
{
}
bool Insert(Node* node)
{
if (!fTree.Insert(node))
return false;
Node** previousNext;
if (Node* previous = fTree.PreviousDontSplay(Definition::GetKey(node)))
previousNext = Definition::GetListLink(previous);
else
previousNext = &fFirst;
*Definition::GetListLink(node) = *previousNext;
*previousNext = node;
return true;
}
Node* Remove(const Key& key)
{
Node* node = fTree.Remove(key);
if (node == NULL)
return NULL;
Node** previousNext;
if (Node* previous = fTree.PreviousDontSplay(key))
previousNext = Definition::GetListLink(previous);
else
previousNext = &fFirst;
*previousNext = *Definition::GetListLink(node);
return node;
}
bool Remove(Node* node)
{
if (!fTree.Remove(node))
return false;
Node** previousNext;
if (Node* previous = fTree.PreviousDontSplay(Definition::GetKey(node)))
previousNext = Definition::GetListLink(previous);
else
previousNext = &fFirst;
*previousNext = *Definition::GetListLink(node);
return true;
}
Node* Lookup(const Key& key)
{
return fTree.Lookup(key);
}
Node* Root() const
{
return fTree.Root();
}
/*!
Test if the tree is logically empty.
\return true if empty, false otherwise.
*/
bool IsEmpty() const
{
return fTree.IsEmpty();
}
Node* PreviousDontSplay(const Key& key)
{
return fTree.PreviousDontSplay(key);
}
Node* FindClosest(const Key& key, bool greater, bool orEqual)
{
return fTree.FindClosest(key, greater, orEqual);
}
Node* FindMin()
{
return fTree.FindMin();
}
Node* FindMax()
{
return fTree.FindMax();
}
Iterator GetIterator()
{
return Iterator(this);
}
ConstIterator GetIterator() const
{
return ConstIterator(this);
}
Iterator GetIterator(const Key& key, bool greater, bool orEqual)
{
return Iterator(this, fTree.FindClosest(key, greater, orEqual));
}
ConstIterator GetIterator(const Key& key, bool greater, bool orEqual) const
{
return ConstIterator(this, FindClosest(key, greater, orEqual));
}
IteratableSplayTree& operator=(const IteratableSplayTree& other)
{
fTree = other.fTree;
fFirst = other.fFirst;
return *this;
}
protected:
friend class Iterator;
friend class ConstIterator;
SplayTree<Definition> fTree;
Node* fFirst;
};
#endif
@@ -1,111 +1,0 @@
/*
* Copyright 2001-2008, Axel Dörfler, axeld@pinc-software.de.
* This file may be used under the terms of the MIT License.
*/
#ifndef KERNEL_UTIL_STACK_H
#define KERNEL_UTIL_STACK_H
#include <stdlib.h>
#include <SupportDefs.h>
#include <AutoDeleter.h>
template<class T> class Stack {
public:
Stack()
:
fArray(NULL),
fUsed(0),
fMax(0)
{
}
~Stack()
{
free(fArray);
}
bool IsEmpty() const
{
return fUsed == 0;
}
void MakeEmpty()
{
fUsed = 0;
}
status_t Push(T value)
{
if (fUsed >= fMax) {
fMax += 16;
T *newArray = (T *)realloc(fArray, fMax * sizeof(T));
if (newArray == NULL)
return B_NO_MEMORY;
fArray = newArray;
}
fArray[fUsed++] = value;
return B_OK;
}
bool Pop(T *value)
{
if (fUsed == 0)
return false;
*value = fArray[--fUsed];
return true;
}
T *Array()
{
return fArray;
}
int32 CountItems() const
{
return fUsed;
}
private:
T *fArray;
int32 fUsed;
int32 fMax;
};
template<typename T> class StackDelete {
public:
inline void operator()(Stack<T>* stack)
{
if (stack == NULL)
return;
T item;
while (stack->Pop(&item)) {
delete item;
}
delete stack;
}
};
template<typename T> class StackDeleter
: public BPrivate::AutoDeleter<Stack<T>, StackDelete<T> > {
public:
StackDeleter()
{
}
StackDeleter(Stack<T>* stack)
: BPrivate::AutoDeleter<Stack<T>, StackDelete<T> >(stack)
{
}
};
#endif
@@ -6,12 +6,11 @@
#define RTF_H
#include "Stack.h"
#include <List.h>
#include <String.h>
#include <GraphicsDefs.h>
#include <BufferIO.h>
#include <util/Stack.h>
namespace RTF {
@@ -1,70 +1,0 @@
/* Stack - a template stack class
*
* Copyright 2001-2005, Axel Dörfler, axeld@pinc-software.de.
* This file may be used under the terms of the MIT License.
*/
#ifndef STACK_H
#define STACK_H
#include <stdlib.h>
#include <SupportDefs.h>
template<class T> class Stack {
public:
Stack()
:
fArray(NULL),
fUsed(0),
fMax(0)
{
}
~Stack()
{
free(fArray);
}
bool IsEmpty() const
{
return fUsed == 0;
}
void MakeEmpty()
{
fUsed = 0;
}
status_t Push(T value)
{
if (fUsed >= fMax) {
fMax += 16;
T *newArray = (T *)realloc(fArray, fMax * sizeof(T));
if (newArray == NULL)
return B_NO_MEMORY;
fArray = newArray;
}
fArray[fUsed++] = value;
return B_OK;
}
bool Pop(T *value)
{
if (fUsed == 0)
return false;
*value = fArray[--fUsed];
return true;
}
private:
T *fArray;
int32 fUsed;
int32 fMax;
};
#endif
@@ -23,8 +23,6 @@
#include <AutoDeleter.h>
#include "Stack.h"
#define READ_BUFFER_SIZE 2048
@@ -1,1 +1,0 @@
#include <../private/kernel/util/BumpAllocator.h>
@@ -1,1 +1,0 @@
#include <../private/kernel/util/DoublyLinkedList.h>
@@ -1,1 +1,0 @@
#include <../private/kernel/util/OpenHashTable.h>
@@ -1,1 +1,0 @@
#include <../private/kernel/util/SinglyLinkedList.h>
@@ -11,9 +11,10 @@
#include <lock.h>
#include <string.h>
#include <util/SplayTree.h>
#include "DirectoryIterator.h"
#include "exfat.h"
#include "SplayTree.h"
#include "Volume.h"
@@ -1,6 +1,5 @@
SubDir HAIKU_TOP src add-ons kernel file_systems exfat ;
UsePrivateHeaders [ FDirName kernel util ] ;
UsePrivateHeaders shared storage ;
UsePrivateHeaders file_systems ;
UsePrivateKernelHeaders ;
@@ -16,4 +15,4 @@
;
SEARCH on [ FGristFiles DeviceOpener.cpp ]
= [ FDirName $(HAIKU_TOP) src add-ons kernel file_systems shared ] ;
= [ FDirName $(HAIKU_TOP) src add-ons kernel file_systems shared ] ;
@@ -18,9 +18,9 @@
#include <string.h>
#include <StorageDefs.h>
#include <util/SplayTree.h>
#include "exfat.h"
#include "SplayTree.h"
struct node_key {
@@ -9,7 +9,7 @@
#include <image.h>
#include <OS.h>
#include <kernel/util/DoublyLinkedList.h>
#include <util/DoublyLinkedList.h>
#include "FSCapabilities.h"
#include "Locker.h"
@@ -8,7 +8,7 @@
#include <fs_interface.h>
#include <SupportDefs.h>
#include <kernel/util/DoublyLinkedList.h>
#include <util/DoublyLinkedList.h>
#include "FSCapabilities.h"