source: golgotha/src/i4/memory/array.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: 4.5 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#ifndef I4_ARRAY_HH
10#define I4_ARRAY_HH
11
12// this template class manages an array of object
13// it automaically expands when add() is called and not enough elements are
14// available.  It also has an array reference operator allowing for transparent
15// range checking.
16
17#include "error/error.hh"
18#include "memory/malloc.hh"
19#include "search.hh"
20#include <stdlib.h>
21
22template <class T>
23class i4_array
24{
25protected:
26  T *entry;
27  int used,entries,grow;
28public:
29
30  int size() const { return used; }
31  int max_size() const { return entries; }
32  T& operator[](int i) const
33  {
34    I4_ASSERT(i>=0 && i<used, "i4_array::bad array reference");
35    return entry[i];
36  }   
37
38  T& operator()(int i) const
39  {
40    I4_ASSERT(i>=0 && i<used, "i4_array::bad array reference");
41    return entry[i];
42  }   
43
44  void resize(int _entries, int _grow = -1)
45  {
46    if (_grow>=0)
47      grow = _grow;
48
49    entries = _entries;
50    T* new_entry = (T*)i4_realloc(entry, sizeof(T)*entries, "grow array");
51    I4_ASSERT(new_entry, "i4_array::out of memory");
52    entry = new_entry;
53  }
54
55  i4_array(int entries, int grow = 0) : entries(entries), grow(grow), entry(0), used(0)
56  {
57    if (entries>0)
58    {
59      entry = (T*)i4_malloc(sizeof(T)*entries,"grow array");
60      I4_ASSERT(entry, "i4_array::can't allocate entries");
61    }
62    else
63      entry = 0;
64  }
65
66  void uninit()     // frees memory (use clear just to reset)
67  {
68    if (entry)
69      i4_free(entry);
70    entry=0;
71    used=0;
72    entries=0;
73  }
74 
75  ~i4_array()
76  {
77    uninit();
78  }
79
80  void grow_bigger()
81  {
82    if (grow)
83    {
84      entries += grow;
85
86      T* new_entry = (T*)i4_realloc(entry, sizeof(T)*entries, "grow array");
87       
88      I4_ASSERT(new_entry, "i4_array::out of memory");
89
90      entry = new_entry;
91    }
92    else
93      I4_ASSERT(0, "i4_array::out of entries");
94  }
95 
96  T *add_at(int ref)
97  {
98    if (used==entries)
99      grow_bigger();
100
101    for (int i=used; i>ref; i--)
102      entry[i] = entry[i-1];
103    used++;
104    return entry+ref;   
105  }
106
107  T *add()
108  {
109    if (used==entries)
110      grow_bigger();
111
112    T *ret=entry+used;
113    used++;
114    return ret;
115  }
116
117  T* add_many(int num)
118  {
119    while (used+num>entries)
120      grow_bigger();
121
122    T *ret=entry+used;
123    used+=num;
124    return ret;
125  }
126
127  int add_at(T item, int ref)
128  {
129    T *q=add_at(ref);
130    *q=item;
131    return ref;
132  }
133
134  int add(T item)
135  {
136    T *q=add();
137    *q=item;
138    return used-1;
139  }
140 
141  int add_array(const i4_array& tab,int ref = -1)
142  {
143    if (ref<0)
144      ref += used+1;
145
146    I4_ASSERT(ref>=0 && ref<=used,"i4_array::bad item referenced");
147
148    if (used+tab.size() >= entries)
149    {
150      if (grow)
151      {
152        if (used+tab.size() >= entries+grow)
153          entries = used+tab.size();
154        else
155          entries += grow;
156
157        T* new_entry = (T*)realloc(entry, sizeof(T)*entries);
158       
159        I4_ASSERT(new_entry, "i4_array::out of memory");
160
161        entry = new_entry;
162      }
163      else
164        I4_ASSERT(0, "i4_array::out of entries");
165    }
166
167    int i;
168
169    for (i=used-1; i>ref; i--)
170      entry[i+tab.size()] = entry[i];
171    for (i=0; i<tab.size(); i++)
172      entry[ref+i] = tab.entry[i];
173
174    used+=tab.size();
175
176    return ref;
177  }
178 
179  void remove(int ref)
180  {
181    I4_ASSERT(ref>=0 && ref<used, "i4_array::bad item deletion");
182
183    used--;
184    for (int i=ref; i<used; i++)
185      entry[i] = entry[i+1];
186  }
187 
188  void clear()
189  {
190    used = 0;
191  }
192
193  void sort(int (*compar)(const T *, const T *))
194  {
195    typedef int (*compare_type)(const void *x, const void *y);
196
197    qsort(entry, used, sizeof(T), (compare_type)compar);
198  }
199
200  int binary_search(const T *find, int (*compar)(const T* a, const T* b))
201  {
202    if (size()==0) return -1;
203
204    w32 res;
205
206    if (i4_base_bsearch(find, res, entry, sizeof(T), (w32)size(), (i4_bsearch_compare_function_type)compar))
207      return res;
208    else
209      return -1;                   
210  }
211
212};
213
214#endif
Note: See TracBrowser for help on using the repository browser.