avl.h

/* 
 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/>.
*/

/* returns a pointer to the users shared memory or NULL if name
 * is not found. */
static inline
void *find_segment_name(const struct shm_arena *a,
            const char *name, size_t *user_size)
{
  struct arena_header *a_hdr;
  struct seg_header *seg;
  int map_num;
  offset_t offset;

  a_hdr = ((struct arena_header *)(a->mapping[0].start));
  map_num = a_hdr->alloc_mapnum;
  offset = a_hdr->alloc_offset;
  seg = get_seg_header(a, map_num, offset);

  while(seg)
    {
      char *seg_name;
      int cmp;
      seg_name = get_seg_name(seg);
      cmp = strcmp(name, seg_name);
      if(cmp < 0) /* smaller are to the left */
    seg = get_seg_header(a, seg->left_mapnum, seg->left_offset);
      else if(cmp > 0) /* larger to the right */
    seg = get_seg_header(a, seg->right_mapnum, seg->right_offset);
      else /* cmp == 0  We have a match! */
    {
      if(user_size)
        *user_size = seg->user_length;
      return  get_seg_ptr(seg);
    }
    }
  return NULL;
}

/* returns a pointer to the segment header. */
static inline
struct seg_header *find_segment(const struct shm_arena *a,
                const char *name, mapnum_t *mapnum)
{
  struct arena_header *a_hdr;
  struct seg_header *seg;
  int map_num;
  offset_t offset;

  ASSERT(mapnum);

  a_hdr = ((struct arena_header *)(a->mapping[0].start));
  map_num = a_hdr->alloc_mapnum;
  offset = a_hdr->alloc_offset;
  seg = get_seg_header(a, map_num, offset);

  while(seg)
    {
      char *seg_name;
      int cmp;
      seg_name = get_seg_name(seg);
      cmp = strcmp(name, seg_name);
      if(cmp < 0) /* smaller are to the left */
    seg = get_seg_header(a, map_num=seg->left_mapnum, seg->left_offset);
      else if(cmp > 0) /* larger to the right */
    seg = get_seg_header(a, map_num=seg->right_mapnum, seg->right_offset);
      else /* cmp == 0  We have a match! */
    {
      *mapnum = map_num;
      return seg;
    }
    }
  return NULL;
}

/* returns a pointer to the struct seg_header of the smallest free
 * segment that has a total size of at least size size.
 *
 * mapnum is a pointer to the mapnum, that is returned, which is the
 * mapnum associated with the seg_header that is returned.
 */
static inline
struct seg_header *find_free_segment(const struct shm_arena *a,
                     size_t size, mapnum_t *ret_mapnum)
{
  struct arena_header *a_hdr;
  struct seg_header *seg, *prev_seg = NULL;
  int prev_mapnum = -1, mapnum;

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

  ASSERT(a_hdr);

  mapnum = a_hdr->free_mapnum;
  seg = get_seg_header(a, mapnum, a_hdr->free_offset);

  while(seg)
    {
      size_t len;
      
      len = seg->length * CHUNK;

      if(len >= size) /* smaller are to the left */
    {
      prev_seg = seg;
      prev_mapnum = mapnum;

      mapnum = seg->left_mapnum;
      seg = get_seg_header(a, mapnum, seg->left_offset);
    }
      else /* if(len < size) *//* larger to the right */
    {
      mapnum = seg->right_mapnum;
      seg = get_seg_header(a, mapnum, seg->right_offset);
    }
    }


  if(!seg)
    {
      *ret_mapnum = prev_mapnum;
      return prev_seg;
    }
  else
    {
      *ret_mapnum = mapnum;
      return seg;
    }
}

static inline int
difference(const struct shm_arena *a, struct seg_header *p_hdr)
/* returns the difference between the height of the left and right
 * child nodes of p_hdr. */
{
  height_t left_ht, right_ht;
  struct seg_header *seg;

  if(!p_hdr) return 0;

  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;

  return (left_ht - right_ht);
}

/* This is FOR TESTING/DEBUGING */
extern
struct seg_header
*_shm_check_free_segment(const struct shm_arena *a,
            mapnum_t mapnum, offset_t offset);

typedef int (*compare_func_t)(const struct seg_header *, mapnum_t, offset_t,
                   const struct seg_header *, mapnum_t, offset_t);

extern
int _shm_compare_free(const struct seg_header *hdr1, mapnum_t mapnum1, offset_t top1,
         const struct seg_header *hdr0, mapnum_t mapnum0, offset_t top0);
extern
int _shm_compare_allocated(const struct seg_header *hdr1,
              mapnum_t mapnum1,
              offset_t top1,
              const struct seg_header *hdr0,
              mapnum_t mapnum0,
              offset_t top0);

extern
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);

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

static inline
void insert_free_segment(const struct shm_arena *a, struct seg_header *seg,
             mapnum_t mapnum)
{
  struct arena_header *a_hdr;

  ASSERT(a);
  ASSERT(seg);
  ASSERT(get_seg_footer(seg)->flags & IS_FREE);

  a_hdr = a->header;

  ASSERT(a_hdr);

  if(!(a_hdr->free_offset))
    {
      /* We've got no root node to put this segment node onto, so we
       * will make this seg be the top root node segment. */
      a_hdr->free_offset = get_offset(a, seg, mapnum);
      a_hdr->free_mapnum = mapnum;
      seg->height = 0;
      return;
    }

  _shm_insert_node(a, seg, mapnum,
          &a_hdr->free_mapnum, &a_hdr->free_offset,
          _shm_compare_free);
}

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

static inline
void insert_alloc_segment(const struct shm_arena *a, struct seg_header *seg,
              mapnum_t mapnum)
{
  struct arena_header *a_hdr;

  ASSERT(a);
  ASSERT(seg);
  ASSERT(!(get_seg_footer(seg)->flags & IS_FREE));

  a_hdr = a->header;

  ASSERT(a_hdr);

  if(!(a_hdr->alloc_offset))
    {
      /* We've got no root node to put this segment node onto, so we
       * will make this seg be the top root node segment. */
      a_hdr->alloc_offset = get_offset(a, seg, mapnum);
      a_hdr->alloc_mapnum = mapnum;
      seg->height = 0;
      return;
    }

  ASSERT(&a_hdr->alloc_mapnum);
  ASSERT(&a_hdr->alloc_offset);

  _shm_insert_node(a, seg, mapnum,
          &a_hdr->alloc_mapnum, &a_hdr->alloc_offset,
          _shm_compare_allocated);
}