source: proiecte/swift/trunk/lib/hoard-371/src/heaplayers/nestedheap.h @ 176

Last change on this file since 176 was 176, checked in by (none), 14 years ago
  • imported repo from "guagal"
File size: 3.0 KB
Line 
1// -*- C++ -*-
2
3/*
4
5  Heap Layers: An Extensible Memory Allocation Infrastructure
6 
7  Copyright (C) 2000-2003 by Emery Berger
8  http://www.cs.umass.edu/~emery
9  emery@cs.umass.edu
10 
11  This program is free software; you can redistribute it and/or modify
12  it under the terms of the GNU General Public License as published by
13  the Free Software Foundation; either version 2 of the License, or
14  (at your option) any later version.
15 
16  This program is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  GNU General Public License for more details.
20 
21  You should have received a copy of the GNU General Public License
22  along with this program; if not, write to the Free Software
23  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
24
25*/
26
27#ifndef _NESTEDHEAP_H_
28#define _NESTEDHEAP_H_
29
30#include <assert.h>
31
32/**
33 * @class NestedHeap
34 * @brief Hierarchical heaps.
35 * @author Emery Berger <http://www.cs.umass.edu/~emery>
36 */
37
38namespace HL {
39
40template <class SuperHeap>
41class NestedHeap : public SuperHeap {
42public:
43
44  NestedHeap (void)
45    : parent (NULL),
46      child (NULL),
47      prev (NULL),
48      next (NULL)
49  {
50  }
51
52  ~NestedHeap (void)
53  {
54    clear();
55    if (parent != NULL) {
56      parent->removeChild (this);
57    }
58    removeSibling (this);
59  }
60
61  inline void clear (void) {
62
63    // Clear this heap.
64    SuperHeap::clear();
65
66#if 0
67    //
68    // Iterate through all children and delete them.
69    //
70
71    if (child != NULL) {
72      NestedHeap<SuperHeap> * nextChild = child->next;
73      while (child != NULL) {
74        NestedHeap<SuperHeap> * prevChild = child->prev;
75        delete child;
76        child = prevChild;
77      }
78      child = nextChild;
79      while (child != NULL) {
80        nextChild = child->next;
81        delete child;
82        child = nextChild;
83      }
84    }
85    assert (child == NULL);
86
87#else // clear all the children.
88
89    NestedHeap<SuperHeap> * ch = child;
90    while (ch != NULL) {
91      NestedHeap<SuperHeap> * nextChild = ch->next;
92      ch->clear();
93      ch = nextChild;
94    }
95#endif
96
97  }
98
99  void addChild (NestedHeap<SuperHeap> * ch)
100  {
101    if (child == NULL) {
102      child = ch;
103      child->prev = NULL;
104      child->next = NULL;
105    } else {
106      assert (child->prev == NULL);
107      assert (ch->next == NULL);
108      ch->prev = NULL;
109      ch->next = child;
110      child->prev = ch;
111      child = ch;
112    }
113    child->parent = this;
114  }
115
116private:
117
118  void removeChild (NestedHeap<SuperHeap> * ch)
119  {
120    assert (ch != NULL);
121    if (child == ch) {
122      if (ch->prev) {
123        child = ch->prev;
124      } else if (ch->next) {
125        child = ch->next;
126      } else {
127        child = NULL;
128      }
129    }
130    removeSibling (ch);
131  }
132
133  inline static void removeSibling (NestedHeap<SuperHeap> * sib)
134  {
135    if (sib->prev) {
136      sib->prev->next = sib->next;
137    }
138    if (sib->next) {
139      sib->next->prev = sib->prev;
140    }
141  }
142
143  NestedHeap<SuperHeap> * parent;
144  NestedHeap<SuperHeap> * child;
145  NestedHeap<SuperHeap> * prev;
146  NestedHeap<SuperHeap> * next;
147
148};
149
150}
151
152#endif
Note: See TracBrowser for help on using the repository browser.