← Back to branch summary

~ubuntu-branches/ubuntu/karmic/gnustep-base/karmic

« back to all changes in this revision

Viewing changes to Headers/Additions/GNUstepBase/GSIArray.h

  • Committer: Bazaar Package Importer
  • Author(s): Eric Heintzmann
  • Date: 2005-04-17 00:14:38 UTC
  • mfrom: (1.2.1 upstream) (2.1.2 hoary)
  • Revision ID: james.westby@ubuntu.com-20050417001438-enf0y07c9tku85z1
Tags: 1.10.3-1
New upstream release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
Headers/Additions/GNUstepBase/GSIArray.h
 
1
/* A fast (Inline) array implementation without objc method overhead.
 
2
 * Copyright (C) 1998,1999  Free Software Foundation, Inc.
 
3
 * 
 
4
 * Author:      Richard Frith-Macdonald <richard@brainstorm.co.uk>
 
5
 * Created:     Nov 1998
 
6
 * 
 
7
 * This file is part of the GNUstep Base Library.
 
8
 * 
 
9
 * This library is free software; you can redistribute it and/or
 
10
 * modify it under the terms of the GNU Library General Public
 
11
 * License as published by the Free Software Foundation; either
 
12
 * version 2 of the License, or (at your option) any later version.
 
13
 * 
 
14
 * This library is distributed in the hope that it will be useful,
 
15
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
17
 * Library General Public License for more details.
 
18
 * 
 
19
 * You should have received a copy of the GNU Library General Public
 
20
 * License along with this library; if not, write to the Free
 
21
 * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA. */
 
22
 
 
23
#include <Foundation/NSObject.h>
 
24
#include <Foundation/NSZone.h>
 
25
 
 
26
/* To easily un-inline functions for debugging */
 
27
#ifndef INLINE
 
28
#define INLINE inline
 
29
#endif
 
30
 
 
31
/* To turn assertions on, define GSI_ARRAY_CHECKS */
 
32
#ifdef  GSI_ARRAY_CHECKS
 
33
#define GSI_ARRAY_CHECK NSCAssert(array->count <= array->cap && array->old <= array->cap && array->old >= 1, NSInternalInconsistencyException)
 
34
#else
 
35
#define GSI_ARRAY_CHECK
 
36
#endif
 
37
 
 
38
/*
 
39
 This file should be INCLUDED in files wanting to use the GSIArray
 
40
 *      functions - these are all declared inline for maximum performance.
 
41
 *
 
42
 *      The file including this one may predefine some macros to alter
 
43
 *      the behaviour (default macros assume the items are NSObjects
 
44
 *      that are to be retained in the array) ...
 
45
 *
 
46
 *      GSI_ARRAY_RETAIN()
 
47
 *              Macro to retain an array item
 
48
 *
 
49
 *      GSI_ARRAY_RELEASE()
 
50
 *              Macro to release the item.
 
51
 *
 
52
 *      The next two values can be defined in order to let us optimise
 
53
 *      even further when either retain or release operations are not needed.
 
54
 *
 
55
 *      GSI_ARRAY_NO_RELEASE
 
56
 *              Defined if no release operation is needed for an item
 
57
 *      GSI_ARRAY_NO_RETAIN
 
58
 *              Defined if no retain operation is needed for a an item
 
59
 *               
 
60
 *      The value GSI_ARRAY_EXTRA may be defined as the type of an extra
 
61
 *      field produced in every array.  The name of this field is 'extra'.
 
62
 *
 
63
 *      The value GSI_ARRAY_TYPE may be defined as an additional type
 
64
 *      which must be valid as an array element.  Otherwise the types are
 
65
 *      controlled by the mechanism in GSUnion.h
 
66
 */
 
67
 
 
68
 
 
69
#ifdef  GSI_ARRAY_NO_RETAIN
 
70
#ifdef  GSI_ARRAY_RETAIN
 
71
#undef  GSI_ARRAY_RETAIN
 
72
#endif
 
73
#define GSI_ARRAY_RETAIN(A, X)  
 
74
#else
 
75
#ifndef GSI_ARRAY_RETAIN
 
76
#define GSI_ARRAY_RETAIN(A, X)  [(X).obj retain]
 
77
#endif
 
78
#endif
 
79
 
 
80
#ifdef  GSI_ARRAY_NO_RELEASE
 
81
#ifdef  GSI_ARRAY_RELEASE
 
82
#undef  GSI_ARRAY_RELEASE
 
83
#endif
 
