OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [vec.h] - Blame information for rev 826

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Vector API for GNU compiler.
2
   Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
3
   Free Software Foundation, Inc.
4
   Contributed by Nathan Sidwell <nathan@codesourcery.com>
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify it under
9
the terms of the GNU General Public License as published by the Free
10
Software Foundation; either version 3, or (at your option) any later
11
version.
12
 
13
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14
WARRANTY; without even the implied warranty of MERCHANTABILITY or
15
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16
for more details.
17
 
18
You should have received a copy of the GNU General Public License
19
along with GCC; see the file COPYING3.  If not see
20
<http://www.gnu.org/licenses/>.  */
21
 
22
#ifndef GCC_VEC_H
23
#define GCC_VEC_H
24
 
25
/* The macros here implement a set of templated vector types and
26
   associated interfaces.  These templates are implemented with
27
   macros, as we're not in C++ land.  The interface functions are
28
   typesafe and use static inline functions, sometimes backed by
29
   out-of-line generic functions.  The vectors are designed to
30
   interoperate with the GTY machinery.
31
 
32
   Because of the different behavior of structure objects, scalar
33
   objects and of pointers, there are three flavors, one for each of
34
   these variants.  Both the structure object and pointer variants
35
   pass pointers to objects around -- in the former case the pointers
36
   are stored into the vector and in the latter case the pointers are
37
   dereferenced and the objects copied into the vector.  The scalar
38
   object variant is suitable for int-like objects, and the vector
39
   elements are returned by value.
40
 
41
   There are both 'index' and 'iterate' accessors.  The iterator
42
   returns a boolean iteration condition and updates the iteration
43
   variable passed by reference.  Because the iterator will be
44
   inlined, the address-of can be optimized away.
45
 
46
   The vectors are implemented using the trailing array idiom, thus
47
   they are not resizeable without changing the address of the vector
48
   object itself.  This means you cannot have variables or fields of
49
   vector type -- always use a pointer to a vector.  The one exception
50
   is the final field of a structure, which could be a vector type.
51
   You will have to use the embedded_size & embedded_init calls to
52
   create such objects, and they will probably not be resizeable (so
53
   don't use the 'safe' allocation variants).  The trailing array
54
   idiom is used (rather than a pointer to an array of data), because,
55
   if we allow NULL to also represent an empty vector, empty vectors
56
   occupy minimal space in the structure containing them.
57
 
58
   Each operation that increases the number of active elements is
59
   available in 'quick' and 'safe' variants.  The former presumes that
60
   there is sufficient allocated space for the operation to succeed
61
   (it dies if there is not).  The latter will reallocate the
62
   vector, if needed.  Reallocation causes an exponential increase in
63
   vector size.  If you know you will be adding N elements, it would
64
   be more efficient to use the reserve operation before adding the
65
   elements with the 'quick' operation.  This will ensure there are at
66
   least as many elements as you ask for, it will exponentially
67
   increase if there are too few spare slots.  If you want reserve a
68
   specific number of slots, but do not want the exponential increase
69
   (for instance, you know this is the last allocation), use the
70
   reserve_exact operation.  You can also create a vector of a
71
   specific size from the get go.
72
 
73
   You should prefer the push and pop operations, as they append and
74
   remove from the end of the vector. If you need to remove several
75
   items in one go, use the truncate operation.  The insert and remove
76
   operations allow you to change elements in the middle of the
77
   vector.  There are two remove operations, one which preserves the
78
   element ordering 'ordered_remove', and one which does not
79
   'unordered_remove'.  The latter function copies the end element
80
   into the removed slot, rather than invoke a memmove operation.  The
81
   'lower_bound' function will determine where to place an item in the
82
   array using insert that will maintain sorted order.
83
 
84
   When a vector type is defined, first a non-memory managed version
85
   is created.  You can then define either or both garbage collected
86
   and heap allocated versions.  The allocation mechanism is specified
87
   when the type is defined, and is therefore part of the type.  If
88
   you need both gc'd and heap allocated versions, you still must have
89
   *exactly* one definition of the common non-memory managed base vector.
90
 
91
   If you need to directly manipulate a vector, then the 'address'
92
   accessor will return the address of the start of the vector.  Also
93
   the 'space' predicate will tell you whether there is spare capacity
94
   in the vector.  You will not normally need to use these two functions.
95
 
96
   Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro, to
97
   get the non-memory allocation version, and then a
98
   DEF_VEC_ALLOC_{O,P,I}(TYPEDEF,ALLOC) macro to get memory managed
99
   vectors.  Variables of vector type are declared using a
100
   VEC(TYPEDEF,ALLOC) macro.  The ALLOC argument specifies the
101
   allocation strategy, and can be either 'gc' or 'heap' for garbage
102
   collected and heap allocated respectively.  It can be 'none' to get
103
   a vector that must be explicitly allocated (for instance as a
104
   trailing array of another structure).  The characters O, P and I
105
   indicate whether TYPEDEF is a pointer (P), object (O) or integral
106
   (I) type.  Be careful to pick the correct one, as you'll get an
107
   awkward and inefficient API if you use the wrong one.  There is a
108
   check, which results in a compile-time warning, for the P and I
109
   versions, but there is no check for the O versions, as that is not
110
   possible in plain C.  Due to the way GTY works, you must annotate
111
   any structures you wish to insert or reference from a vector with a
112
   GTY(()) tag.  You need to do this even if you never declare the GC
113
   allocated variants.
114
 
115
   An example of their use would be,
116
 
117
   DEF_VEC_P(tree);   // non-managed tree vector.
118
   DEF_VEC_ALLOC_P(tree,gc);    // gc'd vector of tree pointers.  This must
119
                                // appear at file scope.
120
 
121
   struct my_struct {
122
     VEC(tree,gc) *v;      // A (pointer to) a vector of tree pointers.
123
   };
124
 
125
   struct my_struct *s;
126
 
127
   if (VEC_length(tree,s->v)) { we have some contents }
128
   VEC_safe_push(tree,gc,s->v,decl); // append some decl onto the end
129
   for (ix = 0; VEC_iterate(tree,s->v,ix,elt); ix++)
130
     { do something with elt }
131
 
132
*/
133
 
