|
GDB (API)
|
|
GDB (API)
|
00001 /* Vector API for GDB. 00002 Copyright (C) 2004-2013 Free Software Foundation, Inc. 00003 Contributed by Nathan Sidwell <nathan@codesourcery.com> 00004 00005 This file is part of GDB. 00006 00007 This program is free software; you can redistribute it and/or modify 00008 it under the terms of the GNU General Public License as published by 00009 the Free Software Foundation; either version 3 of the License, or 00010 (at your option) any later version. 00011 00012 This program is distributed in the hope that it will be useful, 00013 but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 GNU General Public License for more details. 00016 00017 You should have received a copy of the GNU General Public License 00018 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 00019 00020 #if !defined (GDB_VEC_H) 00021 #define GDB_VEC_H 00022 00023 #include <stddef.h> 00024 00025 #include "gdb_string.h" 00026 #include "gdb_assert.h" 00027 00028 /* The macros here implement a set of templated vector types and 00029 associated interfaces. These templates are implemented with 00030 macros, as we're not in C++ land. The interface functions are 00031 typesafe and use static inline functions, sometimes backed by 00032 out-of-line generic functions. 00033 00034 Because of the different behavior of structure objects, scalar 00035 objects and of pointers, there are three flavors, one for each of 00036 these variants. Both the structure object and pointer variants 00037 pass pointers to objects around -- in the former case the pointers 00038 are stored into the vector and in the latter case the pointers are 00039 dereferenced and the objects copied into the vector. The scalar 00040 object variant is suitable for int-like objects, and the vector 00041 elements are returned by value. 00042 00043 There are both 'index' and 'iterate' accessors. The iterator 00044 returns a boolean iteration condition and updates the iteration 00045 variable passed by reference. Because the iterator will be 00046 inlined, the address-of can be optimized away. 00047 00048 The vectors are implemented using the trailing array idiom, thus 00049 they are not resizeable without changing the address of the vector 00050 object itself. This means you cannot have variables or fields of 00051 vector type -- always use a pointer to a vector. The one exception 00052 is the final field of a structure, which could be a vector type. 00053 You will have to use the embedded_size & embedded_init calls to 00054 create such objects, and they will probably not be resizeable (so 00055 don't use the 'safe' allocation variants). The trailing array 00056 idiom is used (rather than a pointer to an array of data), because, 00057 if we allow NULL to also represent an empty vector, empty vectors 00058 occupy minimal space in the structure containing them. 00059 00060 Each operation that increases the number of active elements is 00061 available in 'quick' and 'safe' variants. The former presumes that 00062 there is sufficient allocated space for the operation to succeed 00063 (it dies if there is not). The latter will reallocate the 00064 vector, if needed. Reallocation causes an exponential increase in 00065 vector size. If you know you will be adding N elements, it would 00066 be more efficient to use the reserve operation before adding the 00067 elements with the 'quick' operation. This will ensure there are at 00068 least as many elements as you ask for, it will exponentially 00069 increase if there are too few spare slots. If you want reserve a 00070 specific number of slots, but do not want the exponential increase 00071 (for instance, you know this is the last allocation), use a 00072 negative number for reservation. You can also create a vector of a 00073 specific size from the get go. 00074 00075 You should prefer the push and pop operations, as they append and 00076 remove from the end of the vector. If you need to remove several 00077 items in one go, use the truncate operation. The insert and remove 00078 operations allow you to change elements in the middle of the 00079 vector. There are two remove operations, one which preserves the 00080 element ordering 'ordered_remove', and one which does not 00081 'unordered_remove'. The latter function copies the end element 00082 into the removed slot, rather than invoke a memmove operation. The 00083 'lower_bound' function will determine where to place an item in the 00084 array using insert that will maintain sorted order. 00085 00086 If you need to directly manipulate a vector, then the 'address' 00087 accessor will return the address of the start of the vector. Also 00088 the 'space' predicate will tell you whether there is spare capacity 00089 in the vector. You will not normally need to use these two functions. 00090 00091 Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro. 00092 Variables of vector type are declared using a VEC(TYPEDEF) macro. 00093 The characters O, P and I indicate whether TYPEDEF is a pointer 00094 (P), object (O) or integral (I) type. Be careful to pick the 00095 correct one, as you'll get an awkward and inefficient API if you 00096 use the wrong one. There is a check, which results in a 00097 compile-time warning, for the P and I versions, but there is no 00098 check for the O versions, as that is not possible in plain C. 00099 00100 An example of their use would be, 00101 00102 DEF_VEC_P(tree); // non-managed tree vector. 00103 00104 struct my_struct { 00105 VEC(tree) *v; // A (pointer to) a vector of tree pointers. 00106 }; 00107 00108 struct my_struct *s; 00109 00110 if (VEC_length(tree, s->v)) { we have some contents } 00111 VEC_safe_push(tree, s->v, decl); // append some decl onto the end 00112 for (ix = 0; VEC_iterate(tree, s->v, ix, elt); ix++) 00113 { do something with elt } 00114 00115 */ 00116 00117 /* Macros to invoke API calls. A single macro works for both pointer 00118 and object vectors, but the argument and return types might well be 00119 different. In each macro, T is the typedef of the vector elements. 00120 Some of these macros pass the vector, V, by reference (by taking 00121 its address), this is noted in the descriptions. */ 00122 00123 /* Length of vector 00124 unsigned VEC_T_length(const VEC(T) *v); 00125 00126 Return the number of active elements in V. V can be NULL, in which 00127 case zero is returned. */ 00128 00129 #define VEC_length(T,V) (VEC_OP(T,length)(V)) 00130 00131 00132 /* Check if vector is empty 00133 int VEC_T_empty(const VEC(T) *v); 00134 00135 Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */ 00136 00137 #define VEC_empty(T,V) (VEC_length (T,V) == 0) 00138 00139 00140 /* Get the final element of the vector. 00141 T VEC_T_last(VEC(T) *v); // Integer 00142 T VEC_T_last(VEC(T) *v); // Pointer 00143 T *VEC_T_last(VEC(T) *v); // Object 00144 00145 Return the final element. V must not be empty. */ 00146 00147 #define VEC_last(T,V) (VEC_OP(T,last)(V VEC_ASSERT_INFO)) 00148 00149 /* Index into vector 00150 T VEC_T_index(VEC(T) *v, unsigned ix); // Integer 00151 T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer 00152 T *VEC_T_index(VEC(T) *v, unsigned ix); // Object 00153 00154 Return the IX'th element. If IX must be in the domain of V. */ 00155 00156 #define VEC_index(T,V,I) (VEC_OP(T,index)(V,I VEC_ASSERT_INFO)) 00157 00158 /* Iterate over vector 00159 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer 00160 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer 00161 int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object 00162 00163 Return iteration condition and update PTR to point to the IX'th 00164 element. At the end of iteration, sets PTR to NULL. Use this to 00165 iterate over the elements of a vector as follows, 00166 00167 for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++) 00168 continue; */ 00169 00170 #define VEC_iterate(T,V,I,P) (VEC_OP(T,iterate)(V,I,&(P))) 00171 00172 /* Allocate new vector. 00173 VEC(T,A) *VEC_T_alloc(int reserve); 00174 00175 Allocate a new vector with space for RESERVE objects. If RESERVE 00176 is zero, NO vector is created. */ 00177 00178 #define VEC_alloc(T,N) (VEC_OP(T,alloc)(N)) 00179 00180 /* Free a vector. 00181 void VEC_T_free(VEC(T,A) *&); 00182 00183 Free a vector and set it to NULL. */ 00184 00185 #define VEC_free(T,V) (VEC_OP(T,free)(&V)) 00186 00187 /* A cleanup function for a vector. 00188 void VEC_T_cleanup(void *); 00189 00190 Clean up a vector. */ 00191 00192 #define VEC_cleanup(T) (VEC_OP(T,cleanup)) 00193 00194 /* Use these to determine the required size and initialization of a 00195 vector embedded within another structure (as the final member). 00196 00197 size_t VEC_T_embedded_size(int reserve); 00198 void VEC_T_embedded_init(VEC(T) *v, int reserve); 00199 00200 These allow the caller to perform the memory allocation. */ 00201 00202 #define VEC_embedded_size(T,N) (VEC_OP(T,embedded_size)(N)) 00203 #define VEC_embedded_init(T,O,N) (VEC_OP(T,embedded_init)(VEC_BASE(O),N)) 00204 00205 /* Copy a vector. 00206 VEC(T,A) *VEC_T_copy(VEC(T) *); 00207 00208 Copy the live elements of a vector into a new vector. The new and 00209 old vectors need not be allocated by the same mechanism. */ 00210 00211 #define VEC_copy(T,V) (VEC_OP(T,copy)(V)) 00212 00213 /* Merge two vectors. 00214 VEC(T,A) *VEC_T_merge(VEC(T) *, VEC(T) *); 00215 00216 Copy the live elements of both vectors into a new vector. The new 00217 and old vectors need not be allocated by the same mechanism. */ 00218 #define VEC_merge(T,V1,V2) (VEC_OP(T,merge)(V1, V2)) 00219 00220 /* Determine if a vector has additional capacity. 00221 00222 int VEC_T_space (VEC(T) *v,int reserve) 00223 00224 If V has space for RESERVE additional entries, return nonzero. You 00225 usually only need to use this if you are doing your own vector 00226 reallocation, for instance on an embedded vector. This returns 00227 nonzero in exactly the same circumstances that VEC_T_reserve 00228 will. */ 00229 00230 #define VEC_space(T,V,R) (VEC_OP(T,space)(V,R VEC_ASSERT_INFO)) 00231 00232 /* Reserve space. 00233 int VEC_T_reserve(VEC(T,A) *&v, int reserve); 00234 00235 Ensure that V has at least abs(RESERVE) slots available. The 00236 signedness of RESERVE determines the reallocation behavior. A 00237 negative value will not create additional headroom beyond that 00238 requested. A positive value will create additional headroom. Note 00239 this can cause V to be reallocated. Returns nonzero iff 00240 reallocation actually occurred. */ 00241 00242 #define VEC_reserve(T,V,R) (VEC_OP(T,reserve)(&(V),R VEC_ASSERT_INFO)) 00243 00244 /* Push object with no reallocation 00245 T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer 00246 T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer 00247 T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object 00248 00249 Push a new element onto the end, returns a pointer to the slot 00250 filled in. For object vectors, the new value can be NULL, in which 00251 case NO initialization is performed. There must 00252 be sufficient space in the vector. */ 00253 00254 #define VEC_quick_push(T,V,O) (VEC_OP(T,quick_push)(V,O VEC_ASSERT_INFO)) 00255 00256 /* Push object with reallocation 00257 T *VEC_T_safe_push (VEC(T,A) *&v, T obj); // Integer 00258 T *VEC_T_safe_push (VEC(T,A) *&v, T obj); // Pointer 00259 T *VEC_T_safe_push (VEC(T,A) *&v, T *obj); // Object 00260 00261 Push a new element onto the end, returns a pointer to the slot 00262 filled in. For object vectors, the new value can be NULL, in which 00263 case NO initialization is performed. Reallocates V, if needed. */ 00264 00265 #define VEC_safe_push(T,V,O) (VEC_OP(T,safe_push)(&(V),O VEC_ASSERT_INFO)) 00266 00267 /* Pop element off end 00268 T VEC_T_pop (VEC(T) *v); // Integer 00269 T VEC_T_pop (VEC(T) *v); // Pointer 00270 void VEC_T_pop (VEC(T) *v); // Object 00271 00272 Pop the last element off the end. Returns the element popped, for 00273 pointer vectors. */ 00274 00275 #define VEC_pop(T,V) (VEC_OP(T,pop)(V VEC_ASSERT_INFO)) 00276 00277 /* Truncate to specific length 00278 void VEC_T_truncate (VEC(T) *v, unsigned len); 00279 00280 Set the length as specified. The new length must be less than or 00281 equal to the current length. This is an O(1) operation. */ 00282 00283 #define VEC_truncate(T,V,I) \ 00284 (VEC_OP(T,truncate)(V,I VEC_ASSERT_INFO)) 00285 00286 /* Grow to a specific length. 00287 void VEC_T_safe_grow (VEC(T,A) *&v, int len); 00288 00289 Grow the vector to a specific length. The LEN must be as 00290 long or longer than the current length. The new elements are 00291 uninitialized. */ 00292 00293 #define VEC_safe_grow(T,V,I) \ 00294 (VEC_OP(T,safe_grow)(&(V),I VEC_ASSERT_INFO)) 00295 00296 /* Replace element 00297 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer 00298 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer 00299 T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object 00300 00301 Replace the IXth element of V with a new value, VAL. For pointer 00302 vectors returns the original value. For object vectors returns a 00303 pointer to the new value. For object vectors the new value can be 00304 NULL, in which case no overwriting of the slot is actually 00305 performed. */ 00306 00307 #define VEC_replace(T,V,I,O) (VEC_OP(T,replace)(V,I,O VEC_ASSERT_INFO)) 00308 00309 /* Insert object with no reallocation 00310 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer 00311 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer 00312 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object 00313 00314 Insert an element, VAL, at the IXth position of V. Return a pointer 00315 to the slot created. For vectors of object, the new value can be 00316 NULL, in which case no initialization of the inserted slot takes 00317 place. There must be sufficient space. */ 00318 00319 #define VEC_quick_insert(T,V,I,O) \ 00320 (VEC_OP(T,quick_insert)(V,I,O VEC_ASSERT_INFO)) 00321 00322 /* Insert object with reallocation 00323 T *VEC_T_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer 00324 T *VEC_T_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer 00325 T *VEC_T_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object 00326 00327 Insert an element, VAL, at the IXth position of V. Return a pointer 00328 to the slot created. For vectors of object, the new value can be 00329 NULL, in which case no initialization of the inserted slot takes 00330 place. Reallocate V, if necessary. */ 00331 00332 #define VEC_safe_insert(T,V,I,O) \ 00333 (VEC_OP(T,safe_insert)(&(V),I,O VEC_ASSERT_INFO)) 00334 00335 /* Remove element retaining order 00336 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer 00337 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer 00338 void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object 00339 00340 Remove an element from the IXth position of V. Ordering of 00341 remaining elements is preserved. For pointer vectors returns the 00342 removed object. This is an O(N) operation due to a memmove. */ 00343 00344 #define VEC_ordered_remove(T,V,I) \ 00345 (VEC_OP(T,ordered_remove)(V,I VEC_ASSERT_INFO)) 00346 00347 /* Remove element destroying order 00348 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer 00349 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer 00350 void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object 00351 00352 Remove an element from the IXth position of V. Ordering of 00353 remaining elements is destroyed. For pointer vectors returns the 00354 removed object. This is an O(1) operation. */ 00355 00356 #define VEC_unordered_remove(T,V,I) \ 00357 (VEC_OP(T,unordered_remove)(V,I VEC_ASSERT_INFO)) 00358 00359 /* Remove a block of elements 00360 void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len); 00361 00362 Remove LEN elements starting at the IXth. Ordering is retained. 00363 This is an O(N) operation due to memmove. */ 00364 00365 #define VEC_block_remove(T,V,I,L) \ 00366 (VEC_OP(T,block_remove)(V,I,L VEC_ASSERT_INFO)) 00367 00368 /* Get the address of the array of elements 00369 T *VEC_T_address (VEC(T) v) 00370 00371 If you need to directly manipulate the array (for instance, you 00372 want to feed it to qsort), use this accessor. */ 00373 00374 #define VEC_address(T,V) (VEC_OP(T,address)(V)) 00375 00376 /* Find the first index in the vector not less than the object. 00377 unsigned VEC_T_lower_bound (VEC(T) *v, const T val, 00378 int (*lessthan) (const T, const T)); // Integer 00379 unsigned VEC_T_lower_bound (VEC(T) *v, const T val, 00380 int (*lessthan) (const T, const T)); // Pointer 00381 unsigned VEC_T_lower_bound (VEC(T) *v, const T *val, 00382 int (*lessthan) (const T*, const T*)); // Object 00383 00384 Find the first position in which VAL could be inserted without 00385 changing the ordering of V. LESSTHAN is a function that returns 00386 true if the first argument is strictly less than the second. */ 00387 00388 #define VEC_lower_bound(T,V,O,LT) \ 00389 (VEC_OP(T,lower_bound)(V,O,LT VEC_ASSERT_INFO)) 00390 00391 /* Reallocate an array of elements with prefix. */ 00392 extern void *vec_p_reserve (void *, int); 00393 extern void *vec_o_reserve (void *, int, size_t, size_t); 00394 #define vec_free_(V) xfree (V) 00395 00396 #define VEC_ASSERT_INFO ,__FILE__,__LINE__ 00397 #define VEC_ASSERT_DECL ,const char *file_,unsigned line_ 00398 #define VEC_ASSERT_PASS ,file_,line_ 00399 #define vec_assert(expr, op) \ 00400 ((void)((expr) ? 0 : (gdb_assert_fail (op, file_, line_, \ 00401 ASSERT_FUNCTION), 0))) 00402 00403 #define VEC(T) VEC_##T 00404 #define VEC_OP(T,OP) VEC_##T##_##OP 00405 00406 #define VEC_T(T) \ 00407 typedef struct VEC(T) \ 00408 { \ 00409 unsigned num; \ 00410 unsigned alloc; \ 00411 T vec[1]; \ 00412 } VEC(T) 00413 00414 /* Vector of integer-like object. */ 00415 #define DEF_VEC_I(T) \ 00416 static inline void VEC_OP (T,must_be_integral_type) (void) \ 00417 { \ 00418 (void)~(T)0; \ 00419 } \ 00420 \ 00421 VEC_T(T); \ 00422 DEF_VEC_FUNC_P(T) \ 00423 DEF_VEC_ALLOC_FUNC_I(T) \ 00424 struct vec_swallow_trailing_semi 00425 00426 /* Vector of pointer to object. */ 00427 #define DEF_VEC_P(T) \ 00428 static inline void VEC_OP (T,must_be_pointer_type) (void) \ 00429 { \ 00430 (void)((T)1 == (void *)1); \ 00431 } \ 00432 \ 00433 VEC_T(T); \ 00434 DEF_VEC_FUNC_P(T) \ 00435 DEF_VEC_ALLOC_FUNC_P(T) \ 00436 struct vec_swallow_trailing_semi 00437 00438 /* Vector of object. */ 00439 #define DEF_VEC_O(T) \ 00440 VEC_T(T); \ 00441 DEF_VEC_FUNC_O(T) \ 00442 DEF_VEC_ALLOC_FUNC_O(T) \ 00443 struct vec_swallow_trailing_semi 00444 00445 #define DEF_VEC_ALLOC_FUNC_I(T) \ 00446 static inline VEC(T) *VEC_OP (T,alloc) \ 00447 (int alloc_) \ 00448 { \ 00449 /* We must request exact size allocation, hence the negation. */ \ 00450 return (VEC(T) *) vec_o_reserve (NULL, -alloc_, \ 00451 offsetof (VEC(T),vec), sizeof (T)); \ 00452 } \ 00453 \ 00454 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \ 00455 { \ 00456 size_t len_ = vec_ ? vec_->num : 0; \ 00457 VEC (T) *new_vec_ = NULL; \ 00458 \ 00459 if (len_) \ 00460 { \ 00461 /* We must request exact size allocation, hence the negation. */ \ 00462 new_vec_ = (VEC (T) *) \ 00463 vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \ 00464 \ 00465 new_vec_->num = len_; \ 00466 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \ 00467 } \ 00468 return new_vec_; \ 00469 } \ 00470 \ 00471 static inline VEC(T) *VEC_OP (T,merge) (VEC(T) *vec1_, VEC(T) *vec2_) \ 00472 { \ 00473 if (vec1_ && vec2_) \ 00474 { \ 00475 size_t len_ = vec1_->num + vec2_->num; \ 00476 VEC (T) *new_vec_ = NULL; \ 00477 \ 00478 /* We must request exact size allocation, hence the negation. */ \ 00479 new_vec_ = (VEC (T) *) \ 00480 vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \ 00481 \ 00482 new_vec_->num = len_; \ 00483 memcpy (new_vec_->vec, vec1_->vec, sizeof (T) * vec1_->num); \ 00484 memcpy (new_vec_->vec + vec1_->num, vec2_->vec, \ 00485 sizeof (T) * vec2_->num); \ 00486 \ 00487 return new_vec_; \ 00488 } \ 00489 else \ 00490 return VEC_copy (T, vec1_ ? vec1_ : vec2_); \ 00491 } \ 00492 \ 00493 static inline void VEC_OP (T,free) \ 00494 (VEC(T) **vec_) \ 00495 { \ 00496 if (*vec_) \ 00497 vec_free_ (*vec_); \ 00498 *vec_ = NULL; \ 00499 } \ 00500 \ 00501 static inline void VEC_OP (T,cleanup) \ 00502 (void *arg_) \ 00503 { \ 00504 VEC(T) **vec_ = arg_; \ 00505 if (*vec_) \ 00506 vec_free_ (*vec_); \ 00507 *vec_ = NULL; \ 00508 } \ 00509 \ 00510 static inline int VEC_OP (T,reserve) \ 00511 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \ 00512 { \ 00513 int extend = !VEC_OP (T,space) \ 00514 (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \ 00515 \ 00516 if (extend) \ 00517 *vec_ = (VEC(T) *) vec_o_reserve (*vec_, alloc_, \ 00518 offsetof (VEC(T),vec), sizeof (T)); \ 00519 \ 00520 return extend; \ 00521 } \ 00522 \ 00523 static inline void VEC_OP (T,safe_grow) \ 00524 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \ 00525 { \ 00526 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \ 00527 "safe_grow"); \ 00528 VEC_OP (T,reserve) (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ \ 00529 VEC_ASSERT_PASS); \ 00530 (*vec_)->num = size_; \ 00531 } \ 00532 \ 00533 static inline T *VEC_OP (T,safe_push) \ 00534 (VEC(T) **vec_, const T obj_ VEC_ASSERT_DECL) \ 00535 { \ 00536 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ 00537 \ 00538 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \ 00539 } \ 00540 \ 00541 static inline T *VEC_OP (T,safe_insert) \ 00542 (VEC(T) **vec_, unsigned ix_, const T obj_ VEC_ASSERT_DECL) \ 00543 { \ 00544 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ 00545 \ 00546 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \ 00547 } 00548 00549 #define DEF_VEC_FUNC_P(T) \ 00550 static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \ 00551 { \ 00552 return vec_ ? vec_->num : 0; \ 00553 } \ 00554 \ 00555 static inline T VEC_OP (T,last) \ 00556 (const VEC(T) *vec_ VEC_ASSERT_DECL) \ 00557 { \ 00558 vec_assert (vec_ && vec_->num, "last"); \ 00559 \ 00560 return vec_->vec[vec_->num - 1]; \ 00561 } \ 00562 \ 00563 static inline T VEC_OP (T,index) \ 00564 (const VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ 00565 { \ 00566 vec_assert (vec_ && ix_ < vec_->num, "index"); \ 00567 \ 00568 return vec_->vec[ix_]; \ 00569 } \ 00570 \ 00571 static inline int VEC_OP (T,iterate) \ 00572 (const VEC(T) *vec_, unsigned ix_, T *ptr) \ 00573 { \ 00574 if (vec_ && ix_ < vec_->num) \ 00575 { \ 00576 *ptr = vec_->vec[ix_]; \ 00577 return 1; \ 00578 } \ 00579 else \ 00580 { \ 00581 *ptr = 0; \ 00582 return 0; \ 00583 } \ 00584 } \ 00585 \ 00586 static inline size_t VEC_OP (T,embedded_size) \ 00587 (int alloc_) \ 00588 { \ 00589 return offsetof (VEC(T),vec) + alloc_ * sizeof(T); \ 00590 } \ 00591 \ 00592 static inline void VEC_OP (T,embedded_init) \ 00593 (VEC(T) *vec_, int alloc_) \ 00594 { \ 00595 vec_->num = 0; \ 00596 vec_->alloc = alloc_; \ 00597 } \ 00598 \ 00599 static inline int VEC_OP (T,space) \ 00600 (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \ 00601 { \ 00602 vec_assert (alloc_ >= 0, "space"); \ 00603 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ 00604 } \ 00605 \ 00606 static inline T *VEC_OP (T,quick_push) \ 00607 (VEC(T) *vec_, T obj_ VEC_ASSERT_DECL) \ 00608 { \ 00609 T *slot_; \ 00610 \ 00611 vec_assert (vec_->num < vec_->alloc, "quick_push"); \ 00612 slot_ = &vec_->vec[vec_->num++]; \ 00613 *slot_ = obj_; \ 00614 \ 00615 return slot_; \ 00616 } \ 00617 \ 00618 static inline T VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \ 00619 { \ 00620 T obj_; \ 00621 \ 00622 vec_assert (vec_->num, "pop"); \ 00623 obj_ = vec_->vec[--vec_->num]; \ 00624 \ 00625 return obj_; \ 00626 } \ 00627 \ 00628 static inline void VEC_OP (T,truncate) \ 00629 (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \ 00630 { \ 00631 vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \ 00632 if (vec_) \ 00633 vec_->num = size_; \ 00634 } \ 00635 \ 00636 static inline T VEC_OP (T,replace) \ 00637 (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \ 00638 { \ 00639 T old_obj_; \ 00640 \ 00641 vec_assert (ix_ < vec_->num, "replace"); \ 00642 old_obj_ = vec_->vec[ix_]; \ 00643 vec_->vec[ix_] = obj_; \ 00644 \ 00645 return old_obj_; \ 00646 } \ 00647 \ 00648 static inline T *VEC_OP (T,quick_insert) \ 00649 (VEC(T) *vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \ 00650 { \ 00651 T *slot_; \ 00652 \ 00653 vec_assert (vec_->num < vec_->alloc && ix_ <= vec_->num, "quick_insert"); \ 00654 slot_ = &vec_->vec[ix_]; \ 00655 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ 00656 *slot_ = obj_; \ 00657 \ 00658 return slot_; \ 00659 } \ 00660 \ 00661 static inline T VEC_OP (T,ordered_remove) \ 00662 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ 00663 { \ 00664 T *slot_; \ 00665 T obj_; \ 00666 \ 00667 vec_assert (ix_ < vec_->num, "ordered_remove"); \ 00668 slot_ = &vec_->vec[ix_]; \ 00669 obj_ = *slot_; \ 00670 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ 00671 \ 00672 return obj_; \ 00673 } \ 00674 \ 00675 static inline T VEC_OP (T,unordered_remove) \ 00676 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ 00677 { \ 00678 T *slot_; \ 00679 T obj_; \ 00680 \ 00681 vec_assert (ix_ < vec_->num, "unordered_remove"); \ 00682 slot_ = &vec_->vec[ix_]; \ 00683 obj_ = *slot_; \ 00684 *slot_ = vec_->vec[--vec_->num]; \ 00685 \ 00686 return obj_; \ 00687 } \ 00688 \ 00689 static inline void VEC_OP (T,block_remove) \ 00690 (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \ 00691 { \ 00692 T *slot_; \ 00693 \ 00694 vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \ 00695 slot_ = &vec_->vec[ix_]; \ 00696 vec_->num -= len_; \ 00697 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \ 00698 } \ 00699 \ 00700 static inline T *VEC_OP (T,address) \ 00701 (VEC(T) *vec_) \ 00702 { \ 00703 return vec_ ? vec_->vec : 0; \ 00704 } \ 00705 \ 00706 static inline unsigned VEC_OP (T,lower_bound) \ 00707 (VEC(T) *vec_, const T obj_, \ 00708 int (*lessthan_)(const T, const T) VEC_ASSERT_DECL) \ 00709 { \ 00710 unsigned int len_ = VEC_OP (T, length) (vec_); \ 00711 unsigned int half_, middle_; \ 00712 unsigned int first_ = 0; \ 00713 while (len_ > 0) \ 00714 { \ 00715 T middle_elem_; \ 00716 half_ = len_ >> 1; \ 00717 middle_ = first_; \ 00718 middle_ += half_; \ 00719 middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \ 00720 if (lessthan_ (middle_elem_, obj_)) \ 00721 { \ 00722 first_ = middle_; \ 00723 ++first_; \ 00724 len_ = len_ - half_ - 1; \ 00725 } \ 00726 else \ 00727 len_ = half_; \ 00728 } \ 00729 return first_; \ 00730 } 00731 00732 #define DEF_VEC_ALLOC_FUNC_P(T) \ 00733 static inline VEC(T) *VEC_OP (T,alloc) \ 00734 (int alloc_) \ 00735 { \ 00736 /* We must request exact size allocation, hence the negation. */ \ 00737 return (VEC(T) *) vec_p_reserve (NULL, -alloc_); \ 00738 } \ 00739 \ 00740 static inline void VEC_OP (T,free) \ 00741 (VEC(T) **vec_) \ 00742 { \ 00743 if (*vec_) \ 00744 vec_free_ (*vec_); \ 00745 *vec_ = NULL; \ 00746 } \ 00747 \ 00748 static inline void VEC_OP (T,cleanup) \ 00749 (void *arg_) \ 00750 { \ 00751 VEC(T) **vec_ = arg_; \ 00752 if (*vec_) \ 00753 vec_free_ (*vec_); \ 00754 *vec_ = NULL; \ 00755 } \ 00756 \ 00757 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \ 00758 { \ 00759 size_t len_ = vec_ ? vec_->num : 0; \ 00760 VEC (T) *new_vec_ = NULL; \ 00761 \ 00762 if (len_) \ 00763 { \ 00764 /* We must request exact size allocation, hence the negation. */ \ 00765 new_vec_ = (VEC (T) *)(vec_p_reserve (NULL, -len_)); \ 00766 \ 00767 new_vec_->num = len_; \ 00768 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \ 00769 } \ 00770 return new_vec_; \ 00771 } \ 00772 \ 00773 static inline VEC(T) *VEC_OP (T,merge) (VEC(T) *vec1_, VEC(T) *vec2_) \ 00774 { \ 00775 if (vec1_ && vec2_) \ 00776 { \ 00777 size_t len_ = vec1_->num + vec2_->num; \ 00778 VEC (T) *new_vec_ = NULL; \ 00779 \ 00780 /* We must request exact size allocation, hence the negation. */ \ 00781 new_vec_ = (VEC (T) *)(vec_p_reserve (NULL, -len_)); \ 00782 \ 00783 new_vec_->num = len_; \ 00784 memcpy (new_vec_->vec, vec1_->vec, sizeof (T) * vec1_->num); \ 00785 memcpy (new_vec_->vec + vec1_->num, vec2_->vec, \ 00786 sizeof (T) * vec2_->num); \ 00787 \ 00788 return new_vec_; \ 00789 } \ 00790 else \ 00791 return VEC_copy (T, vec1_ ? vec1_ : vec2_); \ 00792 } \ 00793 \ 00794 static inline int VEC_OP (T,reserve) \ 00795 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \ 00796 { \ 00797 int extend = !VEC_OP (T,space) \ 00798 (*vec_, alloc_ < 0 ? -alloc_ : alloc_ VEC_ASSERT_PASS); \ 00799 \ 00800 if (extend) \ 00801 *vec_ = (VEC(T) *) vec_p_reserve (*vec_, alloc_); \ 00802 \ 00803 return extend; \ 00804 } \ 00805 \ 00806 static inline void VEC_OP (T,safe_grow) \ 00807 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \ 00808 { \ 00809 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \ 00810 "safe_grow"); \ 00811 VEC_OP (T,reserve) \ 00812 (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \ 00813 (*vec_)->num = size_; \ 00814 } \ 00815 \ 00816 static inline T *VEC_OP (T,safe_push) \ 00817 (VEC(T) **vec_, T obj_ VEC_ASSERT_DECL) \ 00818 { \ 00819 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ 00820 \ 00821 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \ 00822 } \ 00823 \ 00824 static inline T *VEC_OP (T,safe_insert) \ 00825 (VEC(T) **vec_, unsigned ix_, T obj_ VEC_ASSERT_DECL) \ 00826 { \ 00827 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ 00828 \ 00829 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \ 00830 } 00831 00832 #define DEF_VEC_FUNC_O(T) \ 00833 static inline unsigned VEC_OP (T,length) (const VEC(T) *vec_) \ 00834 { \ 00835 return vec_ ? vec_->num : 0; \ 00836 } \ 00837 \ 00838 static inline T *VEC_OP (T,last) (VEC(T) *vec_ VEC_ASSERT_DECL) \ 00839 { \ 00840 vec_assert (vec_ && vec_->num, "last"); \ 00841 \ 00842 return &vec_->vec[vec_->num - 1]; \ 00843 } \ 00844 \ 00845 static inline T *VEC_OP (T,index) \ 00846 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ 00847 { \ 00848 vec_assert (vec_ && ix_ < vec_->num, "index"); \ 00849 \ 00850 return &vec_->vec[ix_]; \ 00851 } \ 00852 \ 00853 static inline int VEC_OP (T,iterate) \ 00854 (VEC(T) *vec_, unsigned ix_, T **ptr) \ 00855 { \ 00856 if (vec_ && ix_ < vec_->num) \ 00857 { \ 00858 *ptr = &vec_->vec[ix_]; \ 00859 return 1; \ 00860 } \ 00861 else \ 00862 { \ 00863 *ptr = 0; \ 00864 return 0; \ 00865 } \ 00866 } \ 00867 \ 00868 static inline size_t VEC_OP (T,embedded_size) \ 00869 (int alloc_) \ 00870 { \ 00871 return offsetof (VEC(T),vec) + alloc_ * sizeof(T); \ 00872 } \ 00873 \ 00874 static inline void VEC_OP (T,embedded_init) \ 00875 (VEC(T) *vec_, int alloc_) \ 00876 { \ 00877 vec_->num = 0; \ 00878 vec_->alloc = alloc_; \ 00879 } \ 00880 \ 00881 static inline int VEC_OP (T,space) \ 00882 (VEC(T) *vec_, int alloc_ VEC_ASSERT_DECL) \ 00883 { \ 00884 vec_assert (alloc_ >= 0, "space"); \ 00885 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ 00886 } \ 00887 \ 00888 static inline T *VEC_OP (T,quick_push) \ 00889 (VEC(T) *vec_, const T *obj_ VEC_ASSERT_DECL) \ 00890 { \ 00891 T *slot_; \ 00892 \ 00893 vec_assert (vec_->num < vec_->alloc, "quick_push"); \ 00894 slot_ = &vec_->vec[vec_->num++]; \ 00895 if (obj_) \ 00896 *slot_ = *obj_; \ 00897 \ 00898 return slot_; \ 00899 } \ 00900 \ 00901 static inline void VEC_OP (T,pop) (VEC(T) *vec_ VEC_ASSERT_DECL) \ 00902 { \ 00903 vec_assert (vec_->num, "pop"); \ 00904 --vec_->num; \ 00905 } \ 00906 \ 00907 static inline void VEC_OP (T,truncate) \ 00908 (VEC(T) *vec_, unsigned size_ VEC_ASSERT_DECL) \ 00909 { \ 00910 vec_assert (vec_ ? vec_->num >= size_ : !size_, "truncate"); \ 00911 if (vec_) \ 00912 vec_->num = size_; \ 00913 } \ 00914 \ 00915 static inline T *VEC_OP (T,replace) \ 00916 (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \ 00917 { \ 00918 T *slot_; \ 00919 \ 00920 vec_assert (ix_ < vec_->num, "replace"); \ 00921 slot_ = &vec_->vec[ix_]; \ 00922 if (obj_) \ 00923 *slot_ = *obj_; \ 00924 \ 00925 return slot_; \ 00926 } \ 00927 \ 00928 static inline T *VEC_OP (T,quick_insert) \ 00929 (VEC(T) *vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \ 00930 { \ 00931 T *slot_; \ 00932 \ 00933 vec_assert (vec_->num < vec_->alloc && ix_ <= vec_->num, "quick_insert"); \ 00934 slot_ = &vec_->vec[ix_]; \ 00935 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ 00936 if (obj_) \ 00937 *slot_ = *obj_; \ 00938 \ 00939 return slot_; \ 00940 } \ 00941 \ 00942 static inline void VEC_OP (T,ordered_remove) \ 00943 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ 00944 { \ 00945 T *slot_; \ 00946 \ 00947 vec_assert (ix_ < vec_->num, "ordered_remove"); \ 00948 slot_ = &vec_->vec[ix_]; \ 00949 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ 00950 } \ 00951 \ 00952 static inline void VEC_OP (T,unordered_remove) \ 00953 (VEC(T) *vec_, unsigned ix_ VEC_ASSERT_DECL) \ 00954 { \ 00955 vec_assert (ix_ < vec_->num, "unordered_remove"); \ 00956 vec_->vec[ix_] = vec_->vec[--vec_->num]; \ 00957 } \ 00958 \ 00959 static inline void VEC_OP (T,block_remove) \ 00960 (VEC(T) *vec_, unsigned ix_, unsigned len_ VEC_ASSERT_DECL) \ 00961 { \ 00962 T *slot_; \ 00963 \ 00964 vec_assert (ix_ + len_ <= vec_->num, "block_remove"); \ 00965 slot_ = &vec_->vec[ix_]; \ 00966 vec_->num -= len_; \ 00967 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \ 00968 } \ 00969 \ 00970 static inline T *VEC_OP (T,address) \ 00971 (VEC(T) *vec_) \ 00972 { \ 00973 return vec_ ? vec_->vec : 0; \ 00974 } \ 00975 \ 00976 static inline unsigned VEC_OP (T,lower_bound) \ 00977 (VEC(T) *vec_, const T *obj_, \ 00978 int (*lessthan_)(const T *, const T *) VEC_ASSERT_DECL) \ 00979 { \ 00980 unsigned int len_ = VEC_OP (T, length) (vec_); \ 00981 unsigned int half_, middle_; \ 00982 unsigned int first_ = 0; \ 00983 while (len_ > 0) \ 00984 { \ 00985 T *middle_elem_; \ 00986 half_ = len_ >> 1; \ 00987 middle_ = first_; \ 00988 middle_ += half_; \ 00989 middle_elem_ = VEC_OP (T,index) (vec_, middle_ VEC_ASSERT_PASS); \ 00990 if (lessthan_ (middle_elem_, obj_)) \ 00991 { \ 00992 first_ = middle_; \ 00993 ++first_; \ 00994 len_ = len_ - half_ - 1; \ 00995 } \ 00996 else \ 00997 len_ = half_; \ 00998 } \ 00999 return first_; \ 01000 } 01001 01002 #define DEF_VEC_ALLOC_FUNC_O(T) \ 01003 static inline VEC(T) *VEC_OP (T,alloc) \ 01004 (int alloc_) \ 01005 { \ 01006 /* We must request exact size allocation, hence the negation. */ \ 01007 return (VEC(T) *) vec_o_reserve (NULL, -alloc_, \ 01008 offsetof (VEC(T),vec), sizeof (T)); \ 01009 } \ 01010 \ 01011 static inline VEC(T) *VEC_OP (T,copy) (VEC(T) *vec_) \ 01012 { \ 01013 size_t len_ = vec_ ? vec_->num : 0; \ 01014 VEC (T) *new_vec_ = NULL; \ 01015 \ 01016 if (len_) \ 01017 { \ 01018 /* We must request exact size allocation, hence the negation. */ \ 01019 new_vec_ = (VEC (T) *) \ 01020 vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \ 01021 \ 01022 new_vec_->num = len_; \ 01023 memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); \ 01024 } \ 01025 return new_vec_; \ 01026 } \ 01027 \ 01028 static inline VEC(T) *VEC_OP (T,merge) (VEC(T) *vec1_, VEC(T) *vec2_) \ 01029 { \ 01030 if (vec1_ && vec2_) \ 01031 { \ 01032 size_t len_ = vec1_->num + vec2_->num; \ 01033 VEC (T) *new_vec_ = NULL; \ 01034 \ 01035 /* We must request exact size allocation, hence the negation. */ \ 01036 new_vec_ = (VEC (T) *) \ 01037 vec_o_reserve (NULL, -len_, offsetof (VEC(T),vec), sizeof (T)); \ 01038 \ 01039 new_vec_->num = len_; \ 01040 memcpy (new_vec_->vec, vec1_->vec, sizeof (T) * vec1_->num); \ 01041 memcpy (new_vec_->vec + vec1_->num, vec2_->vec, \ 01042 sizeof (T) * vec2_->num); \ 01043 \ 01044 return new_vec_; \ 01045 } \ 01046 else \ 01047 return VEC_copy (T, vec1_ ? vec1_ : vec2_); \ 01048 } \ 01049 \ 01050 static inline void VEC_OP (T,free) \ 01051 (VEC(T) **vec_) \ 01052 { \ 01053 if (*vec_) \ 01054 vec_free_ (*vec_); \ 01055 *vec_ = NULL; \ 01056 } \ 01057 \ 01058 static inline void VEC_OP (T,cleanup) \ 01059 (void *arg_) \ 01060 { \ 01061 VEC(T) **vec_ = arg_; \ 01062 if (*vec_) \ 01063 vec_free_ (*vec_); \ 01064 *vec_ = NULL; \ 01065 } \ 01066 \ 01067 static inline int VEC_OP (T,reserve) \ 01068 (VEC(T) **vec_, int alloc_ VEC_ASSERT_DECL) \ 01069 { \ 01070 int extend = !VEC_OP (T,space) (*vec_, alloc_ < 0 ? -alloc_ : alloc_ \ 01071 VEC_ASSERT_PASS); \ 01072 \ 01073 if (extend) \ 01074 *vec_ = (VEC(T) *) \ 01075 vec_o_reserve (*vec_, alloc_, offsetof (VEC(T),vec), sizeof (T)); \ 01076 \ 01077 return extend; \ 01078 } \ 01079 \ 01080 static inline void VEC_OP (T,safe_grow) \ 01081 (VEC(T) **vec_, int size_ VEC_ASSERT_DECL) \ 01082 { \ 01083 vec_assert (size_ >= 0 && VEC_OP(T,length) (*vec_) <= (unsigned)size_, \ 01084 "safe_grow"); \ 01085 VEC_OP (T,reserve) \ 01086 (vec_, (int)(*vec_ ? (*vec_)->num : 0) - size_ VEC_ASSERT_PASS); \ 01087 (*vec_)->num = size_; \ 01088 } \ 01089 \ 01090 static inline T *VEC_OP (T,safe_push) \ 01091 (VEC(T) **vec_, const T *obj_ VEC_ASSERT_DECL) \ 01092 { \ 01093 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ 01094 \ 01095 return VEC_OP (T,quick_push) (*vec_, obj_ VEC_ASSERT_PASS); \ 01096 } \ 01097 \ 01098 static inline T *VEC_OP (T,safe_insert) \ 01099 (VEC(T) **vec_, unsigned ix_, const T *obj_ VEC_ASSERT_DECL) \ 01100 { \ 01101 VEC_OP (T,reserve) (vec_, 1 VEC_ASSERT_PASS); \ 01102 \ 01103 return VEC_OP (T,quick_insert) (*vec_, ix_, obj_ VEC_ASSERT_PASS); \ 01104 } 01105 01106 #endif /* GDB_VEC_H */
1.7.6.1
