splay-tree.c File Reference

#include "wizard/studio.h"
#include "wizard/exception.h"
#include "wizard/exception-private.h"
#include "wizard/log.h"
#include "wizard/memory_.h"
#include "wizard/splay-tree.h"
#include "wizard/semaphore.h"
#include "wizard/string_.h"

Include dependency graph for splay-tree.c:

Go to the source code of this file.

Data Structures
struct	_NodeInfo
struct	_SplayTreeInfo
Defines
#define	MaxSplayTreeDepth   1024
Typedefs
typedef struct _NodeInfo	NodeInfo
Functions
static int	IterateOverSplayTree (SplayTreeInfo *, int(*)(NodeInfo *, const void *), const void *)
static void	SplaySplayTree (SplayTreeInfo *, const void *)
WizardExport WizardBooleanType	AddValueToSplayTree (SplayTreeInfo *splay_tree, const void *key, const void *value)
static NodeInfo *	LinkSplayTreeNodes (NodeInfo **nodes, const size_t low, const size_t high)
static int	SplayTreeToNodeArray (NodeInfo *node, const void *nodes)
static void	BalanceSplayTree (SplayTreeInfo *splay_tree)
static void *	GetFirstSplayTreeNode (SplayTreeInfo *splay_tree)
WizardExport SplayTreeInfo *	CloneSplayTree (SplayTreeInfo *splay_tree, void *(*clone_key)(void *), void *(*clone_value)(void *))
WizardExport int	CompareSplayTreeString (const void *target, const void *source)
WizardExport int	CompareSplayTreeStringInfo (const void *target, const void *source)
WizardExport WizardBooleanType	DeleteNodeByValueFromSplayTree (SplayTreeInfo *splay_tree, const void *value)
WizardExport WizardBooleanType	DeleteNodeFromSplayTree (SplayTreeInfo *splay_tree, const void *key)
WizardExport SplayTreeInfo *	DestroySplayTree (SplayTreeInfo *splay_tree)
WizardExport const void *	GetNextKeyInSplayTree (SplayTreeInfo *splay_tree)
WizardExport const void *	GetNextValueInSplayTree (SplayTreeInfo *splay_tree)
WizardExport const void *	GetValueFromSplayTree (SplayTreeInfo *splay_tree, const void *key)
WizardExport size_t	GetNumberOfNodesInSplayTree (const SplayTreeInfo *splay_tree)
WizardExport SplayTreeInfo *	NewSplayTree (int(*compare)(const void *, const void *), void *(*relinquish_key)(void *), void *(*relinquish_value)(void *))
WizardExport void *	RemoveNodeByValueFromSplayTree (SplayTreeInfo *splay_tree, const void *value)
WizardExport void *	RemoveNodeFromSplayTree (SplayTreeInfo *splay_tree, const void *key)
WizardExport void	ResetSplayTree (SplayTreeInfo *splay_tree)
WizardExport void	ResetSplayTreeIterator (SplayTreeInfo *splay_tree)
static NodeInfo *	Splay (SplayTreeInfo *splay_tree, const size_t depth, const void *key, NodeInfo **node, NodeInfo **parent, NodeInfo **grandparent)

---

Define Documentation

#define MaxSplayTreeDepth   1024

Definition at line 63 of file splay-tree.c.

Referenced by Splay().

---

Typedef Documentation

typedef struct _NodeInfo NodeInfo

---

Function Documentation

WizardExport WizardBooleanType AddValueToSplayTree	(	SplayTreeInfo *	splay_tree,
		const void *	key,
		const void *	value
	)

Definition at line 150 of file splay-tree.c.

References LockSemaphoreInfo(), _SplayTreeInfo::semaphore, SplaySplayTree(), _SplayTreeInfo::root, _SplayTreeInfo::compare, _NodeInfo::key, _SplayTreeInfo::relinquish_value, _NodeInfo::value, _SplayTreeInfo::relinquish_key, UnlockSemaphoreInfo(), WizardTrue, AcquireWizardMemory(), WizardFalse, _NodeInfo::left, _NodeInfo::right, _SplayTreeInfo::key, and _SplayTreeInfo::nodes.