84
#define GSI_ARRAY_RELEASE(A, X) 
 
85
#else
 
86
#ifndef GSI_ARRAY_RELEASE
 
87
#define GSI_ARRAY_RELEASE(A, X) [(X).obj release]
 
88
#endif
 
89
#endif
 
90
 
 
91
/*
 
92
 *      If there is no bitmask defined to supply the types that
 
93
 *      may be stored in the array, default to permitting all types.
 
94
 */
 
95
#ifndef GSI_ARRAY_TYPES
 
96
#define GSI_ARRAY_TYPES GSUNION_ALL
 
97
#endif
 
98
 
 
99
/*
 
100
 *      Set up the name of the union to store array elements.
 
101
 */
 
102
#ifdef  GSUNION
 
103
#undef  GSUNION
 
104
#endif
 
105
#define GSUNION GSIArrayItem
 
106
 
 
107
/*
 
108
 *      Set up the types that will be storable in the union.
 
109
 *      See 'GSUnion.h' for details.
 
110
 */
 
111
#ifdef  GSUNION_TYPES
 
112
#undef  GSUNION_TYPES
 
113
#endif
 
114
#define GSUNION_TYPES   GSI_ARRAY_TYPES
 
115
#ifdef  GSUNION_EXTRA
 
116
#undef  GSUNION_EXTRA
 
117
#endif
 
118
 
 
119
/*
 
120
 * Override extra type used in array value
 
121
 */
 
122
#ifdef  GSI_ARRAY_TYPE
 
123
#define GSUNION_EXTRA   GSI_ARRAY_TYPE
 
124
#endif
 
125
 
 
126
/*
 
127
 *      Generate the union typedef
 
128
 */
 
129
#include <GNUstepBase/GSUnion.h>
 
130
 
 
131
struct  _GSIArray {
 
132
  GSIArrayItem  *ptr;
 
133
  unsigned      count;
 
134
  unsigned      cap;
 
135
  unsigned      old;
 
136
  NSZone        *zone;
 
137
#ifdef  GSI_ARRAY_EXTRA
 
138
  GSI_ARRAY_EXTRA       extra;
 
139
#endif
 
140
};
 
141
typedef struct  _GSIArray       GSIArray_t;
 
142
typedef struct  _GSIArray       *GSIArray;
 
143
 
 
144
static INLINE unsigned
 
145
GSIArrayCapacity(GSIArray array)
 
146
{
 
147
  return array->cap;
 
148
}
 
149
 
 
150
static INLINE unsigned
 
151
GSIArrayCount(GSIArray array)
 
152
{
 
153
  return array->count;
 
154
}
 
155
 
 
156
static INLINE void
 
157
GSIArrayGrow(GSIArray array)
 
158
{
 
159
  unsigned int  next;
 
160
  unsigned int  size;
 
161
  GSIArrayItem  *tmp;
 
162
 
 
163
  if (array->old == 0)
 
164
    {
 
165
      /*
 
166
       * Statically initialised buffer ... copy into new heap buffer.
 
167
       */
 
168
      array->old = array->cap / 2;
 
169
      if (array->old < 1)
 
170
        {
 
171
          array->old = 1;
 
172
        }
 
173
      next = array->cap + array->old;
 
174
      size = next*sizeof(GSIArrayItem);
 
175
      tmp = NSZoneMalloc(array->zone, size);
 
176
      memcpy(tmp, array->ptr, array->count * sizeof(GSIArrayItem));
 
177
    }
 
178
  else
 
179
    {
 
180
      next = array->cap + array->old;
 
181
      size = next*sizeof(GSIArrayItem);
 
182
      tmp = NSZoneRealloc(array->zone, array->ptr, size);
 
183
    }
 
184
 
 
185
  if (tmp == 0)
 
186
    {
 
187
      [NSException raise: NSMallocException
 
188
                  format: @"failed to grow GSIArray"];
 
189
    }
 
190
  array->ptr = tmp;
 
191
  array->old = array->cap;
 
192
  array->cap = next;
 
193
}
 
194
 
 
195
static INLINE void
 
196
GSIArrayGrowTo(GSIArray array, unsigned next)
 
