avl.c

/* 
 shm-arena    shared memory arena
 Copyright (C) 2006-2008 Lance Arsenault (LGPL v3)


    This file is part of shm-arena.

    shm-arena is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as
    published by the Free Software Foundation; either version 3 of the
    License, or (at your option) any later version.

    shm-arena is distributed in the hope that it will be useful, but
    WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this program.  If not, see
    <http://www.gnu.org/licenses/>.
*/

#include "config.h"
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <pthread.h>
#include <stdint.h>

#include <pthread.h>
#include "spew.h"
#include "assert.h"
#include "debug_lock.h"
#include "shm_arena.h"
#include "arena.h"
#include "avl.h"


/***********************************************************************
  Common AVL tree functions.  Text book stuff except we can't use
  pointers in shared memory, so we have an address offset and mapping
  number (mapnum), instead of a single pointer.  See arena.h for more
  comments on the stucture of the shared memory.
***********************************************************************/

/* CAUTION: The AVL tree functions in this file do not merge free
 * adjacent nodes that is done outside this file, in get.c for
 * example. That makes this a little more straight forward, but it
 * could be a little more optimized.  The code in this file only knows
 * about the struct seg_header in the segments and don't not know
 * about any other data in the segments. */


static inline void
fix_height(const struct shm_arena *a, struct seg_header *p_hdr)
/* AVL function.  Fixes the height of a node after a node is inserted
 * to or detached from this parent node (p_hdr). I think that ternary
 * conditionals rock! */
{
  height_t left_ht, right_ht;
  struct seg_header *seg;

  seg = get_seg_header(a, p_hdr->left_mapnum, p_hdr->left_offset);
  left_ht = seg ? seg->height : -1;

  seg = get_seg_header(a, p_hdr->right_mapnum, p_hdr->right_offset);
  right_ht = seg ? seg->height : -1;

  p_hdr->height = (left_ht > right_ht) ? left_ht+1 : right_ht+1;
}

static inline void
rotate_left(const struct shm_arena *a, struct seg_header *x,
        mapnum_t x_mapnum, offset_t x_offset,
        mapnum_t *top_mapnum, offset_t *top_offset)
/*       x                   y
        / \                 / \
           y     ---->     x
          / \             / \
         z                   z
*/
{
  struct seg_header *y;
  mapnum_t y_mapnum;
  offset_t y_offset;

  ASSERT(x && x->right_mapnum > -1 && x->right_offset);

  /* save the mapnum and offset of y (right child of x) */
  y_mapnum = x->right_mapnum;
  y_offset = x->right_offset;
  
  /* get node struct pointer to y (right child of x) */
  y = get_seg_header(a, y_mapnum, y_offset);
  
  /* change the right child of x to z (left child of y) */
  x->right_mapnum = y->left_mapnum;
  x->right_offset = y->left_offset;

  /* make x a child of y */
  y->left_mapnum = x_mapnum;
  y->left_offset = x_offset;
  
  if(top_offset)
    {
      /* make y a child of what was x's parent */
      *top_mapnum = y_mapnum;
      *top_offset = y_offset;
    }
}

static inline void
rotate_right(const struct shm_arena *a, struct seg_header *x,
         mapnum_t x_mapnum, offset_t x_offset,
         mapnum_t *top_mapnum, offset_t *top_offset)
/*        x                  y
         / \                / \
        y        --->          x
       / \                    / \
          z                  z
*/
{
  struct seg_header *y;
  mapnum_t y_mapnum;
  offset_t y_offset;

  ASSERT(x && x->left_mapnum > -1 && x->left_offset);

  /* save the mapnum and offset of y (left child of x) */
  y_mapnum = x->left_mapnum;
  y_offset = x->left_offset;

  /* get node struct pointer to y (left child of x) */
  y = get_seg_header(a, y_mapnum, y_offset);

  /* change the right child of x to z (right child of y) */
  x->left_mapnum = y->right_mapnum;
  x->left_offset = y->right_offset;

  /* make x a child of y */
  y->right_mapnum = x_mapnum;
  y->right_offset = x_offset;

  if(top_offset)
    {
      /* make y a child of what was x's parent */
      *top_mapnum = y_mapnum;
      *top_offset = y_offset;
    }
}

static inline void
balance_right(const struct shm_arena *a, struct seg_header *x,
          mapnum_t x_mapnum, offset_t x_offset,
          mapnum_t *top_mapnum, offset_t *top_offset)
