Utilities. More...

Collaboration diagram for utilities:

Classes
class	Cord

class	HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >

class	Iterator< originalT, Struct, FunctionPrev, FunctionNext, T >
	An iterator applicable for many data structures. More...

class	TreeIterator< originalT, Struct, FunctionPrev, FunctionNext, K, T >
	An iterator applicable for many data structures. More...

class	IteratorAdapter< T, Iterator >
	IteratorAdapter reinterpret_casts an Iterators element to another type. More...

struct	_ListNode_t< T >
	One node in the list. More...

class	List< T, nodePoolSize >

class	LruCache< K, T, Slots >
	LruCache provides a least-recently-used cache abstraction. More...

class	Pair< T1, T2 >

class	RadixTree< T >
	A key/value dictionary for string keys. More...

class	RangeList< T, Reversed >

class	StaticCord< N >

class	StaticString< N >

class	String

class	ConstantString< N >

class	StringView

class	HashedStringView

struct	nonconst_type< T >
	Remove the const qualifier of a type. More...

struct	nonconst_type< const T >
	Remove the const qualifier of a type. More...

class	Tree< K, E >
	A key/value dictionary. More...

class	Vector< T >
	A vector / dynamic array. More...

Macros
#define	STRING_DISABLE_EXPENSIVE_COPY_CONSTRUCTION 1

#define	HASH_STRINGVIEWS_BY_DEFAULT false

#define	BS8(x) ((uint8_t)(x))

#define	BS16(x) __builtin_bswap16((uint16_t)(x))

#define	BS32(x) __builtin_bswap32((uint32_t)(x))

#define	BS64(x) __builtin_bswap64((uint64_t)(x))

#define	BIG_TO_HOST8(x) (x)

#define	BIG_TO_HOST16(x) (x)

#define	BIG_TO_HOST32(x) (x)

#define	BIG_TO_HOST64(x) (x)

#define	HOST_TO_BIG8(x) (x)

#define	HOST_TO_BIG16(x) (x)

#define	HOST_TO_BIG32(x) (x)

#define	HOST_TO_BIG64(x) (x)

#define	LITTLE_TO_HOST8(x) BS8((x))

#define	LITTLE_TO_HOST16(x) BS16((x))

#define	LITTLE_TO_HOST32(x) BS32((x))

#define	LITTLE_TO_HOST64(x) BS64((x))

#define	HOST_TO_LITTLE8(x) BS8((x))

#define	HOST_TO_LITTLE16(x) BS16((x))

#define	HOST_TO_LITTLE32(x) BS32((x))

#define	HOST_TO_LITTLE64(x) BS64((x))

#define	MAX_FUNCTION_NAME 128

#define	MAX_PARAMS 32

#define	MAX_PARAM_LENGTH 64

Typedefs
typedef RangeList< uintptr_t >	MemoryAllocator

typedef StaticString< 32 >	TinyStaticString

typedef StaticString< 64 >	NormalStaticString

typedef StaticString< 128 >	LargeStaticString

typedef StaticString< 1024 >	HugeStaticString

Functions
template<typename originalT , class Struct , Struct (Struct::)() FunctionPrev, Struct (Struct::)() FunctionNext, typename T1 , typename T2 >
bool	operator== (const Iterator< originalT, Struct, FunctionPrev, FunctionNext, T1 > &x1, const Iterator< originalT, Struct, FunctionPrev, FunctionNext, T2 > &x2)

template<typename originalT , class Struct , Struct (Struct::)() FunctionPrev, Struct (Struct::)() FunctionNext, typename K1 , typename T1 , typename K2 , typename T2 >
bool	operator== (const TreeIterator< originalT, Struct, FunctionPrev, FunctionNext, K1, T1 > &x1, const TreeIterator< originalT, Struct, FunctionPrev, FunctionNext, K2, T2 > &x2)

template<class T1 , class T2 >
bool	operator== (const Pair< T1, T2 > &left, const Pair< T1, T2 > &right)

template<class T1 , class T2 >
bool	operator!= (const Pair< T1, T2 > &left, const Pair< T1, T2 > &right)

template<class T1 , class T2 >
bool	operator< (const Pair< T1, T2 > &left, const Pair< T1, T2 > &right)

template<class T1 , class T2 >
bool	operator<= (const Pair< T1, T2 > &left, const Pair< T1, T2 > &right)

template<class T1 , class T2 >
bool	operator> (const Pair< T1, T2 > &left, const Pair< T1, T2 > &right)

template<class T1 , class T2 >
bool	operator>= (const Pair< T1, T2 > &left, const Pair< T1, T2 > &right)

template<typename T1 , typename T2 >
Pair< T1, T2 >	makePair (T1 a, T2 b)

template<size_t N>
ConstantString< N >	MakeConstantString (const char(&str)[N])

template<class T1 , class T2 >
bool	operator!= (const T1 &x1, const T2 &x2)
	Global != operator for types with overloaded == operator.

template<class T >
T	operator++ (T &x, int)
	Global postincrement operator for types with overloaded preincrement operator.

template<class T >
T	operator-- (T &x, int)
	Global postdecrement operator for types with overloaded predecrement operator.

EXPORTED_PUBLIC void *	page_align (void *p) PURE

	List< T, nodePoolSize >::List ()

	List< T, nodePoolSize >::List (const List &x)

	List< T, nodePoolSize >::~List ()

List &	List< T, nodePoolSize >::operator= (const List &x)

size_t	List< T, nodePoolSize >::size () const

size_t	List< T, nodePoolSize >::count () const

void	List< T, nodePoolSize >::pushBack (const T &value)

void	List< T, nodePoolSize >::pushBack (T &&value)

bool	List< T, nodePoolSize >::tryPushBack (const T &value)

bool	List< T, nodePoolSize >::tryPushBack (T &&value)

T	List< T, nodePoolSize >::popBack ()

void	List< T, nodePoolSize >::pushFront (const T &value)

void	List< T, nodePoolSize >::pushFront (T &&value)

T	List< T, nodePoolSize >::popFront ()