197
{
 
198
  unsigned int  size;
 
199
  GSIArrayItem  *tmp;
 
200
 
 
201
  if (next < array->count)
 
202
    {
 
203
      [NSException raise: NSInvalidArgumentException
 
204
                  format: @"attempt to shrink below count"];
 
205
    }
 
206
  size = next*sizeof(GSIArrayItem);
 
207
  tmp = NSZoneRealloc(array->zone, array->ptr, size);
 
208
 
 
209
  if (tmp == 0)
 
210
    {
 
211
      [NSException raise: NSMallocException
 
212
                  format: @"failed to grow GSIArray"];
 
213
    }
 
214
  array->ptr = tmp;
 
215
  array->old = array->cap;
 
216
  array->cap = next;
 
217
}
 
218
 
 
219
static INLINE void
 
220
GSIArrayInsertItem(GSIArray array, GSIArrayItem item, unsigned index)
 
221
{
 
222
  unsigned int  i;
 
223
 
 
224
  GSI_ARRAY_RETAIN(array, item);
 
225
  GSI_ARRAY_CHECK;
 
226
  if (array->count == array->cap)
 
227
    {
 
228
      GSIArrayGrow(array);
 
229
    }
 
230
  for (i = array->count++; i > index; i--)
 
231
    {
 
232
      array->ptr[i] = array->ptr[i-1];
 
233
    }
 
234
  array->ptr[i] = item;
 
235
  GSI_ARRAY_CHECK;
 
236
}
 
237
 
 
238
static INLINE void
 
239
GSIArrayInsertItemNoRetain(GSIArray array, GSIArrayItem item, unsigned index)
 
240
{
 
241
  unsigned int  i;
 
242
 
 
243
  GSI_ARRAY_CHECK;
 
244
  if (array->count == array->cap)
 
245
    {
 
246
      GSIArrayGrow(array);
 
247
    }
 
248
  for (i = array->count++; i > index; i--)
 
249
    {
 
250
      array->ptr[i] = array->ptr[i-1];
 
251
    }
 
252
  array->ptr[i] = item;
 
253
  GSI_ARRAY_CHECK;
 
254
}
 
255
 
 
256
static INLINE void
 
257
GSIArrayAddItem(GSIArray array, GSIArrayItem item)
 
258
{
 
259
  GSI_ARRAY_RETAIN(array, item);
 
260
  GSI_ARRAY_CHECK;
 
261
  if (array->count == array->cap)
 
262
    {
 
263
      GSIArrayGrow(array);
 
264
    }
 
265
  array->ptr[array->count++] = item;
 
266
  GSI_ARRAY_CHECK;
 
267
}
 
268
 
 
269
static INLINE void
 
270
GSIArrayAddItemNoRetain(GSIArray array, GSIArrayItem item)
 
271
{
 
272
  GSI_ARRAY_CHECK;
 
273
  if (array->count == array->cap)
 
274
    {
 
275
      GSIArrayGrow(array);
 
276
    }
 
277
  array->ptr[array->count++] = item;
 
278
  GSI_ARRAY_CHECK;
 
279
}
 
280
 
 
281
/*
 
282
 *      The comparator function takes two items as arguments, the first is the
 
283
 *      item to be added, the second is the item already in the array.
 
284
 *      The function should return NSOrderedAscending if the item to be
 
285
 *      added is 'less than' the item in the array, NSOrderedDescending
 
286
 *      if it is greater, and NSOrderedSame if it is equal.
 
287
 */
 
288
static INLINE unsigned
 
289
GSIArrayInsertionPosition(GSIArray array, GSIArrayItem item, 
 
290
        NSComparisonResult (*sorter)(GSIArrayItem, GSIArrayItem))
 
291
{
 
292
  unsigned int  upper = array->count;
 
293
  unsigned int  lower = 0;
 
294
  unsigned int  index;
 
295
 
 
296
  /*
 
297
   *    Binary search for an item equal to the one to be inserted.
 
298
   */
 
299
  for (index = upper/2; upper != lower; index = (upper+lower)/2)
 
300
    {
 
301
      NSComparisonResult comparison;
 
302
 
 
303
      comparison = (*sorter)(item, (array->ptr[index]));
 
304
      if (comparison == NSOrderedAscending)
 
305
        {
 
306
          upper = index;
 
307
        }
 
308
      else if (comparison == NSOrderedDescending)
 
309
        {
 
310
          lower = index + 1;
 
311
        }
 
312
      else
 
313
        {
 
314
          break;
 
315
        }
 
316
    }
 
317
  /*
 
318
   *    Now skip past any equal items so the insertion point is AFTER any
 
319
   *    items that are equal to the new one.
 
320
   */
 
321
  while (index < array->count
 
322
    && (*sorter)(item, (array->ptr[index])) != NSOrderedAscending)
 
323
    {
 
324
      index++;
 
325
    }
 
326
#ifdef  GSI_ARRAY_CHECKS
 
327
  NSCAssert(index <= array->count, NSInternalInconsistencyException);
 
328
#endif
 
329
  return index;
 
330
}
 