/* Restores balance at x when the right child of x is too high. */
{
  int right_difference;
  struct seg_header *y;

  ASSERT(x && x->right_mapnum > -1 && x->right_offset);

  y = get_seg_header(a, x->right_mapnum, x->right_offset);

  right_difference = difference(a, y);

  if(right_difference == 0)
    {
      /* Case 1a: both subtrees of right child of x have the same
       * height.

         Let h be a height of a node in the tree, given nodes x,y,z
         for the rest of the nodes we just denote the height. We
         rotate_left(about x):


                          x(h+2)                         y(h+2)
                           / \                            / \
                          /   \                          /   \
    balance off -->    (h-1)  y(h+1)     ----->       x(h+1) (h)
                               / \                      / \
                              /   \                    /   \
                            z(h)  (h)               (h-1)  z(h)


     So we see that x decreases height 1 and y increases height
     by 1.
      */
      rotate_left(a, x, x_mapnum, x_offset, top_mapnum, top_offset);
      x->height--;
      y->height++;
      return;
    }
  if(right_difference < 0) /* flip the < to > for balance_left() */
    {
      /* Case 1b: right subtree of right child of x is higher.

         Let h be a height of a node in the tree, given nodes x,y,z
         for the rest of the nodes we just denote the height.  We
         rotate_left(about x):


                      x(h+3)                         y(h+2)
                       / \                            / \
                      /   \                          /   \
  balance off -->   (h)  y(h+2)      ----->      x(h+1) (h+1)
                          / \                      / \
                         /   \                    /   \
                       z(h) (h+1)               (h)   z(h)


     So we see that x decreases height 2 and y height is
     unchanged.
      */
      rotate_left(a, x, x_mapnum, x_offset, top_mapnum, top_offset);
      x->height -= 2;
      return;
    }

  /* right_diffence > 0 */
  {
    /* Case 2: left subtree (z) of right child of x is higher.

       We rotate_right(about y) and than rotate_left(about x) like so:


                      x(h+3)                         x
                       / \                          / \
                      /   \                        /   \
                     /     \                      /     \
  balance off -->  (h)    y(h+2)                (h)      z
                           / \                          / \ 
                          /   \        ----->          /   \
                         /     \                      /     \
                      z(h+1)   yr(h)                 zl      y
                       / \                                  / \
                      /   \                                /   \
                     /     \                              /     \
                zl(h|h-1) zr(h-1|h)                      zr     yr


                      
                                      z(h+2)
                                      /   \
                                     /     \
                                    /       \
                                   /         \
              ----->           x(h+1)       y(h+1)
                                 / \         / \
                                /   \       /   \
                               /     \     /     \
                              /      zl   zr     yr
                            (h)  (h|h-1) (h-1|h) (h)


       After the two rotations we compute the new heights.  So x
       decrease height by 2, y decreases height by 1, and z increases
       height by 1.
     */
    struct seg_header *z;

    /*  z = x right left child */
    z = get_seg_header(a, y->left_mapnum, y->left_offset);

    ASSERT(z);

    rotate_right(a, y, x->right_mapnum, x->right_offset,
         &(x->right_mapnum), &(x->right_offset));
    rotate_left(a, x, x_mapnum, x_offset, top_mapnum, top_offset);
    x->height -= 2;
    y->height -= 1;
    z->height += 1;
  }
}

static inline void
balance_left(const struct shm_arena *a, struct seg_header *x,
         mapnum_t x_mapnum, offset_t x_offset,
         mapnum_t *top_mapnum, offset_t *top_offset)
/* Restores balance at x when the left child of x is too high.  We get
 * this function by changing right to left and left to right, and < to
 * > in balance_right() above. */
{
  int left_difference;
  struct seg_header *y;

  ASSERT(x && x->left_mapnum > -1 && x->left_offset);

  y = get_seg_header(a, x->left_mapnum, x->left_offset);

  left_difference = difference(a, y);

  if(left_difference == 0)
    {
      /* Case 1a: both subtrees of left child of x have the same
       * height. */
      rotate_right(a, x, x_mapnum, x_offset, top_mapnum, top_offset);
      x->height--;
      y->height++;
      return;
    }
  if(left_difference > 0)
    {
      /* Case 1b: left subtree of left child of x is higher. */
      rotate_right(a, x, x_mapnum, x_offset, top_mapnum, top_offset);
      x->height -= 2;
      return;
    }

  /* left_diffence < 0 */
  /* Case 2: right subtree of left child of x is higher. */
  {
    struct seg_header *xlr;

    /*  xlr = x left right */
    xlr = get_seg_header(a, y->right_mapnum, y->right_offset);

    ASSERT(xlr);

    rotate_left(a, y, x->left_mapnum, x->left_offset,
         &(x->left_mapnum), &(x->left_offset));
    rotate_right(a, x, x_mapnum, x_offset, top_mapnum, top_offset);
    x->height -= 2;
    y->height -= 1;
    xlr->height += 1;
  }
}

