Answers/Solutions to Exercises in Chapter 9, Exercise 6

E6: Redo exercise 4 to obtain a compacted version of the tree.

S6: A sample program is below. Points to focus on: ARENA was changed a bit to provide some info like how many segments used, of what size, and total number of bytes allocated. Another change concerns the problem mention in Exercise 4 --- only trees allocated from the same arena were possible. So here we can have several arenas and each tree can be allocated in its own arena. For that end some changes must be made (like not having the arena as a static object of the classes CHILD, NODE, and TREE), and arenas are passed along, so every CHILD, or NODE, or TREE object knows its arena. Care must be taken that all elements of a tree are within the same arena. Now the compactification is achieved by creating the tree (as in Exercise 4), then finding out the total of bytes allocated, creating a new arena with the size of segment being the total size of bytes, and a copy of the tree is created in that new arena (simple statistics should show that the new arena has only 1 segment). Then the tree is relativized, and that provides the compacted version of the tree. We copy it as is to yet another arena, absolutize it there, and see if we got our tree back, as certainly we did.

#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];
  }

int TotalSize() {
  int res;
  if (last_segment < 0) return 0;
  res = last_segment*segment_size + next_ind;
  return res;
}
short NumberOfSegments() { return last_segment+1; }
short SegmentSize() { return segment_size; }

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,ARENA* a) { arena=a; node=n; next=0; }
  CHILD* Attach(NODE* n) { next = new(arena) CHILD(n,arena); return next; }
protected:
  NODE* node;
  CHILD* next;
  ARENA* arena;
  
  //the following methods are only for arena allocation
  void* operator new(size_t s,ARENA* a) { return a->Alloc(s); }

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

  

  // the implementation of these three functions must be postponed after
  // the definition of NODE
  void* Relativize(); 
  static CHILD* Absolutize(void* c,ARENA* a);
  CHILD* Copy(ARENA*); // make a copy ofyourself in a different arena
};//end class CHILD


class NODE
{
  friend class CHILD;
  friend class TREE;
public:
  NODE(char v,ARENA* a) { arena=a; value=v; first=0;  }
  void Attach(NODE *n) { 
    if (first==0) 
      first=new(arena) CHILD(n,arena);
    else{
    for(CHILD* p=first; p->next!=0; p=p->next);
    p->Attach(n);
    }
  }
protected:
  char value;
  CHILD* first;
  ARENA *arena;

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

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

  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();
    return arena->Relativize(this);
  }

  static NODE* Absolutize(void* n,ARENA* a) {
    NODE* node;
    node=(NODE*)a->Absolutize(n);
    if (node->first!=0) node->first=CHILD::Absolutize((void*)node->first,a);
    return node;
  } 

  NODE* Copy(ARENA* a) { // make a copy of yourself in a different arena
    NODE* n = new(a) NODE(value,a);
    if (first!=0) n->first=first->Copy(a);
    return n;
  }

};//end class NODE


// 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,ARENA *a) {
  CHILD* child;
  child=(CHILD*)a->Absolutize(c);
  if (child->node!=0) child->node=NODE::Absolutize((void*)child->node,a);
  if (child->next!=0) child->next=CHILD::Absolutize((void*)child->next,a);
  return child;
}// end CHILD::Absolutize


// the implementation of this function must have been postponed after 
// NODE has been defined
CHILD* CHILD::Copy(ARENA* a) { // make a copy of yourself in a different arena
    NODE* n = node->Copy(a);
    CHILD* c = new(a) CHILD(n,a);
    if (next!=0) c->next=next->Copy(a);
    return c;
}//end CHILD::Copy



class TREE
{
public:
  TREE(ARENA *a) { arena=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(arena) NODE(c,arena); }
  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(arena) NODE(c,arena);
      root->Attach(n);
      return;
    }else
      Attach1(root,c,v);
  }

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

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

  TREE* Copy(ARENA* a) { // make a copy of yourself in a different arena
    if (arena==0) return 0;  // fail, not ready for copying
    if (root==0) return 0;   // fail, not ready for copying
    NODE* root1 = root->Copy(a);
    TREE* t = new TREE(a);
    t->SetRoot(root1);
    return t;
  }

protected:
  NODE* root;
  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(arena) NODE(c,arena);
        q->node->Attach(t);
        return;
      }else
        Attach1(q->node,c,v);
    }
  }

};//end class TREE




// 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\narena has " << arena.NumberOfSegments() << " segments of size " 
       << arena.SegmentSize() << " with " << arena.TotalSize() 
       << " bytes used in total\n\n" << flush;

  // create a new arena that will accommodate a copy of the tree, but with just
  // one segment
  int total = arena.TotalSize();
  ARENA arena1(total,4);
  TREE* t1 = t.Copy(&arena1);

  if (t1!=0) t1->ShowAddresses();
  cout << "\n\narena has " << arena1.NumberOfSegments() << " segments of size " 
       << arena1.SegmentSize() << " with " << arena1.TotalSize() 
       << " bytes used in total\n\n" << flush;

  void* root = t1->Relativize();   // now tree is compacted in one segment

  // create a different arena
  ARENA arena2(0,0);
  arena2=arena1;      // copy the data to arena2 from arena1
  TREE t2(&arena2);   // create a tree with serialized body in arena2
  t2.Absolutize(root);// absolutize the tree in arena2
  t2.ShowAddresses(); // show the nodes and addresses of the tree

  t1->Absolutize(root);
  t1->ShowAddresses();
  
  return 0;
}//end main

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