view release on metacpan or  search on metacpan

avltree/avltree.c  view on Meta::CPAN

        up[top++] = heir;
        heir = heir->link[0];
      }

      /* Swap data */
      save = it->data;
      it->data = heir->data;
      heir->data = save;

      /* Unlink successor and fix parent */
      up[top - 1]->link[up[top - 1] == it] = heir->link[1];

      tree->rel ( heir->data );
      free ( heir );
    }

    /* Walk back up the search path */
    while ( --top >= 0 && !done ) {
      /* Update balance factors */
      up[top]->balance += upd[top] != 0 ? -1 : +1;

      /* Terminate or rebalance as necessary */
      if ( abs ( up[top]->balance ) == 1 )
        break;
      else if ( abs ( up[top]->balance ) > 1 ) {
        remove_balance ( up[top], upd[top], done );

        /* Fix parent */
        if ( top != 0 )
          up[top - 1]->link[upd[top - 1]] = up[top];
        else
          tree->root = up[0];
      }
    }

    --tree->size;
  }

  return 1;
}

size_t avltree_size ( avltree_t *tree )
{
  return tree->size;
}

avltrav_t *avltnew ( void )
{
  return malloc ( sizeof ( avltrav_t ) );
}

void avltdelete ( avltrav_t *trav )
{
  free ( trav );
}

/*
  First step in traversal,
  handles min and max
*/
static SV *start (pTHX_ avltrav_t *trav, avltree_t *tree, int dir )
{
  trav->tree = tree;
  trav->it = tree->root;
  trav->top = 0;

  /* Build a path to work with */
  if ( trav->it != NULL ) {
    while ( trav->it->link[dir] != NULL ) {
      trav->path[trav->top++] = trav->it;
      trav->it = trav->it->link[dir];
    }
  }

  return trav->it == NULL ? &PL_sv_undef : trav->it->data;
}

/*
  Subsequent traversal steps,
  handles ascending and descending
*/
static SV *move (pTHX_ avltrav_t *trav, int dir )
{
  if ( trav->it->link[dir] != NULL ) {
    /* Continue down this branch */
    trav->path[trav->top++] = trav->it;
    trav->it = trav->it->link[dir];

    while ( trav->it->link[!dir] != NULL ) {
      trav->path[trav->top++] = trav->it;
      trav->it = trav->it->link[!dir];
    }
  }
  else {
    /* Move to the next branch */
    avlnode_t *last;

    do {
      if ( trav->top == 0 ) {
        trav->it = NULL;
        break;
      }

      last = trav->it;
      trav->it = trav->path[--trav->top];
    } while ( last == trav->it->link[dir] );
  }

  return trav->it == NULL ? &PL_sv_undef : trav->it->data;
}

SV *avltfirst (pTHX_ avltrav_t *trav, avltree_t *tree )
{
  return start (aTHX_ trav, tree, 0 ); /* Min value */
}

SV *avltlast (pTHX_ avltrav_t *trav, avltree_t *tree )
{
  return start (aTHX_ trav, tree, 1 ); /* Max value */
}

SV *avltnext (pTHX_ avltrav_t *trav )
{
  return move (aTHX_ trav, 1 ); /* Toward larger items */
}

SV *avltprev (pTHX_ avltrav_t *trav )
{
  return move (aTHX_ trav, 0 ); /* Toward smaller items */
}