MagickCore 7.1.0
Convert, Edit, Or Compose Bitmap Images
Data Structures | Macros | Typedefs | Functions
splay-tree.c File Reference
#include "MagickCore/studio.h"
#include "MagickCore/exception.h"
#include "MagickCore/exception-private.h"
#include "MagickCore/locale_.h"
#include "MagickCore/log.h"
#include "MagickCore/memory_.h"
#include "MagickCore/memory-private.h"
#include "MagickCore/splay-tree.h"
#include "MagickCore/semaphore.h"
#include "MagickCore/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 *)
 
MagickExport MagickBooleanType 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)
 
MagickExport SplayTreeInfo * CloneSplayTree (SplayTreeInfo *splay_tree, void *(*clone_key)(void *), void *(*clone_value)(void *))
 
MagickExport int CompareSplayTreeString (const void *target, const void *source)
 
MagickExport int CompareSplayTreeStringInfo (const void *target, const void *source)
 
MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree (SplayTreeInfo *splay_tree, const void *value)
 
MagickExport MagickBooleanType DeleteNodeFromSplayTree (SplayTreeInfo *splay_tree, const void *key)
 
MagickExport SplayTreeInfo * DestroySplayTree (SplayTreeInfo *splay_tree)
 
MagickExport const void * GetNextKeyInSplayTree (SplayTreeInfo *splay_tree)
 
MagickExport const void * GetNextValueInSplayTree (SplayTreeInfo *splay_tree)
 
MagickExport const void * GetRootValueFromSplayTree (SplayTreeInfo *splay_tree)
 
MagickExport const void * GetValueFromSplayTree (SplayTreeInfo *splay_tree, const void *key)
 
MagickExport size_t GetNumberOfNodesInSplayTree (const SplayTreeInfo *splay_tree)
 
MagickExport SplayTreeInfo * NewSplayTree (int(*compare)(const void *, const void *), void *(*relinquish_key)(void *), void *(*relinquish_value)(void *))
 
MagickExport void * RemoveNodeByValueFromSplayTree (SplayTreeInfo *splay_tree, const void *value)
 
MagickExport void * RemoveNodeFromSplayTree (SplayTreeInfo *splay_tree, const void *key)
 
MagickExport void ResetSplayTree (SplayTreeInfo *splay_tree)
 
MagickExport 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 65 of file splay-tree.c.

Typedef Documentation

◆ NodeInfo

typedef struct _NodeInfo NodeInfo

Function Documentation

◆ AddValueToSplayTree()

MagickExport MagickBooleanType AddValueToSplayTree ( SplayTreeInfo *  splay_tree,
const void *  key,
const void *  value 
)

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

References AcquireMagickMemory(), _SplayTreeInfo::compare, _NodeInfo::key, _SplayTreeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), MagickFalse, MagickTrue, _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, SplaySplayTree(), UnlockSemaphoreInfo(), and _NodeInfo::value.

Referenced by AcquireCoderCache(), AcquireUniqueFileResource(), CloneSplayTree(), GetEXIFProperty(), GetMVGMacros(), GetXMLTreeAttributes(), GetXMPProperty(), LoadLocaleCache(), LoadTypeCache(), RegisterMagickInfo(), SetImageArtifact(), SetImageOption(), SetImageProfileInternal(), SetImageProperty(), SetImageRegistry(), SyncExifProfile(), and WriteTo8BimProfile().

◆ BalanceSplayTree()

static void BalanceSplayTree ( SplayTreeInfo *  splay_tree)
static

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

References AcquireQuantumMemory(), _SplayTreeInfo::balance, IterateOverSplayTree(), LinkSplayTreeNodes(), MagickFalse, _SplayTreeInfo::nodes, RelinquishMagickMemory(), ResourceLimitFatalError, _SplayTreeInfo::root, SplayTreeToNodeArray(), and ThrowFatalException.

Referenced by SplaySplayTree().

◆ CloneSplayTree()

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

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

References AddValueToSplayTree(), _SplayTreeInfo::compare, GetFirstSplayTreeNode(), GetMagickModule, IsEventLogging(), _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, NewSplayTree(), _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), and _NodeInfo::value.

Referenced by CloneImageArtifacts(), CloneImageOptions(), CloneImageProfiles(), and CloneImageProperties().

◆ CompareSplayTreeString()

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

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

References LocaleCompare().

Referenced by AcquireCoderCache(), AcquireLocaleSplayTree(), AcquireTypeCache(), AcquireUniqueFileResource(), GetXMPProperty(), IsMagickTreeInstantiated(), SetImageArtifact(), SetImageOption(), SetImageProfileInternal(), SetImageProperty(), and SetImageRegistry().

