Debian Codegraph @

xo/larray.cxx

raw
1 /* larray.cxx
2 $Id: larray.cxx,v 1.2 1997/10/18 04:57:33 elf Exp $
3
4 written by Marc Singer
5 9 October 1997
6
7 This file is part of the project XO. See the file README for
8 more information.
9
10 Copyright (C) 1997 Marc Singer
11
12 This program is free software; you can redistribute it and/or
13 modify it under the terms of the GNU General Public License as
14 published by the Free Software Foundation; either version 2 of the
15 License, or (at your option) any later version.
16
17 This program is distributed in the hope that it will be useful, but
18 WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 General Public License for more details.
21
22 You should have received a copy of the GNU General Public License
23 in a file called COPYING along with this program; if not, write to
24 the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA
25 02139, USA.
26
27 -- IMPLEMENTATION NOTE --
28 The m_cStep member is set to -1 if a request was made to allocate
29 the array larger than 64 AND we are not using GCC or Win32. Once
30 allocated, we do not permit reallocation.
31
32 */
33
34 /* ----- Includes */
35
36 #include "standard.h"
37 #include "larray.h"
38
39 #include <memory.h>
40 #include <assert.h>
41
42 #define max(a,b) (((a) >= (b)) ? (a) : (b))
43 #define min(a,b) (((a) <= (b)) ? (a) : (b))
44
45
46 /* ----- Class Globals/Statics */
47
48 /* ----- Methods */
49
50 /* LArray::add
51
52 adds an item to the end of the array.
53
54 */
55
56 bool LArray::add (const void* pv)
57 {
58 if (!alloc (m_cItems + 1))
59 return false;
60
61 memcpy (_at (m_cItems++), pv, m_cbEach);
62 return true;
63 } /* LArray::add */
64
65
66 /* LArray::add_new
67
68 adds an item to the end of the array and returns pointer to it.
69
70 */
71
72 void* LArray::add_new (void)
73 {
74 if (!alloc (m_cItems + 1))
75 return NULL;
76
77 return _at (m_cItems++);
78 } /* LArray::add_new */
79
80
81 /* LArray::alloc
82
83 tries to make space for cItems in the array. If there is already
84 enough space, nothing is done. The return value is true if there
85 is enough room for cItems.
86
87 */
88
89 bool LArray::alloc (long cItems)
90 {
91 assert (m_cbEach);
92
93 if (m_cStep < 0)
94 return false;
95
96 if (m_cStep == 0)
97 m_cStep = 1;
98 cItems = ((cItems + m_cStep - 1)/m_cStep)*m_cStep;
99 if (m_cItemMax >= cItems) {
100 assert (m_cItemMax == 0 || m_rgItems);
101 return true;
102 } /* if */
103
104 if (m_rgItems) {
105 void* pItems = realloc (m_rgItems, size_t (m_cbEach*cItems));
106 if (!pItems)
107 return false;
108 m_rgItems = pItems;
109 memset (_at (m_cItemMax), 0, size_t (m_cbEach*(cItems - m_cItemMax)));
110 } /* if */
111 else
112 m_rgItems = calloc ((size_t) cItems, m_cbEach);
113 if (m_rgItems)
114 m_cItemMax = cItems;
115 return m_rgItems != NULL;
116 } /* LArray::alloc */
117
118
119 /* LArray::alloc_to
120
121 allocates the array to include at least cItems and it also sets
122 the current number of filled items to cItems. The effect is the
123 same as adding cItems worth of empty cells, but this method is
124 faster.
125
126 */
127
128 bool LArray::alloc_to (long cItems)
129 {
130 if (!alloc (cItems) && m_cItemMax < cItems)
131 return false;
132 m_cItems = max (m_cItems, cItems);
133 return true;
134 } /* LArray::alloc_to */
135
136
137 /* LArray::at
138
139 routines to convert indicies and pointers into pointers and
140 indicies. Note that these are NOT inline so we can use dynamic
141 linking to change them.
142
143 */
144
145 void* LArray::at (long iItem) const
146 {
147 return _at (iItem);
148 } /* LArray::at */
149
150 long LArray::at (const void* pv) const
151 {
152 if (pv < m_rgItems || pv >= _at (m_cItems))
153 return -1;
154 return _at (pv);
155 } /* LArray::at */
156
157 /* LArray::attach
158
159 uses an external data pointer for the array storage. This
160 automatically sets the m_cbStep to -2 which indicates that the
161 array does not own the storage. LArray uses the cb parameter to
162 compute the number of available slots for the array.
163
164 */
165
166 void LArray::attach (void* pv, long cb)
167 {
168 release ();
169 m_rgItems = pv;
170 m_cStep = -2;
171 m_cItemMax = cb/m_cbEach;
172 } /* LArray::attach */
173
174 /* LArray::contains
175
176 returns true if the array contains en element matching the data
177 pointed to by *pv. Note that this is a SLOW operation requiring a
178 comparison with every element in the array.
179
180 */
181
182 bool LArray::contains (const void* pv)
183 {
184 for (void* pvElement = NULL; pvElement = enumerate (pvElement); )
185 if (memcmp (pvElement, pv, m_cbEach) == 0)
186 return true;
187 return false;
188 } /* LArray::contains */
189
190
191 /* LArray::enumerate and enumerate_reverse
192
193 enumerates a reference pointer to the items in the list. The
194 return value points to the next item in the array. To enumerate
195 all items in the array, pass NULL the first time and the last
196 returned pointer on successive calls. Enumerate is complete when
197 the function returns NULL.
198
199 The variant enumerate_reverse enumerates from the end of the list.
200 It is useful when deleting items from the array because the
201 enumeration pointer will be properly decremented on each iteration.
202
203 These functions enumerate pointers to the elements of the array.
204 This means that in order to enumerate the elements of an array of
205 character pointers, you need to construct the loop this way:
206
207 for (char** ppch = NULL; ppch = (char**) array.enumerate ((void*) ppch);) {
208 printf ("Got the string '%s'\n", *ppch);
209
210 */
211
212 void* LArray::enumerate (const void* pv)
213 {
214 if (!pv)
215 return m_cItems ? m_rgItems : NULL;
216
217 if (pv < m_rgItems) // Error case
218 return NULL;
219
220 long iItem = _at (pv);
221 if (iItem < 0 || iItem >= m_cItems)
222 return NULL;
223 ++iItem;
224 return (iItem < m_cItems) ? _at (iItem) : NULL;
225 } /* LArray::enumerate */
226
227 void* LArray::enumerate_reverse (const void* pv)
228 {
229 if (!pv)
230 return m_cItems ? _at (m_cItems - 1) : NULL;
231
232 if (pv < m_rgItems) // Error case
233 return NULL;
234
235 long iItem = _at (pv) - 1;
236 return (iItem >= 0 && iItem < m_cItems) ? _at (iItem) : NULL;
237 } /* LArray::enumerate_reverse */
238
239
240 /* LArray::get
241
242 gets an item in the array. m_cbEach bytes are copied from index
243 iItem. The return value is true if the item was copied.
244
245 */
246
247 bool LArray::get (long iItem, void* pv)
248 {
249 if (iItem < 0 || iItem >= m_cItems || !pv)
250 return false;
251 memcpy (pv, _at (iItem), m_cbEach);
252 return true;
253 } /* LArray::get */
254
255
256 /* LArray::init
257
258 initializes the array. cbEach is the size of each item and cStep
259 is the number of items to allocate when the array is full.
260
261 */
262
263 void LArray::init (int cbEach, int cStep)
264 {
265 release ();
266
267 m_cbEach = cbEach;
268 m_cStep = cStep;
269 } /* LArray::init */
270
271
272 /* LArray::insert
273
274 makes space before the indicated item for a new item in the array.
275 Note that this function has the side-effect of changing the
276 addresses of the items that follow and potentially of all items if
277 the array is realloc'd in a new memory location. The return value
278 is the pointer to the new, blank item or NULL if the memory cannot
279 be allocated for it.
280
281 */
282
283 void* LArray::insert (const void* pv)
284 {
285 assert (m_cbEach);
286
287 long iInsert = at (pv);
288 if (iInsert == -1)
289 return NULL;
290
291 if (!alloc_to (m_cItems + 1))
292 return NULL;
293 // (m_cItems has been incremented)
294
295 // -- Move data after iInsert to accomodate new entry
296 pv = _at (iInsert);
297 memmove (((char*) pv) + m_cbEach,
298 ((char*) pv),
299 size_t ((m_cItems - 1 - iInsert)*m_cbEach));
300 // ++m_cItems;
301
302 return (void*) pv;
303 } /* LArray::insert */
304
305
306 /* LArray::reference
307
308 returns a pointer to the specified item. If the index is out of
309 range, the return value is NULL.
310
311 */
312
313 void* LArray::reference (long iItem)
314 {
315 if (iItem < 0 || iItem >= m_cItems)
316 return NULL;
317 return _at (iItem);
318 } /* LArray::reference */
319
320
321 /* LArray::release
322
323 releases memory allocated for the array. Note that if the array
324 stores pointers, those pointers are not freed.
325
326 */
327
328 void LArray::release (void)
329 {
330 if (m_rgItems) {
331 if (m_cStep >= 0)
332 free (m_rgItems);
333 } /* if */
334
335 m_rgItems = NULL;
336 m_cItems = m_cItemMax = 0;
337 } /* LArray::release */
338
339
340 /* LArray::remove with variants
341
342 removes cItems from the list at offset iItem. The size of the
343 allocation does not change. The variant that takes a void*
344 pointer removes only that item from the list.
345
346 */
347
348 void LArray::remove (long iItem, long cItems)
349 {
350 iItem = min (m_cItems - 1, iItem);
351 if (iItem < 0)
352 return;
353 cItems = min (m_cItemMax - iItem, cItems);
354
355 memmove (_at (iItem), _at (iItem + cItems),
356 size_t ((m_cItems - iItem - cItems)*m_cbEach));
357 m_cItems -= cItems;
358 } /* LArray::remove */
359
360
361 void LArray::remove (const void* pv)
362 {
363 if (!m_cItems)
364 return;
365
366 long iItem = at (pv);
367 if (iItem == -1)
368 return;
369
370 long cItems = 1;
371
372 memmove (_at (iItem), _at (iItem + cItems),
373 size_t ((m_cItems - iItem - cItems)*m_cbEach));
374 m_cItems -= cItems;
375 } /* LArray::remove */
376
377
378 /* LArray::set
379
380 sets the data for an item in the array.
381
382 */
383
384 bool LArray::set (long iItem, const void* pv)
385 {
386 if (!alloc_to (iItem))
387 return false;
388
389 memcpy (_at (iItem), pv, m_cbEach);
390 return true;
391 } /* LArray::set */
392
393
394 /* LArray::truncate
395
396 truncates the array at cItems items. This is used to effectively
397 shrink array usage when the array might grow again.
398
399 */
400
401 void LArray::truncate (long cItems)
402 {
403 cItems = max (0, cItems);
404 m_cItems = min (m_cItems, cItems);
405 } /* LArray::truncate */