Iterator	List< T, nodePoolSize >::erase (Iterator &Iter)

ReverseIterator	List< T, nodePoolSize >::erase (ReverseIterator &Iter)

void	List< T, nodePoolSize >::clear ()

void	List< T, nodePoolSize >::assign (const List &x)

	RadixTree< T >::RadixTree ()

	RadixTree< T >::RadixTree (bool bCaseSensitive)

	RadixTree< T >::~RadixTree ()

	RadixTree< T >::RadixTree (const RadixTree< T > &x)

RadixTree &	RadixTree< T >::operator= (const RadixTree &x)

size_t	RadixTree< T >::count () const

void	RadixTree< T >::insert (const String &key, const T &value)

MUST_USE_RESULT bool	RadixTree< T >::lookup (const String &key, T &value) const

void	RadixTree< T >::remove (const String &key)

Node *	RadixTree< T >::cloneNode (Node node, Node parent)

void	RadixTree< T >::clear ()

void	RadixTree< T >::dump (void(emit_line)(const char s)) const

void	RadixTree< T >::Node::returnAllChildren ()

Node *	RadixTree< T >::Node::findChild (const char *cpKey) const

void	RadixTree< T >::Node::addChild (Node *pNode)

void	RadixTree< T >::Node::replaceChild (Node pNodeOld, Node pNodeNew)

void	RadixTree< T >::Node::removeChild (Node *pChild)

MatchType	RadixTree< T >::Node::matchKey (const char *cpKey, size_t &offset) const

void	RadixTree< T >::Node::setKey (const char *cpKey)

void	RadixTree< T >::Node::setKey (const char *cpKey, size_t lengthHint)

void	RadixTree< T >::Node::setKey (const String &cpKey)

Node *	RadixTree< T >::Node::getFirstChild () const

void	RadixTree< T >::Node::prependKey (const String &cpKey)

Node *	RadixTree< T >::Node::doNext () const

Node *	RadixTree< T >::Node::getNextSibling () const

void	RadixTree< T >::Node::dump (void(emit_line)(const char s)) const

	Vector< T >::Vector ()

	Vector< T >::Vector (size_t size)

	Vector< T >::Vector (const Vector &x)

	Vector< T >::~Vector ()

Vector &	Vector< T >::operator= (const Vector &x)

T &	Vector< T >::operator[] (size_t index)

const T &	Vector< T >::operator[] (size_t index) const

size_t	Vector< T >::size () const

size_t	Vector< T >::count () const

void	Vector< T >::pushBack (const T &value)

void	Vector< T >::pushBack (T &&value)

T	Vector< T >::popBack ()

void	Vector< T >::pushFront (const T &value)

void	Vector< T >::pushFront (T &&value)

T	Vector< T >::popFront ()

void	Vector< T >::setAt (size_t idx, const T &value)

void	Vector< T >::clear (bool freeMem=false)

void	Vector< T >::erase (size_t index)

Iterator	Vector< T >::erase (Iterator iter)

ReverseIterator	Vector< T >::erase (ReverseIterator iter)

void	Vector< T >::assign (const Vector &x)

bool	Vector< T >::tryReserve (size_t size, bool copy=true)

void	Vector< T >::reserve (size_t size, bool copy)

void	Vector< T >::reserve (size_t size, bool copy, bool free)

void	Vector< T >::swap (Iterator a, Iterator b)

void	Vector< T >::insert (size_t index, const T &value)

Variables
template class EXPORTED_PUBLIC	StaticCord< 8 >

template class EXPORTED_PUBLIC	StaticString< 32 >

template class EXPORTED_PUBLIC	StaticString< 64 >

template class EXPORTED_PUBLIC	StaticString< 128 >

template class EXPORTED_PUBLIC	StaticString< 1024 >

Detailed Description

Utilities.

Classes, functions, defines that are utilised in the whole kernel

Macro Definition Documentation

◆ BIG_TO_HOST16

#define BIG_TO_HOST16 ( x ) (x)

Definition at line 86 of file utility.h.

◆ BIG_TO_HOST32

#define BIG_TO_HOST32 ( x ) (x)

Definition at line 87 of file utility.h.

◆ BIG_TO_HOST64

#define BIG_TO_HOST64 ( x ) (x)

Definition at line 88 of file utility.h.

◆ BIG_TO_HOST8

#define BIG_TO_HOST8 ( x ) (x)

Definition at line 85 of file utility.h.

◆ BS16

#define BS16 ( x ) __builtin_bswap16((uint16_t)(x))

Definition at line 56 of file utility.h.

◆ BS32

#define BS32 ( x ) __builtin_bswap32((uint32_t)(x))

Definition at line 57 of file utility.h.

◆ BS64

#define BS64 ( x ) __builtin_bswap64((uint64_t)(x))

Definition at line 58 of file utility.h.

◆ BS8

#define BS8 ( x ) ((uint8_t)(x))

Definition at line 55 of file utility.h.

◆ HASH_STRINGVIEWS_BY_DEFAULT

#define HASH_STRINGVIEWS_BY_DEFAULT false

Definition at line 26 of file StringView.h.

◆ HOST_TO_BIG16

#define HOST_TO_BIG16 ( x ) (x)

Definition at line 91 of file utility.h.

◆ HOST_TO_BIG32

#define HOST_TO_BIG32 ( x ) (x)

Definition at line 92 of file utility.h.

◆ HOST_TO_BIG64

#define HOST_TO_BIG64 ( x ) (x)

Definition at line 93 of file utility.h.

◆ HOST_TO_BIG8

#define HOST_TO_BIG8 ( x ) (x)

Definition at line 90 of file utility.h.

◆ HOST_TO_LITTLE16

#define HOST_TO_LITTLE16 ( x ) BS16((x))

Definition at line 101 of file utility.h.

◆ HOST_TO_LITTLE32

#define HOST_TO_LITTLE32 ( x ) BS32((x))

Definition at line 102 of file utility.h.

◆ HOST_TO_LITTLE64

#define HOST_TO_LITTLE64 ( x ) BS64((x))