134
/* Macros to invoke API calls.  A single macro works for both pointer
135
   and object vectors, but the argument and return types might well be
136
   different.  In each macro, T is the typedef of the vector elements,
137
   and A is the allocation strategy.  The allocation strategy is only
138
   present when it is required.  Some of these macros pass the vector,
139
   V, by reference (by taking its address), this is noted in the
140
   descriptions.  */
141
 
142
/* Length of vector
143
   unsigned VEC_T_length(const VEC(T) *v);
144
 
145
   Return the number of active elements in V.  V can be NULL, in which
146
   case zero is returned.  */
147
 
148
#define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V)))
149
 
150
 
151
/* Check if vector is empty
152
   int VEC_T_empty(const VEC(T) *v);
153
 
154
   Return nonzero if V is an empty vector (or V is NULL), zero otherwise.  */
155
 
156
#define VEC_empty(T,V)  (VEC_length (T,V) == 0)
157
 
158
 
159
/* Get the final element of the vector.
160
   T VEC_T_last(VEC(T) *v); // Integer
161
   T VEC_T_last(VEC(T) *v); // Pointer
162
   T *VEC_T_last(VEC(T) *v); // Object
163
 
164
   Return the final element.  V must not be empty.  */
165
 
166
#define VEC_last(T,V)   (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO))
167
 
168
/* Index into vector
169
   T VEC_T_index(VEC(T) *v, unsigned ix); // Integer
170
   T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer
171
   T *VEC_T_index(VEC(T) *v, unsigned ix); // Object
172
 
173
   Return the IX'th element.  If IX must be in the domain of V.  */
174
 
175
#define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO))
176
 
177
/* Iterate over vector
178
   int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer
179
   int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer
180
   int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object
181
 
182
   Return iteration condition and update PTR to point to the IX'th
183
   element.  At the end of iteration, sets PTR to NULL.  Use this to
184
   iterate over the elements of a vector as follows,
185
 
186
     for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
187
       continue;  */
188
 
189
#define VEC_iterate(T,V,I,P)    (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P)))
190
 
191
/* Allocate new vector.
192
   VEC(T,A) *VEC_T_A_alloc(int reserve);
193
 
194
   Allocate a new vector with space for RESERVE objects.  If RESERVE
195
   is zero, NO vector is created.  */
196
 
197
#define VEC_alloc(T,A,N)        (VEC_OP(T,A,alloc)(N MEM_STAT_INFO))
198
 
199
/* Free a vector.
200
   void VEC_T_A_free(VEC(T,A) *&);
201
 
202
   Free a vector and set it to NULL.  */
203
 
204
#define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V))
205
 
206
/* Use these to determine the required size and initialization of a
207
   vector embedded within another structure (as the final member).
208
 
209
   size_t VEC_T_embedded_size(int reserve);
210
   void VEC_T_embedded_init(VEC(T) *v, int reserve);
211
 
212
   These allow the caller to perform the memory allocation.  */
213
 
214
#define VEC_embedded_size(T,N)   (VEC_OP(T,base,embedded_size)(N))
215
#define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N))
216
 
217
/* Copy a vector.
218
   VEC(T,A) *VEC_T_A_copy(VEC(T) *);
219
 
220
   Copy the live elements of a vector into a new vector.  The new and
221
   old vectors need not be allocated by the same mechanism.  */
222
 
223
#define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO))
224
 
225
/* Determine if a vector has additional capacity.
226
 
227
   int VEC_T_space (VEC(T) *v,int reserve)
228
 
229
   If V has space for RESERVE additional entries, return nonzero.  You
230
   usually only need to use this if you are doing your own vector
231
   reallocation, for instance on an embedded vector.  This returns
232
   nonzero in exactly the same circumstances that VEC_T_reserve
233
   will.  */
234
 
235
#define VEC_space(T,V,R) \
236
        (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO))
237
 
238
/* Reserve space.
239
   int VEC_T_A_reserve(VEC(T,A) *&v, int reserve);
240
 
241
   Ensure that V has at least RESERVE slots available.  This will
242
   create additional headroom.  Note this can cause V to be
243
   reallocated.  Returns nonzero iff reallocation actually
244
   occurred.  */
245
 
