libwww/Library/src/HTBTree.html - annotate

Return to HTBTree.html CVS log
Up to [Public] / libwww / Library / src
Annotation of libwww/Library/src/HTBTree.html, revision 2.9

2.8       frystyk     1: <HTML>
                      2: <HEAD>
                      3: <TITLE>Balanced Binary Tree</TITLE>
                      4: </HEAD>
2.7       timbl       5: <BODY>
2.8       frystyk     6: <H1>Balanced Binary Tree</H1>
                      7: 
                      8: <PRE>
                      9: /*
                     10: **     (c) COPYRIGHT CERN 1994.
                     11: **     Please first read the full copyright statement in the file COPYRIGH.
                     12: */
                     13: </PRE>
                     14: 
                     15: Tree creation, traversal and freeing. User-supplied comparison
                     16: routine.<P>
                     17: 
                     18: This module is implemented by <A HREF="HTBTree.c">HTBTree.c</A>, and
                     19: it is a part of the <A
                     20: HREF="http://info.cern.ch/hypertext/WWW/Library/User/Guide/Guide.html">
                     21: Library of Common Code</A>.
                     22: 
                     23: <PRE>
2.9     ! roeber     24: #include "sysdep.h"
        !            25: 
2.8       frystyk    26: #ifdef SHORT_NAMES
2.7       timbl      27: #define        HTBTree_new             HTBTNew
                     28: #define        HTBTree_free            HTBTFree
                     29: #define HTBTreeAndObject_free  HTBTAOFr
                     30: #define HTBTree_add            HTBTAdd
                     31: #define        HTBTree_next            HTBTNext
                     32: /* #define     HTBTree_object          HTBTObje already a macro */
                     33: #endif
1.1       timbl      34: 
                     35: 
2.7       timbl      36: </PRE>
                     37: <H2>Data structures</H2>
                     38: <PRE>typedef struct _HTBTree_element {
1.1       timbl      39:     void                       *object;        /* User object */
                     40:     struct _HTBTree_element    *up;
                     41:     struct _HTBTree_element    *left;
                     42:     int                                left_depth;
                     43:     struct _HTBTree_element    *right;
                     44:     int                                right_depth;
                     45: } HTBTElement;
                     46: 
2.6       secret     47: typedef int (*HTComparer) PARAMS((void * a, void * b));
1.1       timbl      48: 
                     49: typedef struct _HTBTree_top {
                     50:     HTComparer                 compare;
                     51:     struct _HTBTree_element    *top;   
                     52: } HTBTree;
                     53: 
                     54: 
2.7       timbl      55: </PRE>
                     56: <H2>Create a binary tree given its discrimination
                     57: routine</H2>
                     58: <PRE>extern HTBTree * HTBTree_new PARAMS((HTComparer comp));
1.1       timbl      59: 
                     60: 
                     61: 
2.7       timbl      62: </PRE>
                     63: <H2>Free storage of the tree but not
                     64: of the objects</H2>
                     65: <PRE>extern void HTBTree_free PARAMS((HTBTree* tree));
2.6       secret     66: 
                     67: 
                     68: 
2.7       timbl      69: </PRE>
                     70: <H2>Free storage of the tree and of the
                     71: objects</H2>
                     72: <PRE>extern void HTBTreeAndObject_free PARAMS((HTBTree* tree));
2.6       secret     73: 
                     74: 
1.1       timbl      75: 
2.7       timbl      76: </PRE>
                     77: <H2>Add an object to a binary tree</H2>
                     78: <PRE>
                     79: extern void HTBTree_add PARAMS((HTBTree* tree, void * object));
1.1       timbl      80: 
                     81: 
2.7       timbl      82: </PRE>
                     83: <H2>Find user object for element</H2>
                     84: <PRE>#define HTBTree_object(element)  ((element)->object)
1.1       timbl      85: 
                     86: 
2.7       timbl      87: </PRE>
                     88: <H2>Find next element in depth-first
                     89: order</H2>
                     90: <H3>On entry,</H3>
                     91: <DL>
                     92: <DT>ele
                     93: <DD>if NULL, start with leftmost element.
                     94: if != 0 give next object to the right.
                     95: <DT>returns
                     96: <DD>Pointer to element ot NULL
                     97: if none left.
                     98: </DL>
1.1       timbl      99: 
2.7       timbl     100: <PRE>extern HTBTElement * HTBTree_next PARAMS((HTBTree* tree, HTBTElement * ele));
1.1       timbl     101: 
2.7       timbl     102: </PRE>end</BODY>
Webmaster