home *** CD-ROM | disk | FTP | other *** search
/ Oracle Video Server 3.0.3.1 / OVS_3031_NT.iso / win32 / medianet / server / include / yssp.h < prev    next >
Encoding:
C/C++ Source or Header  |  1996-07-15  |  14.7 KB  |  509 lines
  1. /* Copyright (c) 1995 by Oracle Corporation.  All Rights Reserved.
  2.  *
  3.  * yssp.h - Hash Table Manipulation
  4.  *
  5.  * DESCRIPTION
  6.  *
  7.  *  SPlay trees.  These are self-adjusting search trees
  8.  *  suitable for many purposes, including priority queues and ordered
  9.  *  search spaces.
  10.  *
  11.  *  For compatibility with yshsh:
  12.  * 
  13.  *    ysspTree *ysSpCreate( ysspCmpFunc cmpfunc, ysmff delfunc); 
  14.  *    void      ysSpDestroy(ysspTree *t);
  15.  *    void      ysSpIns(ysspTree *t, dvoid *key, size_t keysz, dvoid *val);
  16.  *    dvoid    *ysSpRem(ysspTree *t, dvoid *key, size_t keysz);
  17.  *    dvoid    *ysSpFind(ysspTree *t, dvoid *key, size_t keysz);
  18.  * 
  19.  *  For compatibility with mtsp:
  20.  *
  21.  *     ysspTree   *ysspNewTree( ysspTree *t, ysspCmpFunc *cmp );
  22.  *     ysspNode   *ysspLookup( dvoid *key, ysspTree *t );
  23.  *     ysspNode   *ysspFirstLookup( dvoid *key, ysspTree *t );
  24.  *     ysspNode   *ysspPELookup( dvoid *key, ysspTree *t );
  25.  *     ysspNode   *ysspNextLookup( dvoid *key, ysspTree *t );
  26.  *     ysspNode   *ysspEnq( ysspNode *node, ysspTree *t );
  27.  *     ysspNode   *ysspEnqAfter( ysspNode *node, ysspTree *t );
  28.  *     ysspNode   *ysspDeq( ysspNode **np );
  29.  *     ysspNode   *ysspDeqTree( ysspTree *t );
  30.  *     void       ysspRemove( ysspNode *node, ysspTree *t );
  31.  *     void       ysspSplay( ysspNode *n, ysspTree *t );
  32.  *     ysspNode   *ysspFHead( ysspTree *t );
  33.  *     ysspNode   *ysspFNext( ysspNode *n );
  34.  *
  35.  * ATTRS: public, external
  36.  *
  37.  * NOTES
  38.  *
  39.  *  Idiomatic use of these trees using the second familiy of interfaces
  40.  *  is as follows.
  41.  *
  42.  *    1.  Embed the node somewhere in another structure, and the tree
  43.  *        in some context.
  44.  *
  45.  *        typedef 
  46.  *        {
  47.  *            ysspNode n_mystruct;
  48.  *            myKeyType  key_mystruct;
  49.  *            ...
  50.  *        } mystruct;
  51.  *
  52.  *        typedef
  53.  *        {
  54.  *            ysspTree    t_mycx;
  55.  *            ...
  56.  *        } mycx;
  57.  *
  58.  *    2.  Initialize the tree when the context is set up.
  59.  *
  60.  *        ysspNewTree( &cx->t_myccx, myKeyTypeCmp );
  61.  *
  62.  *    3.  Insert with a duplicate check
  63.  *
  64.  *        mystruct *m;
  65.  *        if( !ysspLookup( (dvoid*)&keyval, &cx->t_mycx ) )
  66.  *        {
  67.  *        m = (mystruct*)ysmGlbAlloc( sizeof(*n), "mystruct");
  68.  *        m->key_mystruct = keyval;
  69.  *        m->node_mystruct.key_ysspNode = (dvoid*)&m->key_mystruct;
  70.  *        ysspEnq( &m->node_mystruct, &cx->t_mycx );
  71.  *        }
  72.  *
  73.  *    4.  Deletion by key value
  74.  *        
  75.  *        ysspNode *n;
  76.  *        if( (n = sspLookup( (dvoid*)&keyval, &cx->t_mycx ) ) )
  77.  *        {
  78.  *        ysspRemove( n, &cx->t_mycx );
  79.  *        ysmGlbFree( (dvoid*)n );
  80.  *        }
  81.  *
  82.  *    5.  Read-only iterate over the tree
  83.  *
  84.  *        ysspNode *n;
  85.  *        mystruct *m;
  86.  *        for( n = ysspFHead( &cx->t_mycx ) ; n ; n = ysspFnext( n ) )
  87.  *        {
  88.  *        m = (mystruct*)n;
  89.  *        mySomething( cx, m );
  90.  *        }
  91.  *
  92.  *    6.  Iterate over tree when current node may be deleted.
  93.  *
  94.  *        ysspNode *n, *next;
  95.  *        for( n = ysspFHead( &cx->t_mycx ) ; n ; n = next )
  96.  *        {
  97.  *        next = ysspFNext( n );
  98.  *        if( myPredicate( (mystruct*)n ) )
  99.  *            ysspRemove( n, &cx->t_mycx );
  100.  *        }
  101.  *
  102.  *    7.  Iteration when anything may happen to the tree during the loop.
  103.  *
  104.  *        This keeps a local copy of the current key and does a "next"
  105.  *        lookup on each iteration; slower, but safe and correct.
  106.  *
  107.  *        ysspNode *n;
  108.  *        myKeyType key;
  109.  *        boolean first = TRUE;
  110.  *
  111.  *        while( (n = first ? ysspFHead( &cx->t_mycx ) :
  112.  *            ysspNextLookup( (dvoid*)&key, &cx->t_mycx ) )
  113.  *        {
  114.  *        first = FALSE;
  115.  *        key = *(myKeyType*)n->key_ysspNode;
  116.  *        myDoAnythingToTheTree( (mystruct*)n, cx );
  117.  *        }  
  118.  *
  119.  *    8.  Tree deletion
  120.  *
  121.  *        ysspNode *n;
  122.  *        while( (n = ysspDeqTree( &cx->t_mycx ) ) )
  123.  *        ysmGlbFree( (dvoid*)n );
  124.  *
  125.  *
  126.  * MODIFIED   (MM/DD/YY)
  127.  *   dbrower   08/ 2/95 -  created, derived from mtsp.h and yshsh.h
  128.  *   dbrower   02/16/96 -  add ysspDeqTree, improve documentation.
  129.  *   dbrower   03/ 1/96 -  change cmp funcs to return sword, not sb4; olint.
  130.  */
  131.  
  132. /*
  133.  * This is derived from code:
  134.  *
  135.  * Copyright (c) 1994 by Academic Press, Boston, Massachusetts.
  136.  * Written by David Brower.  Not derived from licensed software.
  137.  * From the book "Software Solutions in C", edited by Dale Schumacher.
  138.  *
  139.  * Permission is granted to anyone to use this software for any
  140.  * purpose on any computer system, and to redistribute it in any way,
  141.  * subject to the following restrictions:
  142.  *
  143.  *   1. The author is not responsible for the consequences of use of
  144.  *    this software, no matter how awful, even if they arise
  145.  *    from defects in it.
  146.  *
  147.  *   2. The origin of this software must not be misrepresented, either
  148.  *    by explicit claim or by omission.
  149.  *
  150.  *   3. Altered versions must be plainly marked as such, and must not
  151.  *    be misrepresented (by explicit claim or omission) as being
  152.  *    the original software.
  153.  *
  154.  *   4. This notice must not be removed or altered.
  155.  */
  156.  
  157.  
  158. #ifndef YSSP_ORACLE
  159. #define YSSP_ORACLE
  160.  
  161. #ifndef SYSX_ORACLE
  162. #include <sysx.h>
  163. #endif
  164. #ifndef YS_ORACLE
  165. #include <ys.h>
  166. #endif
  167.  
  168. EXTC_START
  169.  
  170. /* PUBLIC TYPES AND CONSTANTS */
  171.  
  172. typedef struct ysspTree ysspTree; 
  173. typedef struct ysspNode ysspNode;
  174.  
  175. /*
  176.  * Comparison function handed to either ysSpCreate or ysSpNewTree
  177.  * a and b are the values of the key_ysspNode fields of nodes, or
  178.  * the "key" argument given to a lookup or find function.
  179.  */
  180. typedef sword (*ysspCmpFunc)( CONST dvoid *a, CONST dvoid *b );
  181.  
  182. struct ysspTree
  183. {
  184.   ysspNode        *root_ysspTree;
  185.   ysspCmpFunc        cmp_ysspTree;
  186.   ysmff            delfunc_ysspTree;
  187. };
  188.  
  189. /* This node is assumed to be embedded in the data object; key must be
  190.    set by hand before enqueueing with ysspEnq. */
  191.  
  192. struct ysspNode
  193. {
  194.   ysspNode *left_ysspNode;
  195.   ysspNode *right_ysspNode;
  196.   ysspNode *up_ysspNode;
  197.   dvoid        *key_ysspNode;
  198. };
  199.  
  200. /*
  201.  * ysSpCreate - create a splay tree
  202.  *
  203.  * DESCRIPTION
  204.  * ysSpCreate() creates a splay tree.
  205.  *
  206.  * The cmpfunc is a function that compares two elements for order.
  207.  * No default is provided; you must supply one.
  208.  *
  209.  * The delfunc is a function that is used to free the elements still
  210.  * in the splay tree when ysSpDestroy() is called.  If no delfunc is
  211.  * needed, a null pointer may be passed.
  212.  */
  213. ysspTree *ysSpCreate( ysspCmpFunc cmpfunc, ysmff delfunc); 
  214.  
  215. /*
  216.  * ysSpDestroy - destroy a splay tree
  217.  *
  218.  * DESCRIPTION
  219.  * ysSpDestroy() destroys a splay tree previously created by ysSpCreate().
  220.  * For each node still in the splay tree, the delfunc passed to
  221.  * ysSpCreate() is invoked (unless it is null) against each value,
  222.  * and the node is also freed; finally the allocated tree is released.
  223.  *
  224.  * You probably don't want to call this on a tree started with
  225.  * ysspNewTree!
  226.  */
  227. void   ysSpDestroy(ysspTree *t);
  228.  
  229. /*
  230.  * ysSpIns - insert element into a splay tree
  231.  *
  232.  * DESCRIPTION
  233.  * ysSpIns() inserts an element into a splay tree.  key and keysz specify
  234.  * the key that will allow this element to located later.  val is the value
  235.  * of the element to insert.  Duplicates are not detected by this routine.
  236.  * ysSpFind() may be used first to decide whether there is a duplicate key
  237.  * in the table.
  238.  */
  239. void   ysSpIns(ysspTree *t, dvoid *key, size_t keysz, dvoid *val);
  240.  
  241. /*
  242.  * ysSpRem - remove element from a splay tree
  243.  *
  244.  * DESCRIPTION
  245.  * ysSpRem() removes an element from a splay tree.  key and keysz specify
  246.  * the key that is used to locate the element.  The element is removed from
  247.  * the splay tree and its value is returned.  If the element is not found,
  248.  * a null pointer is returned.
  249.  *
  250.  * keysz is ignored.
  251.  */
  252. dvoid *ysSpRem(ysspTree *t, dvoid *key, size_t keysz);
  253.  
  254. /*
  255.  * ysSpFind - find element in splay tree
  256.  *
  257.  * DESCRIPTION
  258.  * ysSpFind() finds an element in a splay tree.  key and keysz specify
  259.  * the key that is used to locate the element.  If the element is found,
  260.  * its value is returned.  Otherwise, a null pointer is returned.
  261.  *
  262.  * keysz is ignored.
  263.  */
  264. dvoid *ysSpFind(ysspTree *t, dvoid *key, size_t keysz);
  265.  
  266.  
  267. /* ---------------------------- ysspNewTree ---------------------------- */
  268. ysspTree   *ysspNewTree( ysspTree *t, ysspCmpFunc cmp );
  269. /*
  270.   NAME
  271.     ysspNewTree
  272.   DESCRIPTION
  273.     Initialize a tree, using the supplied function for ordering comparisons.
  274.   PARAMETERS
  275.     t        - pointer to tree to set up
  276.     cmp        - function to use for comparisons
  277.   RETURNS
  278.     pointer to the tree.
  279. */
  280.  
  281. /* ---------------------------- ysspLookup ---------------------------- */
  282. ysspNode   *ysspLookup( CONST dvoid *key, ysspTree *t );
  283. /*
  284.   NAME
  285.     ysspLookup
  286.   DESCRIPTION
  287.     Given a pointer to a key, do a lookup in the tree and return a
  288.     pointer to the located tree node, or NULL.
  289.   PARAMETERS
  290.     key        - pointer to a key value to locate.
  291.     t        - the tree to search
  292.   RETURNS
  293.     pointer to the ysspNode located, or NULL if not found.
  294. */
  295.  
  296. /* ---------------------------- ysspFirstLookup ---------------------------- */
  297. ysspNode   *ysspFirstLookup( CONST dvoid *key, ysspTree *t );
  298. /*
  299.   NAME
  300.     ysspFirstLookup
  301.   DESCRIPTION
  302.     Given a pointer to a key, do a lookup in the tree and return the
  303.     first node with the key.  Useful if duplicates are allowed. First
  304.     is splayed to the root, so subsequent lookups return the first.
  305.   PARAMETERS
  306.     key        - pointer to a key value to locate.
  307.     t        - the tree to search
  308.   RETURNS
  309.     pointer to the ysspNode located, or NULL if not found.
  310. */
  311.  
  312. /* ---------------------------- ysspPELookup ---------------------------- */
  313. ysspNode   *ysspPELookup( CONST dvoid *key, ysspTree *t );
  314. /*
  315.   NAME
  316.     ysspLookup
  317.   DESCRIPTION
  318.     Given a pointer to a key, do a lookup in the tree and return a
  319.     pointer to the matching node, or the one prior.  If no match and
  320.     none prior, return NULL.
  321.   PARAMETERS
  322.     key        - pointer to a key value to locate.
  323.     t        - the tree to search
  324.   RETURNS
  325.     pointer to the ysspNode located, or NULL if not found.
  326. */
  327.  
  328. /* ---------------------------- ysspNextLookup ---------------------------- */
  329. ysspNode   *ysspNextLookup( CONST dvoid *key, ysspTree *t );
  330. /*
  331.   NAME
  332.     ysspNextLookup
  333.   DESCRIPTION
  334.     Given a pointer to a key, do a lookup in the tree and return a
  335.     pointer to the next node that follows the key, even if the key
  336.     does not exist in the tree.  Returns NULL only if there are no
  337.     successors.
  338.   PARAMETERS
  339.     key        - pointer to a key value to locate.
  340.     t        - the tree to search
  341.   RETURNS
  342.     pointer to the ysspNode located, or NULL if not found.
  343. */
  344.  
  345. /* ---------------------------- ysspEnq ---------------------------- */
  346. ysspNode   *ysspEnq( ysspNode *node, ysspTree *t );
  347. /*
  348.   NAME
  349.     ysspEnq
  350.   DESCRIPTION
  351.     Insert a new node into the tree.   If nodes with the key already
  352.     exist the node may be inserted in any location with respect to
  353.     those nodes.
  354.   PARAMETERS
  355.     node    - node to insert, with key_mtNode pointing to the key
  356.           value.
  357.     t        - the tree to insert into.
  358.   RETURNS
  359.     pointer to the node.
  360. */
  361.  
  362.  
  363. /* ---------------------------- ysspEnqAfter ---------------------------- */
  364. ysspNode   *ysspEnqAfter( ysspNode *newnd, ysspNode *old, ysspTree *t );
  365. /*
  366.   NAME
  367.     ysspEnqAfter
  368.   DESCRIPTION
  369.     Insert a new node into the tree after the old node.  No checking
  370.     of key values is performed.
  371.   PARAMETERS
  372.     newnd - node to insert, with key_mtNode pointing to the key value.
  373.     old   - node to insert new after.
  374.     t      - the tree to insert into.
  375.   RETURNS
  376.     pointer to the node.
  377. */
  378.  
  379.  
  380. /* ---------------------------- ysspDeq ---------------------------- */
  381. ysspNode   *ysspDeq( ysspNode **np );
  382. /*
  383.   NAME
  384.     ysspDeq
  385.   DESCRIPTION
  386.     Return and remove (dequeue) the lowest node in a sub-tree,
  387.     identified by a pointer to the node pointer.
  388.     Repetitive dequeue operations without inserts are O(1).
  389.   PARAMETERS
  390.     np        -- pointer to a node pointer, for instance the
  391.            address of a tree root, eg: &t->root_ysspTree;  (IN/OUT)
  392.   RETURNS
  393.     pointer to the dequeued node, or NULL if the tree was empty.
  394. */
  395.  
  396.  
  397. /* ---------------------------- ysspDeqTree ---------------------------- */
  398. #define ysspDeqTree( t )    (ysspDeq( &(t)->root_ysspTree))
  399. /*
  400.   NAME
  401.     ysspDeqTree
  402.   DESCRIPTION
  403.     Dequeue the first node in a tree, removing it.  Successive
  404.     operations are O(1) becuase of tree reorganization.
  405.     
  406.   PARAMETERS
  407.     t        -- the tree whose head to remove (IN/OUT)
  408.   RETURNS
  409.     pointer to the removed node, or NULL if tree is empty.
  410. */
  411.  
  412.  
  413.  
  414. /* ---------------------------- ysspRemove ---------------------------- */
  415. void        ysspRemove( ysspNode *node, ysspTree *t );
  416. /*
  417.   NAME
  418.     ysspRemove
  419.   DESCRIPTION
  420.     Remove an arbitrary node from a tree.  Chaos will ensue if the
  421.     node is not in the tree.
  422.     
  423.   PARAMETERS
  424.     node    -- the node to remove.
  425.     t        -- the tree to remove it from.
  426.   RETURNS
  427.     none
  428. */
  429.  
  430.  
  431. /* ---------------------------- ysspSplay ---------------------------- */
  432. void        ysspSplay( ysspNode *n, ysspTree *t );
  433. /*
  434.   NAME
  435.     ysspSplay
  436.   DESCRIPTION
  437.     Rotate the node to the root of the tree, using the "splay"
  438.     algorithm.  This should rarely be called by clients.
  439.   PARAMETERS
  440.     n        -- the node to pull up.
  441.     t        -- the tree containing it.
  442.   RETURNS
  443.     none
  444. */
  445.  
  446.  
  447. /* ---------------------------- ysspFHead ---------------------------- */
  448. ysspNode   *ysspFHead( ysspTree *t );
  449. /*
  450.   NAME
  451.     ysspFHead
  452.   DESCRIPTION
  453.     Locate the lowest node in a tree, quickly without reorganizing.
  454.     This is suitable for starting quick ordered scans of the tree.
  455.   PARAMETERS
  456.     t        -- tree in question.
  457.   RETURNS
  458.     pointer to the lowest node, or NULL if the tree is empty.
  459. */
  460.  
  461.  
  462. /* ---------------------------- ysspFTail ---------------------------- */
  463. ysspNode   *ysspFTail( ysspTree *t );
  464. /*
  465.   NAME
  466.     ysspFTail
  467.   DESCRIPTION
  468.     Locate the highest node in a tree, quickly without reorganizing.
  469.     This is suitable for starting quick ordered scans of the tree.
  470.   PARAMETERS
  471.     t        -- tree in question.
  472.   RETURNS
  473.     pointer to the lowest node, or NULL if the tree is empty.
  474. */
  475.  
  476.  
  477. /* ---------------------------- ysspFNext ---------------------------- */
  478. ysspNode   *ysspFNext( ysspNode *n );
  479. /*
  480.   NAME
  481.     ysspFNext
  482.   DESCRIPTION
  483.     Return the next node in a tree, quickly without reorgainizing.
  484.     This is suitable for increment steps in a fast tree scan.
  485.   PARAMETERS
  486.     n        -- the node whose successor is to be found
  487.   RETURNS
  488.     pointer to the next node, or NULL if there is none.
  489. */
  490.  
  491. /* ---------------------------- ysspFPrev ---------------------------- */
  492. ysspNode   *ysspFPrev( ysspNode *n );
  493. /*
  494.   NAME
  495.     ysspFPrev
  496.   DESCRIPTION
  497.     Return the previous node in a tree, quickly without reorgainizing.
  498.     This is suitable for increment steps in a fast tree scan.
  499.   PARAMETERS
  500.     n        -- the node whose successor is to be found
  501.   RETURNS
  502.     pointer to the prev node, or NULL if there is none.
  503. */
  504.  
  505. EXTC_END
  506. #endif /* YSSP_ORACLE */
  507.  
  508.  
  509.