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"
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
Function Documentation
| WizardExport WizardBooleanType AddValueToSplayTree | ( | SplayTreeInfo * | splay_tree, | |
| const void * | key, | |||
| const void * | value | |||
| ) |
Definition at line 150 of file splay-tree.c.
References AcquireAlignedMemory(), _SplayTreeInfo::compare, _SplayTreeInfo::key, _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, SplaySplayTree(), UnlockSemaphoreInfo(), _NodeInfo::value, WizardFalse, and WizardTrue.
Referenced by AcquireUniqueFileResource(), CloneSplayTree(), GenerateSessionKey(), GetXMLTreeAttributes(), and SetKeyInfo().
| static void BalanceSplayTree | ( | SplayTreeInfo * | splay_tree | ) | [static] |
Definition at line 276 of file splay-tree.c.
References AcquireQuantumMemory(), _SplayTreeInfo::balance, CacheDomain, IterateOverSplayTree(), LinkSplayTreeNodes(), MemoryError, _SplayTreeInfo::nodes, RelinquishWizardMemory(), _SplayTreeInfo::root, SplayTreeToNodeArray(), ThrowWizardFatalError, and WizardFalse.
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 AddValueToSplayTree(), _SplayTreeInfo::compare, _SplayTreeInfo::debug, GetFirstSplayTreeNode(), GetWizardModule, _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogWizardEvent(), NewSplayTree(), _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, ResourceDomain, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), _NodeInfo::value, WizardAssert, WizardFalse, and WizardSignature.
| 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 _SplayTreeInfo::compare, _SplayTreeInfo::debug, GetFirstSplayTreeNode(), GetWizardModule, _SplayTreeInfo::key, _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogWizardEvent(), _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, RelinquishWizardMemory(), ResourceDomain, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), _NodeInfo::value, WizardAssert, WizardFalse, WizardSignature, and WizardTrue.
| WizardExport WizardBooleanType DeleteNodeFromSplayTree | ( | SplayTreeInfo * | splay_tree, | |
| const void * | key | |||
| ) |
Definition at line 597 of file splay-tree.c.
References _SplayTreeInfo::compare, _SplayTreeInfo::debug, GetWizardModule, _NodeInfo::key, _SplayTreeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogWizardEvent(), _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, RelinquishWizardMemory(), ResourceDomain, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), _NodeInfo::value, WizardAssert, WizardFalse, WizardSignature, and WizardTrue.
Referenced by RelinquishUniqueFileResource().
| WizardExport SplayTreeInfo* DestroySplayTree | ( | SplayTreeInfo * | splay_tree | ) |
Definition at line 676 of file splay-tree.c.
References DestroySemaphoreInfo(), _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, RelinquishWizardMemory(), _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, UnlockSemaphoreInfo(), _NodeInfo::value, and WizardSignature.
Referenced by DestroyKeyInfo(), and ResourceComponentTerminus().
| static void* GetFirstSplayTreeNode | ( | SplayTreeInfo * | splay_tree | ) | [static] |
Definition at line 329 of file splay-tree.c.
References _NodeInfo::key, _NodeInfo::left, and _SplayTreeInfo::root.
Referenced by CloneSplayTree(), DeleteNodeByValueFromSplayTree(), RemoveNodeByValueFromSplayTree(), and ResetSplayTreeIterator().
| WizardExport const void* GetNextKeyInSplayTree | ( | SplayTreeInfo * | splay_tree | ) |
Definition at line 763 of file splay-tree.c.
References _SplayTreeInfo::debug, GetWizardModule, _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogWizardEvent(), _SplayTreeInfo::next, ResourceDomain, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), WizardAssert, WizardFalse, and WizardSignature.
Referenced by AsynchronousResourceComponentTerminus(), and RelinquishUniqueFileResource().
| WizardExport const void* GetNextValueInSplayTree | ( | SplayTreeInfo * | splay_tree | ) |
Definition at line 817 of file splay-tree.c.
References _SplayTreeInfo::debug, GetWizardModule, _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogWizardEvent(), _SplayTreeInfo::next, ResourceDomain, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), _NodeInfo::value, WizardAssert, WizardFalse, and WizardSignature.
| WizardExport size_t GetNumberOfNodesInSplayTree | ( | const SplayTreeInfo * | splay_tree | ) |
Definition at line 927 of file splay-tree.c.
References _SplayTreeInfo::debug, GetWizardModule, LogWizardEvent(), _SplayTreeInfo::nodes, ResourceDomain, _SplayTreeInfo::signature, TraceEvent, WizardAssert, WizardFalse, and WizardSignature.
| WizardExport const void* GetValueFromSplayTree | ( | SplayTreeInfo * | splay_tree, | |
| const void * | key | |||
| ) |
Definition at line 872 of file splay-tree.c.
References _SplayTreeInfo::compare, _SplayTreeInfo::debug, GetWizardModule, _NodeInfo::key, LockSemaphoreInfo(), LogWizardEvent(), ResourceDomain, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), _NodeInfo::value, WizardAssert, WizardFalse, and WizardSignature.
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 AcquireQuantumMemory(), CacheDomain, _NodeInfo::left, MemoryError, _SplayTreeInfo::nodes, RelinquishWizardMemory(), _NodeInfo::right, _SplayTreeInfo::root, ThrowWizardFatalError, WizardFalse, and WizardTrue.
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 AcquireAlignedMemory(), AllocateSemaphoreInfo(), _SplayTreeInfo::balance, CacheDomain, _SplayTreeInfo::compare, _SplayTreeInfo::debug, IsEventLogging(), _SplayTreeInfo::key, MemoryError, _SplayTreeInfo::next, _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, ResetWizardMemory(), _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, ThrowWizardFatalError, WizardFalse, 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 _SplayTreeInfo::compare, _SplayTreeInfo::debug, GetFirstSplayTreeNode(), GetWizardModule, _SplayTreeInfo::key, _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogWizardEvent(), _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_value, RelinquishWizardMemory(), ResourceDomain, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), _NodeInfo::value, WizardAssert, WizardFalse, and WizardSignature.
| WizardExport void* RemoveNodeFromSplayTree | ( | SplayTreeInfo * | splay_tree, | |
| const void * | key | |||
| ) |
Definition at line 1252 of file splay-tree.c.
References _SplayTreeInfo::compare, _SplayTreeInfo::debug, GetWizardModule, _NodeInfo::key, _SplayTreeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogWizardEvent(), _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, RelinquishWizardMemory(), ResourceDomain, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), _NodeInfo::value, WizardAssert, WizardFalse, and WizardSignature.
| WizardExport void ResetSplayTree | ( | SplayTreeInfo * | splay_tree | ) |
Definition at line 1333 of file splay-tree.c.
References _SplayTreeInfo::balance, _SplayTreeInfo::debug, GetWizardModule, _SplayTreeInfo::key, _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogWizardEvent(), _SplayTreeInfo::next, _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, RelinquishWizardMemory(), ResourceDomain, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, TraceEvent, UnlockSemaphoreInfo(), _NodeInfo::value, WizardAssert, WizardFalse, and WizardSignature.
| WizardExport void ResetSplayTreeIterator | ( | SplayTreeInfo * | splay_tree | ) |
Definition at line 1425 of file splay-tree.c.
References _SplayTreeInfo::debug, GetFirstSplayTreeNode(), GetWizardModule, LockSemaphoreInfo(), LogWizardEvent(), _SplayTreeInfo::next, ResourceDomain, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, TraceEvent, UnlockSemaphoreInfo(), WizardAssert, WizardFalse, and WizardSignature.
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::balance, _SplayTreeInfo::compare, _NodeInfo::key, _NodeInfo::left, MaxSplayTreeDepth, _NodeInfo::right, WizardFalse, and WizardTrue.
Referenced by SplaySplayTree().
| static void SplaySplayTree | ( | SplayTreeInfo * | splay_tree, | |
| const void * | key | |||
| ) | [static] |
Definition at line 1559 of file splay-tree.c.
References _SplayTreeInfo::balance, BalanceSplayTree(), CacheDomain, _SplayTreeInfo::compare, _NodeInfo::key, _SplayTreeInfo::key, MemoryError, _SplayTreeInfo::root, Splay(), ThrowWizardFatalError, and WizardFalse.
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().