/* _shm_compare_free() is used to add a free AVL node
 *
 * return  1 if free segment 1 is after (to the right) the free segment 0
 * return -1 if free segment 1 is before (to the left) the free segment 0
 * return  0 if they are the same
 */
DLL_LOCAL
int _shm_compare_free(const struct seg_header *seg1,
              mapnum_t mapnum1, offset_t top1,
              const struct seg_header *seg0,
              mapnum_t mapnum0, offset_t top0)
{
  ASSERT(seg1);
  ASSERT(seg0);

  if(seg1->length > seg0->length)
    return 1;
  if(seg1->length < seg0->length)
    return -1;
  /* hdr1->length == hdr0->length */
  if(mapnum1 > mapnum0)
    return 1;
  if(mapnum1 < mapnum0)
    return -1;
  /* hdr1->length == hdr0->length && mapnum1 == mapnum0 */
  if(top1 > top0)
    return 1;
  if(top1 < top0)
    return -1;
  return 0; /* They are the same. */
}

/* We need the prototype of this function to be the same as
 * _shm_compare_free() so that we may have a common _shm_insert_node() and
 * detach_node() functions for free and allocated segments.  We have
 * one AVL tree for free shared memory segments and one AVL tree for
 * allocated shared memory segments, for a given arena file. */
DLL_LOCAL
int _shm_compare_allocated(const struct seg_header *seg1,
              mapnum_t mapnum1  __attribute__ ((unused)),
              offset_t top1 __attribute__ ((unused)),
              const struct seg_header *seg0,
              mapnum_t mapnum0 __attribute__ ((unused)),
              offset_t top0 __attribute__ ((unused)))
{
  int cmp;

  cmp = strcmp(get_seg_name(seg1), get_seg_name(seg0));

  return (cmp>0) ? 1 : ((cmp) ? -1 : 0);
  /*  1 means that seg1 should be to the right of seg0
   * -1 means that seg1 should be to the left of seg0
   *  0 means that seg1 has the same string as seg0 */
}

static
struct seg_header *detach_left_most(const struct shm_arena *a,
                    struct seg_header *seg,
                    mapnum_t seg_mapnum,
                    mapnum_t *parent_mapnum,
                    offset_t *parent_offset,
                    mapnum_t *return_mapnum /* The mapnum of the
                                  * left most find. */
                    )
/* detachs the left most child of seg and returns it.  Does remove the
 * right child of this left most node and attach it to the parent of
 * the left most node. */
{
  int cmp;
  struct seg_header *child, *ret;

  *return_mapnum = seg_mapnum;
  ret = seg;

  child = get_seg_header(a, seg->left_mapnum, seg->left_offset);

  if(child)
    {
      ret = detach_left_most(a, child, seg->left_mapnum, 
                 &seg->left_mapnum, &seg->left_offset,
                 return_mapnum);
    }
  else
    {
      /* seg is the left_most node */
      /* attach parent to right child of left_most node */
      *parent_mapnum = seg->right_mapnum;
      *parent_offset = seg->right_offset;

      /* detach right child */
      seg->right_mapnum = -1;
      seg->right_offset = 0;

      return ret;
    }


  /* now fix balance */

  fix_height(a, seg);

  cmp = difference(a, seg);

  if(cmp > 1)
    /* left is too high */
    balance_left(a, seg, *parent_mapnum, *parent_offset, 
         parent_mapnum, parent_offset);
  else if(cmp < -1)
    /* right is too high */
    balance_right(a, seg, *parent_mapnum, *parent_offset, 
          parent_mapnum, parent_offset);

  /* else *//* They are balanced already. */

  return ret;
}

