home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / db / esm-3.1 / esm-3 / usr / local / sm / src / client / version / destroyNode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-05-05  |  4.6 KB  |  179 lines
  1. /*
  2.  *   $RCSfile: destroyNode.c,v $  
  3.  *   $Revision: 1.1.1.1 $  
  4.  *   $Date: 1996/05/04 21:55:32 $      
  5.  */ 
  6. /**********************************************************************
  7. * EXODUS Database Toolkit Software
  8. * Copyright (c) 1991 Computer Sciences Department, University of
  9. *                    Wisconsin -- Madison
  10. * All Rights Reserved.
  11. *
  12. * Permission to use, copy, modify and distribute this software and its
  13. * documentation is hereby granted, provided that both the copyright
  14. * notice and this permission notice appear in all copies of the
  15. * software, derivative works or modified versions, and any portions
  16. * thereof, and that both notices appear in supporting documentation.
  17. *
  18. * THE COMPUTER SCIENCES DEPARTMENT OF THE UNIVERSITY OF WISCONSIN --
  19. * MADISON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION.  
  20. * THE DEPARTMENT DISCLAIMS ANY LIABILITY OF ANY KIND FOR ANY DAMAGES
  21. * WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  22. *
  23. * The EXODUS Project Group requests users of this software to return 
  24. * any improvements or extensions that they make to:
  25. *
  26. *   EXODUS Project Group 
  27. *     c/o David J. DeWitt and Michael J. Carey
  28. *   Computer Sciences Department
  29. *   University of Wisconsin -- Madison
  30. *   Madison, WI 53706
  31. *
  32. *     or exodus@cs.wisc.edu
  33. *
  34. * In addition, the EXODUS Project Group requests that users grant the 
  35. * Computer Sciences Department rights to redistribute these changes.
  36. **********************************************************************/
  37.  
  38. #include <stdio.h>
  39. #include "ess.h"
  40. #include "checking.h"
  41. #include "io.h"
  42. #include "object.h"
  43. #include "trace.h"
  44. #include "error.h"
  45. #include "list.h"
  46. #include "pool.h"
  47. #include "bf_external_group.h"
  48. #include "version_graph.h"
  49. #include "version_funcs.h"
  50. #include "sm_macro.h"
  51.  
  52. /*
  53.  * DestroyNode() records the fact that a version has been destroyed.
  54.  * This may involve leaving a tombstone in its place.
  55.  */
  56.  
  57.  int
  58. destroyNode(
  59.     VERSIONGRAPH     *graph,            /* graph containing node    */
  60.     VHGNODEID        nodeId,         /* node to destroy            */
  61.     BOOL            *graphEmpty     /* OUT: true if last node deleted */
  62. )
  63. {
  64.     VHGNODE*             node;
  65.     VHGNODE*             childNode;
  66.  
  67.     TRPRINT(TR_VERSION, TR_LEVEL_1, ("freezing node &d \n", nodeId) );
  68.  
  69.     CHECK_VERSIONGRAPH_MAGIC(graph);
  70.  
  71.     /*
  72.      *    So far the graph is not empty
  73.      */
  74.     *graphEmpty = FALSE;
  75.     
  76.     /*
  77.      *  Validate  nodeId
  78.      */
  79.     if (nodeId >= graph->nodeCount) {
  80.         SM_ERROR(TYPE_WARNING, esmINTERNAL);
  81.         return(esmFAILURE);
  82.     }
  83.  
  84.     /*
  85.      *  Get a pointer to the node
  86.      */
  87.     node = &graph->nodeArray[nodeId];
  88.  
  89.     /*
  90.      *  Do some defensive error checking.  
  91.      */
  92.     CHECK_VHGNODE_MAGIC(node);
  93.  
  94.     /*
  95.      *    The Algorithm:
  96.      *    1. If node has no children, remove it from the VHG and call
  97.      *       destroyNode on the parent(node) if the parent is a tombstone.
  98.      *    2. If node has 1 child, delete the node and put the child
  99.      *     in it's place.
  100.      *    3. if the node has > 1 children, make the node a tombstone
  101.      */
  102.  
  103.     /*
  104.      *    See if node has no children
  105.      */
  106.     if (VHGLIST_EMPTY(graph, &node->children)) {
  107.     
  108.         /*
  109.          *    See if graph will now be empty, if so return that fact.
  110.          */
  111.         if (nodeId == graph->root) {
  112.             *graphEmpty = TRUE;
  113.             return (esmNOERROR);
  114.         }
  115.  
  116.         /*
  117.          *    Remove the node, and put it on the free list
  118.          */
  119.         listVHGRemove(graph, &node->siblings);
  120.         listVHGEnq(graph, &graph->freeList, &node->siblings);
  121.  
  122.         /*
  123.          *     If the parent is a tombstone, call destroy node on it
  124.          */
  125.         if (graph->nodeArray[node->parentId].flags & V_tombstone) {
  126.             return(destroyNode(graph, node->parentId, graphEmpty));
  127.         }
  128.  
  129.     } else if ( VHGDEREF(graph, node->children.succ)->succ == 
  130.                 VHGOFFSET(graph, &node->children) ) {
  131.         /*
  132.          *    Node has only one child, so get it
  133.          */
  134.         childNode = listVHGDeq(graph, &node->children);
  135.         CHECK_VHGNODE_MAGIC(childNode);
  136.         SM_ASSERT(LEVEL_3, VHGLIST_EMPTY(graph, &node->children));
  137.  
  138.         /*
  139.          *    See if the node is the root node
  140.          */
  141.         if (node->parentId == VHGNULLNODE) {
  142.             
  143.             /*
  144.              *    Node is the root, so move the child into
  145.              *    the root position and place the node on the
  146.              *    free list.
  147.              */
  148.             SM_ASSERT(LEVEL_3, graph->root == nodeId);
  149.             graph->root = childNode->id;
  150.             childNode->parentId = VHGNULLNODE;
  151.             listVHGEnq(graph, &graph->freeList, &node->siblings);
  152.  
  153.         } else {
  154.  
  155.             /*
  156.              *    Node is not the root node.
  157.              *    Place the child node on the list of siblings of node
  158.              *    and update its parent id.
  159.              */
  160.             listVHGEnq(graph, &node->children, &childNode->siblings);
  161.             childNode->parentId = node->parentId;
  162.  
  163.             /*
  164.              *    Remove the orginal node, and put it on the free list
  165.              */
  166.             listVHGRemove(graph, &node->siblings);
  167.             listVHGEnq(graph, &graph->freeList, &node->siblings);
  168.         }
  169.  
  170.     } else {
  171.  
  172.         /*
  173.          *    Node has more than one child, so make it a tombstone
  174.          */
  175.         node->flags |= V_tombstone;
  176.     }
  177.     return(esmNOERROR);
  178. }
  179.