246
#define VEC_reserve(T,A,V,R)    \
247
        (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
248
 
249
/* Reserve space exactly.
250
   int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve);
251
 
252
   Ensure that V has at least RESERVE slots available.  This will not
253
   create additional headroom.  Note this can cause V to be
254
   reallocated.  Returns nonzero iff reallocation actually
255
   occurred.  */
256
 
257
#define VEC_reserve_exact(T,A,V,R)      \
258
        (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
259
 
260
/* Push object with no reallocation
261
   T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
262
   T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
263
   T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object
264
 
265
   Push a new element onto the end, returns a pointer to the slot
266
   filled in. For object vectors, the new value can be NULL, in which
267
   case NO initialization is performed.  There must
268
   be sufficient space in the vector.  */
269
 
270
#define VEC_quick_push(T,V,O)   \
271
        (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO))
272
 
273
/* Push object with reallocation
274
   T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer
275
   T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer
276
   T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object
277
 
278
   Push a new element onto the end, returns a pointer to the slot
279
   filled in. For object vectors, the new value can be NULL, in which
280
   case NO initialization is performed.  Reallocates V, if needed.  */
281
 
282
#define VEC_safe_push(T,A,V,O)          \
283
        (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
284
 
285
/* Pop element off end
286
   T VEC_T_pop (VEC(T) *v);             // Integer
287
   T VEC_T_pop (VEC(T) *v);             // Pointer
288
   void VEC_T_pop (VEC(T) *v);          // Object
289
 
290
   Pop the last element off the end. Returns the element popped, for
291
   pointer vectors.  */
292
 
293
#define VEC_pop(T,V)    (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO))
294
 
295
/* Truncate to specific length
296
   void VEC_T_truncate (VEC(T) *v, unsigned len);
297
 
298
   Set the length as specified.  The new length must be less than or
299
   equal to the current length.  This is an O(1) operation.  */
300
 
301
#define VEC_truncate(T,V,I)             \
302
        (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO))
303
 
304
/* Grow to a specific length.
305
   void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
306
 
307
   Grow the vector to a specific length.  The LEN must be as
308
   long or longer than the current length.  The new elements are
309
   uninitialized.  */
310
 
311
#define VEC_safe_grow(T,A,V,I)          \
312
        (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
313
 
314
/* Grow to a specific length.
315
   void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len);
316
 
317
   Grow the vector to a specific length.  The LEN must be as
318
   long or longer than the current length.  The new elements are
319
   initialized to zero.  */
320
 
321
#define VEC_safe_grow_cleared(T,A,V,I)          \
322
        (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
323
 
324
/* Replace element
325
   T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
326
   T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer
327
   T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val);  // Object
328
 
329
   Replace the IXth element of V with a new value, VAL.  For pointer
330
   vectors returns the original value. For object vectors returns a
331
   pointer to the new value.  For object vectors the new value can be
332
   NULL, in which case no overwriting of the slot is actually
333
   performed.  */
334
 
335
#define VEC_replace(T,V,I,O)            \
336
        (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
337
 
338
/* Insert object with no reallocation
339
   T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
340
   T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
341
   T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
342
 
343
   Insert an element, VAL, at the IXth position of V. Return a pointer
344
   to the slot created.  For vectors of object, the new value can be
345
   NULL, in which case no initialization of the inserted slot takes
346
   place. There must be sufficient space.  */
347
 
348
#define VEC_quick_insert(T,V,I,O)       \
349
        (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
350
 
351
/* Insert object with reallocation
352
   T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
353
   T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer
354
   T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object
355
 
356
   Insert an element, VAL, at the IXth position of V. Return a pointer
357
   to the slot created.  For vectors of object, the new value can be
358
   NULL, in which case no initialization of the inserted slot takes
359
   place. Reallocate V, if necessary.  */
360
 
361
#define VEC_safe_insert(T,A,V,I,O)      \
362
        (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
363
 
364
/* Remove element retaining order
365
   T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
366
   T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
367
   void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
368
 
369
   Remove an element from the IXth position of V. Ordering of
370
   remaining elements is preserved.  For pointer vectors returns the
371
   removed object.  This is an O(N) operation due to a memmove.  */
372
 
373
#define VEC_ordered_remove(T,V,I)       \
374
        (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
375
 
376
/* Remove element destroying order
377
   T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
378
   T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
379
   void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
380
 
381
   Remove an element from the IXth position of V. Ordering of
382
   remaining elements is destroyed.  For pointer vectors returns the
383
   removed object.  This is an O(1) operation.  */
384
 
385
#define VEC_unordered_remove(T,V,I)     \
386
        (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
387
 
388
/* Remove a block of elements
389
   void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
390
 
391
   Remove LEN elements starting at the IXth.  Ordering is retained.
392
   This is an O(1) operation.  */
393
 
394
#define VEC_block_remove(T,V,I,L)       \
395
        (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
396
 
397
/* Get the address of the array of elements
398
   T *VEC_T_address (VEC(T) v)
399
 
400
   If you need to directly manipulate the array (for instance, you
401
   want to feed it to qsort), use this accessor.  */
402
 
403
#define VEC_address(T,V)                (VEC_OP(T,base,address)(VEC_BASE(V)))
404
 
405
/* Find the first index in the vector not less than the object.
406
   unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
407
                               bool (*lessthan) (const T, const T)); // Integer
408
   unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
409
                               bool (*lessthan) (const T, const T)); // Pointer
410
   unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
411
                               bool (*lessthan) (const T*, const T*)); // Object
412
 
413
   Find the first position in which VAL could be inserted without
414
   changing the ordering of V.  LESSTHAN is a function that returns
415
   true if the first argument is strictly less than the second.  */
416
 
417
#define VEC_lower_bound(T,V,O,LT)    \
418
       (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
419
 
420
/* Reallocate an array of elements with prefix.  */
421
extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
422
extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL);
423
extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
424
extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t
425
                                     MEM_STAT_DECL);
426
extern void ggc_free (void *);
427
#define vec_gc_free(V) ggc_free (V)
428
extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
429
extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL);
430
extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
431
extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t
432
                                       MEM_STAT_DECL);
433
extern void dump_vec_loc_statistics (void);
434
#ifdef GATHER_STATISTICS
435
void vec_heap_free (void *);
436
#else
437
#define vec_heap_free(V) free (V)
438
#endif
439
 
440
#if ENABLE_CHECKING
441
#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
442
#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
443
#define VEC_CHECK_PASS ,file_,line_,function_
444
 
445
#define VEC_ASSERT(EXPR,OP,T,A) \
446
  (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
447
 
448
extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
449
     ATTRIBUTE_NORETURN;
450
#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
451
#else
452
#define VEC_CHECK_INFO
453
#define VEC_CHECK_DECL
454
#define VEC_CHECK_PASS
455
#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
456
#endif
457
 
458
/* Note: gengtype has hardwired knowledge of the expansions of the
459
   VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros.  If you change the
460
   expansions of these macros you may need to change gengtype too.  */
461
 
462
#define VEC(T,A) VEC_##T##_##A
463
#define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
464
 
465
/* Base of vector type, not user visible.  */
466
#define VEC_T(T,B)                                                        \
467
typedef struct VEC(T,B)                                                   \
468
{                                                                         \
469
  unsigned num;                                                           \
470
  unsigned alloc;                                                         \
471
  T vec[1];                                                               \
472
} VEC(T,B)
473
 
474
#define VEC_T_GTY(T,B)                                                    \
475
typedef struct GTY(()) VEC(T,B)                                           \
476
{                                                                         \
477
  unsigned num;                                                           \
478
  unsigned alloc;                                                         \
479
  T GTY ((length ("%h.num"))) vec[1];                                     \
480
} VEC(T,B)
481
 
482
/* Derived vector type, user visible.  */
483
#define VEC_TA_GTY(T,B,A,GTY)                                             \
484
typedef struct GTY VEC(T,A)                                               \
485
{                                                                         \
486
  VEC(T,B) base;                                                          \
487
} VEC(T,A)
488
 
489
#define VEC_TA(T,B,A)                                                     \
490
typedef struct VEC(T,A)                                                   \
491
{                                                                         \
492
  VEC(T,B) base;                                                          \
493
} VEC(T,A)
494
 
495
/* Convert to base type.  */
496
#define VEC_BASE(P)  ((P) ? &(P)->base : 0)
497
 
498
/* Vector of integer-like object.  */
499
#define DEF_VEC_I(T)                                                      \
500
static inline void VEC_OP (T,must_be,integral_type) (void)                \
501
{                                                                         \
502
  (void)~(T)0;                                                             \
503
}                                                                         \
504
                                                                          \
505
VEC_T(T,base);                                                            \
506
VEC_TA(T,base,none);                                                      \
507
DEF_VEC_FUNC_P(T)                                                         \
508
struct vec_swallow_trailing_semi
509
#define DEF_VEC_ALLOC_I(T,A)                                              \
510
VEC_TA(T,base,A);                                                         \
511
DEF_VEC_ALLOC_FUNC_I(T,A)                                                 \
512
DEF_VEC_NONALLOC_FUNCS_I(T,A)                                             \
513
struct vec_swallow_trailing_semi
514
 
515
/* Vector of pointer to object.  */
516
#define DEF_VEC_P(T)                                                      \
517
static inline void VEC_OP (T,must_be,pointer_type) (void)                 \
518
{                                                                         \
519
  (void)((T)1 == (void *)1);                                              \
520
}                                                                         \
521
                                                                          \
522
VEC_T_GTY(T,base);                                                        \
523
VEC_TA(T,base,none);                                                      \
524
DEF_VEC_FUNC_P(T)                                                         \
525
struct vec_swallow_trailing_semi
526
#define DEF_VEC_ALLOC_P(T,A)                                              \
527
VEC_TA(T,base,A);                                                         \
528
DEF_VEC_ALLOC_FUNC_P(T,A)                                                 \
529
DEF_VEC_NONALLOC_FUNCS_P(T,A)                                             \
530
struct vec_swallow_trailing_semi
531
 
532
#define DEF_VEC_FUNC_P(T)                                                 \
533
static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)   \
534
{                                                                         \
535
  return vec_ ? vec_->num : 0;                                             \
536
}                                                                         \
537
                                                                          \
538
static inline T VEC_OP (T,base,last)                                      \
539
     (const VEC(T,base) *vec_ VEC_CHECK_DECL)                             \
540
{                                                                         \
541
  VEC_ASSERT (vec_ && vec_->num, "last", T, base);                        \
542
                                                                          \
543
  return vec_->vec[vec_->num - 1];                                        \
544
}                                                                         \
545
                                                                          \
546
static inline T VEC_OP (T,base,index)                                     \
547
     (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)               \
548
{                                                                         \
549
  VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base);                 \
550
                                                                          \
551
  return vec_->vec[ix_];                                                  \
552
}                                                                         \
553
                                                                          \
554
static inline int VEC_OP (T,base,iterate)                                 \
555
     (const VEC(T,base) *vec_, unsigned ix_, T *ptr)                      \
556
{                                                                         \
557
  if (vec_ && ix_ < vec_->num)                                            \
558
    {                                                                     \
559
      *ptr = vec_->vec[ix_];                                              \
560
      return 1;                                                           \
561
    }                                                                     \
562
  else                                                                    \
563
    {                                                                     \
564
      *ptr = (T) 0;                                                        \
565
      return 0;                                                            \
566
    }                                                                     \
567
}                                                                         \
568
                                                                          \
569
static inline size_t VEC_OP (T,base,embedded_size)                        \
570
     (int alloc_)                                                         \
571
{                                                                         \
572
  return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);                 \
573
}                                                                         \
574
                                                                          \
575
static inline void VEC_OP (T,base,embedded_init)                          \
576
     (VEC(T,base) *vec_, int alloc_)                                      \
577
{                                                                         \
578
  vec_->num = 0;                                                   \
579
  vec_->alloc = alloc_;                                                   \
580
}                                                                         \
581
                                                                          \
582
static inline int VEC_OP (T,base,space)                                   \
583
     (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)                       \
584
{                                                                         \
585
  VEC_ASSERT (alloc_ >= 0, "space", T, base);                              \
586
  return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_;    \
587
}                                                                         \
588
                                                                          \
589
static inline T *VEC_OP (T,base,quick_push)                               \
590
     (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL)                           \
591
{                                                                         \
592
  T *slot_;                                                               \
593
                                                                          \
594
  VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base);                  \
595
  slot_ = &vec_->vec[vec_->num++];                                        \
596
  *slot_ = obj_;                                                          \
597
                                                                          \
598
  return slot_;                                                           \
599
}                                                                         \
600
                                                                          \
601
static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL)    \
602
{                                                                         \
603
  T obj_;                                                                 \
604
                                                                          \
605
  VEC_ASSERT (vec_->num, "pop", T, base);                                 \
606
  obj_ = vec_->vec[--vec_->num];                                          \
607
                                                                          \
608
  return obj_;                                                            \
609
}                                                                         \
610
                                                                          \
611
static inline void VEC_OP (T,base,truncate)                               \
612
     (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)                   \
613
{                                                                         \
614
  VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base);   \
615
  if (vec_)                                                               \
616
    vec_->num = size_;                                                    \
617
}                                                                         \
618
                                                                          \
619
static inline T VEC_OP (T,base,replace)                                   \
620
     (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)             \
621
{                                                                         \
622
  T old_obj_;                                                             \
623
                                                                          \
624
  VEC_ASSERT (ix_ < vec_->num, "replace", T, base);                       \
625
  old_obj_ = vec_->vec[ix_];                                              \
626
  vec_->vec[ix_] = obj_;                                                  \
627
                                                                          \
628
  return old_obj_;                                                        \
629
}                                                                         \
630
                                                                          \
631
static inline T *VEC_OP (T,base,quick_insert)                             \
632
     (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)             \
633
{                                                                         \
634
  T *slot_;                                                               \
635
                                                                          \
636
  VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base);                \
637
  VEC_ASSERT (ix_ <= vec_->num, "insert", T, base);                       \
638
  slot_ = &vec_->vec[ix_];                                                \
639
  memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T));           \
