d0 - The Classic M68k Amiga Developer Resource

NEWS APPS DOCS ABOUT

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 */

NAME

SYNOPSIS

FUNCTION

INPUTS

RESULT

NOTES

EXAMPLE

BUGS

SEE ALSO

Comments

Comments: