Answers/Solutions to Exercises in Chapter 9, Exercise 4

E4: Write a program that creates a linked tree in which each node has an arbitrary number of children. Then write a function that utilizes allocation from arena strategy that creates the tree in a serialized way. Relativize the serialized tree, copy the segments somewhere else in the memory, absolutize the tree and check that it is the same tree. You can modify the code presented in this chapter.

S4:  A sample program is below. It uses class ARENA from the book. There are some drawbacks for this approach. Since each class CHILD, NODE, and TREE have the arena as a static object, we can have all the trees just in that one arena. That may be a problem, for solution see the sample solution of Exercise 6.

#include <iostream.h>
#include <stdlib.h>

class ARENA
{
public:
  ARENA(int ss,int a) { 
    arena = 0; 
    last_segment = -1; 
    segment_size = ss;       //arena segment size
    align = a;               //memory alignment boundary
  }

  ~ARENA() {
    for(int i = 0; i <= last_segment; i++)
     delete[] arena[i];
    delete[] arena;
  }

  ARENA& operator= (const ARENA& ar) {
    int i, j;

    for(i = 0; i <= last_segment; i++)  // destroy old data
      delete[] arena[i];
    delete[] arena;
    arena = 0;

    segment_size = ar.segment_size;       // copy new data
    next_ind = ar.next_ind;
    last_segment = ar.last_segment;
    align = ar.align;

    arena = new char* [last_segment+1];
    for(i = 0; i <= last_segment; i++) {
      arena[i] = new char[segment_size];
      for(j = 0; j < segment_size; j++)
        arena[i][j] = ar.arena[i][j];
    }
    return *this;
  }

  void* Alloc(size_t s) {  //alloc. memory of size s from its segment
    char** a;              //obtains a new segment if need be
    int i;
    void* ret;

    if (arena == 0) {                       //alloc 1st segment
      arena = new char*[1];
      last_segment = 0;
      arena[0] = new char[segment_size];
      last_segment = 0;
      next_ind = 0;
    }else if (s > (size_t) segment_size-next_ind) { 
      last_segment++;
      a = new char*[last_segment+1];
      for(i = 0; i < last_segment; i++)
        a[i] = arena[i];
      delete[] arena;
      arena = a;
      arena[last_segment] = new char[segment_size];
      next_ind = 0;
    }
    ret = (void*) &arena[last_segment][next_ind];
    next_ind += s;
    // align next_ind for future use
    while(((long)&arena[last_segment][next_ind]%align) != 0)
      if (next_ind >= segment_size) break;

    // if next_ind runs to the end of the segment, no problem
    // on next Alloc() a new segment will be enforced
    return ret;
  }

void* Relativize(void* s) {     //relativizes address s with respect
    short segment, offset, *ip; //to the segment that s belongs to
    void* res;

    if (s == 0) return 0;

    for(segment = 0; segment <= last_segment; segment++) {
      if (s < arena[segment]) 
        continue;
      if (s >= arena[segment]+segment_size) 
        continue;
      // so we have the right segment
      offset = (short) ((long)s - (long)arena[segment]);
      segment++;        // shift segment by 1 so the beginning does
      ip = (short*)&res;  // not get relativized to 0
      *ip++ = segment;
      *ip = offset;
      return res;
    }
    return 0;
  }

void* Absolutize(void* s) {  //absolutize relative address s
    short *ip, segment, offset;
    void* r;

    if (s == 0) return 0;
    r = s;
    ip = (short*) &r;
    segment = *ip++;
    segment--;            // undo the shift
    offset = *ip;
    return (void*)&arena[segment][offset];
  }

protected:
  char** arena;
  short last_segment;
  short segment_size;
  short next_ind;
  short align;

};//end class ARENA


class TREE;
class NODE;
class CHILDREN;


class CHILD
{
  friend class NODE;
  friend class TREE;
  friend class CHILDREN;
public:
  CHILD(NODE* n) { node=n; next=0; }
  CHILD* Attach(NODE* n) { next = new CHILD(n); return next; }
protected:
  NODE* node;
  CHILD* next;
  static ARENA* arena;
  
  //the following methods are only for arena allocation
  static void* operator new(size_t s) { return arena->Alloc(s); }

  // we will deallocate the whole arena instead
  static void operator delete(void* s) { return; }

  static void SetArena(ARENA* a) { //set the arena for CHILD object
    static int first = 1;
    if (first) {
      arena = a;
      first = 0;
    }
  }

  // the implementation of these two functions must be postponed after
  // the definition of NODE
  void* Relativize(); 
  static CHILD* Absolutize(void* c);

};//end class CHILD
ARENA* CHILD::arena;



class NODE
{
  friend class CHILD;
  friend class TREE;
public:
  NODE(char v) { value=v; last=first=0;  }
  void Attach(NODE *n) { 
    if (first==0) 
      last=first=new CHILD(n);
    else
      last=last->Attach(n);
  }
protected:
  char value;
  CHILD* first;
  CHILD* last;
  static ARENA *arena;

  //the following methods are only for arena allocation
  static void* operator new(size_t s) { return arena->Alloc(s); }

  // we will deallocate the whole arena instead
  static void operator delete(void* s) { return; }

  static void SetArena(ARENA* a) { //set the arena for NODE object
    static int first = 1;
    if (first) {
      arena = a;
      first = 0;
      CHILD::SetArena(a);
    }
  }

  void Show() {
    CHILD* p;
    for(p=first; p!=0; p=p->next)
      p->node->Show();
    cout << ' ' << value;
  }

  void ShowAddresses() {
    CHILD* p;
    int i;
    cout << value << " [" << this << "]\n";
    for(i=1,p=first; p!=0; p=p->next,i++) {
      cout << p << " [child " << i << " of " << value << "]\n";
      p->node->ShowAddresses();
    }
  }

  void* Relativize() {
    if (first!=0) first=(CHILD*)first->Relativize();
    if (last!=0) last=(CHILD*)arena->Relativize(last);
    return arena->Relativize(this);
  }

  static NODE* Absolutize(void* n) {
    NODE* node;
    node=(NODE*)arena->Absolutize(n);
    if (node->first!=0) node->first=CHILD::Absolutize((void*)node->first);
    if (node->last !=0) node->last=(CHILD*)arena->Absolutize((void*)node->last);
    return node;
  } 
 
};//end class NODE
ARENA* NODE::arena = 0;


// the implementation of this function must have been postponed after 
// NODE has been defined
// function CHILD::Relativize ------------------------------------
void* CHILD::Relativize() {
  if (node!=0) node=(NODE*)node->Relativize();
  if (next!=0) next=(CHILD*) next->Relativize();
  return arena->Relativize(this);
}// end CHILD::Relativize


// the implementation of this static function must have been postponed 
// after NODE has been defined
// function CHILD::Absolutize ------------------------------------
CHILD* CHILD::Absolutize(void* c) {
  CHILD* child;
  child=(CHILD*)arena->Absolutize(c);
  if (child->node!=0) child->node=NODE::Absolutize((void*)child->node);
  if (child->next!=0) child->next=CHILD::Absolutize((void*)child->next);
  return child;
}// end CHILD::Absolutize





class TREE
{
public:
  TREE(ARENA *a) { SetArena(a); root = 0; }

  void Show() {
    if (root == 0) return;
    root->Show();
    cout << '\n' << flush;
  }

  void ShowAddresses() {
    if (root==0) return;
    root->ShowAddresses();
  }

  void SetRoot(char c) { root = new NODE(c); }
  void SetRoot(NODE* r) { root=r; }
  NODE* GetRoot() { return root; }
  void Attach(char c,char v) {
    if (root==0) return;
    // traverse the tree and find the node with value v
    if (root->value==v) {
      NODE* n = new NODE(c);
      root->Attach(n);
      return;
    }else
      Attach1(root,c,v);
  }

  static void SetArena(ARENA* a) {  //set arena for TREE object
    static int first = 1;
    if (first) {
      arena = a;
      NODE::SetArena(a);
      first = 0;
    }
  }

  void* Relativize() {
    if (root!=0) 
    root=(NODE*)root->Relativize();
  return root;
  }

  void Absolutize(void* r) {
    if (r == 0) return;
    root = NODE::Absolutize(r);
  }

protected:
  NODE* root;
  static ARENA* arena;

  void Attach1(NODE* p,char c,char v) {
    if (p==0) return;
    for(CHILD* q=p->first; q!=0; q=q->next) {
      if (q->node->value==v) {
        NODE* t=new NODE(c);
        q->node->Attach(t);
        return;
      }else
        Attach1(q->node,c,v);
    }
  }

};//end class TREE
ARENA* TREE::arena = 0;




// function main -----------------------------------------------
int main()
{

  ARENA arena(24,4);  // create arena

  TREE t(&arena);     // create empty tree with arena
  // create the body of the tree
  t.SetRoot('d');
  t.Attach('a','d');
  t.Attach('b','d');
  t.Attach('c','d');
  t.Attach('e','c');
  t.Attach('g','c');
  t.Attach('h','e');

  t.ShowAddresses();  // show the nodes and address of the tree
  cout << "\n\n" << flush;

  // now relativize the tree inside arena, remember the relative address of the root
  void *root;
  root=t.Relativize();

  ARENA barena(0,0);  // create different arena
  barena=arena;       // copy data from arena to barena

  TREE t1(&barena);   // create a tree with serialized body in barena
  t1.Absolutize(root);// absolutize the tree in barena
  t1.ShowAddresses(); // show the nodes and addresses of the tree

  return 0;
}//end main

Back to Answers/Solutions Index                          Back to Answers/Solutions for Chapter 9 Index