640
  *slot_ = obj_;                                                          \
641
                                                                          \
642
  return slot_;                                                           \
643
}                                                                         \
644
                                                                          \
645
static inline T VEC_OP (T,base,ordered_remove)                            \
646
     (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
647
{                                                                         \
648
  T *slot_;                                                               \
649
  T obj_;                                                                 \
650
                                                                          \
651
  VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
652
  slot_ = &vec_->vec[ix_];                                                \
653
  obj_ = *slot_;                                                          \
654
  memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T));           \
655
                                                                          \
656
  return obj_;                                                            \
657
}                                                                         \
658
                                                                          \
659
static inline T VEC_OP (T,base,unordered_remove)                          \
660
     (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
661
{                                                                         \
662
  T *slot_;                                                               \
663
  T obj_;                                                                 \
664
                                                                          \
665
  VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
666
  slot_ = &vec_->vec[ix_];                                                \
667
  obj_ = *slot_;                                                          \
668
  *slot_ = vec_->vec[--vec_->num];                                        \
669
                                                                          \
670
  return obj_;                                                            \
671
}                                                                         \
672
                                                                          \
673
static inline void VEC_OP (T,base,block_remove)                           \
674
     (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)      \
675
{                                                                         \
676
  T *slot_;                                                               \
677
                                                                          \
678
  VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base);          \
679
  slot_ = &vec_->vec[ix_];                                                \
680
  vec_->num -= len_;                                                      \
681
  memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T));          \