Definition at line 103 of file utility.h.

◆ HOST_TO_LITTLE8

#define HOST_TO_LITTLE8 ( x ) BS8((x))

Definition at line 100 of file utility.h.

◆ LITTLE_TO_HOST16

#define LITTLE_TO_HOST16 ( x ) BS16((x))

Definition at line 96 of file utility.h.

◆ LITTLE_TO_HOST32

#define LITTLE_TO_HOST32 ( x ) BS32((x))

Definition at line 97 of file utility.h.

◆ LITTLE_TO_HOST64

#define LITTLE_TO_HOST64 ( x ) BS64((x))

Definition at line 98 of file utility.h.

◆ LITTLE_TO_HOST8

#define LITTLE_TO_HOST8 ( x ) BS8((x))

Definition at line 95 of file utility.h.

◆ MAX_FUNCTION_NAME

#define MAX_FUNCTION_NAME 128

Definition at line 107 of file utility.h.

◆ MAX_PARAM_LENGTH

#define MAX_PARAM_LENGTH 64

Definition at line 109 of file utility.h.

◆ MAX_PARAMS

#define MAX_PARAMS 32

Definition at line 108 of file utility.h.

◆ STRING_DISABLE_EXPENSIVE_COPY_CONSTRUCTION

#define STRING_DISABLE_EXPENSIVE_COPY_CONSTRUCTION 1

Definition at line 36 of file String.h.

Typedef Documentation

◆ HugeStaticString

typedef StaticString<1024> HugeStaticString

Definition at line 527 of file StaticString.h.

◆ LargeStaticString

typedef StaticString<128> LargeStaticString

Definition at line 526 of file StaticString.h.

◆ MemoryAllocator

typedef RangeList<uintptr_t> MemoryAllocator

Definition at line 28 of file MemoryAllocator.h.

◆ NormalStaticString

typedef StaticString<64> NormalStaticString

Definition at line 525 of file StaticString.h.

◆ TinyStaticString

typedef StaticString<32> TinyStaticString

Definition at line 524 of file StaticString.h.

Function Documentation

◆ addChild()

template<class T >

void RadixTree< T >::Node::addChild ( Node * pNode )

Adds a new child.

Definition at line 694 of file RadixTree.h.

Referenced by RadixTree< T >::cloneNode(), RadixTree< T >::insert(), and RadixTree< T >::remove().

Here is the caller graph for this function:

◆ assign() [1/2]

template<typename T , size_t nodePoolSize>

void List< T, nodePoolSize >::assign ( const List< T, nodePoolSize > & x )

Copy the content of a List into this List

Parameters

[in] x the reference List

Definition at line 412 of file List.h.

Referenced by List< T, nodePoolSize >::List().

Here is the caller graph for this function:

◆ assign() [2/2]

template<class T >

void Vector< T >::assign ( const Vector< T > & x )

Copy the content of a Vector into this Vector

Parameters

[in] x the reference Vector

Definition at line 414 of file Vector.h.

Referenced by Vector< T >::Vector().

Here is the caller graph for this function:

◆ clear() [1/3]

template<typename T , size_t nodePoolSize>

void List< T, nodePoolSize >::clear ( )

Remove all elements from the List

Definition at line 399 of file List.h.

References _ListNode_t< T >::m_Next.

Referenced by Ohci::reclaimTransferDescriptors().

Here is the caller graph for this function:

◆ clear() [2/3]

template<class T >

void RadixTree< T >::clear ( )

Clear the tree.

Definition at line 642 of file RadixTree.h.

Referenced by RadixTree< T >::RadixTree().

Here is the caller graph for this function:

◆ clear() [3/3]

template<class T >

void Vector< T >::clear ( bool freeMem = false )

Clear the Vector. Pass freeMem = true to also free the memory consumed by the Vector. Pass freeMem = false to retain the memory for future Vector usage.

Definition at line 378 of file Vector.h.

Referenced by PosixSubsystem::copyDescriptors(), Directory::emptyCache(), PosixSubsystem::freeMultipleFds(), VFS::getMounts(), LockManager::LockManager(), PciAtaController::PciAtaController(), X86CommonPhysicalMemoryManager::shutdown(), KernelElf::unloadModules(), and HostedPhysicalMemoryManager::~HostedPhysicalMemoryManager().

Here is the caller graph for this function:

◆ cloneNode()

template<class T >

RadixTree< T >::Node * RadixTree< T >::cloneNode	(	Node *	node,
		Node *	parent
	)

private

Internal function to create a copy of a subtree.

Definition at line 622 of file RadixTree.h.

References RadixTree< T >::Node::addChild(), Vector< T >::begin(), Vector< T >::end(), RadixTree< T >::Node::m_Children, RadixTree< T >::Node::m_Key, and RadixTree< T >::Node::value.

Referenced by RadixTree< T >::RadixTree().

Here is the caller graph for this function:

◆ count() [1/3]

template<typename T , size_t nodePoolSize>

size_t List< T, nodePoolSize >::count ( ) const

Get the number of elements in the List

Definition at line 212 of file List.h.

Referenced by Scheduler::acquireProcess(), Ehci::cancelAsyncAndDrain(), Ohci::cancelAsyncAndDrain(), Uhci::cancelAsyncAndDrain(), Event::completeDelivery(), Event::deregisterThread(), Scheduler::getNumProcesses(), Ehci::irq(), Ohci::irq(), Uhci::irq(), Event::pendingCount(), Uhci::reclaimQueueHeadLocked(), UsbPnP::reprobeDevices(), Thread::shutdown(), and Event::waitForDeliveries().

Here is the caller graph for this function:

◆ count() [2/3]

template<class T >

size_t RadixTree< T >::count ( ) const

Get the number of elements in the Tree

Returns: the number of elements in the Tree

Definition at line 348 of file RadixTree.h.

◆ count() [3/3]

template<class T >

size_t Vector< T >::count ( ) const

Get the number of elements in the Vector

Returns: the number of elements in the Vector

Definition at line 270 of file Vector.h.

