home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / Samples / CSAPE32.ARJ / SOURCE / OWLSCR / DIGBTREE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-11-01  |  5.8 KB  |  224 lines
  1. /*
  2.     digbtree.c
  3.  
  4.     % Binary tree manipulation code.
  5.  
  6.     OWL-DIG 1.2
  7.     Copyright (c) 1990 by Oakland Group, Inc.
  8.     ALL RIGHTS RESERVED.
  9.  
  10.     Revision History:
  11.     -----------------
  12.      5/31/90 bkd    Created.
  13.      8/14/90 bkd    made btree_TreeInsert return a btreecode
  14.      9/24/90 jsm    added cast for C++
  15.     10/03/90 ted    added conditional code to work around Watcom compiler bug.
  16. */
  17.  
  18. #include "oakhead.h"
  19. #include "disppriv.h"
  20. #include "digutil.h"
  21. /* -------------------------------------------------------------------------- */
  22.  
  23. OSTATIC void DIGPRIV btree_TreeClose(btree_type bt, btnode_type node);
  24. OSTATIC btreecode DIGPRIV btree_TreeInsert(btree_type bt, btnode_type tree, VOID *data);
  25. OSTATIC VOID * DIGPRIV btree_TreeGet(btree_type bt, btnode_type tree, byte *key);
  26.  
  27. /*
  28.     A btree is a simple ordered binary tree.  Associated with each
  29.      btree are three routines:
  30.     1) The nodecomp routine.  This routine compares any two nodes
  31.        and provides a signed numeric value corresponding to
  32.        less than, equal to or greater than.
  33.     2) The keycomp routine.  This one is similar to the nodecomp
  34.        routine except that instead being given two nodes, this
  35.        one is fed a node and a pointer to a "key".  The key is
  36.        that part of a node which is used for these comparisons.
  37.     3) The freertn routine.  At btree_Close time (and possibly
  38.        during error recovery) a tree must be freed up.  The node
  39.        data pointers are (most likely) lost at this point.  They are
  40.        fed to the freertn before being cast into the void.  Ugh.
  41.        That last thing sounds like a nasty pun.  I apologize.
  42. */
  43.  
  44. /* -------------------------------------------------------------------------- */
  45. /********* CREATORS *********/
  46.  
  47. btree_type DIGPRIV btree_Open(
  48.     btree_nodecomp_fptr nodecomp,
  49.     btree_keycomp_fptr keycomp,
  50.     btree_freertn_fptr freertn)
  51. {
  52.     register btree_type bt;
  53.  
  54.     if ((bt = (btree_type) omalloc(OA_BTREE, sizeof(* (btree_type) 0)))
  55.         == NULL) {
  56.         return(NULL);
  57.     }
  58.  
  59.     bt->root = NULL;
  60.     bt->nodecomp = nodecomp;
  61.     bt->keycomp = keycomp;
  62.     bt->freertn = freertn;
  63.  
  64.     return(bt);
  65. }
  66. /* -------------------------------------------------------------------------- */
  67. /********* DESTROYERS *********/
  68.  
  69. void DIGPRIV btree_Close(btree_type bt)
  70. {
  71.     if (bt == NULL) {
  72.         return;
  73.     }
  74.     btree_TreeClose(bt, bt->root);
  75. }
  76. /* -------------------------------------------------------------------------- */
  77. /********* MUTATORS *********/
  78.  
  79. btreecode DIGPRIV btree_Insert(btree_type bt, VOID *data)
  80. /*
  81.     btree_Insert - Insert a hunk of data into a btree.  Can return
  82.     a number of values:
  83.     BTREE_ERROR    - An error occurred.  Most likely this
  84.             means that you ran out of memory.
  85.     BTREE_DUP    - A node was found that, according to the nodecomp
  86.             routine, has the same weight as the new data.
  87.     BTREE_OK    - Data were inserted without incident.
  88. */
  89. {
  90.     btnode_type node;
  91.     btreecode    rval;
  92.  
  93.     if (bt == NULL || data == NULL) {
  94.         return(BTREE_ERROR);
  95.     }
  96.  
  97.     node = bt->root;
  98.     if (node == NULL) {
  99. #ifdef __WATCOMC__
  100.         node = NULL;        /* Just to avoid Watcom compiler crash */
  101. #endif
  102.         if ((node = (btnode_type)
  103.             omalloc(OA_BTREE, sizeof(* (btnode_type) 0))) == NULL) {
  104.             return(BTREE_ERROR);
  105.         }
  106.         node->lchild = node->rchild = NULL;
  107.         node->data = data;
  108.  
  109.         bt->root = node;
  110.  
  111.         rval = BTREE_OK;
  112.     }
  113.     else {
  114.         rval = btree_TreeInsert(bt, bt->root, data);
  115.     }
  116.     return(rval);
  117. }
  118. /* -------------------------------------------------------------------------- */
  119. /********* OBSERVERS *********/
  120.  
  121. VOID * DIGPRIV btree_Get(btree_type bt, VOID *key)
  122. {
  123.     VOID *rval;
  124.  
  125.     if (bt == NULL || key == NULL) {
  126.         return(NULL);
  127.     }
  128.     rval = btree_TreeGet(bt, bt->root, (byte *) key);
  129.     return(rval);
  130. }
  131. /* -------------------------------------------------------------------------- */
  132. /* -------------------------------------------------------------------------- */
  133.  
  134. static void DIGPRIV btree_TreeClose(btree_type bt, btnode_type node)
  135. /*
  136.     (recursively) closes down nodes in a tree.
  137. */
  138. {
  139.     if (node == NULL) {
  140.         return;
  141.     }
  142.  
  143.     /* Close down the children below this node */
  144.  
  145.     btree_TreeClose(bt, node->lchild);
  146.     btree_TreeClose(bt, node->rchild);
  147.  
  148.     /* and now close this node proper. */
  149.  
  150.     (*bt->freertn)(node->data);
  151.  
  152.     ofree(OA_BTREE, (VOID *) node);
  153. }
  154. /* -------------------------------------------------------------------------- */
  155.  
  156. static btreecode DIGPRIV btree_TreeInsert(btree_type bt, btnode_type tree, VOID *data)
  157. /*
  158.     btree_TreeInsert - An internal recursive routine used by btree_Insert
  159.      to insert a hunk of data.
  160. */
  161. {
  162.     register int comparison;
  163.     register btnode_type newnode;
  164.     btnode_type *childp, tchild;
  165.  
  166.     comparison = (*bt->nodecomp)(tree->data, data);
  167.  
  168.     if (comparison == 0) {
  169.         return(BTREE_DUP);
  170.     }
  171.     else if (comparison < 0) {
  172.         childp = &(tree->rchild);
  173.     }
  174.     else {
  175.         childp = &(tree->lchild);
  176.     }
  177.  
  178.     tchild = *childp;
  179.     if (tchild == NULL) {
  180. #ifdef __WATCOMC__
  181.         tchild = NULL;        /* Just to avoid Watcom compiler crash */
  182. #endif
  183.         if ((newnode = (btnode_type)
  184.             omalloc(OA_BTREE, sizeof(* (btnode_type) 0))) == NULL) {
  185.             return(BTREE_ERROR);
  186.         }
  187.         newnode->lchild = newnode->rchild = NULL;
  188.         newnode->data = data;
  189.         *childp = newnode;
  190.  
  191.         return(BTREE_OK);
  192.     }
  193.     else {
  194.         return(btree_TreeInsert(bt, *childp, data));
  195.     }
  196. }
  197. /* -------------------------------------------------------------------------- */
  198.  
  199. static VOID * DIGPRIV btree_TreeGet(btree_type bt, btnode_type tree, byte *key)
  200. {
  201.     register int comparison;
  202.     register btnode_type child;
  203.  
  204.     if (tree == NULL) {
  205.         return(NULL);
  206.     }
  207.  
  208.     comparison = (*bt->keycomp)(tree->data, key);
  209.  
  210.     if (comparison == 0) {
  211.         return(tree->data);
  212.     }
  213.     else if (comparison < 0) {
  214.         child = tree->rchild;
  215.     }
  216.     else {
  217.         child = tree->lchild;
  218.     }
  219.  
  220.     return(btree_TreeGet(bt, child, key));
  221. }
  222. /* -------------------------------------------------------------------------- */
  223.  
  224.