682
}                                                                         \
683
                                                                          \
684
static inline T *VEC_OP (T,base,address)                                  \
685
     (VEC(T,base) *vec_)                                                  \
686
{                                                                         \
687
  return vec_ ? vec_->vec : 0;                                             \
688
}                                                                         \
689
                                                                          \
690
static inline unsigned VEC_OP (T,base,lower_bound)                        \
691
     (VEC(T,base) *vec_, const T obj_,                                    \
692
      bool (*lessthan_)(const T, const T) VEC_CHECK_DECL)                 \
693
{                                                                         \
694
   unsigned int len_ = VEC_OP (T,base, length) (vec_);                    \
695
   unsigned int half_, middle_;                                           \
696
   unsigned int first_ = 0;                                                \
697
   while (len_ > 0)                                                        \
698
     {                                                                    \
699
        T middle_elem_;                                                   \
700
        half_ = len_ >> 1;                                                \
701
        middle_ = first_;                                                 \
702
        middle_ += half_;                                                 \
703
        middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
704
        if (lessthan_ (middle_elem_, obj_))                               \
705
          {                                                               \
706
             first_ = middle_;                                            \
707
             ++first_;                                                    \
708
             len_ = len_ - half_ - 1;                                     \
709
          }                                                               \
710
        else                                                              \
711
          len_ = half_;                                                   \
712
     }                                                                    \
713
   return first_;                                                         \
714
}
715
 
716
#define DEF_VEC_ALLOC_FUNC_P(T,A)                                         \
717
static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
718
     (int alloc_ MEM_STAT_DECL)                                           \
719
{                                                                         \
720
  return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_             \
721
                                                 PASS_MEM_STAT);          \
722
}
723
 
724
 
725
#define DEF_VEC_NONALLOC_FUNCS_P(T,A)                                     \
726
static inline void VEC_OP (T,A,free)                                      \
727
     (VEC(T,A) **vec_)                                                    \
728
{                                                                         \
729
  if (*vec_)                                                              \
730
    vec_##A##_free (*vec_);                                               \
731
  *vec_ = NULL;                                                           \
732
}                                                                         \
733
                                                                          \
734
static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
735
{                                                                         \
736
  size_t len_ = vec_ ? vec_->num : 0;                                      \
737
  VEC (T,A) *new_vec_ = NULL;                                             \
738
                                                                          \
739
  if (len_)                                                               \
740
    {                                                                     \
741
      new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact                  \
742
                               (NULL, len_ PASS_MEM_STAT));               \
743
                                                                          \
744
      new_vec_->base.num = len_;                                          \
745
      memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
746
    }                                                                     \
747
  return new_vec_;                                                        \
748
}                                                                         \
749
                                                                          \
750
static inline int VEC_OP (T,A,reserve)                                    \
751
     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
752
{                                                                         \
753
  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
754
                                       VEC_CHECK_PASS);                   \
755
                                                                          \
756
  if (extend)                                                             \
757
    *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
758
                                                                          \
759
  return extend;                                                          \
760
}                                                                         \
761
                                                                          \
762
static inline int VEC_OP (T,A,reserve_exact)                              \
763
     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
764
{                                                                         \
765
  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
766
                                       VEC_CHECK_PASS);                   \
767
                                                                          \
768
  if (extend)                                                             \
769
    *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_         \
770
                                                    PASS_MEM_STAT);       \
771
                                                                          \
772
  return extend;                                                          \
773
}                                                                         \
774
                                                                          \
775
static inline void VEC_OP (T,A,safe_grow)                                 \
776
     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
777
{                                                                         \
778
  VEC_ASSERT (size_ >= 0                                           \
779
              && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
780
                                                 "grow", T, A);           \
781
  VEC_OP (T,A,reserve_exact) (vec_,                                       \
782
                              size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
783
                              VEC_CHECK_PASS PASS_MEM_STAT);              \
784
  VEC_BASE (*vec_)->num = size_;                                          \
785
}                                                                         \
786
                                                                          \
787
static inline void VEC_OP (T,A,safe_grow_cleared)                         \
788
     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
789
{                                                                         \
790
  int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
791
  VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
792
  memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,          \
793
          sizeof (T) * (size_ - oldsize));                                \
794
}                                                                         \
795
                                                                          \
796
static inline T *VEC_OP (T,A,safe_push)                                   \
797
     (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)               \
798
{                                                                         \
799
  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
800
                                                                          \
801
  return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
802
}                                                                         \
803
                                                                          \
804
static inline T *VEC_OP (T,A,safe_insert)                                 \
805
     (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)  \
806
{                                                                         \
807
  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
808
                                                                          \
809
  return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
810
                                       VEC_CHECK_PASS);                   \
811
}
812
 
813
/* Vector of object.  */
814
#define DEF_VEC_O(T)                                                      \
815
VEC_T_GTY(T,base);                                                        \
816
VEC_TA(T,base,none);                                              \
817
DEF_VEC_FUNC_O(T)                                                         \
818
struct vec_swallow_trailing_semi
819
#define DEF_VEC_ALLOC_O(T,A)                                              \
820
VEC_TA(T,base,A);                                                         \
821
DEF_VEC_ALLOC_FUNC_O(T,A)                                                 \
822
DEF_VEC_NONALLOC_FUNCS_O(T,A)                                             \
823
struct vec_swallow_trailing_semi
824
 