static inline void
detach_from_parent(const struct shm_arena *a,
           struct seg_header *seg,
           mapnum_t *parent_mapnum,
           offset_t *parent_offset)
{
  ASSERT(seg);

  if(seg->left_offset && seg->right_offset)
    {
      int cmp;

      /* We must get tricky here since there are child
       * nodes to the left and right of seg. */
      struct seg_header *left_most_seg;
      mapnum_t left_most_mapnum;
      struct seg_header *r_seg, *l_seg;

      r_seg = get_seg_header(a, seg->right_mapnum, seg->right_offset);
      l_seg = get_seg_header(a, seg->left_mapnum, seg->left_offset);

      /* detach the left most segment from the right child of seg.
       * This will also keep the tree connected except for the node we
       * are detaching, left_most_seg. */
      left_most_seg =
    detach_left_most(a, r_seg, seg->right_mapnum,
             &seg->right_mapnum, &seg->right_offset,
             &left_most_mapnum);

      /* have left_most_seg replace seg */

      *parent_mapnum = left_most_mapnum;
      *parent_offset = get_offset(a, left_most_seg, left_most_mapnum);

      left_most_seg->left_mapnum = seg->left_mapnum;
      left_most_seg->left_offset = seg->left_offset;

      left_most_seg->right_mapnum = seg->right_mapnum;
      left_most_seg->right_offset = seg->right_offset;

      /* If left_most_seg == r_seg we must balance it after we balance
       * l_seg. */
      if(left_most_seg != r_seg)
    {
      /* now fix the balance what was the right child of seg */
      fix_height(a, r_seg);
      cmp = difference(a, r_seg);
      
      if(cmp > 1)
        /* left is too high */
        balance_left(a, r_seg,
             left_most_seg->right_mapnum, left_most_seg->right_offset, 
             &left_most_seg->right_mapnum, &left_most_seg->right_offset);
      else if(cmp < -1)
        /* right is too high */
        balance_right(a, r_seg,
              left_most_seg->right_mapnum, left_most_seg->right_offset, 
              &left_most_seg->right_mapnum, &left_most_seg->right_offset);
    }

      /* now fix the balance what was the left child of seg */

      fix_height(a, l_seg);
      cmp = difference(a, l_seg);

      if(cmp > 1)
    /* left is too high */
    balance_left(a, r_seg,
             left_most_seg->left_mapnum, left_most_seg->left_offset, 
             &left_most_seg->left_mapnum, &left_most_seg->left_offset);
      else if(cmp < -1)
    /* right is too high */
    balance_right(a, r_seg,
              left_most_seg->left_mapnum, left_most_seg->left_offset, 
              &left_most_seg->left_mapnum, &left_most_seg->left_offset);

      /* now fix the balance what was seg, but is now left_most_seg */

      fix_height(a, left_most_seg);
      cmp = difference(a, left_most_seg);

      if(cmp > 1)
    /* left is too high */
    balance_left(a, left_most_seg,
             *parent_mapnum, *parent_offset,
             parent_mapnum, parent_offset);
      else if(cmp < -1)
    /* right is too high */
    balance_right(a, left_most_seg,
              *parent_mapnum, *parent_offset,
              parent_mapnum, parent_offset);

    }
  else if(seg->left_offset)
    {
      /* there is no right child to seg */
      *parent_mapnum = seg->left_mapnum;
      *parent_offset = seg->left_offset;
      /* The parent height will be fixed later. */
    }
  else
    {
      /* there is no left child to seg */
      *parent_mapnum = seg->right_mapnum;
      *parent_offset = seg->right_offset;
      /* The parent height will be fixed later. */
    }
  /* no more children for seg */
  seg->left_mapnum = -1;
  seg->left_offset = 0;
  seg->right_mapnum = -1;
  seg->right_offset = 0;
}

/***********************************************************************
 *                           PARAMETERS
 *
 * a is the local arena object
 *
 * seg is the segment (node) we are putting in the tree.
 * 
 * seg_mapnum is the memory mapping that the segment seg is in.
 *
 * parent_mapnum is a pointer to the mapping number to the (segment)
 * root node of the sub-tree that we are currently traversing.
 *
 * parent_offset is a pointer to the offset to the (segment) root node
 * of the sub-tree that we are currently traversing.
 ***********************************************************************
 */

static
int detach_node(const struct shm_arena *a,
        struct seg_header *seg,
        mapnum_t seg_mapnum,
        mapnum_t *parent_mapnum,
        offset_t *parent_offset,
        compare_func_t compare_func)