◆ CompareSplayTreeStringInfo()

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

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

References CompareStringInfo().

◆ DeleteNodeByValueFromSplayTree()

MagickExport MagickBooleanType DeleteNodeByValueFromSplayTree ( SplayTreeInfo *  splay_tree,
const void *  value 
)

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

References _SplayTreeInfo::compare, GetFirstSplayTreeNode(), GetMagickModule, IsEventLogging(), _NodeInfo::key, _SplayTreeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, MagickTrue, _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, RelinquishMagickMemory(), _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), and _NodeInfo::value.

Referenced by UnregisterMagickInfo().

◆ DeleteNodeFromSplayTree()

MagickExport MagickBooleanType DeleteNodeFromSplayTree ( SplayTreeInfo *  splay_tree,
const void *  key 
)

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

References _SplayTreeInfo::compare, GetMagickModule, IsEventLogging(), _NodeInfo::key, _SplayTreeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, MagickTrue, _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, RelinquishMagickMemory(), _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), and _NodeInfo::value.

Referenced by DeleteImageArtifact(), DeleteImageOption(), DeleteImageProfile(), DeleteImageProperty(), DeleteImageRegistry(), and RelinquishUniqueFileResource().

◆ DestroySplayTree()

MagickExport SplayTreeInfo * DestroySplayTree ( SplayTreeInfo *  splay_tree)

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

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

Referenced by CoderComponentTerminus(), DestroyImageArtifacts(), DestroyImageOptions(), DestroyImageProfiles(), DestroyImageProperties(), GetEXIFProperty(), LocaleComponentTerminus(), MagickComponentTerminus(), RegistryComponentTerminus(), RenderMVGContent(), ResourceComponentTerminus(), SyncExifProfile(), and TypeComponentTerminus().

◆ GetFirstSplayTreeNode()

static void * GetFirstSplayTreeNode ( SplayTreeInfo *  splay_tree)
inlinestatic

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

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

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

◆ GetNextKeyInSplayTree()

MagickExport const void * GetNextKeyInSplayTree ( SplayTreeInfo *  splay_tree)

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

References GetMagickModule, IsEventLogging(), _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, _SplayTreeInfo::next, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, and UnlockSemaphoreInfo().

Referenced by AsynchronousResourceComponentTerminus(), GetNextImageArtifact(), GetNextImageOption(), GetNextImageProfile(), GetNextImageProperty(), and GetNextImageRegistry().

◆ GetNextValueInSplayTree()

MagickExport const void * GetNextValueInSplayTree ( SplayTreeInfo *  splay_tree)

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

References GetMagickModule, IsEventLogging(), _NodeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, _SplayTreeInfo::next, _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), and _NodeInfo::value.

Referenced by GetCoderInfoList(), GetCoderList(), GetImageMagick(), GetLocaleInfo_(), GetLocaleInfoList(), GetLocaleList(), GetMagickInfoList(), GetMagickList(), GetTypeInfoByFamily(), GetTypeInfoList(), GetTypeList(), and UnregisterMagickInfo().

◆ GetNumberOfNodesInSplayTree()

MagickExport size_t GetNumberOfNodesInSplayTree ( const SplayTreeInfo *  splay_tree)

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

References GetMagickModule, IsEventLogging(), LogMagickEvent(), MagickCoreSignature, MagickFalse, _SplayTreeInfo::nodes, _SplayTreeInfo::signature, and TraceEvent.

Referenced by AcquireLocaleSplayTree(), AcquireTypeCache(), GetCoderInfoList(), GetCoderList(), GetLocaleInfoList(), GetLocaleList(), GetMagickInfoList(), GetMagickList(), GetTypeInfoList(), GetTypeList(), and UnregisterMagickInfo().

◆ GetRootValueFromSplayTree()

MagickExport const void * GetRootValueFromSplayTree ( SplayTreeInfo *  splay_tree)

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

References GetMagickModule, IsEventLogging(), LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, TraceEvent, UnlockSemaphoreInfo(), and _NodeInfo::value.

Referenced by GetCoderInfo(), GetImageArtifact(), GetMagickInfo(), and GetTypeInfo().

◆ GetValueFromSplayTree()

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

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

References _SplayTreeInfo::compare, GetMagickModule, IsEventLogging(), _NodeInfo::key, LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), and _NodeInfo::value.

