root.c File Reference

Root Sets. More...

#include "internal.h"

Include dependency graph for root.c:

Go to the source code of this file.

Defines
#define	MAX_ROOTS   (sizeof(tm.roots)/sizeof(tm.roots[0]))
Functions
static int	_tm_root_add_1 (tm_root *a)
	Add a single root set.
static int	tm_root_subtract (tm_root *a, tm_root *b, tm_root *c)
	Subtract b from a, returning result in c.
static void	_tm_root_add (tm_root *a)
	Add a root set, while splitting it by anti-roots.
int	tm_root_add (const char *name, const void *l, const void *h)
	API: Add a root set.
void	tm_root_remove (const char *name, const void *l, const void *h)
int	tm_ptr_is_in_root_set (const void *ptr)

---

Detailed Description

Root Sets.

Definition in file root.c.

---

Define Documentation

#define MAX_ROOTS   (sizeof(tm.roots)/sizeof(tm.roots[0]))

Referenced by _tm_root_add_1().

---

Function Documentation

static void _tm_root_add

(

tm_root *

a

)

[static]

Add a root set, while splitting it by anti-roots.

Definition at line 172 of file root.c.

References _tm_root_add_1(), tm_data::aroots, tm_data::naroots, tm, and tm_root_subtract().

Referenced by tm_root_add(), and tm_root_remove().

{
  int i;
  tm_root c[2];

  /* Scan anti-roots for possible splitting */
  for ( i = 0; i < tm.naroots; ++ i ) {
    switch ( tm_root_subtract(a, &tm.aroots[i], c) ) {
    case -1: /* deleted */
      return;
      break;
      
    case 0: /* OK */
      break;
      
    case 1: /* clipped */
      *a = c[0];
      break;
      
    case 2: /* split */
      _tm_root_add(&c[0]);
      *a = c[1];
      break;
    }
  }

  _tm_root_add_1(a);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int _tm_root_add_1

(

tm_root *

a

)

[static]

Add a single root set.

Definition at line 12 of file root.c.

References tm_root::h, tm_root::l, MAX_ROOTS, tm_root::name, tm_data::nroots, tm_data::root_datai, tm_data::root_newi, tm_data::roots, tm, tm_assert_test, and tm_msg().

Referenced by _tm_root_add().

{
  int i;
#define MAX_ROOTS (sizeof(tm.roots)/sizeof(tm.roots[0]))

  if ( a->l >= a->h )
    return -1;

  /* Scan for empty slot. */
  for ( i = 0; i < MAX_ROOTS; ++ i ) {
    if ( tm.roots[i].name == 0 || tm.roots[i].l == tm.roots[i].h ) {
      break;
    }
  }

  if ( tm.nroots <= i ) {
    tm.nroots = i + 1;
  }

  tm_assert_test(i < MAX_ROOTS);
  tm_assert_test(i >= tm.root_datai);

  if ( tm.root_newi == -1 ) {
    tm.root_newi = i;
  }

  tm.roots[i] = *a;

  tm_msg("R a [%p,%p] %s %d\n", 
         tm.roots[i].l, 
         tm.roots[i].h,
         tm.roots[i].name,
         i);

  return i;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int tm_ptr_is_in_root_set

(

const void *

ptr

)

Definition at line 274 of file root.c.

References tm_root::h, tm_root::l, tm_data::nroots, tm_data::roots, and tm.

Referenced by tm_init().

{
  int i;

  for ( i = 0; i < tm.nroots; ++ i ) {
    if ( tm.roots[i].l <= ptr && ptr < tm.roots[i].h ) {
      return i + 1;
    }
  }

  return 0;
}

Here is the caller graph for this function:

static int tm_root_subtract	(	tm_root *	a,
		tm_root *	b,
		tm_root *	c
	)			[static]

Subtract b from a, returning result in c.

Return 0 if b is empty.

Case: b in a:

 a   L-------------------------------------------H
 b      L--------------------H
 c   0

Return -1.

Case: b out of a:

 a   L-------------H                        L--------------H
 b                   L--------------------H
 c   0

Return 0.

Case: b is in a:

 a            L------H
 b   H-----------------------H
 c1                  L-------H
 c2  L--------H

Save c1 and c2. Return 2.

Case: b.h in a:

 a          L---------------------H
 b    L--------------------H
 c                         L------H

Return 1.

Case: b.l in a:

 a   L---------------------H
 b             L--------------------H
 c   L---------H

Return 1.

Definition at line 56 of file root.c.

References tm_root::h, tm_root::l, and tm_abort().

Referenced by _tm_root_add(), and tm_root_remove().

{
  const void *tmp;

  if ( a->l > a->h ) {
    tmp = a->l; a->l = a->h; a->h = tmp;
  }
  if ( b->l > b->h ) {
    tmp = b->l; b->l = b->h; b->h = tmp;
  }
  /*! Return 0 if b is empty. */
  if ( b->l == b->h ) {
    return 0;
  }

  if ( (a->l == b->l) || (b->l <= a->l && a->h <= b->h) ) {
    /**
     * Case: b in a:
     *
     * <pre>
     *
     * a   L-------------------------------------------H
     * b      L--------------------H
     * c   0
     *
     * </pre>
     *
     * Return -1.
     */
    return -1; /* Delete flag */
  }
  if ( b->h <= a->l || b->l >= a->h ) {
    /**
     * Case: b out of a:
     *
     * <pre>
     *
     * a   L-------------H                        L--------------H
     * b                   L--------------------H
     * c   0
     *
     * </pre>
     *
     * Return 0.
     */
    /* *c = *a; */
    return 0;
  }
  if ( a->l < b->l && b->h < a->h ) {
    /**
     * Case: b is in a:
     *
     * <pre>
     *
     * a            L------H
     * b   H-----------------------H
     * c1                  L-------H
     * c2  L--------H
     *
     * </pre>
     *
     * Save c1 and c2.
     * Return 2.
     */
    c[0] = *a;
    c[0].l = b->h;
    c[1] = *a;
    c[1].h = b->l;
    return 2;
  }
  if ( a->l < b->h && b->h <= a->h ) {
    /**
     * Case: b.h in a:
     *
     * <pre>
     *
     * a          L---------------------H
     * b    L--------------------H
     * c                         L------H
     *
     * </pre>
     *
     * Return 1.
     */
    *c = *a;
    c->l = b->h;
    return 1;
  }
  if ( a->l < b->l && b->l <= a->h ) {
    /**
     * Case: b.l in a:
     *
     * <pre>
     *
     * a   L---------------------H
     * b             L--------------------H
     * c   L---------H
     *
     * </pre>
     *
     * Return 1.
     */
    *c = *a;
    c->h = b->l;
    return 1;
  }

  tm_abort();
  return -1;
}

Here is the call graph for this function:

Here is the caller graph for this function: