home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 347_01 / tavl_ins.c < prev    next >
C/C++ Source or Header  |  1991-10-19  |  5KB  |  157 lines
  1. /*:file:version:date: "%n    V.%v;  %f"
  2.  * "TAVL_INS.C    V.12;  19-Oct-91,14:19:36"
  3.  *
  4.  *  Module:     tavl_insert
  5.  *  Purpose:    Insert item into TAVL_TREE;  "item" may be anything,
  6.  *              but the user-defined function "key_of()" given when tree was
  7.  *              initialized by "tavl_init()" must be able to read an
  8.  *              identifier from "item" which can be compared with other
  9.  *              indentifiers via the user defined function "cmp()".
  10.  *
  11.  *              If a datanode is found such that identifier(datanode) equals
  12.  *              identifier(item), the new data from item replaces the data
  13.  *              existing in datanode if & only if parameter replace == 1.
  14.  *
  15.  * !!NOTE!!     Programs that use this module must also link in the module
  16.  *              whose source is in the file "TAVLREBL.C".
  17.  *
  18.  *
  19.  *  Released to the PUBLIC DOMAIN
  20.  *
  21.  *  author:                 Bert C. Hughes
  22.  *                          200 N.Saratoga
  23.  *                          St.Paul, MN 55104
  24.  *                          Compuserve 71211,577
  25.  */
  26.  
  27.    /* Debugging "assert"s are in the code to test integrity of the    */
  28.    /* tree. All assertions should be removed from production versions */
  29.    /* of the library by compiling the library with NDEBUG defined.    */
  30.    /* See the header "assert.h".*/
  31.  
  32. #include <assert.h>
  33. #include "tavltree.h"
  34. #include "tavlpriv.h"
  35.  
  36. TAVL_nodeptr tavl_insert(TAVL_treeptr tree, void *item, int replace)
  37.                 /*
  38.                 Using the user supplied (key_of) & (cmp) functions, *tree
  39.                 is searched for a node which matches *item. If a match is
  40.                 found, the new item replaces the old if & only if
  41.                 replace != 0.  If no match is found the item is inserted
  42.                 into *tree.  "tavl_insert" returns a pointer to the node
  43.                 inserted into or found in *tree. "tavl_insert" returns
  44.                 NULL if & only if it is unable to allocate memory for
  45.                 a new node.
  46.                 */
  47. {
  48.     TAVL_nodeptr a,y,f;
  49.     register TAVL_nodeptr p,q;
  50.     register int cmpval = -1; /* cmpval must be initialized - if tree is */
  51.     int side;                 /* empty node inserted as LeftChild of head */
  52.     char junk;
  53.  
  54.     /*  Locate insertion point for item.  "a" keeps track of most
  55.         recently seen node with (bf != 0) - or it is the top of the
  56.         tree, if no nodes with (p->bf != 0) are encountered.  "f"
  57.         is parent of "a".  "q" follows "p" through tree.
  58.     */
  59.  
  60.     q = tree->head;   a = q;  f = NULL;  p = Leftchild(q);
  61.  
  62.     while (p) {
  63.         if (p->bf) { a = p; f = q; }
  64.  
  65.         q = p;
  66.  
  67.         cmpval = (*tree->cmp)((*tree->key_of)(item),(*tree->key_of)(p->dataptr));
  68.  
  69.         if (cmpval < 0)
  70.             p = Leftchild(p);
  71.         else if (cmpval > 0)
  72.             p = Rightchild(p);
  73.         else {
  74.             if (replace) {
  75.                 void *temp = (*tree->make_item)(item);
  76.                 if (temp) {
  77.                     (*tree->free_item)(p->dataptr);
  78.                     p->dataptr = temp;
  79.                 }
  80.                 else p = NULL;
  81.             }
  82.             return p;
  83.         }
  84.     }
  85.  
  86.     /* wasn't found - create new node as child of q */
  87.  
  88.     y = (*tree->alloc)(sizeof(TAVL_NODE));
  89.  
  90.     if (y) {
  91.         y->bf = 0;
  92.         y->Lbit = THREAD;
  93.         y->Rbit = THREAD;
  94.         if ((y->dataptr = (*tree->make_item)(item)) == NULL) {
  95.             (*tree->dealloc)(y);
  96.             return NULL;        /* must be out of memory */
  97.         }
  98.     }
  99.     else return NULL;           /* out of memory */
  100.  
  101.     if (cmpval < 0) {           /* connect to tree and thread it */
  102.         y->Lptr = q->Lptr;
  103.         y->Rptr = q;
  104.         q->Lbit = LINK;
  105.         q->Lptr = y;
  106.     }
  107.     else {
  108.         y->Rptr = q->Rptr;
  109.         y->Lptr = q;
  110.         q->Rbit = LINK;
  111.         q->Rptr = y;
  112.     }
  113.  
  114.     /*  Adjust balance factors on path from a to q.  By definition of "a",
  115.         all nodes on this path have bf = 0, and so will change to LEFT or
  116.         RIGHT.
  117.     */
  118.  
  119.     if ((a == tree->head) || ((*tree->cmp)((*tree->key_of)(item),
  120.                                            (*tree->key_of)(a->dataptr))< 0)) {
  121.         p = a->Lptr; side = LEFT;
  122.     }
  123.     else {
  124.         p = a->Rptr; side = RIGHT;
  125.     }
  126.  
  127.     /* adjust balance factors */
  128.  
  129.     while (p != y) {
  130.         if ((*tree->cmp)((*tree->key_of)(p->dataptr),(*tree->key_of)(item))> 0) {
  131.             p->bf = LEFT;   p = p->Lptr;
  132.         }
  133.         else {
  134.             p->bf = RIGHT;  p = p->Rptr;
  135.         }
  136.     }
  137.  
  138.     tree->head->bf = 0;     /* if a==tree->head, tree is already balanced */
  139.  
  140.     /* Is tree balanced? */
  141.  
  142.     if (abs(a->bf += side) < 2) return y;
  143.  
  144.     p = rebalance_tavl(a,&junk);
  145.  
  146.     assert(junk);   /* rebalance always sets junk to 0 */
  147.  
  148.     assert(f);      /* f was set non-NULL by the search loop */
  149.  
  150.     if (f->Rptr != a)
  151.         f->Lptr = p;
  152.     else
  153.         f->Rptr = p;
  154.  
  155.     return y;
  156. }
  157.