a1200   NEWS   APPS   DOCS   ABOUT
a1200
----
a1200
----
Autodocs
 Libraries:
 exec.library
  AVL_AddNode
  AVL_FindFirstNode
  AVL_FindLastNode
  AVL_FindNextNodeByAddress
  AVL_FindNextNodeByKey
  AVL_FindNode
  AVL_FindPrevNodeByAddress
  AVL_FindPrevNodeByKey
  AVL_RemNodeByAddress
  AVL_RemNodeByKey
  AbortIO
  AddDevice
  AddHead
  AddIntServer
  AddLibrary
  AddMemHandler
  AddMemList
  AddPort
  AddResource
  AddSemaphore
  AddTail
  AddTask
  Alert
  AllocAbs
  AllocEntry
  AllocMem
  AllocPooled
  AllocSignal
  AllocTrap
  AllocVec
  Allocate
  AttemptSemaphore
  AttemptSemaphoreShared
  AvailMem
  CacheClearE
  CacheClearU
  CacheControl
  CachePostDMA
  CachePreDMA
  Cause
  CheckIO
  CloseDevice
  CloseLibrary
  ColdReboot
  CopyMem
  CopyMemQuick
  CreateIORequest
  CreateMsgPort
  CreatePool
  Deallocate
  Debug
  DeleteIORequest
  DeleteMsgPort
  DeletePool
  Disable
  DoIO
  Enable
  Enqueue
  FindName
  FindPort
  FindResident
  FindSemaphore
  FindTask
  Forbid
  FreeEntry
  FreeMem
  FreePooled
  FreeSignal
  FreeTrap
  FreeVec
  GetCC
  GetMsg
  InitCode
  InitResident
  InitSemaphore
  InitStruct
  Insert
  MakeFunctions
  MakeLibrary
  ObtainQuickVector
  ObtainSemaphore
  ObtainSemaphoreList
  ObtainSemaphoreShared
  OldOpenLibrary
  OpenDevice
  OpenLibrary
  OpenResource
  Permit
  Procure
  PutMsg
  RawDoFmt
  ReleaseSemaphore
  ReleaseSemaphoreList
  RemDevice
  RemHead
  RemIntServer
  RemLibrary
  RemMemHandler
  RemPort
  RemResource
  RemSemaphore
  RemTail
  RemTask
  Remove
  ReplyMsg
  SendIO
  SetExcept
  SetFunction
  SetIntVector
  SetSR
  SetSignal
  SetTaskPri
  Signal
  StackSwap
  SumKickData
  SumLibrary
  SuperState
  Supervisor
  TypeOfMem
  UserState
  Vacate
  Wait
  WaitIO
  WaitPort
Include
GuruMeditation
Docs » Autodocs » exec.library » AVL_AddNode

NAME

       AVL_AddNode -- Add node to the tree (V45)

SYNOPSIS

       result = AVL_AddNode( root, node, func )
D0 A0 A1 A2
struct AVLNode *AVL_FindNextNodeByKey(struct AVLNode **,
struct AVLNode *,
AVLNODECOMP);

FUNCTION

       The function will add the given node to the AVL tree in the correct
position. The correct position is determined by the compare function
which is also passed in and which defines relative value of nodes
by determining their "key" values and comparing them.
Note that the compare function works like strcmp() by returning
<0, 0, >0 results to define a less/equal/greater relationship.
Note that there is no arbitration for access to the tree. You
should use a SignalSemaphore if arbitration is required.

INPUTS

       root  - Address of(!) the root pointer(!) of the AVL tree.
Initially, the root pointer must be set to NULL, which
represents an empty AVL tree.
node - The node to add
func - The compare function to find the right position for
the node in the tree

RESULT

       If the node could be added, NULL is returned.
If there is already a node in the tree that has the same key, the
pointer to that node be returned and the given node will not be
added.

NOTES

       There are a few things to remember about AVL trees. First, they
are binary balanced trees. You can expect O(log2(n)) performance
for adding, removing, and searching by key.
Second, the implementation does not care what kind of compare
functions you provide to the AVL functions, i.e., what sort order
you define.
To work with an AVL tree you need two compare functions:
AVLNODECOMP - Determines keys of two nodes and compares them
AVLKEYCOMP - Compares a node's key to a given key
The interpretation of the keys in these two functions must match.
If your compare functions are flawed, the AVL trees will not work.
The implementation does not compare keys or makes any assumption
about them. A key can be anything that fits into a 32 bit value,
even a pointer to the "true" key, whatever it may be.
Remember that each key in a tree must be unique. If you
want to add elements with identical keys, you could use, e.g.,
the memory address of the element as "second level" key to ensure
unique keys for insertion into the tree. In that case, however,
it is obviously not possible to retrieve the node by a single key.
Also, remember that a struct AVLNode can be embedded anywhere
within your element's structure.
The example below illustrates all the points made above. If you
don't need second level keys or embedded struct AVLNode's, you
can simplify things.
Finally, the implementation is not recursive and you don't have
to provide a huge stack even when using AVL functions on
huge trees.

EXAMPLE

       struct Element
{
struct Node el_Node; /* Normal maintenance */
UWORD el_pad;
ULONG el_SortKey; /* Bringing order into things ... */
struct AVLNode el_AVLNode; /* Fast access */
ULONG el_Content; /* Magic private content */
};
...
LONG ASM AVLNodeComp(REG(a0) struct AVLNode *avlnode1,
REG(a1) struct AVLNode *avlnode2)
{
struct Element *el1, *el2;
LONG res;
el1 = ElementStart(avlnode1);
el2 = ElementStart(avlnode2);
res = (LONG)(el1->el_SortKey - el2->el_SortKey);
if(res == 0)
{
// For identical keys, use, e.g., the address as 2nd key
res = (LONG)((ULONG)avlnode1 - (ULONG)avlnode2);
} /* if */
return(res);
} /* AVLNodeComp */
static LONG ASM AVLKeyComp(REG(a0) struct AVLNode *avlnode,
REG(a1) AVLKey avlkey)
{
struct Element *el;
LONG res;
el = ElementStart(avlnode);
res = (LONG)(el->el_SortKey - (ULONG)avlkey);
return(res);
} /* AVLKeyComp */
...
/* Initially, the tree must be marked as empty! */
avlroot = NULL;
...
if(AVL_AddNode(&avlroot, &el->el_AVLNode, AVLNodeComp))
{
// This should not happen because our AVLNodeComp()
// ensures that each node's key is unique by using its address
.
// If it happens it means that we are trying to readd a
// node that already has been added in this case.
} /* if */

BUGS

SEE ALSO

AVL_FindLastNode(), AVL_FindFirstNode(), AVL_RemNodeByKey(), AVL_RemNodeByAddress(), AVL_FindNextNodeByKey(), AVL_FindNextNodeByAddress()

Comments

Name:
E-mail: Use this if you want a message if you get a response, will not be shown.
Comment:
Select correct short for:

Fairlight

FLT
DJ
SCX
TSL

Comments:

$VER: d0.se 1.14 Copyright © 2011-2024 Tobias Geijersson support at d0 dot se