Referenced by NetworkStack::acquireDevice(), Process::acquireThread(), Ext2Directory::addEntry(), ScsiDisk::align(), Ext2File::allocateFileRange(), RamFile::allocateFileRange(), IoPortManager::allocateIoPortList(), PhysicalMemoryManager::allocateMemoryRegionList(), VFS::checkAccess(), RamFile::ShrinkPlan::commit(), Device::Device(), UsbHub::disconnectAllDevices(), HostedVirtualAddressSpace::doAllocateStack(), X64VirtualAddressSpace::doAllocateStack(), RadixTree< T >::Node::doNext(), Scheduler::drainDeferredTimeAccounting(), Ext2Node::ensureLargeEnough(), Directory::enumerate(), KernelElf::executeModules(), Ext2File::Ext2File(), IoPortManager::freeIoPortList(), PhysicalMemoryManager::freeMemoryRegionList(), PosixSubsystem::freeMultipleFds(), ScsiDisk::getAlignmentPoint(), KernelElf::getModuleCount(), Device::getNumChildren(), Process::getNumThreads(), ProcessorBase::informationAt(), HostedPhysicalMemoryManager::initialisationDone(), PosixSubsystem::invoke(), Directory::lookupChildAt(), InputManager::mainThread(), KernelElf::prepareRuntimeModules(), Ext2File::readPage(), Ext2File::readPages(), RadixTree< T >::remove(), Ext2Directory::removeEntryLocked(), Ext2Directory::sync(), FatFilesystem::sync(), Ext2File::syncPages(), File::syncRange(), KernelElf::waitForModulesToLoad(), and Ext2File::~Ext2File().

Here is the caller graph for this function:

◆ doNext()

template<class T >

RadixTree< T >::Node * RadixTree< T >::Node::doNext ( ) const

private

Returns the next Node to look at during an in-order iteration.

Definition at line 781 of file RadixTree.h.

References Vector< T >::count(), RadixTree< T >::Node::getFirstChild(), RadixTree< T >::Node::getNextSibling(), RadixTree< T >::Node::m_Children, and RadixTree< T >::Node::m_pParent.

◆ dump() [1/2]

template<class T >

void RadixTree< T >::Node::dump ( void(*)(const char *s) emit_line ) const

Definition at line 821 of file RadixTree.h.

◆ dump() [2/2]

template<class T >

void RadixTree< T >::dump ( void(*)(const char *s) emit_line ) const

Dump the RadixTree in dot format.

Definition at line 655 of file RadixTree.h.

◆ erase() [1/5]

template<typename T , size_t nodePoolSize>

List< T, nodePoolSize >::Iterator List< T, nodePoolSize >::erase ( Iterator & Iter )

Erase an element

Parameters

[in] iterator the iterator that points to the element

Definition at line 352 of file List.h.

References Iterator< originalT, Struct, FunctionPrev, FunctionNext, T >::__getNode(), _ListNode_t< T >::m_Next, and _ListNode_t< T >::m_Previous.

Referenced by Event::completeDelivery(), EpollInstance::control(), Thread::cullEvent(), Thread::cullEvent(), RingBuffer< T, preallocatedSize >::cullMonitorTargets(), RingBuffer< T, preallocatedSize >::cullMonitorTargets(), RingBuffer< T, preallocatedSize >::cullMonitorTargets(), Thread::cullSignalEvent(), Event::deregisterThread(), Thread::getNextEvent(), Ohci::irq(), Uhci::irq(), User::leave(), Group::leave(), Scheduler::removeProcess(), and Thread::transferProcessSignalsTo().

Here is the caller graph for this function:

◆ erase() [2/5]

template<class T >

Vector< T >::Iterator Vector< T >::erase ( Iterator iter )

Erase one Element

Definition at line 402 of file Vector.h.

◆ erase() [3/5]

template<typename T , size_t nodePoolSize>

List< T, nodePoolSize >::ReverseIterator List< T, nodePoolSize >::erase ( ReverseIterator & Iter )

Erase an element with a reverse iterator

Parameters

[in] reverse iterator the iterator that points to the element

Definition at line 375 of file List.h.

References Iterator< originalT, Struct, FunctionPrev, FunctionNext, T >::__getNode(), _ListNode_t< T >::m_Next, and _ListNode_t< T >::m_Previous.

◆ erase() [4/5]

template<class T >

Vector< T >::ReverseIterator Vector< T >::erase ( ReverseIterator iter )

Erase one Element

Definition at line 408 of file Vector.h.

◆ erase() [5/5]

template<class T >

void Vector< T >::erase ( size_t index )

Erase the element at the given index.

Definition at line 389 of file Vector.h.

Referenced by NetworkStack::deRegisterDevice(), IoPortManager::free(), Device::removeChild(), Device::removeChild(), Process::removeThread(), Ext2Directory::sync(), HostedPhysicalMemoryManager::unmapRegion(), X86CommonPhysicalMemoryManager::unmapRegion(), Arm64PhysicalMemoryManager::unmapRegion(), Armv7PhysicalMemoryManager::unmapRegion(), and Ext2File::~Ext2File().

Here is the caller graph for this function:

◆ findChild()

template<class T >

RadixTree< T >::Node * RadixTree< T >::Node::findChild ( const char * cpKey ) const

Locates a child of this node, given the key portion of key (lookahead on the first token)

Definition at line 683 of file RadixTree.h.

Referenced by RadixTree< T >::insert(), RadixTree< T >::lookup(), and RadixTree< T >::remove().

Here is the caller graph for this function:

◆ getFirstChild()

template<class T >

RadixTree< T >::Node * RadixTree< T >::Node::getFirstChild ( ) const

Returns the first found child of the node.

Definition at line 769 of file RadixTree.h.

Referenced by RadixTree< T >::Node::doNext(), and RadixTree< T >::remove().

Here is the caller graph for this function:

◆ getNextSibling()

template<class T >

RadixTree< T >::Node * RadixTree< T >::Node::getNextSibling ( ) const

private

Returns the node's next sibling, by looking at its parent's children.

Definition at line 804 of file RadixTree.h.

