| 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 */ |