Referenced by GenerateSessionKey(), SetKeyInfo(), AcquireUniqueFileResource(), CloneSplayTree(), and GetXMLTreeAttributes().

static void BalanceSplayTree

(

SplayTreeInfo *

splay_tree

)

[static]

Definition at line 276 of file splay-tree.c.

References _SplayTreeInfo::nodes, _SplayTreeInfo::balance, WizardFalse, AcquireQuantumMemory(), ThrowWizardFatalError, CacheDomain, MemoryError, IterateOverSplayTree(), SplayTreeToNodeArray(), _SplayTreeInfo::root, LinkSplayTreeNodes(), and RelinquishWizardMemory().

Referenced by SplaySplayTree().

WizardExport SplayTreeInfo* CloneSplayTree	(	SplayTreeInfo *	splay_tree,
		void *(*)(void *)	clone_key,
		void *(*)(void *)	clone_value
	)

Definition at line 342 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, NewSplayTree(), _SplayTreeInfo::compare, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, LockSemaphoreInfo(), _SplayTreeInfo::semaphore, _SplayTreeInfo::root, UnlockSemaphoreInfo(), GetFirstSplayTreeNode(), SplaySplayTree(), AddValueToSplayTree(), _NodeInfo::key, _NodeInfo::value, _NodeInfo::right, and _NodeInfo::left.

WizardExport int CompareSplayTreeString	(	const void *	target,
		const void *	source
	)

Definition at line 408 of file splay-tree.c.

References LocaleCompare().

Referenced by AcquireUniqueFileResource().

WizardExport int CompareSplayTreeStringInfo	(	const void *	target,
		const void *	source
	)

Definition at line 444 of file splay-tree.c.

References CompareStringInfo().

Referenced by AcquireKeyInfo().

WizardExport WizardBooleanType DeleteNodeByValueFromSplayTree	(	SplayTreeInfo *	splay_tree,
		const void *	value
	)

Definition at line 482 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, LockSemaphoreInfo(), _SplayTreeInfo::semaphore, _SplayTreeInfo::root, UnlockSemaphoreInfo(), GetFirstSplayTreeNode(), SplaySplayTree(), _NodeInfo::right, _NodeInfo::left, _NodeInfo::key, _NodeInfo::value, _SplayTreeInfo::key, _SplayTreeInfo::compare, _SplayTreeInfo::relinquish_value, _SplayTreeInfo::relinquish_key, RelinquishWizardMemory(), _SplayTreeInfo::nodes, and WizardTrue.

WizardExport WizardBooleanType DeleteNodeFromSplayTree	(	SplayTreeInfo *	splay_tree,
		const void *	key
	)

Definition at line 597 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, _SplayTreeInfo::root, LockSemaphoreInfo(), _SplayTreeInfo::semaphore, SplaySplayTree(), _SplayTreeInfo::key, _SplayTreeInfo::compare, _NodeInfo::key, UnlockSemaphoreInfo(), _NodeInfo::left, _NodeInfo::right, _SplayTreeInfo::relinquish_value, _NodeInfo::value, _SplayTreeInfo::relinquish_key, RelinquishWizardMemory(), _SplayTreeInfo::nodes, and WizardTrue.

Referenced by RelinquishUniqueFileResource().

WizardExport SplayTreeInfo* DestroySplayTree

(

SplayTreeInfo *

splay_tree

)

Definition at line 676 of file splay-tree.c.

References LockSemaphoreInfo(), _SplayTreeInfo::semaphore, _SplayTreeInfo::root, _SplayTreeInfo::relinquish_value, _NodeInfo::value, _SplayTreeInfo::relinquish_key, _NodeInfo::key, _NodeInfo::left, _NodeInfo::right, RelinquishWizardMemory(), _SplayTreeInfo::signature, WizardSignature, UnlockSemaphoreInfo(), and DestroySemaphoreInfo().