Referenced by RadixTree< T >::Node::doNext().

Here is the caller graph for this function:

◆ insert() [1/2]

template<class T >

void RadixTree< T >::insert	(	const String &	key,
		const T &	value
	)

Add an element to the Tree.

Parameters

[in]	key	the key
[in]	value	the element

Definition at line 353 of file RadixTree.h.

References RadixTree< T >::Node::addChild(), RadixTree< T >::Node::findChild(), String::ltrim(), RadixTree< T >::Node::m_Key, RadixTree< T >::Node::matchKey(), and RadixTree< T >::Node::replaceChild().

Referenced by DynamicLinker::loadObject(), and DynamicLinker::loadProgram().

Here is the caller graph for this function:

◆ insert() [2/2]

template<class T >

void Vector< T >::insert	(	size_t	index,
		const T &	value
	)

Insert into the vector, moving all items after the given position along.

Definition at line 496 of file Vector.h.

◆ List() [1/2]

template<typename T , size_t nodePoolSize>

List< T, nodePoolSize >::List ( )

Default constructor, does nothing

Definition at line 187 of file List.h.

◆ List() [2/2]

template<typename T , size_t nodePoolSize>

List< T, nodePoolSize >::List ( const List< T, nodePoolSize > & x )

Copy-constructor

Parameters

[in] x reference object

Definition at line 191 of file List.h.

References List< T, nodePoolSize >::assign().

◆ lookup()

template<class T >

bool RadixTree< T >::lookup	(	const String &	key,
		T &	value
	)		const

Attempts to find an element with the given key.

This stable scalar-and-output form is safe across the native-kernel and cross-compiled module boundary. On failure, value is reset to T().

Definition at line 454 of file RadixTree.h.

References RadixTree< T >::Node::findChild(), RadixTree< T >::Node::m_Key, and RadixTree< T >::Node::matchKey().

Referenced by DynamicLinker::loadObject(), and DynamicLinker::loadProgram().

Here is the caller graph for this function:

◆ MakeConstantString()

template<size_t N>

ConstantString< N > MakeConstantString ( const char(&) str[N] )

Definition at line 285 of file String.h.

◆ makePair()

template<typename T1 , typename T2 >

Pair< T1, T2 > makePair	(	T1	a,
		T2	b
	)

Definition at line 88 of file Pair.h.

◆ matchKey()

template<class T >

RadixTree< T >::Node::MatchType RadixTree< T >::Node::matchKey	(	const char *	cpKey,
		size_t &	offset
	)		const

Compares cpKey and this node's key, returning the type of match found. The offset out parameter provides the position where a partial match ceases.

Definition at line 721 of file RadixTree.h.

References RadixTree< T >::m_bCaseSensitive.

Referenced by RadixTree< T >::insert(), RadixTree< T >::lookup(), and RadixTree< T >::remove().

Here is the caller graph for this function:

◆ operator!=() [1/2]

template<class T1 , class T2 >

bool operator!=	(	const Pair< T1, T2 > &	left,
		const Pair< T1, T2 > &	right
	)

Definition at line 57 of file Pair.h.

◆ operator!=() [2/2]

template<class T1 , class T2 >

bool operator!=	(	const T1 &	x1,
		const T2 &	x2
	)

Global != operator for types with overloaded == operator.

Before C++20, provide != for every type that provides ==. Newer modes rewrite inequality through the equality operator.

Parameters

[in]	x1	first operand
[in]	x2	second operand

Returns: true, if the objects are not equal, false otherwise

Definition at line 34 of file template.h.

◆ operator++()

template<class T >

T operator++	(	T &	x,
		int
	)

Global postincrement operator for types with overloaded preincrement operator.

Global postincrement operator is provided for every type that provides a preincrement operator.

Parameters

[in] x object

Returns: original object

Definition at line 43 of file template.h.

◆ operator--()

template<class T >

T operator--	(	T &	x,
		int
	)

Global postdecrement operator for types with overloaded predecrement operator.

Global postdecrement operator is provided for every type that provides a predecrement operator.

Parameters

[in] x object

Returns: original object

Definition at line 53 of file template.h.

◆ operator<()

template<class T1 , class T2 >

bool operator<	(	const Pair< T1, T2 > &	left,
		const Pair< T1, T2 > &	right
	)

Definition at line 62 of file Pair.h.

◆ operator<=()

template<class T1 , class T2 >

bool operator<=	(	const Pair< T1, T2 > &	left,
		const Pair< T1, T2 > &	right
	)

Definition at line 73 of file Pair.h.

◆ operator=() [1/3]

template<typename T , size_t nodePoolSize>

List< T, nodePoolSize > & List< T, nodePoolSize >::operator= ( const List< T, nodePoolSize > & x )

Assignment operator

Parameters

[in] x the object that should be copied

Definition at line 202 of file List.h.

◆ operator=() [2/3]

template<class T >

RadixTree< T > & RadixTree< T >::operator= ( const RadixTree< T > & x )

The assignment operator

Parameters

[in] x the object that should be copied

Todo:: check for incompatible case-sensitivity?

Definition at line 335 of file RadixTree.h.

◆ operator=() [3/3]

template<class T >

Vector< T > & Vector< T >::operator= ( const Vector< T > & x )

The assignment operator

Parameters

[in] x the object that should be copied

Definition at line 243 of file Vector.h.

◆ operator==() [1/3]

template<typename originalT , class Struct , Struct *(Struct::*)() FunctionPrev, Struct *(Struct::*)() FunctionNext, typename T1 , typename T2 >

bool operator==	(	const Iterator< originalT, Struct, FunctionPrev, FunctionNext, T1 > &	x1,
		const Iterator< originalT, Struct, FunctionPrev, FunctionNext, T2 > &	x2
	)

Comparison operator for the Iterator class

Parameters

[in]	x1	the first operand
[in]	x2	the second operand

Returns: true, if the two iterator point to the same object, false otherwise

Definition at line 256 of file Iterator.h.

References Iterator< originalT, Struct, FunctionPrev, FunctionNext, T >::m_Node.