331
 
 
332
#ifdef  GSI_ARRAY_CHECKS
 
333
static INLINE void
 
334
GSIArrayCheckSort(GSIArray array, 
 
335
        NSComparisonResult (*sorter)(GSIArrayItem, GSIArrayItem))
 
336
{
 
337
  unsigned int  i;
 
338
 
 
339
  for (i = 1; i < array->count; i++)
 
340
    {
 
341
#ifdef  GSI_ARRAY_CHECKS
 
342
      NSCAssert(((*sorter)(array->ptr[i-1], array->ptr[i]) 
 
343
#endif
 
344
                 != NSOrderedDecending), NSInvalidArgumentException);
 
345
    }
 
346
}
 
347
#endif
 
348
 
 
349
static INLINE void
 
350
GSIArrayInsertSorted(GSIArray array, GSIArrayItem item, 
 
351
        NSComparisonResult (*sorter)(GSIArrayItem, GSIArrayItem))
 
352
{
 
353
  unsigned int  index;
 
354
 
 
355
  index = GSIArrayInsertionPosition(array, item, sorter);
 
356
  GSIArrayInsertItem(array, item, index);
 
357
#ifdef  GSI_ARRAY_CHECKS
 
358
  GSIArrayCheckSort(array, sorter);
 
359
#endif
 
360
}
 
361
 
 
362
static INLINE void
 
363
GSIArrayInsertSortedNoRetain(GSIArray array, GSIArrayItem item,
 
364
        NSComparisonResult (*sorter)(GSIArrayItem, GSIArrayItem))
 
365
{
 
366
  unsigned int  index;
 
367
 
 
368
  index = GSIArrayInsertionPosition(array, item, sorter);
 
369
  GSIArrayInsertItemNoRetain(array, item, index);
 
370
#ifdef  GSI_ARRAY_CHECKS
 
371
  GSIArrayCheckSort(array, sorter);
 
372
#endif
 
373
}
 
374
 
 
375
static INLINE void
 
376
GSIArrayRemoveItemAtIndex(GSIArray array, unsigned index)
 
377
{
 
378
  GSIArrayItem  tmp;
 
379
#ifdef  GSI_ARRAY_CHECKS
 
380
  NSCAssert(index < array->count, NSInvalidArgumentException);
 
381
#endif
 
382
  tmp = array->ptr[index];
 
383
  while (++index < array->count)
 
384
    array->ptr[index-1] = array->ptr[index];
 
385
  array->count--;
 
386
  GSI_ARRAY_RELEASE(array, tmp);
 
387
}
 
388
 
 
389
static INLINE void
 
390
GSIArrayRemoveLastItem(GSIArray array)
 
391
{
 
392
#ifdef  GSI_ARRAY_CHECKS
 
393
  NSCAssert(array->count, NSInvalidArgumentException);
 
394
#endif
 
395
  GSI_ARRAY_RELEASE(array, array->ptr[array->count-1]);
 
396
  array->count--;
 
397
}
 
398
 
 
399
static INLINE void
 
400
GSIArrayRemoveItemAtIndexNoRelease(GSIArray array, unsigned index)
 
401
{
 
402
  GSIArrayItem  tmp;
 
403
#ifdef  GSI_ARRAY_CHECKS
 
404
  NSCAssert(index < array->count, NSInvalidArgumentException);
 
405
#endif
 
406
  tmp = array->ptr[index];
 
407
  while (++index < array->count)
 
408
    array->ptr[index-1] = array->ptr[index];
 
409
  array->count--;
 
410
}
 
411
 
 
412
static INLINE void
 
413
GSIArraySetItemAtIndex(GSIArray array, GSIArrayItem item, unsigned index)
 
414
{
 
415
  GSIArrayItem  tmp;
 
416
#ifdef  GSI_ARRAY_CHECKS
 
417
  NSCAssert(index < array->count, NSInvalidArgumentException);
 
418
#endif
 
419
  tmp = array->ptr[index];
 
420
  GSI_ARRAY_RETAIN(array, item);
 
421
  array->ptr[index] = item;
 
422
  GSI_ARRAY_RELEASE(array, tmp);
 
423
}
 
