source: golgotha/src/i4/memory/lalloc.hh @ 80

Last change on this file since 80 was 80, checked in by Sam Hocevar, 12 years ago
  • Adding the Golgotha source code. Not sure what's going to be interesting in there, but since it's all public domain, there's certainly stuff to pick up.
File size: 5.6 KB
Line 
1/********************************************************************** <BR>
2  This file is part of Crack dot Com's free source code release of
3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for
4  information about compiling & licensing issues visit this URL</a>
5  <PRE> If that doesn't help, contact Jonathan Clark at
6  golgotha_source@usa.net (Subject should have "GOLG" in it)
7***********************************************************************/
8
9//{{{ Linear Allocator template
10//
11//  Implements a memory allocator that has constant time memory
12//  allocation and deallocation.  Heap can optionally grow by a fixed
13//  amount when no items are left.
14//
15//Usage:
16//
17//  Create allocator with:
18//   
19//    i4_linear_allocator_template<type> Name(intial_number_of_items,
20//                               growth_rate,
21//                               debugging string
22//                              );
23//   
24//  Get new item with:
25//   
26//    item = Name.alloc();
27//
28//  Free previously allocated item with:
29//
30//    Name.free(item);
31//
32//  When I4_DEBUG is defined, you can dump the contents of the
33//    allocator with:
34//
35//    Name.dump();
36//
37//Oliver Yu
38//
39//$Id: lalloc.hh,v 1.13 1998/06/22 17:44:45 jc Exp $
40//copyright 1996  Crack dot Com
41
42#ifndef LALLOC_HPP
43#define LALLOC_HPP
44
45#include "arch.hh"
46#include "memory/malloc.hh"
47#include "error/error.hh"
48#include "threads/threads.hh"
49#include <stdio.h>
50
51class i4_linear_allocator
52{
53protected:
54  i4_critical_section_class lock;
55
56  class PreBlock
57  {
58    typedef char *pointer;
59  public:
60    PreBlock *link;
61#ifdef I4_DEBUG
62    w32 items;
63#endif
64    void *GetPtr(int i, int size)
65    {
66      return (void*)(((pointer)this) + sizeof(PreBlock) + size*i );
67    }
68
69    void *init(w32 size, PreBlock *_link, w32 _items, void *_next)
70    {
71      void *ref;
72#ifdef I4_DEBUG
73      items = _items;
74#endif
75      link = _link;
76      for (w32 i=0; i<_items; i++)
77      {
78        ref = GetPtr(i, size);
79        *((void **)ref) = _next;
80        _next = ref;
81      }
82      return _next;
83    }
84
85#ifdef I4_DEBUG
86    void dump(w32 size)
87    {
88      printf("PreBlock: %p", GetPtr(0, size));
89      for (w32 i=0; i<items; i++)
90      {
91        if (i%4 == 0)
92          printf("\n%3lx: ",i);
93        printf("%8lx ", *((w32*)GetPtr(i, size)) );
94      }
95      printf("\n");
96    }
97
98    int valid_pointer(void *ptr, int size)
99    {
100      w32 offs = (w32)((pointer)ptr - (((pointer)this) + sizeof(PreBlock)));
101
102      return ( (offs/size < items) && (offs%size == 0) );
103    }
104#endif
105  };
106 
107  PreBlock *mem;
108  void *next;
109  w32 grow, size;
110  char *name;
111
112  //{{{ Debugging Variables
113#ifdef I4_DEBUG
114  w32 blocks, items;
115#endif
116public:
117  i4_linear_allocator(w32 size, w32 _number, w32 _grow, char *_name)
118    : mem(0), next(0),
119      name(_name),
120      grow(_grow),
121      size(size)
122  //
123  //  Create linear allocator
124  //
125  //Param:
126  //  w32 _number    number of items to start with
127  //  w32 _grow      number of items to grow when out of free items
128  //  char *_name    name of allocator for debugging
129  //
130  //{{{Notes:
131  //  if _grow is 0, allocator will display an error when out of items
132  //  if _number is 0, no space will be allocated until first item request
133  {
134    lock.lock();
135    if (_number>0) {
136      mem = (PreBlock*)i4_malloc( size*_number + sizeof(PreBlock), name );
137      // assert(mem);
138      next = mem->init(size, 0, _number, next);
139    }
140#ifdef I4_DEBUG
141    items = 0;
142    if (mem)
143      blocks = 1;
144#endif
145    lock.unlock();
146  }
147
148
149  ~i4_linear_allocator()
150  //
151  //  destroys blocks of memory used by allocator
152  {
153    PreBlock *p;
154
155    while (mem)
156    {
157      p = mem->link;
158      i4_free((void*)mem);
159      mem = p;
160    }
161  }
162 
163  void* alloc()
164  //
165  //  allocate an item void
166  {
167    lock.lock();
168    void* ret;
169
170    if (next)
171    {
172      ret = next;
173      next = *((void **)next);
174    }
175    else
176    {
177      if (grow==0)
178      {
179        // Out of items, and can't grow
180        printf("Allocator '%s' out of items\n",name);
181      }
182
183      PreBlock *newblock =
184        (PreBlock*) i4_malloc( size*grow + sizeof(PreBlock), name );
185      next = newblock->init(size, mem, grow, next);
186      mem = newblock;
187
188      ret = next;
189      next = *((void **)next);
190#ifdef I4_DEBUG
191      blocks++;
192#endif
193    }
194#ifdef I4_DEBUG
195    items++;
196#endif
197    lock.unlock();
198
199    return ret;
200  }
201 
202  void free(void *item)
203  //
204  //  free item T back into pool
205  //
206  {
207    lock.lock();
208
209#ifdef I4_DEBUG
210    PreBlock *p;
211
212    p = mem;
213    while ( p && !p->valid_pointer(item, size) )
214      p = p->link;
215    if (!p)
216    {
217      // invalid pointer! do error
218      printf("Bad free!\n");
219      return;
220    }
221#endif
222    *((void **)item) = next;
223    next = item;
224#ifdef I4_DEBUG
225    items--;
226#endif
227    lock.unlock();
228  }
229 
230#ifdef I4_DEBUG
231
232  //  debugging dump of contents of linear allocator
233  void dump()
234  {
235    PreBlock *p;
236
237    printf( "i4_linear_allocator '%s'\n"
238           "Items: %d  Blocks: %d\n"
239           "Next: %p\n",name, items, blocks, next);
240    p = mem;
241    while (p)
242    {
243      p->dump(size);
244      p = p->link;
245    }
246  }
247#endif
248};
249
250template <class T>
251class i4_linear_allocator_template : public i4_linear_allocator
252{
253public:
254  i4_linear_allocator_template(w32 _number, w32 _grow, char *_name)
255    : i4_linear_allocator(sizeof(T), _number, _grow, _name) {}
256
257  T* alloc() { return (T*)i4_linear_allocator::alloc(); }
258  void free(T *item) { i4_linear_allocator::free((void*)item); }
259};
260
261#endif
Note: See TracBrowser for help on using the repository browser.