◆ operator==() [2/3]

template<class T1 , class T2 >

bool operator==	(	const Pair< T1, T2 > &	left,
		const Pair< T1, T2 > &	right
	)

Definition at line 52 of file Pair.h.

◆ operator==() [3/3]

template<typename originalT , class Struct , Struct *(Struct::*)() FunctionPrev, Struct *(Struct::*)() FunctionNext, typename K1 , typename T1 , typename K2 , typename T2 >

bool operator==	(	const TreeIterator< originalT, Struct, FunctionPrev, FunctionNext, K1, T1 > &	x1,
		const TreeIterator< originalT, Struct, FunctionPrev, FunctionNext, K2, T2 > &	x2
	)

Comparison operator for the TreeIterator class

Parameters

[in]	x1	the first operand
[in]	x2	the second operand

Returns: true, if the two iterator point to the same object, false otherwise

Definition at line 269 of file Iterator.h.

References TreeIterator< originalT, Struct, FunctionPrev, FunctionNext, K, T >::m_Node.

◆ operator>()

template<class T1 , class T2 >

bool operator>	(	const Pair< T1, T2 > &	left,
		const Pair< T1, T2 > &	right
	)

Definition at line 78 of file Pair.h.

◆ operator>=()

template<class T1 , class T2 >

bool operator>=	(	const Pair< T1, T2 > &	left,
		const Pair< T1, T2 > &	right
	)

Definition at line 83 of file Pair.h.

◆ operator[]() [1/2]

template<class T >

T & Vector< T >::operator[] ( size_t index )

The [] operator

Parameters

[in] index the index of the element that should be returned

Returns: the element at index index

Definition at line 249 of file Vector.h.

◆ operator[]() [2/2]

template<class T >

const T & Vector< T >::operator[] ( size_t index ) const

Definition at line 257 of file Vector.h.

◆ page_align()

EXPORTED_PUBLIC void * page_align ( void * p )

Page-align the given pointer.

Definition at line 29 of file utility.cc.

Referenced by HostedVirtualAddressSpace::detachMapping(), HostedVirtualAddressSpace::getMapping(), HostedVirtualAddressSpace::handleCopyOnWriteFault(), X64VirtualAddressSpace::handleCopyOnWriteFault(), HostedVirtualAddressSpace::isMapped(), HostedVirtualAddressSpace::map(), HostedVirtualAddressSpace::setFlags(), HostedVirtualAddressSpace::trySetFlags(), and HostedVirtualAddressSpace::unmap().

Here is the caller graph for this function:

◆ popBack() [1/2]

template<typename T , size_t nodePoolSize>

T List< T, nodePoolSize >::popBack ( )

Remove the last element from the List

Returns: the previously last element

Definition at line 278 of file List.h.

◆ popBack() [2/2]

template<class T >

T Vector< T >::popBack ( )

Remove the element from the back and return it

Returns: the removed element

Definition at line 303 of file Vector.h.

Referenced by RamFile::ShrinkPlan::commit(), HostedVirtualAddressSpace::doAllocateStack(), X64VirtualAddressSpace::doAllocateStack(), IoPortManager::freeIoPortList(), PhysicalMemoryManager::freeMemoryRegionList(), and LockManager::released().

Here is the caller graph for this function:

◆ popFront() [1/2]

template<typename T , size_t nodePoolSize>

T List< T, nodePoolSize >::popFront ( )

Remove the first element in the List

Returns: the previously first element

Definition at line 330 of file List.h.

Referenced by Ehci::cancelAsyncAndDrain(), Ohci::cancelAsyncAndDrain(), Uhci::cancelAsyncAndDrain(), Ehci::irq(), Ohci::irq(), Uhci::irq(), Uhci::reclaimQueueHeadLocked(), UsbPnP::reprobeDevices(), and Thread::shutdown().

Here is the caller graph for this function:

◆ popFront() [2/2]

template<class T >

T Vector< T >::popFront ( )

Remove the element from the front and return it

Returns: the removed element

Definition at line 357 of file Vector.h.

Referenced by PosixSubsystem::invoke().

Here is the caller graph for this function:

◆ prependKey()

template<class T >

void RadixTree< T >::Node::prependKey ( const String & cpKey )

Sets the node's key to the concatenation of cpKey and the current key.

Parameters

cpKey Key to prepend to the current key.

Definition at line 774 of file RadixTree.h.

Referenced by RadixTree< T >::remove().

Here is the caller graph for this function:

◆ pushBack() [1/4]

template<typename T , size_t nodePoolSize>

void List< T, nodePoolSize >::pushBack ( const T & value )

Add a value to the end of the List

Parameters

[in] value the value that should be added

Definition at line 216 of file List.h.

References _ListNode_t< T >::m_Next, _ListNode_t< T >::m_Previous, and _ListNode_t< T >::value.

Referenced by Scheduler::addProcess(), PerProcessorScheduler::addThread(), PerProcessorScheduler::addThread(), Ohci::addTransferToTransaction(), Uhci::addTransferToTransaction(), Ohci::cancelAsyncAndDrain(), Uhci::cancelAsyncAndDrain(), EpollInstance::control(), Elf::create(), Elf::createNeededOnly(), PosixSubsystem::freeMultipleFds(), VmwareGraphics::getScreenModes(), VirtioGpu::getScreenModes(), Scheduler::initialise(), Ehci::irq(), Ohci::irq(), Uhci::irq(), User::join(), Group::join(), LwipSocketSyscalls::poll(), Event::registerThread(), UsbPnP::reprobeDevices(), Thread::sendEvent(), and Ohci::terminalizeEDForTeardown().

Here is the caller graph for this function:

◆ pushBack() [2/4]

template<class T >

void Vector< T >::pushBack ( const T & value )

Add an element to the end of the Vector

Parameters

[in] value the element

Definition at line 275 of file Vector.h.

