Annotation of parser3/src/include/pa_array.h, revision 1.106
1.24 paf 1: /** @file
1.59 paf 2: Parser: Array & Array_iterator classes decls.
1.26 paf 3:
1.100 moko 4: Copyright (c) 2001-2024 Art. Lebedev Studio (http://www.artlebedev.com)
1.87 moko 5: Authors: Konstantin Morshnev <moko@design.ru>, Alexandr Petrosian <paf@design.ru>
1.1 paf 6: */
7:
1.24 paf 8: #ifndef PA_ARRAY_H
9: #define PA_ARRAY_H
1.54 paf 10:
1.106 ! moko 11: #define IDENT_PA_ARRAY_H "$Id: pa_array.h,v 1.105 2025/08/01 16:14:44 moko Exp $"
1.24 paf 12:
1.59 paf 13: // includes
14:
15: #include "pa_memory.h"
1.90 moko 16: #include "pa_types.h"
1.106 ! moko 17: #include "pa_int.h"
1.59 paf 18: #include "pa_exception.h"
19:
20: // forwards
21:
22: template<typename T> class Array_iterator;
1.101 moko 23: template<typename T> class Array_robust_iterator;
1.90 moko 24: template<typename T> class Array_reverse_iterator;
1.59 paf 25:
26: // defines
27:
28: #define ARRAY_OPTION_LIMIT_ALL ((size_t)-1)
29:
30: /// Simple Array
31: template<typename T> class Array: public PA_Object {
32:
33: friend class Array_iterator<T>;
1.101 moko 34: friend class Array_robust_iterator<T>;
1.90 moko 35: friend class Array_reverse_iterator<T>;
1.59 paf 36:
37: protected:
38:
39: /// elements[growing size] here
40: T *felements;
41:
42: // allocated size
43: size_t fallocated;
44:
45: // array size
1.94 moko 46: size_t fsize;
1.1 paf 47:
48: public:
1.88 moko 49: typedef Array_iterator<T> Iterator;
1.101 moko 50: typedef Array_robust_iterator<T> RobustIterator;
1.90 moko 51: typedef Array_reverse_iterator<T> ReverseIterator;
1.88 moko 52:
1.59 paf 53: struct Action_options {
54: size_t offset;
55: size_t limit; //< ARRAY_OPTION_LIMIT_ALL means 'all'. zero limit means 'nothing'
56: bool reverse;
57: bool defined;
58:
59: Action_options(
1.95 moko 60: size_t aoffset=0,
61: size_t alimit=ARRAY_OPTION_LIMIT_ALL,
62: bool areverse=false):
1.59 paf 63: offset(aoffset), limit(alimit), reverse(areverse),
64: defined(false) {}
65:
66: bool adjust(size_t count) {
67: if(!count || !limit)
68: return false;
1.70 misha 69: if(offset>=count)
1.59 paf 70: return false;
71: // max(limit)
72: size_t m=reverse?
1.69 misha 73: offset+1
1.59 paf 74: :count-offset;
75: if(!m)
76: return false;
77: // fix limit
1.95 moko 78: if(limit>m)
1.59 paf 79: limit=m;
1.7 paf 80:
1.59 paf 81: return true;
82: }
1.1 paf 83: };
84:
1.59 paf 85: typedef T element_type;
86:
1.71 misha 87: inline Array(size_t initial=0):
88: fallocated(initial),
1.94 moko 89: fsize(0)
1.59 paf 90: {
1.77 misha 91: felements=fallocated?(T *)pa_malloc(fallocated*sizeof(T)):0;
1.59 paf 92: }
1.6 paf 93:
1.92 moko 94: #ifdef USE_DESTRUCTORS
1.73 misha 95: inline ~Array(){
1.75 misha 96: if(felements)
1.77 misha 97: pa_free(felements);
1.72 misha 98: }
1.74 misha 99: #endif
1.72 misha 100:
1.59 paf 101: /// how many items are in Array
1.94 moko 102: inline size_t count() const { return fsize; }
1.92 moko 103:
1.59 paf 104: /// append to array
1.71 misha 105: inline Array& operator+=(T src) {
1.59 paf 106: if(is_full())
1.93 moko 107: expand();
1.7 paf 108:
1.94 moko 109: felements[fsize++]=src;
1.24 paf 110:
1.59 paf 111: return *this;
112: }
1.24 paf 113:
114: /// append other Array portion to this one. starting from offset
1.98 moko 115: void append(const Array& src, size_t offset=0, size_t limit=ARRAY_OPTION_LIMIT_ALL) { //< zero limit means 'nothing'
1.59 paf 116: size_t src_count=src.count();
117: // skip tivials
118: if(!src_count || !limit || offset>=src_count)
1.98 moko 119: return;
1.59 paf 120: // max(limit)
1.82 moko 121: size_t m=src_count-offset;
1.59 paf 122: // fix limit
1.95 moko 123: if(limit>m)
1.59 paf 124: limit=m;
125:
1.94 moko 126: fit(fsize-1+limit);
1.98 moko 127: memcpy(felements+fsize, src.felements+offset, limit * sizeof(T));
1.94 moko 128: fsize+=limit;
1.59 paf 129: }
130:
131: /// get index-element
1.71 misha 132: inline T get(size_t index) const {
1.63 paf 133: assert(index<count());
1.59 paf 134: return felements[index];
135: }
136:
137: /// ref version of get
1.71 misha 138: inline T& get_ref(size_t index) const {
1.63 paf 139: assert(index<count());
1.59 paf 140: return felements[index];
141: }
142:
143: /// put index-element
1.71 misha 144: inline void put(size_t index, T element) {
1.63 paf 145: assert(index<count());
1.59 paf 146: felements[index]=element;
147: }
148:
1.82 moko 149: /// insert index-element
150: inline void insert(size_t index, T element) {
151: assert(index<=count());
152:
153: if(is_full())
1.93 moko 154: expand();
1.82 moko 155:
1.94 moko 156: memmove(felements+index+1, felements+index, (fsize-index) * sizeof(T));
1.82 moko 157:
158: felements[index]=element;
1.94 moko 159: fsize++;
1.82 moko 160: }
161:
1.80 moko 162: /// remove index-element
163: inline void remove(size_t index) {
164: assert(index<count());
1.94 moko 165: if (index<--fsize)
166: memmove(felements+index, felements+index+1, (fsize-index) * sizeof(T));
1.80 moko 167: }
168:
1.71 misha 169: inline T operator [](size_t index) const { return get(index); }
1.29 paf 170:
1.84 moko 171: inline void clear() {
1.94 moko 172: if(fsize)
1.102 moko 173: memset((void *)felements, 0, fsize * sizeof(T));
1.94 moko 174: fsize=0;
1.84 moko 175: }
176:
1.29 paf 177: /// iterate over all elements
1.59 paf 178: template<typename I> void for_each(void (*callback)(T, I), I info) const {
1.94 moko 179: T *last=felements+fsize;
1.60 paf 180: for(T *current=felements; current<last; current++)
181: callback(*current, info);
182: }
183:
184: /// iterate over all elements
1.68 paf 185: template<typename I> void for_each(bool (*callback)(T, I), I info) const {
1.94 moko 186: T *last=felements+fsize;
1.68 paf 187: for(T *current=felements; current<last; current++)
188: if(callback(*current, info))
189: return;
190: }
191:
192: /// iterate over all elements
1.60 paf 193: template<typename I> void for_each_ref(void (*callback)(T&, I), I info) {
1.94 moko 194: T *last=felements+fsize;
1.59 paf 195: for(T *current=felements; current<last; current++)
196: callback(*current, info);
197: }
1.49 paf 198:
1.59 paf 199: /// iterate over all elements until condition becomes true, return that element
200: template<typename I> T first_that(bool (*callback)(T, I), I info) const {
1.94 moko 201: T *last=felements+fsize;
1.59 paf 202: for(T *current=felements; current<last; current++)
203: if(callback(*current, info))
204: return *current;
1.1 paf 205:
1.59 paf 206: return T(0);
207: }
1.1 paf 208:
1.76 misha 209: inline T* ptr(size_t index){
210: return felements + index;
211: }
212:
1.59 paf 213: protected:
1.1 paf 214:
1.94 moko 215: inline bool is_full() {
216: return fsize == fallocated;
1.59 paf 217: }
1.88 moko 218:
1.93 moko 219: inline void expand() {
1.96 moko 220: resize(fallocated>0 ? fallocated+fallocated/2+2 : 3); // 3 is PAF default, confirmed by tests
1.93 moko 221: }
222:
1.94 moko 223: inline void fit(size_t index){
224: if(index >= fallocated)
1.99 moko 225: resize(max(fallocated+fallocated/4, index+1));
1.94 moko 226: }
227:
1.93 moko 228: void resize(size_t asize) {
1.71 misha 229: if(fallocated){
1.93 moko 230: felements=(T *)pa_realloc(felements, asize*sizeof(T));
1.105 moko 231: #ifdef PA_DEBUG_DISABLE_GC
232: // non-gc realloc doesn't zero; manually zero expanded region
233: if(asize > fallocated)
234: memset((void *)(felements+fallocated), 0, (asize-fallocated) * sizeof(T));
235: #endif
1.93 moko 236: fallocated=asize;
1.71 misha 237: } else {
1.93 moko 238: fallocated=asize;
239: felements=(T *)pa_malloc(asize*sizeof(T));
1.71 misha 240: }
1.1 paf 241: }
1.2 paf 242:
1.1 paf 243: private: //disabled
244:
1.59 paf 245: Array(const Array&) {}
1.12 paf 246: Array& operator = (const Array&) { return *this; }
1.42 parser 247: };
248:
1.92 moko 249:
1.59 paf 250: /** Array iterator, usage:
251: @code
252: // Array<T> a;
1.89 moko 253: for(Array_iterator<T> i(a); i; ) {
1.59 paf 254: T& element=i.next();
255: ...
256: }
257: @endcode
258: */
259: template<typename T> class Array_iterator {
260:
261: const Array<T>& farray;
262: T *fcurrent;
263: T *flast;
264:
1.42 parser 265: public:
1.59 paf 266: Array_iterator(const Array<T>& aarray): farray(aarray) {
267: fcurrent=farray.felements;
1.94 moko 268: flast=farray.felements + farray.fsize;
1.42 parser 269: }
270:
271: /// there are still elements
1.90 moko 272: inline operator bool () {
273: return fcurrent < flast;
1.42 parser 274: }
275:
1.88 moko 276: /// returns the current element and advances the iterator
1.90 moko 277: inline T next() {
1.59 paf 278: return *(fcurrent++);
279: }
280:
1.88 moko 281: /// returns the current element
1.90 moko 282: inline T value() {
1.88 moko 283: return *(fcurrent);
284: }
285:
286: // returns the current index of the iterator
1.90 moko 287: inline size_t index() {
1.88 moko 288: return fcurrent - farray.felements;
289: }
1.101 moko 290: };
291:
292: // Slower array iterator for arrays that can be modified during iteration
293: template<typename T> class Array_robust_iterator {
294:
295: const Array<T>& farray;
296: size_t findex;
297:
298: public:
299: Array_robust_iterator(const Array<T>& aarray) : farray(aarray), findex(0) {}
300:
301: inline operator bool() {
302: return findex < farray.fsize;
303: }
304:
305: inline void next() {
306: findex++;
307: }
308:
309: inline T value() {
310: return farray.felements[findex];
311: }
312:
313: inline size_t index() {
314: return findex;
315: }
1.90 moko 316: };
317:
1.101 moko 318: // Robust as used for arrays that can be modified during iteration
1.90 moko 319: template<typename T> class Array_reverse_iterator {
320:
321: const Array<T>& farray;
1.101 moko 322: size_t findex;
1.90 moko 323:
324: public:
1.101 moko 325: Array_reverse_iterator(const Array<T>& aarray): farray(aarray), findex(aarray.fsize) {}
1.90 moko 326:
327: inline operator bool () {
1.101 moko 328: return (findex > 0) && (findex <= farray.fsize);
1.90 moko 329: }
330:
331: inline T prev() {
1.101 moko 332: return farray.felements[--findex];
1.90 moko 333: }
334:
335: inline size_t index() {
1.101 moko 336: return findex;
1.90 moko 337: }
1.59 paf 338: };
1.1 paf 339: #endif
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to pa_array.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / parser3 / src / include