Referenced by DestroyKeyInfo(), and ResourceComponentTerminus().

static void* GetFirstSplayTreeNode

(

SplayTreeInfo *

splay_tree

)

[static]

Definition at line 329 of file splay-tree.c.

References _SplayTreeInfo::root, _NodeInfo::left, and _NodeInfo::key.

Referenced by CloneSplayTree(), DeleteNodeByValueFromSplayTree(), RemoveNodeByValueFromSplayTree(), and ResetSplayTreeIterator().

WizardExport const void* GetNextKeyInSplayTree

(

SplayTreeInfo *

splay_tree

)

Definition at line 763 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, _SplayTreeInfo::root, _SplayTreeInfo::next, LockSemaphoreInfo(), _SplayTreeInfo::semaphore, SplaySplayTree(), _NodeInfo::right, _NodeInfo::left, _NodeInfo::key, and UnlockSemaphoreInfo().

Referenced by AsynchronousResourceComponentTerminus(), and RelinquishUniqueFileResource().

WizardExport const void* GetNextValueInSplayTree

(

SplayTreeInfo *

splay_tree

)

Definition at line 817 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, _SplayTreeInfo::root, _SplayTreeInfo::next, LockSemaphoreInfo(), _SplayTreeInfo::semaphore, SplaySplayTree(), _NodeInfo::right, _NodeInfo::left, _NodeInfo::key, _NodeInfo::value, and UnlockSemaphoreInfo().

WizardExport size_t GetNumberOfNodesInSplayTree

(

const SplayTreeInfo *

splay_tree

)

Definition at line 927 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, and _SplayTreeInfo::nodes.

WizardExport const void* GetValueFromSplayTree	(	SplayTreeInfo *	splay_tree,
		const void *	key
	)

Definition at line 872 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, _SplayTreeInfo::root, LockSemaphoreInfo(), _SplayTreeInfo::semaphore, SplaySplayTree(), _SplayTreeInfo::compare, _NodeInfo::key, UnlockSemaphoreInfo(), and _NodeInfo::value.

Referenced by GetKeyInfo(), and SetKeyInfo().

static int IterateOverSplayTree	(	SplayTreeInfo *	splay_tree,
		int(*)(NodeInfo *, const void *)	method,
		const void *	value
	)		[static]

Definition at line 964 of file splay-tree.c.

References _SplayTreeInfo::root, AcquireQuantumMemory(), _SplayTreeInfo::nodes, ThrowWizardFatalError, CacheDomain, MemoryError, WizardFalse, _NodeInfo::left, _NodeInfo::right, WizardTrue, and RelinquishWizardMemory().

Referenced by BalanceSplayTree().

static NodeInfo* LinkSplayTreeNodes	(	NodeInfo **	nodes,
		const size_t	low,
		const size_t	high
	)		[static]

Definition at line 243 of file splay-tree.c.

References _NodeInfo::left.

Referenced by BalanceSplayTree().

WizardExport SplayTreeInfo* NewSplayTree	(	int(*)(const void *, const void *)	compare,
		void *(*)(void *)	relinquish_key,
		void *(*)(void *)	relinquish_value
	)

Definition at line 1092 of file splay-tree.c.

References AcquireWizardMemory(), ThrowWizardFatalError, CacheDomain, MemoryError, ResetWizardMemory(), _SplayTreeInfo::root, _SplayTreeInfo::compare, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, _SplayTreeInfo::balance, WizardFalse, _SplayTreeInfo::key, _SplayTreeInfo::next, _SplayTreeInfo::nodes, _SplayTreeInfo::debug, IsEventLogging(), _SplayTreeInfo::semaphore, AllocateSemaphoreInfo(), _SplayTreeInfo::signature, and WizardSignature.

Referenced by AcquireKeyInfo(), AcquireUniqueFileResource(), and CloneSplayTree().

WizardExport void* RemoveNodeByValueFromSplayTree	(	SplayTreeInfo *	splay_tree,
		const void *	value
	)