Referenced by LockManager::acquired(), Device::addChild(), Process::addThread(), ScsiDisk::align(), IoPortManager::allocate(), Ext2File::allocateFileRange(), RamFile::allocateFileRange(), IoPortManager::allocateIoPortList(), PhysicalMemoryManager::allocateMemoryRegionList(), HostedPhysicalMemoryManager::allocateRegion(), X86CommonPhysicalMemoryManager::allocateRegion(), Arm64PhysicalMemoryManager::allocateRegion(), Armv7PhysicalMemoryManager::allocateRegion(), Process::beginTermination(), HostedVirtualAddressSpace::clone(), X64VirtualAddressSpace::clone(), PosixSubsystem::copyDescriptors(), Thread::cullEvent(), Thread::cullSignalEvent(), Device::Device(), Scheduler::drainDeferredTimeAccounting(), Ext2File::Ext2File(), Ext2Filesystem::findFreeBlocksInGroup(), PosixSubsystem::freeMultipleFds(), HostedVirtualAddressSpace::freeStack(), X64VirtualAddressSpace::freeStack(), KernelElf::invokeInitModule(), KernelElf::loadModule(), KernelElf::loadModule(), InputManager::mainThread(), HidReport::parseDescriptor(), KernelElf::prepareRuntimeModules(), InputManager::putNotification(), RamFile::readBlock(), NetworkStack::registerDevice(), LockManager::released(), InputManager::shutdown(), FatFilesystem::sync(), File::syncRange(), KernelElf::unloadModules(), and VFS::~VFS().

Here is the caller graph for this function:

◆ pushBack() [3/4]

template<typename T , size_t nodePoolSize>

void List< T, nodePoolSize >::pushBack ( T && value )

Add a value to the end of the List

Parameters

[in] value the value that should be added

Definition at line 231 of file List.h.

References _ListNode_t< T >::m_Next, _ListNode_t< T >::m_Previous, and _ListNode_t< T >::value.

◆ pushBack() [4/4]

template<class T >

void Vector< T >::pushBack ( T && value )

Move a value to the end of the Vector

Parameters

[in] value the value that should be added

Definition at line 289 of file Vector.h.

◆ pushFront() [1/4]

template<typename T , size_t nodePoolSize>

void List< T, nodePoolSize >::pushFront ( const T & value )

Add a value to the front of the List

Parameters

[in] value the value that should be added

Definition at line 300 of file List.h.

References _ListNode_t< T >::m_Next, _ListNode_t< T >::m_Previous, and _ListNode_t< T >::value.

Referenced by Ohci::irq(), Uhci::irq(), and Thread::transferProcessSignalsTo().

Here is the caller graph for this function:

◆ pushFront() [2/4]

template<class T >

void Vector< T >::pushFront ( const T & value )

Add an element to the front of the Vector

Parameters

[in] value the element

Definition at line 313 of file Vector.h.

Referenced by PosixSubsystem::invoke().

Here is the caller graph for this function:

◆ pushFront() [3/4]

template<typename T , size_t nodePoolSize>

void List< T, nodePoolSize >::pushFront ( T && value )

Add a value to the front of the List

Parameters

[in] value the value that should be added

Definition at line 315 of file List.h.

References _ListNode_t< T >::m_Next, _ListNode_t< T >::m_Previous, and _ListNode_t< T >::value.

◆ pushFront() [4/4]

template<class T >

void Vector< T >::pushFront ( T && value )

Move a value to the end of the Vector

Parameters

[in] value the value that should be added

Definition at line 335 of file Vector.h.

◆ RadixTree() [1/3]

template<class T >

RadixTree< T >::RadixTree ( )

The default constructor, does nothing

Definition at line 313 of file RadixTree.h.

◆ RadixTree() [2/3]

template<class T >

RadixTree< T >::RadixTree ( bool bCaseSensitive )

Constructor that offers case sensitivity adjustment.

Definition at line 316 of file RadixTree.h.

◆ RadixTree() [3/3]

template<class T >

RadixTree< T >::RadixTree ( const RadixTree< T > & x )

The copy-constructor

Parameters

[in] x the reference object to copy

Definition at line 326 of file RadixTree.h.

References RadixTree< T >::clear(), RadixTree< T >::cloneNode(), RadixTree< T >::m_nItems, RadixTree< T >::m_pRoot, and RadixTree< T >::returnNode().

◆ remove()

template<class T >

void RadixTree< T >::remove ( const String & key )

Attempts to remove an element with the given key.

Definition at line 505 of file RadixTree.h.

References RadixTree< T >::Node::addChild(), Vector< T >::count(), RadixTree< T >::Node::findChild(), RadixTree< T >::Node::getFirstChild(), RadixTree< T >::Node::m_Children, RadixTree< T >::Node::m_Key, RadixTree< T >::Node::matchKey(), RadixTree< T >::Node::prependKey(), and RadixTree< T >::Node::removeChild().

◆ removeChild()

template<class T >

void RadixTree< T >::Node::removeChild ( Node * pChild )

