Data Structures | Defines | Typedefs | Functions

# 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"`

## 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

Referenced by Splay().

## Typedef Documentation

typedef struct _NodeInfo NodeInfo

## Function Documentation

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

References AcquireWizardMemory(), _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]`

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

Referenced by SplaySplayTree().

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

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 |
| ) |  |  |

References LocaleCompare().

Referenced by AcquireUniqueFileResource().

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

References CompareStringInfo().

Referenced by AcquireKeyInfo().

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

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 |
| ) |  |  |

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 | ) |

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

Referenced by DestroyKeyInfo(), and ResourceComponentTerminus().

static void* GetFirstSplayTreeNode | ( | SplayTreeInfo * | splay_tree | ) | `[static]`

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

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

WizardExport const void* GetNextKeyInSplayTree | ( | SplayTreeInfo * | splay_tree | ) |

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 | ) |

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 | ) |

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 |
| ) |  |  |

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]`

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

Referenced by BalanceSplayTree().

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

References _NodeInfo::left.

Referenced by BalanceSplayTree().

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

References AcquireWizardMemory(), 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, and ThrowWizardFatalError.

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

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

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 |
| ) |  |  |

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 | ) |

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 | ) |

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]`

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

Referenced by SplaySplayTree().

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

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]`

Referenced by BalanceSplayTree().