home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ldapsdk.zip / libraries / libavl / avl.c next >
C/C++ Source or Header  |  2000-09-15  |  18KB  |  756 lines
  1. /* avl.c - routines to implement an avl tree */
  2. /* $OpenLDAP: pkg/ldap/libraries/libavl/avl.c,v 1.13.6.4 2000/09/15 00:50:14 bcollins Exp $ */
  3. /*
  4.  * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved.
  5.  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
  6.  */
  7. /*
  8.  * Copyright (c) 1993 Regents of the University of Michigan.
  9.  * All rights reserved.
  10.  *
  11.  * Redistribution and use in source and binary forms are permitted
  12.  * provided that this notice is preserved and that due credit is given
  13.  * to the University of Michigan at Ann Arbor. The name of the University
  14.  * may not be used to endorse or promote products derived from this
  15.  * software without specific prior written permission. This software
  16.  * is provided ``as is'' without express or implied warranty.
  17.  */
  18.  
  19. #include "portable.h"
  20.  
  21. #include <stdio.h>
  22. #include <ac/stdlib.h>
  23.  
  24. #define AVL_INTERNAL
  25. #include "avl.h"
  26.  
  27. #define ROTATERIGHT(x)    { \
  28.     Avlnode *tmp;\
  29.     if ( *(x) == NULL || (*(x))->avl_left == NULL ) {\
  30.         (void) fputs("RR error\n", stderr); exit( EXIT_FAILURE ); \
  31.     }\
  32.     tmp = (*(x))->avl_left;\
  33.     (*(x))->avl_left = tmp->avl_right;\
  34.     tmp->avl_right = *(x);\
  35.     *(x) = tmp;\
  36. }
  37. #define ROTATELEFT(x)    { \
  38.     Avlnode *tmp;\
  39.     if ( *(x) == NULL || (*(x))->avl_right == NULL ) {\
  40.         (void) fputs("RL error\n", stderr); exit( EXIT_FAILURE ); \
  41.     }\
  42.     tmp = (*(x))->avl_right;\
  43.     (*(x))->avl_right = tmp->avl_left;\
  44.     tmp->avl_left = *(x);\
  45.     *(x) = tmp;\
  46. }
  47.  
  48. /*
  49.  * ravl_insert - called from avl_insert() to do a recursive insert into
  50.  * and balance of an avl tree.
  51.  */
  52.  
  53. static int
  54. ravl_insert(
  55.     Avlnode    **iroot,
  56.     void*    data,
  57.     int        *taller,
  58.     AVL_CMP        fcmp,            /* comparison function */
  59.     AVL_DUP        fdup,            /* function to call for duplicates */
  60.     int        depth
  61. )
  62. {
  63.     int    rc, cmp, tallersub;
  64.     Avlnode    *l, *r;
  65.  
  66.     if ( *iroot == 0 ) {
  67.         if ( (*iroot = (Avlnode *) malloc( sizeof( Avlnode ) ))
  68.             == NULL ) {
  69.             return( -1 );
  70.         }
  71.         (*iroot)->avl_left = 0;
  72.         (*iroot)->avl_right = 0;
  73.         (*iroot)->avl_bf = 0;
  74.         (*iroot)->avl_data = data;
  75.         *taller = 1;
  76.         return( 0 );
  77.     }
  78.  
  79.     cmp = (*fcmp)( data, (*iroot)->avl_data );
  80.  
  81.     /* equal - duplicate name */
  82.     if ( cmp == 0 ) {
  83.         *taller = 0;
  84.         return( (*fdup)( (*iroot)->avl_data, data ) );
  85.     }
  86.  
  87.     /* go right */
  88.     else if ( cmp > 0 ) {
  89.         rc = ravl_insert( &((*iroot)->avl_right), data, &tallersub,
  90.            fcmp, fdup, depth );
  91.         if ( tallersub )
  92.             switch ( (*iroot)->avl_bf ) {
  93.             case LH    : /* left high - balance is restored */
  94.                 (*iroot)->avl_bf = EH;
  95.                 *taller = 0;
  96.                 break;
  97.             case EH    : /* equal height - now right heavy */
  98.                 (*iroot)->avl_bf = RH;
  99.                 *taller = 1;
  100.                 break;
  101.             case RH    : /* right heavy to start - right balance */
  102.                 r = (*iroot)->avl_right;
  103.                 switch ( r->avl_bf ) {
  104.                 case LH    : /* double rotation left */
  105.                     l = r->avl_left;
  106.                     switch ( l->avl_bf ) {
  107.                     case LH    : (*iroot)->avl_bf = EH;
  108.                           r->avl_bf = RH;
  109.                           break;
  110.                     case EH    : (*iroot)->avl_bf = EH;
  111.                           r->avl_bf = EH;
  112.                           break;
  113.                     case RH    : (*iroot)->avl_bf = LH;
  114.                           r->avl_bf = EH;
  115.                           break;
  116.                     }
  117.                     l->avl_bf = EH;
  118.                     ROTATERIGHT( (&r) )
  119.                     (*iroot)->avl_right = r;
  120.                     ROTATELEFT( iroot )
  121.                     *taller = 0;
  122.                     break;
  123.                 case EH    : /* This should never happen */
  124.                     break;
  125.                 case RH    : /* single rotation left */
  126.                     (*iroot)->avl_bf = EH;
  127.                     r->avl_bf = EH;
  128.                     ROTATELEFT( iroot )
  129.                     *taller = 0;
  130.                     break;
  131.                 }
  132.                 break;
  133.             }
  134.         else
  135.             *taller = 0;
  136.     }
  137.  
  138.     /* go left */
  139.     else {
  140.         rc = ravl_insert( &((*iroot)->avl_left), data, &tallersub,
  141.            fcmp, fdup, depth );
  142.         if ( tallersub )
  143.             switch ( (*iroot)->avl_bf ) {
  144.             case LH    : /* left high to start - left balance */
  145.                 l = (*iroot)->avl_left;
  146.                 switch ( l->avl_bf ) {
  147.                 case LH    : /* single rotation right */
  148.                     (*iroot)->avl_bf = EH;
  149.                     l->avl_bf = EH;
  150.                     ROTATERIGHT( iroot )
  151.                     *taller = 0;
  152.                     break;
  153.                 case EH    : /* this should never happen */
  154.                     break;
  155.                 case RH    : /* double rotation right */
  156.                     r = l->avl_right;
  157.                     switch ( r->avl_bf ) {
  158.                     case LH    : (*iroot)->avl_bf = RH;
  159.                           l->avl_bf = EH;
  160.                           break;
  161.                     case EH    : (*iroot)->avl_bf = EH;
  162.                           l->avl_bf = EH;
  163.                           break;
  164.                     case RH    : (*iroot)->avl_bf = EH;
  165.                           l->avl_bf = LH;
  166.                           break;
  167.                     }
  168.                     r->avl_bf = EH;
  169.                     ROTATELEFT( (&l) )
  170.                     (*iroot)->avl_left = l;
  171.                     ROTATERIGHT( iroot )
  172.                     *taller = 0;
  173.                     break;
  174.                 }
  175.                 break;
  176.             case EH    : /* equal height - now left heavy */
  177.                 (*iroot)->avl_bf = LH;
  178.                 *taller = 1;
  179.                 break;
  180.             case RH    : /* right high - balance is restored */
  181.                 (*iroot)->avl_bf = EH;
  182.                 *taller = 0;
  183.                 break;
  184.             }
  185.         else
  186.             *taller = 0;
  187.     }
  188.  
  189.     return( rc );
  190. }
  191.  
  192. /*
  193.  * avl_insert -- insert a node containing data data into the avl tree
  194.  * with root root.  fcmp is a function to call to compare the data portion
  195.  * of two nodes.  it should take two arguments and return <, >, or == 0,
  196.  * depending on whether its first argument is <, >, or == its second
  197.  * argument (like strcmp, e.g.).  fdup is a function to call when a duplicate
  198.  * node is inserted.  it should return 0, or -1 and its return value
  199.  * will be the return value from avl_insert in the case of a duplicate node.
  200.  * the function will be called with the original node's data as its first
  201.  * argument and with the incoming duplicate node's data as its second
  202.  * argument.  this could be used, for example, to keep a count with each
  203.  * node.
  204.  *
  205.  * NOTE: this routine may malloc memory
  206.  */
  207.  
  208. int
  209. avl_insert( Avlnode **root, void* data, AVL_CMP fcmp, AVL_DUP fdup )
  210. {
  211.     int    taller;
  212.  
  213.     return( ravl_insert( root, data, &taller, fcmp, fdup, 0 ) );
  214. }
  215.  
  216. /* 
  217.  * right_balance() - called from delete when root's right subtree has
  218.  * been shortened because of a deletion.
  219.  */
  220.  
  221. static int
  222. right_balance( Avlnode **root )
  223. {
  224.     int    shorter = -1;
  225.     Avlnode    *r, *l;
  226.  
  227.     switch( (*root)->avl_bf ) {
  228.     case RH:    /* was right high - equal now */
  229.         (*root)->avl_bf = EH;
  230.         shorter = 1;
  231.         break;
  232.     case EH:    /* was equal - left high now */
  233.         (*root)->avl_bf = LH;
  234.         shorter = 0;
  235.         break;
  236.     case LH:    /* was right high - balance */
  237.         l = (*root)->avl_left;
  238.         switch ( l->avl_bf ) {
  239.         case RH    : /* double rotation left */
  240.             r = l->avl_right;
  241.             switch ( r->avl_bf ) {
  242.             case RH    :
  243.                 (*root)->avl_bf = EH;
  244.                 l->avl_bf = LH;
  245.                 break;
  246.             case EH    :
  247.                 (*root)->avl_bf = EH;
  248.                 l->avl_bf = EH;
  249.                 break;
  250.             case LH    :
  251.                 (*root)->avl_bf = RH;
  252.                 l->avl_bf = EH;
  253.                 break;
  254.             }
  255.             r->avl_bf = EH;
  256.             ROTATELEFT( (&l) )
  257.             (*root)->avl_left = l;
  258.             ROTATERIGHT( root )
  259.             shorter = 1;
  260.             break;
  261.         case EH    : /* right rotation */
  262.             (*root)->avl_bf = LH;
  263.             l->avl_bf = RH;
  264.             ROTATERIGHT( root );
  265.             shorter = 0;
  266.             break;
  267.         case LH    : /* single rotation right */
  268.             (*root)->avl_bf = EH;
  269.             l->avl_bf = EH;
  270.             ROTATERIGHT( root )
  271.             shorter = 1;
  272.             break;
  273.         }
  274.         break;
  275.     }
  276.  
  277.     return( shorter );
  278. }
  279.  
  280. /* 
  281.  * left_balance() - called from delete when root's left subtree has
  282.  * been shortened because of a deletion.
  283.  */
  284.  
  285. static int
  286. left_balance( Avlnode **root )
  287. {
  288.     int    shorter = -1;
  289.     Avlnode    *r, *l;
  290.  
  291.     switch( (*root)->avl_bf ) {
  292.     case LH:    /* was left high - equal now */
  293.         (*root)->avl_bf = EH;
  294.         shorter = 1;
  295.         break;
  296.     case EH:    /* was equal - right high now */
  297.         (*root)->avl_bf = RH;
  298.         shorter = 0;
  299.         break;
  300.     case RH:    /* was right high - balance */
  301.         r = (*root)->avl_right;
  302.         switch ( r->avl_bf ) {
  303.         case LH    : /* double rotation left */
  304.             l = r->avl_left;
  305.             switch ( l->avl_bf ) {
  306.             case LH    :
  307.                 (*root)->avl_bf = EH;
  308.                 r->avl_bf = RH;
  309.                 break;
  310.             case EH    :
  311.                 (*root)->avl_bf = EH;
  312.                 r->avl_bf = EH;
  313.                 break;
  314.             case RH    :
  315.                 (*root)->avl_bf = LH;
  316.                 r->avl_bf = EH;
  317.                 break;
  318.             }
  319.             l->avl_bf = EH;
  320.             ROTATERIGHT( (&r) )
  321.             (*root)->avl_right = r;
  322.             ROTATELEFT( root )
  323.             shorter = 1;
  324.             break;
  325.         case EH    : /* single rotation left */
  326.             (*root)->avl_bf = RH;
  327.             r->avl_bf = LH;
  328.             ROTATELEFT( root );
  329.             shorter = 0;
  330.             break;
  331.         case RH    : /* single rotation left */
  332.             (*root)->avl_bf = EH;
  333.             r->avl_bf = EH;
  334.             ROTATELEFT( root )
  335.             shorter = 1;
  336.             break;
  337.         }
  338.         break;
  339.     }
  340.  
  341.     return( shorter );
  342. }
  343.  
  344. /*
  345.  * ravl_delete() - called from avl_delete to do recursive deletion of a
  346.  * node from an avl tree.  It finds the node recursively, deletes it,
  347.  * and returns shorter if the tree is shorter after the deletion and
  348.  * rebalancing.
  349.  */
  350.  
  351. static void*
  352. ravl_delete( Avlnode **root, void* data, AVL_CMP fcmp, int *shorter )
  353. {
  354.     int    shortersubtree = 0;
  355.     int    cmp;
  356.     void*    savedata;
  357.     Avlnode    *minnode, *savenode;
  358.  
  359.     if ( *root == NULLAVL )
  360.         return( 0 );
  361.  
  362.     cmp = (*fcmp)( data, (*root)->avl_data );
  363.  
  364.     /* found it! */
  365.     if ( cmp == 0 ) {
  366.         savenode = *root;
  367.         savedata = savenode->avl_data;
  368.  
  369.         /* simple cases: no left child */
  370.         if ( (*root)->avl_left == 0 ) {
  371.             *root = (*root)->avl_right;
  372.             *shorter = 1;
  373.             free( (char *) savenode );
  374.             return( savedata );
  375.         /* no right child */
  376.         } else if ( (*root)->avl_right == 0 ) {
  377.             *root = (*root)->avl_left;
  378.             *shorter = 1;
  379.             free( (char *) savenode );
  380.             return( savedata );
  381.         }
  382.  
  383.         /* 
  384.          * avl_getmin will return to us the smallest node greater
  385.          * than the one we are trying to delete.  deleting this node
  386.          * from the right subtree is guaranteed to end in one of the
  387.          * simple cases above.
  388.          */
  389.  
  390.         minnode = (*root)->avl_right;
  391.         while ( minnode->avl_left != NULLAVL )
  392.             minnode = minnode->avl_left;
  393.  
  394.         /* swap the data */
  395.         (*root)->avl_data = minnode->avl_data;
  396.         minnode->avl_data = savedata;
  397.  
  398.         savedata = ravl_delete( &(*root)->avl_right, data, fcmp,
  399.             &shortersubtree );
  400.  
  401.         if ( shortersubtree )
  402.             *shorter = right_balance( root );
  403.         else
  404.             *shorter = 0;
  405.     /* go left */
  406.     } else if ( cmp < 0 ) {
  407.         if ( (savedata = ravl_delete( &(*root)->avl_left, data, fcmp,
  408.             &shortersubtree )) == 0 ) {
  409.             *shorter = 0;
  410.             return( 0 );
  411.         }
  412.  
  413.         /* left subtree shorter? */
  414.         if ( shortersubtree )
  415.             *shorter = left_balance( root );
  416.         else
  417.             *shorter = 0;
  418.     /* go right */
  419.     } else {
  420.         if ( (savedata = ravl_delete( &(*root)->avl_right, data, fcmp,
  421.             &shortersubtree )) == 0 ) {
  422.             *shorter = 0;
  423.             return( 0 );
  424.         }
  425.  
  426.         if ( shortersubtree ) 
  427.             *shorter = right_balance( root );
  428.         else
  429.             *shorter = 0;
  430.     }
  431.  
  432.     return( savedata );
  433. }
  434.  
  435. /*
  436.  * avl_delete() - deletes the node containing data (according to fcmp) from
  437.  * the avl tree rooted at root.
  438.  */
  439.  
  440. void*
  441. avl_delete( Avlnode **root, void* data, AVL_CMP fcmp )
  442. {
  443.     int    shorter;
  444.  
  445.     return( ravl_delete( root, data, fcmp, &shorter ) );
  446. }
  447.  
  448. static int
  449. avl_inapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
  450. {
  451.     if ( root == 0 )
  452.         return( AVL_NOMORE );
  453.  
  454.     if ( root->avl_left != 0 )
  455.         if ( avl_inapply( root->avl_left, fn, arg, stopflag ) 
  456.             == stopflag )
  457.             return( stopflag );
  458.  
  459.     if ( (*fn)( root->avl_data, arg ) == stopflag )
  460.         return( stopflag );
  461.  
  462.     if ( root->avl_right == 0 )
  463.         return( AVL_NOMORE );
  464.     else
  465.         return( avl_inapply( root->avl_right, fn, arg, stopflag ) );
  466. }
  467.  
  468. static int
  469. avl_postapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
  470. {
  471.     if ( root == 0 )
  472.         return( AVL_NOMORE );
  473.  
  474.     if ( root->avl_left != 0 )
  475.         if ( avl_postapply( root->avl_left, fn, arg, stopflag ) 
  476.             == stopflag )
  477.             return( stopflag );
  478.  
  479.     if ( root->avl_right != 0 )
  480.         if ( avl_postapply( root->avl_right, fn, arg, stopflag ) 
  481.             == stopflag )
  482.             return( stopflag );
  483.  
  484.     return( (*fn)( root->avl_data, arg ) );
  485. }
  486.  
  487. static int
  488. avl_preapply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag )
  489. {
  490.     if ( root == 0 )
  491.         return( AVL_NOMORE );
  492.  
  493.     if ( (*fn)( root->avl_data, arg ) == stopflag )
  494.         return( stopflag );
  495.  
  496.     if ( root->avl_left != 0 )
  497.         if ( avl_preapply( root->avl_left, fn, arg, stopflag ) 
  498.             == stopflag )
  499.             return( stopflag );
  500.  
  501.     if ( root->avl_right == 0 )
  502.         return( AVL_NOMORE );
  503.     else
  504.         return( avl_preapply( root->avl_right, fn, arg, stopflag ) );
  505. }
  506.  
  507. /*
  508.  * avl_apply -- avl tree root is traversed, function fn is called with
  509.  * arguments arg and the data portion of each node.  if fn returns stopflag,
  510.  * the traversal is cut short, otherwise it continues.  Do not use -6 as
  511.  * a stopflag, as this is what is used to indicate the traversal ran out
  512.  * of nodes.
  513.  */
  514.  
  515. int
  516. avl_apply( Avlnode *root, AVL_APPLY fn, void* arg, int stopflag, int type )
  517. {
  518.     switch ( type ) {
  519.     case AVL_INORDER:
  520.         return( avl_inapply( root, fn, arg, stopflag ) );
  521.     case AVL_PREORDER:
  522.         return( avl_preapply( root, fn, arg, stopflag ) );
  523.     case AVL_POSTORDER:
  524.         return( avl_postapply( root, fn, arg, stopflag ) );
  525.     default:
  526.         fprintf( stderr, "Invalid traversal type %d\n", type );
  527.         return( -1 );
  528.     }
  529.  
  530.     /* NOTREACHED */
  531. }
  532.  
  533. /*
  534.  * avl_prefixapply - traverse avl tree root, applying function fprefix
  535.  * to any nodes that match.  fcmp is called with data as its first arg
  536.  * and the current node's data as its second arg.  it should return
  537.  * 0 if they match, < 0 if data is less, and > 0 if data is greater.
  538.  * the idea is to efficiently find all nodes that are prefixes of
  539.  * some key...  Like avl_apply, this routine also takes a stopflag
  540.  * and will return prematurely if fmatch returns this value.  Otherwise,
  541.  * AVL_NOMORE is returned.
  542.  */
  543.  
  544. int
  545. avl_prefixapply(
  546.     Avlnode    *root,
  547.     void*    data,
  548.     AVL_CMP        fmatch,
  549.     void*    marg,
  550.     AVL_CMP        fcmp,
  551.     void*    carg,
  552.     int        stopflag
  553. )
  554. {
  555.     int    cmp;
  556.  
  557.     if ( root == 0 )
  558.         return( AVL_NOMORE );
  559.  
  560.     cmp = (*fcmp)( data, root->avl_data /* , carg */);
  561.     if ( cmp == 0 ) {
  562.         if ( (*fmatch)( root->avl_data, marg ) == stopflag )
  563.             return( stopflag );
  564.  
  565.         if ( root->avl_left != 0 )
  566.             if ( avl_prefixapply( root->avl_left, data, fmatch,
  567.                 marg, fcmp, carg, stopflag ) == stopflag )
  568.                 return( stopflag );
  569.  
  570.         if ( root->avl_right != 0 )
  571.             return( avl_prefixapply( root->avl_right, data, fmatch,
  572.                 marg, fcmp, carg, stopflag ) );
  573.         else
  574.             return( AVL_NOMORE );
  575.  
  576.     } else if ( cmp < 0 ) {
  577.         if ( root->avl_left != 0 )
  578.             return( avl_prefixapply( root->avl_left, data, fmatch,
  579.                 marg, fcmp, carg, stopflag ) );
  580.     } else {
  581.         if ( root->avl_right != 0 )
  582.             return( avl_prefixapply( root->avl_right, data, fmatch,
  583.                 marg, fcmp, carg, stopflag ) );
  584.     }
  585.  
  586.     return( AVL_NOMORE );
  587. }
  588.  
  589. /*
  590.  * avl_free -- traverse avltree root, freeing the memory it is using.
  591.  * the dfree() is called to free the data portion of each node.  The
  592.  * number of items actually freed is returned.
  593.  */
  594.  
  595. int
  596. avl_free( Avlnode *root, AVL_FREE dfree )
  597. {
  598.     int    nleft, nright;
  599.  
  600.     if ( root == 0 )
  601.         return( 0 );
  602.  
  603.     nleft = nright = 0;
  604.     if ( root->avl_left != 0 )
  605.         nleft = avl_free( root->avl_left, dfree );
  606.  
  607.     if ( root->avl_right != 0 )
  608.         nright = avl_free( root->avl_right, dfree );
  609.  
  610.     if ( dfree )
  611.         (*dfree)( root->avl_data );
  612.     free( root );
  613.  
  614.     return( nleft + nright + 1 );
  615. }
  616.  
  617. /*
  618.  * avl_find -- search avltree root for a node with data data.  the function
  619.  * cmp is used to compare things.  it is called with data as its first arg 
  620.  * and the current node data as its second.  it should return 0 if they match,
  621.  * < 0 if arg1 is less than arg2 and > 0 if arg1 is greater than arg2.
  622.  */
  623.  
  624. void*
  625. avl_find( Avlnode *root, const void* data, AVL_CMP fcmp )
  626. {
  627.     int    cmp;
  628.  
  629.     while ( root != 0 && (cmp = (*fcmp)( data, root->avl_data )) != 0 ) {
  630.         if ( cmp < 0 )
  631.             root = root->avl_left;
  632.         else
  633.             root = root->avl_right;
  634.     }
  635.  
  636.     return( root ? root->avl_data : 0 );
  637. }
  638.  
  639. /*
  640.  * avl_find_lin -- search avltree root linearly for a node with data data. 
  641.  * the function cmp is used to compare things.  it is called with data as its
  642.  * first arg and the current node data as its second.  it should return 0 if
  643.  * they match, non-zero otherwise.
  644.  */
  645.  
  646. void*
  647. avl_find_lin( Avlnode *root, const void* data, AVL_CMP fcmp )
  648. {
  649.     void*    res;
  650.  
  651.     if ( root == 0 )
  652.         return( NULL );
  653.  
  654.     if ( (*fcmp)( data, root->avl_data ) == 0 )
  655.         return( root->avl_data );
  656.  
  657.     if ( root->avl_left != 0 )
  658.         if ( (res = avl_find_lin( root->avl_left, data, fcmp ))
  659.             != NULL )
  660.             return( res );
  661.  
  662.     if ( root->avl_right == 0 )
  663.         return( NULL );
  664.     else
  665.         return( avl_find_lin( root->avl_right, data, fcmp ) );
  666. }
  667.  
  668. /* NON-REENTRANT INTERFACE */
  669.  
  670. static void*    *avl_list;
  671. static int    avl_maxlist;
  672. static int    avl_nextlist;
  673.  
  674. #define AVL_GRABSIZE    100
  675.  
  676. /* ARGSUSED */
  677. static int
  678. avl_buildlist( void* data, void* arg )
  679. {
  680.     static int    slots;
  681.  
  682.     if ( avl_list == (void* *) 0 ) {
  683.         avl_list = (void* *) malloc(AVL_GRABSIZE * sizeof(void*));
  684.         slots = AVL_GRABSIZE;
  685.         avl_maxlist = 0;
  686.     } else if ( avl_maxlist == slots ) {
  687.         slots += AVL_GRABSIZE;
  688.         avl_list = (void* *) realloc( (char *) avl_list,
  689.             (unsigned) slots * sizeof(void*));
  690.     }
  691.  
  692.     avl_list[ avl_maxlist++ ] = data;
  693.  
  694.     return( 0 );
  695. }
  696.  
  697. /*
  698.  * avl_getfirst() and avl_getnext() are provided as alternate tree
  699.  * traversal methods, to be used when a single function cannot be
  700.  * provided to be called with every node in the tree.  avl_getfirst()
  701.  * traverses the tree and builds a linear list of all the nodes,
  702.  * returning the first node.  avl_getnext() returns the next thing
  703.  * on the list built by avl_getfirst().  This means that avl_getfirst()
  704.  * can take a while, and that the tree should not be messed with while
  705.  * being traversed in this way, and that multiple traversals (even of
  706.  * different trees) cannot be active at once.
  707.  */
  708.  
  709. void*
  710. avl_getfirst( Avlnode *root )
  711. {
  712.     if ( avl_list ) {
  713.         free( (char *) avl_list);
  714.         avl_list = (void* *) 0;
  715.     }
  716.     avl_maxlist = 0;
  717.     avl_nextlist = 0;
  718.  
  719.     if ( root == 0 )
  720.         return( 0 );
  721.  
  722.     (void) avl_apply( root, avl_buildlist, (void*) 0, -1, AVL_INORDER );
  723.  
  724.     return( avl_list[ avl_nextlist++ ] );
  725. }
  726.  
  727. void*
  728. avl_getnext( void )
  729. {
  730.     if ( avl_list == 0 )
  731.         return( 0 );
  732.  
  733.     if ( avl_nextlist == avl_maxlist ) {
  734.         free( (void*) avl_list);
  735.         avl_list = (void* *) 0;
  736.         return( 0 );
  737.     }
  738.  
  739.     return( avl_list[ avl_nextlist++ ] );
  740. }
  741.  
  742. /* end non-reentrant code */
  743.  
  744.  
  745. int
  746. avl_dup_error( void* left, void* right )
  747. {
  748.     return( -1 );
  749. }
  750.  
  751. int
  752. avl_dup_ok( void* left, void* right )
  753. {
  754.     return( 0 );
  755. }
  756.