825
#define DEF_VEC_FUNC_O(T)                                                 \
826
static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_)   \
827
{                                                                         \
828
  return vec_ ? vec_->num : 0;                                             \
829
}                                                                         \
830
                                                                          \
831
static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL)  \
832
{                                                                         \
833
  VEC_ASSERT (vec_ && vec_->num, "last", T, base);                        \
834
                                                                          \
835
  return &vec_->vec[vec_->num - 1];                                       \
836
}                                                                         \
837
                                                                          \
838
static inline T *VEC_OP (T,base,index)                                    \
839
     (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
840
{                                                                         \
841
  VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base);                 \
842
                                                                          \
843
  return &vec_->vec[ix_];                                                 \
844
}                                                                         \
845
                                                                          \
846
static inline int VEC_OP (T,base,iterate)                                 \
847
     (VEC(T,base) *vec_, unsigned ix_, T **ptr)                           \
848
{                                                                         \
849
  if (vec_ && ix_ < vec_->num)                                            \
850
    {                                                                     \
851
      *ptr = &vec_->vec[ix_];                                             \
852
      return 1;                                                           \
853
    }                                                                     \
854
  else                                                                    \
855
    {                                                                     \
856
      *ptr = 0;                                                            \
857
      return 0;                                                            \
858
    }                                                                     \
859
}                                                                         \
860
                                                                          \
861
static inline size_t VEC_OP (T,base,embedded_size)                        \
862
     (int alloc_)                                                         \
863
{                                                                         \
864
  return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T);                 \
865
}                                                                         \
866
                                                                          \
867
static inline void VEC_OP (T,base,embedded_init)                          \
868
     (VEC(T,base) *vec_, int alloc_)                                      \
869
{                                                                         \
870
  vec_->num = 0;                                                   \
871
  vec_->alloc = alloc_;                                                   \
872
}                                                                         \
873
                                                                          \
874
static inline int VEC_OP (T,base,space)                                   \
875
     (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL)                       \
876
{                                                                         \
877
  VEC_ASSERT (alloc_ >= 0, "space", T, base);                              \
878
  return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_;    \
879
}                                                                         \
880
                                                                          \
881
static inline T *VEC_OP (T,base,quick_push)                               \
882
     (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL)                    \
883
{                                                                         \
884
  T *slot_;                                                               \
885
                                                                          \
886
  VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base);                  \
887
  slot_ = &vec_->vec[vec_->num++];                                        \
888
  if (obj_)                                                               \
889
    *slot_ = *obj_;                                                       \
890
                                                                          \
891
  return slot_;                                                           \
892
}                                                                         \
893
                                                                          \
894
static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
895
{                                                                         \
896
  VEC_ASSERT (vec_->num, "pop", T, base);                                 \
897
  --vec_->num;                                                            \
898
}                                                                         \
899
                                                                          \
900
static inline void VEC_OP (T,base,truncate)                               \
901
     (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL)                   \
902
{                                                                         \
903
  VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base);   \
904
  if (vec_)                                                               \
905
    vec_->num = size_;                                                    \
906
}                                                                         \
907
                                                                          \
908
static inline T *VEC_OP (T,base,replace)                                  \
909
     (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL)      \
910
{                                                                         \
911
  T *slot_;                                                               \
912
                                                                          \
913
  VEC_ASSERT (ix_ < vec_->num, "replace", T, base);                       \
914
  slot_ = &vec_->vec[ix_];                                                \
915
  if (obj_)                                                               \
916
    *slot_ = *obj_;                                                       \
917
                                                                          \
918
  return slot_;                                                           \
919
}                                                                         \
920
                                                                          \
921
static inline T *VEC_OP (T,base,quick_insert)                             \
922
     (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL)      \
923
{                                                                         \
924
  T *slot_;                                                               \
925
                                                                          \
926
  VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base);                \
927
  VEC_ASSERT (ix_ <= vec_->num, "insert", T, base);                       \
928
  slot_ = &vec_->vec[ix_];                                                \
929
  memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T));           \
930
  if (obj_)                                                               \
931
    *slot_ = *obj_;                                                       \
932
                                                                          \
933
  return slot_;                                                           \
934
}                                                                         \
935
                                                                          \
936
static inline void VEC_OP (T,base,ordered_remove)                         \
937
     (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
938
{                                                                         \
939
  T *slot_;                                                               \
940
                                                                          \
941
  VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
942
  slot_ = &vec_->vec[ix_];                                                \
943
  memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T));           \
944
}                                                                         \
945
                                                                          \
946
static inline void VEC_OP (T,base,unordered_remove)                       \
947
     (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL)                     \
948
{                                                                         \
949
  VEC_ASSERT (ix_ < vec_->num, "remove", T, base);                        \
950
  vec_->vec[ix_] = vec_->vec[--vec_->num];                                \
951
}                                                                         \
952
                                                                          \
953
static inline void VEC_OP (T,base,block_remove)                           \
954
     (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL)      \
955
{                                                                         \
956
  T *slot_;                                                               \
957
                                                                          \
958
  VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base);          \
959
  slot_ = &vec_->vec[ix_];                                                \
960
  vec_->num -= len_;                                                      \
961
  memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T));          \
962
}                                                                         \
963
                                                                          \
964
static inline T *VEC_OP (T,base,address)                                  \
965
     (VEC(T,base) *vec_)                                                  \
966
{                                                                         \
967
  return vec_ ? vec_->vec : 0;                                             \
968
}                                                                         \
969
                                                                          \
970
static inline unsigned VEC_OP (T,base,lower_bound)                        \
971
     (VEC(T,base) *vec_, const T *obj_,                                   \
972
      bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL)             \
973
{                                                                         \
974
   unsigned int len_ = VEC_OP (T, base, length) (vec_);                   \
975
   unsigned int half_, middle_;                                           \
976
   unsigned int first_ = 0;                                                \
977
   while (len_ > 0)                                                        \
978
     {                                                                    \
979
        T *middle_elem_;                                                  \
980
        half_ = len_ >> 1;                                                \
981
        middle_ = first_;                                                 \
982
        middle_ += half_;                                                 \
983
        middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
984
        if (lessthan_ (middle_elem_, obj_))                               \
985
          {                                                               \
986
             first_ = middle_;                                            \
987
             ++first_;                                                    \
988
             len_ = len_ - half_ - 1;                                     \
989
          }                                                               \
990
        else                                                              \
991
          len_ = half_;                                                   \
992
     }                                                                    \
993
   return first_;                                                         \
994
}
995
 
