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