/* return:
 *  0 if it will not be found.
 *  1 if it was just found
 * -1 if it was found in a past call.
 */
{
  int cmp;
  struct seg_header *parent;

  parent = get_seg_header(a, *parent_mapnum, *parent_offset);
  cmp = compare_func(seg, seg_mapnum, get_offset(a, seg, seg_mapnum),
             parent, *parent_mapnum, *parent_offset);

  if(cmp > 0)
    {
      /* seg may belong to the right child node of parent */

      if(parent->right_offset)
    {
      int ret;
      ret = detach_node(a, seg, seg_mapnum,
                &parent->right_mapnum,
                &parent->right_offset,
                compare_func);
      if(ret == 1)
        {
          /* it was found in this last call so we detach seg
           * from parent and then continue balancing. */
          detach_from_parent(a, seg,
                 &parent->right_mapnum,
                 &parent->right_offset);
        }
      else if(ret == 0)
        return 0; /* it was not found. */

      /* else *//* ret == -1 */
      /* it was found in a past call so we continue with the
       * balancing. */
    }
      else
    {
      SPEW(_INFO, "Segment node was not found");
      return 0;
    }
    }
  else if(cmp < 0)
    {
      /* seg may belong to the left child node of parent */

      if(parent->left_offset)
    {
      int ret;
      ret = detach_node(a, seg, seg_mapnum,
                &parent->left_mapnum,
                &parent->left_offset,
                compare_func);
      if(ret == 1)
        {
          /* it was found in this last call so we detach seg
           * from parent and then continue balancing. */
          detach_from_parent(a, seg,
                 &parent->left_mapnum,
                 &parent->left_offset);
        }
      else if(ret == 0)
        return 0; /* it was not found. */

      /* else *//* ret == -1 */
      /* it was found in a past call so we continue with the
       * balancing. */
    }
      else
    {
      SPEW(_INFO, "Segment node was not found");
      return 0;
    }
    }
  else /* cmp == 0 */
    {
      /* We found it. */
      ASSERT(seg == parent);
      return 1; /* just found it. */
    }

  fix_height(a, parent);

  cmp = difference(a, parent);

  if(cmp > 1)
    /* left is too high */
    balance_left(a, parent, *parent_mapnum, *parent_offset, 
         parent_mapnum, parent_offset);
  else if(cmp < -1)
    /* right is too high */
    balance_right(a, parent, *parent_mapnum, *parent_offset, 
          parent_mapnum, parent_offset);

  /* else *//* They are balanced already. */

  return -1;
}


DLL_LOCAL
void _shm_insert_node(const struct shm_arena *a,
         struct seg_header *seg,
         mapnum_t seg_mapnum,
         mapnum_t *parent_mapnum,
         offset_t *parent_offset,
         compare_func_t compare_func)
{
  int cmp;
  struct seg_header *parent;

  parent = get_seg_header(a, *parent_mapnum, *parent_offset);
  cmp = compare_func(seg, seg_mapnum, get_offset(a, seg, seg_mapnum),
             parent, *parent_mapnum, *parent_offset);

  ASSERT(cmp != 0); /* The seg should not be the same as a segment in
             * the tree already. */

  if(cmp > 0)
    {
      /* seg belongs to the right child node of parent */

      if(parent->right_offset)
    {
      _shm_insert_node(a, seg, seg_mapnum,
              &parent->right_mapnum,
              &parent->right_offset,
              compare_func);
    }
      else
    {
      /* seg will be the right child node. */
      parent->right_mapnum = seg_mapnum;
      parent->right_offset = get_offset(a, seg, seg_mapnum);
      seg->height = 0;
    }
    }
  else
    {
      /* seg belongs to the left child node of parent */

      if(parent->left_offset)
    {
      _shm_insert_node(a, seg, seg_mapnum,
              &parent->left_mapnum,
              &parent->left_offset,
              compare_func);
    }
      else
    {
      /* seg will be the left child node. */
      parent->left_mapnum = seg_mapnum;
      parent->left_offset = get_offset(a, seg, seg_mapnum);
      seg->height = 0;
    }
    }

  fix_height(a, parent);

  cmp = difference(a, parent);

  ASSERT(cmp <= 2 && cmp >= -2);

  if(cmp > 1)
    /* left is too high */
    balance_left(a, parent, *parent_mapnum, *parent_offset, 
         parent_mapnum, parent_offset);
  else if(cmp < -1)
    /* right is too high */
    balance_right(a, parent, *parent_mapnum, *parent_offset, 
          parent_mapnum, parent_offset);

  /* else *//* They are balanced already. */
}


DLL_LOCAL
int
_shm_detach_free_segment(const struct shm_arena *a,
             struct seg_header *seg,
             mapnum_t mapnum)