996
#define DEF_VEC_ALLOC_FUNC_O(T,A)                                         \
997
static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
998
     (int alloc_ MEM_STAT_DECL)                                           \
999
{                                                                         \
1000
  return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_,            \
1001
                                                 offsetof (VEC(T,A),base.vec), \
1002
                                                 sizeof (T)               \
1003
                                                 PASS_MEM_STAT);          \
1004
}
1005
 
1006
#define DEF_VEC_NONALLOC_FUNCS_O(T,A)                                     \
1007
static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1008
{                                                                         \
1009
  size_t len_ = vec_ ? vec_->num : 0;                                      \
1010
  VEC (T,A) *new_vec_ = NULL;                                             \
1011
                                                                          \
1012
  if (len_)                                                               \
1013
    {                                                                     \
1014
      new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact                  \
1015
                               (NULL, len_,                               \
1016
                                offsetof (VEC(T,A),base.vec), sizeof (T)  \
1017
                                PASS_MEM_STAT));                          \
1018
                                                                          \
1019
      new_vec_->base.num = len_;                                          \
1020
      memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
1021
    }                                                                     \
1022
  return new_vec_;                                                        \
1023
}                                                                         \
1024
                                                                          \
1025
static inline void VEC_OP (T,A,free)                                      \
1026
     (VEC(T,A) **vec_)                                                    \
1027
{                                                                         \
1028
  if (*vec_)                                                              \
1029
    vec_##A##_free (*vec_);                                               \
1030
  *vec_ = NULL;                                                           \
1031
}                                                                         \
1032
                                                                          \
1033
static inline int VEC_OP (T,A,reserve)                                    \
1034
     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1035
{                                                                         \
1036
  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1037
                                       VEC_CHECK_PASS);                   \
1038
                                                                          \
1039
  if (extend)                                                             \
1040
    *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,              \
1041
                                              offsetof (VEC(T,A),base.vec),\
1042
                                              sizeof (T)                  \
1043
                                              PASS_MEM_STAT);             \
1044
                                                                          \
1045
  return extend;                                                          \
1046
}                                                                         \
1047
                                                                          \
1048
static inline int VEC_OP (T,A,reserve_exact)                              \
1049
     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1050
{                                                                         \
1051
  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1052
                                       VEC_CHECK_PASS);                   \
1053
                                                                          \
1054
  if (extend)                                                             \
1055
    *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact                        \
1056
                         (*vec_, alloc_,                                  \
1057
                          offsetof (VEC(T,A),base.vec),                   \
1058
                          sizeof (T) PASS_MEM_STAT);                      \
1059
                                                                          \
1060
  return extend;                                                          \
1061
}                                                                         \
1062
                                                                          \
1063
static inline void VEC_OP (T,A,safe_grow)                                 \
1064
     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1065
{                                                                         \
1066
  VEC_ASSERT (size_ >= 0                                           \
1067
              && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1068
                                                 "grow", T, A);           \
1069
  VEC_OP (T,A,reserve_exact) (vec_,                                       \
1070
                              size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1071
                              VEC_CHECK_PASS PASS_MEM_STAT);              \
1072
  VEC_BASE (*vec_)->num = size_;                                          \
1073
}                                                                         \
1074
                                                                          \
1075
static inline void VEC_OP (T,A,safe_grow_cleared)                         \
1076
     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1077
{                                                                         \
1078
  int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
1079
  VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
1080
  memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,          \
1081
          sizeof (T) * (size_ - oldsize));                                \
1082
}                                                                         \
1083
                                                                          \
1084
static inline T *VEC_OP (T,A,safe_push)                                   \
1085
     (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL)        \
1086
{                                                                         \
1087
  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1088
                                                                          \
1089
  return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
1090
}                                                                         \
1091
                                                                          \
1092
static inline T *VEC_OP (T,A,safe_insert)                                 \
1093
     (VEC(T,A) **vec_, unsigned ix_, const T *obj_                        \
1094
                VEC_CHECK_DECL MEM_STAT_DECL)                             \
1095
{                                                                         \
1096
  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1097
                                                                          \
1098
  return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
1099
                                       VEC_CHECK_PASS);                   \
1100
}
1101
 
1102
#define DEF_VEC_ALLOC_FUNC_I(T,A)                                         \
1103
static inline VEC(T,A) *VEC_OP (T,A,alloc)                                \
1104
     (int alloc_ MEM_STAT_DECL)                                           \
1105
{                                                                         \
1106
  return (VEC(T,A) *) vec_##A##_o_reserve_exact                           \
1107
                      (NULL, alloc_, offsetof (VEC(T,A),base.vec),        \
1108
                       sizeof (T) PASS_MEM_STAT);                         \
1109
}
1110
 
1111
#define DEF_VEC_NONALLOC_FUNCS_I(T,A)                                     \
1112
static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
1113
{                                                                         \
1114
  size_t len_ = vec_ ? vec_->num : 0;                                      \
1115
  VEC (T,A) *new_vec_ = NULL;                                             \
1116
                                                                          \
1117
  if (len_)                                                               \
1118
    {                                                                     \
1119
      new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact                  \
1120
                               (NULL, len_,                               \
1121
                                offsetof (VEC(T,A),base.vec), sizeof (T)  \
1122
                                PASS_MEM_STAT));                          \
1123
                                                                          \
1124
      new_vec_->base.num = len_;                                          \
1125
      memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_);          \
1126
    }                                                                     \
1127
  return new_vec_;                                                        \
1128
}                                                                         \
1129
                                                                          \
1130
static inline void VEC_OP (T,A,free)                                      \
1131
     (VEC(T,A) **vec_)                                                    \
1132
{                                                                         \
1133
  if (*vec_)                                                              \
1134
    vec_##A##_free (*vec_);                                               \
1135
  *vec_ = NULL;                                                           \
1136
}                                                                         \
1137
                                                                          \