Definition at line 1143 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, _SplayTreeInfo::root, LockSemaphoreInfo(), _SplayTreeInfo::semaphore, GetFirstSplayTreeNode(), SplaySplayTree(), _NodeInfo::right, _NodeInfo::left, _NodeInfo::key, _NodeInfo::value, _SplayTreeInfo::key, _SplayTreeInfo::compare, UnlockSemaphoreInfo(), _SplayTreeInfo::relinquish_value, RelinquishWizardMemory(), and _SplayTreeInfo::nodes.

WizardExport void* RemoveNodeFromSplayTree	(	SplayTreeInfo *	splay_tree,
		const void *	key
	)

Definition at line 1252 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, _SplayTreeInfo::root, LockSemaphoreInfo(), _SplayTreeInfo::semaphore, SplaySplayTree(), _SplayTreeInfo::key, _SplayTreeInfo::compare, _NodeInfo::key, UnlockSemaphoreInfo(), _NodeInfo::left, _NodeInfo::right, _NodeInfo::value, _SplayTreeInfo::relinquish_key, RelinquishWizardMemory(), and _SplayTreeInfo::nodes.

WizardExport void ResetSplayTree

(

SplayTreeInfo *

splay_tree

)

Definition at line 1333 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, LockSemaphoreInfo(), _SplayTreeInfo::semaphore, _SplayTreeInfo::root, _SplayTreeInfo::relinquish_value, _NodeInfo::value, _SplayTreeInfo::relinquish_key, _NodeInfo::key, _NodeInfo::left, _NodeInfo::right, RelinquishWizardMemory(), _SplayTreeInfo::key, _SplayTreeInfo::next, _SplayTreeInfo::nodes, _SplayTreeInfo::balance, and UnlockSemaphoreInfo().

WizardExport void ResetSplayTreeIterator

(

SplayTreeInfo *

splay_tree

)

Definition at line 1425 of file splay-tree.c.

References WizardAssert, ResourceDomain, _SplayTreeInfo::signature, WizardSignature, _SplayTreeInfo::debug, WizardFalse, LogWizardEvent(), TraceEvent, GetWizardModule, LockSemaphoreInfo(), _SplayTreeInfo::semaphore, _SplayTreeInfo::next, GetFirstSplayTreeNode(), and UnlockSemaphoreInfo().

Referenced by AsynchronousResourceComponentTerminus(), and RelinquishUniqueFileResource().

static NodeInfo* Splay	(	SplayTreeInfo *	splay_tree,
		const size_t	depth,
		const void *	key,
		NodeInfo **	node,
		NodeInfo **	parent,
		NodeInfo **	grandparent
	)		[static]

Definition at line 1468 of file splay-tree.c.

References _SplayTreeInfo::compare, _NodeInfo::key, _NodeInfo::left, _NodeInfo::right, MaxSplayTreeDepth, _SplayTreeInfo::balance, WizardTrue, and WizardFalse.

Referenced by SplaySplayTree().

static void SplaySplayTree	(	SplayTreeInfo *	splay_tree,
		const void *	key
	)		[static]

Definition at line 1559 of file splay-tree.c.

References _SplayTreeInfo::root, _SplayTreeInfo::key, _SplayTreeInfo::compare, _NodeInfo::key, Splay(), _SplayTreeInfo::balance, WizardFalse, BalanceSplayTree(), ThrowWizardFatalError, CacheDomain, and MemoryError.

Referenced by AddValueToSplayTree(), CloneSplayTree(), DeleteNodeByValueFromSplayTree(), DeleteNodeFromSplayTree(), GetNextKeyInSplayTree(), GetNextValueInSplayTree(), GetValueFromSplayTree(), RemoveNodeByValueFromSplayTree(), and RemoveNodeFromSplayTree().

static int SplayTreeToNodeArray	(	NodeInfo *	node,
		const void *	nodes
	)		[static]

Definition at line 265 of file splay-tree.c.

Referenced by BalanceSplayTree().