424
 
 
425
/*
 
426
 * For direct access ... unsafe if you change the array in any way while
 
427
 * examining the contents of this buffer.
 
428
 */
 
429
static INLINE GSIArrayItem *
 
430
GSIArrayItems(GSIArray array)
 
431
{
 
432
  return array->ptr;
 
433
}
 
434
 
 
435
static INLINE GSIArrayItem
 
436
GSIArrayItemAtIndex(GSIArray array, unsigned index)
 
437
{
 
438
#ifdef  GSI_ARRAY_CHECKS
 
439
  NSCAssert(index < array->count, NSInvalidArgumentException);
 
440
#endif
 
441
  return array->ptr[index];
 
442
}
 
443
 
 
444
static INLINE GSIArrayItem
 
445
GSIArrayLastItem(GSIArray array)
 
446
{
 
447
#ifdef  GSI_ARRAY_CHECKS
 
448
  NSCAssert(array->count, NSInvalidArgumentException);
 
449
#endif
 
450
  return array->ptr[array->count-1];
 
451
}
 
452
 
 
453
static INLINE void
 
454
GSIArrayClear(GSIArray array)
 
455
{
 
456
  if (array->ptr)
 
457
    {
 
458
      /*
 
459
       * Only free memory if it was dynamically initialised (old > 0)
 
460
       */
 
461
      if (array->old > 0)
 
462
        {
 
463
          NSZoneFree(array->zone, (void*)array->ptr);
 
464
        }
 
465
      array->ptr = 0;
 
466
      array->cap = 0;
 
467
    }
 
468
}
 
469
 
 
470
static INLINE void
 
471
GSIArrayRemoveItemsFromIndex(GSIArray array, unsigned index)
 
472
{
 
473
  if (index < array->count)
 
474
    {
 
475
#ifndef GSI_ARRAY_NO_RELEASE
 
476
      while (array->count-- > index)
 
477
        {
 
478
          GSI_ARRAY_RELEASE(array, array->ptr[array->count]);
 
479
        }
 
480
#endif
 
481
      array->count = index;
 
482
    }
 
483
}
 
484
 
 
485
static INLINE void
 
486
GSIArrayRemoveAllItems(GSIArray array)
 
487
{
 
488
#ifndef GSI_ARRAY_NO_RELEASE
 
489
  while (array->count--)
 
490
    {
 
491
      GSI_ARRAY_RELEASE(array, array->ptr[array->count]);
 
492
    }
 
493
#endif
 
494
  array->count = 0;
 
495
}
 
496
 
 
497
static INLINE void
 
498
GSIArrayEmpty(GSIArray array)
 
499
{
 
500
  GSIArrayRemoveAllItems(array);
 
501
  GSIArrayClear(array);
 
502
}
 
503
 
 
504
static INLINE GSIArray
 
505
GSIArrayInitWithZoneAndCapacity(GSIArray array, NSZone *zone, size_t capacity)
 
506
{
 
507
  unsigned int  size;
 
508
 
 
509
  array->zone = zone;
 
510
  array->count = 0;
 
511
  if (capacity < 2)
 
512
    capacity = 2;
 
513
  array->cap = capacity;
 
514
  array->old = capacity/2;
 
515
  size = capacity*sizeof(GSIArrayItem);
 
516
  array->ptr = (GSIArrayItem*)NSZoneMalloc(zone, size);
 
517
  return array;
 
518
}
 
519
 
 
520
static INLINE GSIArray
 
521
GSIArrayInitWithZoneAndStaticCapacity(GSIArray array, NSZone *zone,
 
522
    size_t capacity, GSIArrayItem *buffer)
 
523
{
 
524
  array->zone = zone;
 
525
  array->count = 0;
 
526
  array->cap = capacity;
 
527
  array->old = 0;
 
528
  array->ptr = buffer;
 
529
  return array;
 
530
}
 
531
 
 
532
static INLINE GSIArray
 
533
GSIArrayCopyWithZone(GSIArray array, NSZone *zone)
 
534
{
 
535
  unsigned int i;
 
536
  GSIArray new;
 
537
  new = NSZoneMalloc(zone, sizeof(GSIArray_t));
 
538
  GSIArrayInitWithZoneAndCapacity(new, zone, array->count);
 
539
 
 
540
  for (i = 0; i < array->count; i++)
 
541
    {
 
542
      GSI_ARRAY_RETAIN(array, array->ptr[i]);
 
543
      new->ptr[new->count++] = array->ptr[i];
 
544
    }
 
545
  return new;
 
546
}