1138
static inline int VEC_OP (T,A,reserve)                                    \
1139
     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1140
{                                                                         \
1141
  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1142
                                       VEC_CHECK_PASS);                   \
1143
                                                                          \
1144
  if (extend)                                                             \
1145
    *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_,              \
1146
                                              offsetof (VEC(T,A),base.vec),\
1147
                                              sizeof (T)                  \
1148
                                              PASS_MEM_STAT);             \
1149
                                                                          \
1150
  return extend;                                                          \
1151
}                                                                         \
1152
                                                                          \
1153
static inline int VEC_OP (T,A,reserve_exact)                              \
1154
     (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)           \
1155
{                                                                         \
1156
  int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_            \
1157
                                       VEC_CHECK_PASS);                   \
1158
                                                                          \
1159
  if (extend)                                                             \
1160
    *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact                        \
1161
                         (*vec_, alloc_, offsetof (VEC(T,A),base.vec),    \
1162
                          sizeof (T) PASS_MEM_STAT);                      \
1163
                                                                          \
1164
  return extend;                                                          \
1165
}                                                                         \
1166
                                                                          \
1167
static inline void VEC_OP (T,A,safe_grow)                                 \
1168
     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1169
{                                                                         \
1170
  VEC_ASSERT (size_ >= 0                                           \
1171
              && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
1172
                                                 "grow", T, A);           \
1173
  VEC_OP (T,A,reserve_exact) (vec_,                                       \
1174
                              size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \
1175
                              VEC_CHECK_PASS PASS_MEM_STAT);              \
1176
  VEC_BASE (*vec_)->num = size_;                                          \
1177
}                                                                         \
1178
                                                                          \
1179
static inline void VEC_OP (T,A,safe_grow_cleared)                         \
1180
     (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)            \
1181
{                                                                         \
1182
  int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_);                    \
1183
  VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);      \
1184
  memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0,          \
1185
          sizeof (T) * (size_ - oldsize));                                \
1186
}                                                                         \
1187
                                                                          \
1188
static inline T *VEC_OP (T,A,safe_push)                                   \
1189
     (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL)         \
1190
{                                                                         \
1191
  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1192
                                                                          \
1193
  return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS);  \
1194
}                                                                         \
1195
                                                                          \
1196
static inline T *VEC_OP (T,A,safe_insert)                                 \
1197
     (VEC(T,A) **vec_, unsigned ix_, const T obj_                         \
1198
                VEC_CHECK_DECL MEM_STAT_DECL)                             \
1199
{                                                                         \
1200
  VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);            \
1201
                                                                          \
1202
  return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_         \
1203
                                       VEC_CHECK_PASS);                   \
1204
}
1205
 
1206
/* We support a vector which starts out with space on the stack and
1207
   switches to heap space when forced to reallocate.  This works a
1208
   little differently.  Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use
1209
   DEF_VEC_ALLOC_P_STACK(TYPE).  This uses alloca to get the initial
1210
   space; because alloca can not be usefully called in an inline
1211
   function, and because a macro can not define a macro, you must then
1212
   write a #define for each type:
1213
 
1214
   #define VEC_{TYPE}_stack_alloc(alloc)                          \
1215
     VEC_stack_alloc({TYPE}, alloc)
1216
 
1217
   This is really a hack and perhaps can be made better.  Note that
1218
   this macro will wind up evaluating the ALLOC parameter twice.
1219
 
1220
   Only the initial allocation will be made using alloca, so pass a
1221
   reasonable estimate that doesn't use too much stack space; don't
1222
   pass zero.  Don't return a VEC(TYPE,stack) vector from the function
1223
   which allocated it.  */
1224
 
1225
extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL);
1226
extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL);
1227
extern void *vec_stack_p_reserve_exact_1 (int, void *);
1228
extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
1229
extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
1230
                                         MEM_STAT_DECL);
1231
extern void vec_stack_free (void *);
1232
 
1233
#ifdef GATHER_STATISTICS
1234
#define VEC_stack_alloc(T,alloc,name,line,function)                       \
1235
  (VEC_OP (T,stack,alloc1)                                                \
1236
   (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1237
#else
1238
#define VEC_stack_alloc(T,alloc)                                          \
1239
  (VEC_OP (T,stack,alloc1)                                                \
1240
   (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
1241
#endif
1242
 
1243
#define DEF_VEC_ALLOC_P_STACK(T)                                          \
1244
VEC_TA(T,base,stack);                                                     \
1245
DEF_VEC_ALLOC_FUNC_P_STACK(T)                                             \
1246
DEF_VEC_NONALLOC_FUNCS_P(T,stack)                                         \
1247
struct vec_swallow_trailing_semi
1248
 
1249
#define DEF_VEC_ALLOC_FUNC_P_STACK(T)                                     \
1250
static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)                       \
1251
     (int alloc_, VEC(T,stack)* space)                                    \
1252
{                                                                         \
1253
  return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);    \
1254
}
1255
 
1256
#define DEF_VEC_ALLOC_O_STACK(T)                                          \
1257
VEC_TA(T,base,stack);                                                     \
1258
DEF_VEC_ALLOC_FUNC_O_STACK(T)                                             \
1259
DEF_VEC_NONALLOC_FUNCS_O(T,stack)                                         \
1260
struct vec_swallow_trailing_semi
1261
 
1262
#define DEF_VEC_ALLOC_FUNC_O_STACK(T)                                     \
1263
static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)                       \
1264
     (int alloc_, VEC(T,stack)* space)                                    \
1265
{                                                                         \
1266
  return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);    \
1267
}
1268
 
1269
#define DEF_VEC_ALLOC_I_STACK(T)                                          \
1270
VEC_TA(T,base,stack);                                                     \
1271
DEF_VEC_ALLOC_FUNC_I_STACK(T)                                             \
1272
DEF_VEC_NONALLOC_FUNCS_I(T,stack)                                         \
1273
struct vec_swallow_trailing_semi
1274
 
1275
#define DEF_VEC_ALLOC_FUNC_I_STACK(T)                                     \
1276
static inline VEC(T,stack) *VEC_OP (T,stack,alloc1)                       \
1277
     (int alloc_, VEC(T,stack)* space)                                    \
1278
{                                                                         \
1279
  return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space);   \
1280
}
1281
 
1282
#endif /* GCC_VEC_H */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.