Referenced by GetCoderInfo(), GetEXIFProperty(), GetImageArtifact(), GetImageOption(), GetImageProfile(), GetImageProperty(), GetImageRegistry(), GetLocaleInfo_(), GetMagickInfo(), GetTypeInfo(), RenderMVGContent(), SyncExifProfile(), and WriteTo8BimProfile().

◆ IterateOverSplayTree()

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

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

References AcquireQuantumMemory(), _NodeInfo::left, MagickFalse, MagickTrue, _SplayTreeInfo::nodes, RelinquishMagickMemory(), ResourceLimitFatalError, _NodeInfo::right, _SplayTreeInfo::root, and ThrowFatalException.

Referenced by BalanceSplayTree().

◆ LinkSplayTreeNodes()

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

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

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

Referenced by BalanceSplayTree(), and LinkSplayTreeNodes().

◆ NewSplayTree()

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

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

References AcquireCriticalMemory(), AcquireSemaphoreInfo(), _SplayTreeInfo::balance, _SplayTreeInfo::compare, _SplayTreeInfo::debug, IsEventLogging(), _SplayTreeInfo::key, MagickCoreSignature, MagickFalse, _SplayTreeInfo::next, _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, and _SplayTreeInfo::signature.

Referenced by AcquireCoderCache(), AcquireLocaleSplayTree(), AcquireTypeCache(), AcquireUniqueFileResource(), CloneSplayTree(), GetEXIFProperty(), GetMVGMacros(), GetXMPProperty(), IsMagickTreeInstantiated(), SetImageArtifact(), SetImageOption(), SetImageProfileInternal(), SetImageProperty(), SetImageRegistry(), and SyncExifProfile().

◆ RemoveNodeByValueFromSplayTree()

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

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

References _SplayTreeInfo::compare, GetFirstSplayTreeNode(), GetMagickModule, IsEventLogging(), _NodeInfo::key, _SplayTreeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_value, RelinquishMagickMemory(), _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), and _NodeInfo::value.

◆ RemoveNodeFromSplayTree()

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

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

References _SplayTreeInfo::compare, GetMagickModule, IsEventLogging(), _NodeInfo::key, _SplayTreeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, RelinquishMagickMemory(), _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, SplaySplayTree(), TraceEvent, UnlockSemaphoreInfo(), and _NodeInfo::value.

Referenced by RemoveImageArtifact(), RemoveImageOption(), RemoveImageProfile(), RemoveImageProperty(), and RemoveImageRegistry().

◆ ResetSplayTree()

MagickExport void ResetSplayTree ( SplayTreeInfo *  splay_tree)

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

References _SplayTreeInfo::balance, GetMagickModule, IsEventLogging(), _NodeInfo::key, _SplayTreeInfo::key, _NodeInfo::left, LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, _SplayTreeInfo::next, _SplayTreeInfo::nodes, _SplayTreeInfo::relinquish_key, _SplayTreeInfo::relinquish_value, RelinquishMagickMemory(), _NodeInfo::right, _SplayTreeInfo::root, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, TraceEvent, UnlockSemaphoreInfo(), and _NodeInfo::value.

Referenced by ResetImageOptions().

◆ ResetSplayTreeIterator()

MagickExport void ResetSplayTreeIterator ( SplayTreeInfo *  splay_tree)

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

References GetFirstSplayTreeNode(), GetMagickModule, IsEventLogging(), LockSemaphoreInfo(), LogMagickEvent(), MagickCoreSignature, MagickFalse, _SplayTreeInfo::next, _SplayTreeInfo::semaphore, _SplayTreeInfo::signature, TraceEvent, and UnlockSemaphoreInfo().

Referenced by AsynchronousResourceComponentTerminus(), GetCoderInfoList(), GetCoderList(), GetImageMagick(), GetLocaleInfo_(), GetLocaleInfoList(), GetMagickInfoList(), GetMagickList(), GetTypeInfoByFamily(), GetTypeInfoList(), GetTypeList(), ResetImageArtifactIterator(), ResetImageOptionIterator(), ResetImageProfileIterator(), ResetImagePropertyIterator(), ResetImageRegistryIterator(), and UnregisterMagickInfo().

◆ Splay()

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

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

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

Referenced by Splay(), and SplaySplayTree().

◆ SplaySplayTree()

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

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

References _SplayTreeInfo::balance, BalanceSplayTree(), _SplayTreeInfo::compare, _NodeInfo::key, _SplayTreeInfo::key, MagickFalse, ResourceLimitFatalError, _SplayTreeInfo::root, Splay(), and ThrowFatalException.

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 269 of file splay-tree.c.

Referenced by BalanceSplayTree().