/* returns 0 on success, 1 if not found */
{
  struct arena_header *a_hdr;

  ASSERT(a);
  ASSERT(seg);

  a_hdr = a->header;

  ASSERT(a_hdr);

  if(a_hdr->free_offset == get_offset(a, seg, mapnum) &&
     a_hdr->free_mapnum == mapnum)
    {
      /* Found seg is the root node. */
      detach_from_parent(a, seg, &a_hdr->free_mapnum, &a_hdr->free_offset);

      /* Get the new root node and balance. */
      seg = get_seg_header(a, a_hdr->free_mapnum, a_hdr->free_offset);

      if(seg)
    {
      int cmp;

      /* balance it */
      cmp = difference(a, seg);

      if(cmp > 1)
        /* left is too high */
        balance_left(a, seg, a_hdr->free_mapnum, a_hdr->free_offset, 
             &a_hdr->free_mapnum, &a_hdr->free_offset);
      else if(cmp < -1)
        /* right is too high */
        balance_right(a, seg, a_hdr->free_mapnum, a_hdr->free_offset, 
              &a_hdr->free_mapnum, &a_hdr->free_offset);
    }


      return 0;
    }

  return (detach_node(a, seg, mapnum,
              &a_hdr->free_mapnum, &a_hdr->free_offset,
              _shm_compare_free))?0:1;
}

DLL_LOCAL
int
_shm_detach_alloc_segment(const struct shm_arena *a,
              struct seg_header *seg,
              mapnum_t mapnum)
/* returns 0 on success, 1 if not found */
{
  struct arena_header *a_hdr;

  ASSERT(a);
  ASSERT(seg);

  a_hdr = a->header;

  ASSERT(a_hdr);

  if(a_hdr->alloc_offset == get_offset(a, seg, mapnum) &&
     a_hdr->alloc_mapnum == mapnum)
    {
      /* Found seg is the root node. */
      detach_from_parent(a, seg, &a_hdr->alloc_mapnum, &a_hdr->alloc_offset);

      /* Get the new root node and balance. */
      seg = get_seg_header(a, a_hdr->alloc_mapnum, a_hdr->alloc_offset);

      if(seg)
    {
      int cmp;

      /* balance it */
      cmp = difference(a, seg);

      if(cmp > 1)
        /* left is too high */
        balance_left(a, seg, a_hdr->alloc_mapnum, a_hdr->alloc_offset, 
             &a_hdr->alloc_mapnum, &a_hdr->alloc_offset);
      else if(cmp < -1)
        /* right is too high */
        balance_right(a, seg, a_hdr->alloc_mapnum, a_hdr->alloc_offset, 
              &a_hdr->alloc_mapnum, &a_hdr->alloc_offset);
    }
      return 0;
    }

  return (detach_node(a, seg,  mapnum,
              &a_hdr->alloc_mapnum, &a_hdr->alloc_offset,
              _shm_compare_allocated))?0:1;
}


/* This is FOR TESTING/DEBUGING
 *
 * Check to see that a segment is in the free AVL tree.
 *
 * size is the length of the segment.
 * mapnum is the mapnum of the segment.
 * offset in CHUNKs to the segment from the top of the mapping.
 *
 * returns a pointer to the struct seg_header in the free AVL tree.
 */
DLL_LOCAL
struct seg_header *_shm_check_free_segment(const struct shm_arena *a,
                      mapnum_t mapnum, offset_t offset)
{
  struct arena_header *a_hdr;
  struct seg_header *seg, *p;
  mapnum_t p_mapnum;
  offset_t p_offset;
  int cmp;

  ASSERT(mapnum >= 0 && mapnum < a->num_mappings);
  ASSERT(offset);

  a_hdr = ((struct arena_header *)(a->mapping[0].start));

  ASSERT(a_hdr);

  seg = get_seg_header(a, mapnum, offset);

  p = get_seg_header(a, p_mapnum = a_hdr->free_mapnum,
             p_offset = a_hdr->free_offset);

  while(p_offset)
    {
      cmp = _shm_compare_free(seg, mapnum, offset, p, p_mapnum, p_offset);

      if(cmp > 0)
    /* seg may belong to the right child node of parent */
    p = get_seg_header(a, p_mapnum = p->right_mapnum,
               p_offset = p->right_offset);
      else if(cmp < 0)
    /* seg may belong to the left child node of parent */
    p = get_seg_header(a, p_mapnum = p->left_mapnum,
               p_offset = p->left_offset);
      else
    /* We found it. */
    return seg;
    }

  return NULL;
}