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

Last change on this file since 176 was 176, checked in by (none), 14 years ago
  • imported repo from "guagal"
File size: 8.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
28// An "Obstack".
29
30#ifndef _HLOBSTACK_H_
31#define _HLOBSTACK_H_
32
33
34#ifdef __cplusplus
35
36#include <assert.h>
37#include <new>
38
39/**
40 * @class ObstackHeap
41 * @brief Implements obstack functionality (as in the GNU obstack library).
42 */
43
44namespace HL {
45
46template <int ChunkSize, class SuperHeap>
47class ObstackHeap : public SuperHeap {
48public:
49
50  ObstackHeap (void)
51  {
52    // Get one chunk and set the current position marker.
53    currentChunk = makeChunk (NULL, ChunkSize);
54    currentBase = nextPos = (char *) (currentChunk + 1);
55    assert (isValid());
56  }
57
58  ~ObstackHeap (void) {
59    // Free every chunk.
60    assert (isValid());
61    ChunkHeader * ch = currentChunk;
62    while (ch != NULL) {
63      ChunkHeader * pch = ch->getPrevChunk();
64      // cout << "Freeing chunk " << ch << endl;
65      SuperHeap::free (ch);
66      ch = pch;
67    }
68  }
69
70  // "Grow" the current object.
71  // Returns a point in the object just before the current "grow".
72  inline void * grow (size_t sz) {
73    // If we've grown beyond the confines of this chunk,
74    // get a new one.
75    assert (isValid());
76    if ((int) ((char *) currentChunk->getLimit() - (char *) nextPos) < sz) {
77      ChunkHeader * newCurrent = copyToNew(sz);
78      if (newCurrent == NULL)
79        return NULL;
80#if 0
81      // Now delete the previous chunk if this was the only object in it.
82      if (deleteChunk != NULL) {
83        SuperHeap::free (deleteChunk);
84      }
85#endif
86      assert (isValid());
87    }
88    assert (((int) ((char *) currentChunk->getLimit() - (char *) nextPos) >= sz));
89    assert ((char *) (sz + nextPos) <= currentChunk->getLimit());
90    // Bump the pointer for the next object.
91    void * prevNextPos = nextPos;
92    nextPos += sz;
93    assert (isValid());
94    return prevNextPos;
95  }
96
97
98  inline void * malloc (size_t sz) {
99    assert (isValid());
100    if (currentChunk == NULL) {
101      return NULL;
102    }
103    //sz = align(sz > 0 ? sz : 1);
104    // If this object can't fit in the current chunk,
105    // get another one.
106    if ((int) ((char *) currentChunk->getLimit() - (char *) nextPos) < sz) {
107      // Allocate a chunk that's large enough to hold the requested size.
108      currentChunk = makeChunk (currentChunk, sz);
109      if (currentChunk == NULL) {
110        return NULL;
111      }
112      currentBase = nextPos = (char *) (currentChunk + 1);
113      assert (isValid());
114    }
115    assert (((int) ((char *) currentChunk->getLimit() - (char *) nextPos) >= sz));
116    assert ((char *) (sz + nextPos) <= currentChunk->getLimit());
117    // Bump the pointers forward.
118    currentBase = nextPos;
119    nextPos += sz;
120    void * ptr = currentBase;
121    finalize();
122    assert (isValid());
123    return (void *) ptr;
124  }
125
126  // Free everything allocated "after" ptr.
127  // NB: Freeing NULL safely empties the entire obstack.
128  inline void free (void * ptr) {
129    assert (isValid());
130    // Free every chunk until we find the one that this pointer is in.
131    // Then reset the current position to ptr.
132    while (currentChunk != NULL &&
133           (((char *) currentChunk > (char *) ptr) ||
134            ((char *) currentChunk->getLimit() < (char *) ptr))) {
135      ChunkHeader * pch = currentChunk;
136      currentChunk = currentChunk->getPrevChunk();
137      SuperHeap::free (pch);
138    }
139    if (currentChunk != NULL) {
140      currentBase = nextPos = (char *) ptr;
141      assert (isValid());
142    } else {
143      if (ptr != NULL) {
144        // Something bad has happened -- we tried to free an item that
145        // wasn't in any chunk.
146        abort();
147      } else {
148        // Get one chunk.
149        currentChunk = makeChunk (NULL, ChunkSize);
150        currentBase = nextPos = (char *) (currentChunk + 1);
151        assert (isValid());
152      }
153    }
154  }
155
156
157  inline void * getObjectBase (void) {
158    assert (isValid());
159    return currentBase;
160  }
161
162
163  inline void finalize (void) {
164    assert (isValid());
165    nextPos = (char *) align((int) nextPos);
166    currentBase = nextPos;
167    assert (isValid());
168  }
169
170
171private:
172
173
174  inline int objectSize (void) {
175    int diff = (int) (nextPos - currentBase);
176    assert (diff >= 0);
177    return diff;
178  }
179
180
181  int isValid (void) {
182    // Verify class invariants.
183#ifndef NDEBUG
184    bool c1 = (currentBase <= nextPos);
185    assert (c1);
186    bool c2 = (nextPos <= currentChunk->getLimit());
187    assert (c2);
188    bool c3 = ((char *) currentChunk <= currentChunk->getLimit());
189    assert (c3);
190    bool c4 = ((char *) currentChunk <= currentBase);
191    assert (c4);
192    bool c5 = (currentChunk != currentChunk->getPrevChunk());
193    assert (c5);
194    bool c6 = (objectSize() >= 0);
195    assert (c6);
196    return (c1 && c2 && c3 && c4 && c5 && c6);
197#else
198    return 1;
199#endif
200  }
201
202  // The header for every chunk.
203  class ChunkHeader {
204  public:
205    inline ChunkHeader (ChunkHeader * prev, size_t sz)
206      : _pastEnd ((char *) (this + 1) + sz),
207        _prevChunk (prev)
208    {}
209
210    // Return the end of the current chunk.
211    inline char * getLimit (void) { return _pastEnd; }
212
213    // Return the previous chunk.
214    inline ChunkHeader * getPrevChunk (void) { return _prevChunk; }
215
216  private:
217    // Just past the end of this chunk.
218    char * _pastEnd;
219
220    // Address of prior chunk.
221    ChunkHeader * _prevChunk;
222  };
223
224
225  inline static size_t align (int sz) {
226    return (sz + (sizeof(double) - 1)) & ~(sizeof(double) - 1);
227  }
228
229  // Make a new chunk of at least sz bytes.
230  inline ChunkHeader * makeChunk (ChunkHeader * ch, size_t sz) {
231    // Round up the allocation size to at least one chunk.
232    size_t allocSize
233      = align((sz > ChunkSize - sizeof(ChunkHeader)) ? sz : ChunkSize - sizeof(ChunkHeader));
234    // Make a new chunk.
235    ChunkHeader * newChunk
236      = new (SuperHeap::malloc (sizeof(ChunkHeader) + allocSize)) ChunkHeader (ch, allocSize);
237    return newChunk;
238  }
239
240
241  // Copy the current object to a new chunk.
242  // sz = the minimum amount of extra space we need.
243  inline ChunkHeader * copyToNew (size_t sz) {
244    size_t obj_size = objectSize();
245    size_t new_size = obj_size + sz + (obj_size >> 3) + 100;
246    //size_t new_size = 2 * (obj_size + sz);
247    ChunkHeader * newChunk;
248#if 0
249    // This variable will hold the chunk to be deleted (if any).
250    ChunkHeader * deleteChunk = NULL;
251    // If this object was the only one in the chunk,
252    // link back past this chunk.
253    if (currentBase == (char *) (currentChunk + 1)) {
254      newChunk = makeChunk (currentChunk->getPrevChunk(), new_size);
255      deleteChunk = currentChunk;
256    } else {
257      newChunk = makeChunk (currentChunk, new_size);
258    }
259#else
260    newChunk = makeChunk (currentChunk, new_size);
261#endif
262    if (newChunk == NULL) {
263      currentChunk = NULL;
264      return NULL;
265    }
266    // Copy the current object to the new chunk.
267    memcpy ((char *) (newChunk + 1), currentBase, obj_size);
268    currentChunk = newChunk;
269    currentBase = (char *) (currentChunk + 1);
270    nextPos = currentBase + obj_size;
271#if 0
272    if (deleteChunk != NULL) {
273      SuperHeap::free (deleteChunk);
274    }
275#endif
276    return currentChunk;
277  }
278
279
280  // Current position in the current chunk.
281  char * currentBase;
282
283  // Where to add the next character to the current object.
284  char * nextPos;
285
286  // My current chunk.
287  ChunkHeader * currentChunk;
288
289};
290
291#endif // __cplusplus
292
293// The C version of the above (just large enough to hold all of the data structures).
294struct obstack {
295  void * _dummy[3];
296};
297
298};
299
300#endif // _HLOBSTACK_H_
Note: See TracBrowser for help on using the repository browser.