MagickCore 7.0.10
Data Structures | Macros | 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"
Include dependency graph for splay-tree.c:

Go to the source code of this file.

Data Structures

struct  _NodeInfo
 
struct  _SplayTreeInfo
 

Macros

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

Macro Definition Documentation

◆ MaxSplayTreeDepth

#define MaxSplayTreeDepth   1024

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

Typedef Documentation

◆ NodeInfo

typedef struct _NodeInfo NodeInfo

Function Documentation

◆ AddValueToSplayTree()

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

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

References AcquireWizardMemory(), _SplayTreeInfo::compare, _NodeInfo::key, _SplayTreeInfo::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(), LoadLocaleCache(), and SetKeyInfo().

◆ BalanceSplayTree()

static void BalanceSplayTree ( SplayTreeInfo *  splay_tree)
static

Definition at line 278 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().

◆ CloneSplayTree()

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

Definition at line 344 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.

◆ CompareSplayTreeString()

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

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

References LocaleCompare().

Referenced by AcquireLocaleSplayTree(), and AcquireUniqueFileResource().

◆ CompareSplayTreeStringInfo()

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

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

References CompareStringInfo().

Referenced by AcquireKeyInfo().

◆ DeleteNodeByValueFromSplayTree()

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

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

References _SplayTreeInfo::compare, _SplayTreeInfo::debug, GetFirstSplayTreeNode(), 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.

◆ DeleteNodeFromSplayTree()

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

Definition at line 599 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().

◆ DestroySplayTree()

WizardExport SplayTreeInfo * DestroySplayTree ( SplayTreeInfo *  splay_tree)

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

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

Referenced by DestroyKeyInfo(), LocaleComponentTerminus(), and ResourceComponentTerminus().

◆ GetFirstSplayTreeNode()

static void * GetFirstSplayTreeNode ( SplayTreeInfo *  splay_tree)
inlinestatic

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

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

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

◆ GetNextKeyInSplayTree()

WizardExport const void * GetNextKeyInSplayTree ( SplayTreeInfo *  splay_tree)

Definition at line 765 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().

◆ GetNextValueInSplayTree()

WizardExport const void * GetNextValueInSplayTree ( SplayTreeInfo *  splay_tree)

Definition at line 819 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.

Referenced by GetLocaleInfo_(), GetLocaleInfoList(), and GetLocaleList().

◆ GetNumberOfNodesInSplayTree()

WizardExport size_t GetNumberOfNodesInSplayTree ( const SplayTreeInfo *  splay_tree)

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

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

Referenced by AcquireLocaleSplayTree(), GetLocaleInfoList(), and GetLocaleList().

◆ GetValueFromSplayTree()

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

Definition at line 874 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(), GetLocaleInfo_(), and SetKeyInfo().

◆ IterateOverSplayTree()

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

Definition at line 966 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().

◆ LinkSplayTreeNodes()

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

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

References _NodeInfo::left, LinkSplayTreeNodes(), and _NodeInfo::right.

Referenced by BalanceSplayTree(), and LinkSplayTreeNodes().

◆ NewSplayTree()

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

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

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

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

◆ RemoveNodeByValueFromSplayTree()

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

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

References _SplayTreeInfo::compare, _SplayTreeInfo::debug, GetFirstSplayTreeNode(), GetWizardModule, _NodeInfo::key, _SplayTreeInfo::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.

◆ RemoveNodeFromSplayTree()

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

Definition at line 1254 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.

◆ ResetSplayTree()

WizardExport void ResetSplayTree ( SplayTreeInfo *  splay_tree)

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

References _SplayTreeInfo::balance, _SplayTreeInfo::debug, GetWizardModule, _NodeInfo::key, _SplayTreeInfo::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.

◆ ResetSplayTreeIterator()

WizardExport void ResetSplayTreeIterator ( SplayTreeInfo *  splay_tree)

Definition at line 1427 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(), GetLocaleInfo_(), GetLocaleInfoList(), and RelinquishUniqueFileResource().

◆ Splay()

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

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

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

Referenced by Splay(), and SplaySplayTree().

◆ SplaySplayTree()

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

Definition at line 1566 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().

◆ SplayTreeToNodeArray()

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

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

Referenced by BalanceSplayTree().