Removes a child (doesn't delete it)

Definition at line 710 of file RadixTree.h.

Referenced by RadixTree< T >::remove().

Here is the caller graph for this function:

◆ replaceChild()

template<class T >

void RadixTree< T >::Node::replaceChild	(	Node *	pNodeOld,
		Node *	pNodeNew
	)

Replaces a currently existing child.

Definition at line 700 of file RadixTree.h.

Referenced by RadixTree< T >::insert().

Here is the caller graph for this function:

◆ reserve() [1/2]

template<class T >

void Vector< T >::reserve	(	size_t	size,
		bool	copy
	)

Reserve space for size elements

Parameters

[in]	size	the number of elements to reserve space for
[in]	copy	Should we copy the old contents over?

Definition at line 453 of file Vector.h.

Referenced by KernelElf::prepareRuntimeModules(), and Vector< T >::Vector().

Here is the caller graph for this function:

◆ reserve() [2/2]

template<class T >

void Vector< T >::reserve	(	size_t	size,
		bool	copy,
		bool	free
	)

private

Internal reserve() function.

Parameters

[in]	size	the number of elements to reserve space for
[in]	copy	Should we copy the old contents over?
[in]	free	should we free the old buffer?

Definition at line 458 of file Vector.h.

◆ returnAllChildren()

template<class T >

void RadixTree< T >::Node::returnAllChildren ( )

Definition at line 671 of file RadixTree.h.

◆ setAt()

template<class T >

void Vector< T >::setAt	(	size_t	idx,
		const T &	value
	)

Set an element at the given index, if it exists.

Definition at line 372 of file Vector.h.

◆ setKey() [1/3]

template<class T >

void RadixTree< T >::Node::setKey ( const char * cpKey )

Definition at line 754 of file RadixTree.h.

◆ setKey() [2/3]

template<class T >

void RadixTree< T >::Node::setKey	(	const char *	cpKey,
		size_t	lengthHint
	)

If you know the length of cpKey, this can be a small boost.

Definition at line 759 of file RadixTree.h.

◆ setKey() [3/3]

template<class T >

void RadixTree< T >::Node::setKey ( const String & cpKey )

If you already have a String version of the key, this is fastest.

Definition at line 764 of file RadixTree.h.

◆ size() [1/2]

template<typename T , size_t nodePoolSize>

size_t List< T, nodePoolSize >::size ( ) const

Get the number of elements we reserved space for

Returns: number of elements we reserved space for

Definition at line 208 of file List.h.

◆ size() [2/2]

template<class T >

size_t Vector< T >::size ( ) const

Get the number of elements that we have reserved space for

Returns: the number of elements that we have reserved space for

Definition at line 265 of file Vector.h.

Referenced by Scheduler::drainDeferredTimeAccounting(), and Vector< T >::Vector().

Here is the caller graph for this function:

◆ swap()

template<class T >

void Vector< T >::swap	(	Iterator	a,
		Iterator	b
	)

Swap the two elements.

Definition at line 481 of file Vector.h.

◆ tryPushBack() [1/2]

template<typename T , size_t nodePoolSize>

bool List< T, nodePoolSize >::tryPushBack ( const T & value )

A failed insertion leaves the list unchanged.

Definition at line 246 of file List.h.

References _ListNode_t< T >::m_Next, _ListNode_t< T >::m_Previous, and _ListNode_t< T >::value.

Referenced by MappingList< Object >::reserveBack().

Here is the caller graph for this function:

◆ tryPushBack() [2/2]

template<typename T , size_t nodePoolSize>

bool List< T, nodePoolSize >::tryPushBack ( T && value )

Definition at line 262 of file List.h.

◆ tryReserve()

template<class T >

bool Vector< T >::tryReserve	(	size_t	size,
		bool	copy = `true`
	)

Definition at line 426 of file Vector.h.

◆ Vector() [1/3]

template<class T >

Vector< T >::Vector ( )

The default constructor, does nothing

Definition at line 224 of file Vector.h.

◆ Vector() [2/3]

template<class T >

Vector< T >::Vector ( const Vector< T > & x )

The copy-constructor

Parameters

[in] x the reference object to copy

Definition at line 232 of file Vector.h.

References Vector< T >::assign().

◆ Vector() [3/3]

template<class T >

Vector< T >::Vector ( size_t size )

explicit

Reserves space for size elements

Parameters

[in] size the number of elements

Definition at line 227 of file Vector.h.

References Vector< T >::reserve(), and Vector< T >::size().

◆ ~List()

template<typename T , size_t nodePoolSize>

List< T, nodePoolSize >::~List ( )

Destructor, deallocates memory

Definition at line 196 of file List.h.

References assert.

◆ ~Node()

template<class T >

RadixTree< T >::Node::~Node ( )

Definition at line 666 of file RadixTree.h.

◆ ~RadixTree()

template<class T >

RadixTree< T >::~RadixTree ( )

The destructor, deallocates memory

Definition at line 320 of file RadixTree.h.

◆ ~Vector()

template<class T >

Vector< T >::~Vector ( )

The destructor, deallocates memory

Definition at line 237 of file Vector.h.

Classes

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ BIG_TO_HOST16

◆ BIG_TO_HOST32

◆ BIG_TO_HOST64

◆ BIG_TO_HOST8

◆ BS16

◆ BS32

◆ BS64

◆ BS8

◆ HASH_STRINGVIEWS_BY_DEFAULT

◆ HOST_TO_BIG16

◆ HOST_TO_BIG32

◆ HOST_TO_BIG64

◆ HOST_TO_BIG8

◆ HOST_TO_LITTLE16

◆ HOST_TO_LITTLE32

◆ HOST_TO_LITTLE64

◆ HOST_TO_LITTLE8

◆ LITTLE_TO_HOST16

◆ LITTLE_TO_HOST32

◆ LITTLE_TO_HOST64

◆ LITTLE_TO_HOST8

◆ MAX_FUNCTION_NAME

◆ MAX_PARAM_LENGTH

◆ MAX_PARAMS

◆ STRING_DISABLE_EXPENSIVE_COPY_CONSTRUCTION

Typedef Documentation

◆ HugeStaticString

◆ LargeStaticString

◆ MemoryAllocator

◆ NormalStaticString

◆ TinyStaticString

Function Documentation

◆ addChild()

◆ assign() [1/2]

◆ assign() [2/2]

◆ clear() [1/3]

◆ clear() [2/3]

◆ clear() [3/3]

◆ cloneNode()

◆ count() [1/3]

◆ count() [2/3]

◆ count() [3/3]

◆ doNext()

◆ dump() [1/2]

◆ dump() [2/2]

◆ erase() [1/5]

◆ erase() [2/5]

◆ erase() [3/5]

◆ erase() [4/5]

◆ erase() [5/5]

◆ findChild()

◆ getFirstChild()

◆ getNextSibling()

◆ insert() [1/2]

◆ insert() [2/2]

◆ List() [1/2]

◆ List() [2/2]

◆ lookup()

◆ MakeConstantString()

◆ makePair()

◆ matchKey()

◆ operator!=() [1/2]

◆ operator!=() [2/2]

◆ operator++()

◆ operator--()

◆ operator<()

◆ operator<=()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ operator==() [1/3]

◆ operator==() [2/3]

◆ operator==() [3/3]