pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/liblfds700/src/lfds700_btree_addonly_unbalanced/lfds700_btree_addonly_unbalanced_cleanup.c

   1 /***** includes *****/
   2 #include "lfds700_btree_addonly_unbalanced_internal.h"
   3
   4
   5
   6
   7
   8 /****************************************************************************/
   9 void lfds700_btree_au_cleanup( struct lfds700_btree_au_state *baus,
  10                                void (*element_cleanup_callback)(struct lfds700_btree_au_state *baus, struct lfds700_btree_au_element *baue) )
  11 {
  12   enum lfds700_btree_au_delete_action
  13     delete_action = LFDS700_BTREE_AU_DELETE_SELF; // TRD : to remove compiler warning
  14
  15   struct lfds700_btree_au_element
  16     *baue;
  17
  18   struct lfds700_btree_au_element
  19     *temp;
  20
  21   LFDS700_PAL_ASSERT( baus != NULL );
  22   // TRD : element_delete_function can be NULL
  23
  24   /* TRD : we're not lock-free now, so delete at will
  25            but be iterative, so can be used in kernels (where there's little stack)
  26            and be performant, since the user may be
  27            creating/destroying many of these trees
  28            also remember the user may be deallocating user data
  29            so we cannot visit an element twice
  30
  31            we start at the root and iterate till we go to NULL
  32            if the element has zero children, we delete it and move up to its parent
  33            if the element has one child, we delete it, move its child into its place, and continue from its child
  34            if the element has two children, we move left
  35
  36            the purpose of this is to minimize walking around the tree
  37            to prevent visiting an element twice
  38            while also minimizing code complexity
  39   */
  40
  41   if( element_cleanup_callback == NULL )
  42     return;
  43
  44   LFDS700_MISC_BARRIER_LOAD;
  45
  46   lfds700_btree_au_get_by_absolute_position( baus, &baue, LFDS700_BTREE_AU_ABSOLUTE_POSITION_ROOT );
  47
  48   while( baue != NULL )
  49   {
  50     if( baue->left == NULL and baue->right == NULL )
  51       delete_action = LFDS700_BTREE_AU_DELETE_SELF;
  52
  53     if( baue->left != NULL and baue->right == NULL )
  54       delete_action = LFDS700_BTREE_AU_DELETE_SELF_REPLACE_WITH_LEFT_CHILD;
  55
  56     if( baue->left == NULL and baue->right != NULL )
  57       delete_action = LFDS700_BTREE_AU_DELETE_SELF_REPLACE_WITH_RIGHT_CHILD;
  58
  59     if( baue->left != NULL and baue->right != NULL )
  60       delete_action = LFDS700_BTREE_AU_DELETE_MOVE_LEFT;
  61
  62     switch( delete_action )
  63     {
  64       case LFDS700_BTREE_AU_DELETE_SELF:
  65         // TRD : if we have a parent (we could be root) set his point to us to NULL
  66         if( baue->up != NULL )
  67         {
  68           if( baue->up->left == baue )
  69             baue->up->left = NULL;
  70           if( baue->up->right == baue )
  71             baue->up->right = NULL;
  72         }
  73
  74         temp = baue;
  75         lfds700_btree_au_get_by_relative_position( &baue, LFDS700_BTREE_AU_RELATIVE_POSITION_UP );
  76         element_cleanup_callback( baus, temp );
  77       break;
  78
  79       case LFDS700_BTREE_AU_DELETE_SELF_REPLACE_WITH_LEFT_CHILD:
  80         baue->left->up = baue->up;
  81         if( baue->up != NULL )
  82         {
  83           if( baue->up->left == baue )
  84             baue->up->left = baue->left;
  85           if( baue->up->right == baue )
  86             baue->up->right = baue->left;
  87         }
  88
  89         temp = baue;
  90         lfds700_btree_au_get_by_relative_position( &baue, LFDS700_BTREE_AU_RELATIVE_POSITION_LEFT );
  91         element_cleanup_callback( baus, temp );
  92       break;
  93
  94       case LFDS700_BTREE_AU_DELETE_SELF_REPLACE_WITH_RIGHT_CHILD:
  95         baue->right->up = baue->up;
  96         if( baue->up != NULL )
  97         {
  98           if( baue->up->left == baue )
  99             baue->up->left = baue->right;
 100           if( baue->up->right == baue )
 101             baue->up->right = baue->right;
 102         }
 103
 104         temp = baue;
 105         lfds700_btree_au_get_by_relative_position( &baue, LFDS700_BTREE_AU_RELATIVE_POSITION_RIGHT );
 106         element_cleanup_callback( baus, temp );
 107       break;
 108
 109       case LFDS700_BTREE_AU_DELETE_MOVE_LEFT:
 110         lfds700_btree_au_get_by_relative_position( &baue, LFDS700_BTREE_AU_RELATIVE_POSITION_LEFT );
 111       break;
 112     }
 113   }
 114
 115   return;
 116 }
 117