1 | /* |
2 | * PROGRAM: Common class definition |
3 | * MODULE: object_array.h |
4 | * DESCRIPTION: half-static array of any objects, |
5 | * having MemoryPool'ed constructor. |
6 | * |
7 | * The contents of this file are subject to the Initial |
8 | * Developer's Public License Version 1.0 (the "License"); |
9 | * you may not use this file except in compliance with the |
10 | * License. You may obtain a copy of the License at |
11 | * http://www.ibphoenix.com/main.nfs?a=ibphoenix&page=ibp_idpl. |
12 | * |
13 | * Software distributed under the License is distributed AS IS, |
14 | * WITHOUT WARRANTY OF ANY KIND, either express or implied. |
15 | * See the License for the specific language governing rights |
16 | * and limitations under the License. |
17 | * |
18 | * The Original Code was created by Alexander Peshkoff |
19 | * for the Firebird Open Source RDBMS project. |
20 | * |
21 | * Copyright (c) 2004 Alexander Peshkoff <peshkoff@mail.ru> |
22 | * and all contributors signed below. |
23 | * |
24 | * All Rights Reserved. |
25 | * Contributor(s): ______________________________________. |
26 | */ |
27 | |
28 | #ifndef CLASSES_OBJECTS_ARRAY_H |
29 | #define CLASSES_OBJECTS_ARRAY_H |
30 | |
31 | #include "../common/classes/alloc.h" |
32 | #include "../common/classes/array.h" |
33 | |
34 | namespace Firebird |
35 | { |
36 | template <typename T, typename A = Array<T*, InlineStorage<T*, 8> > > |
37 | class ObjectsArray : protected A |
38 | { |
39 | private: |
40 | typedef A inherited; |
41 | public: |
42 | class const_iterator; // fwd decl. |
43 | |
44 | class iterator |
45 | { |
46 | friend class ObjectsArray<T, A>; |
47 | friend class const_iterator; |
48 | private: |
49 | ObjectsArray *lst; |
50 | size_t pos; |
51 | iterator(ObjectsArray *l, size_t p) : lst(l), pos(p) { } |
52 | public: |
53 | iterator() : lst(0), pos(0) { } |
54 | iterator(const iterator& it) : lst(it.lst), pos(it.pos) { } |
55 | |
56 | iterator& operator++() |
57 | { |
58 | ++pos; |
59 | return (*this); |
60 | } |
61 | iterator operator++(int) |
62 | { |
63 | iterator tmp = *this; |
64 | ++pos; |
65 | return tmp; |
66 | } |
67 | iterator& operator--() |
68 | { |
69 | fb_assert(pos > 0); |
70 | --pos; |
71 | return (*this); |
72 | } |
73 | iterator operator--(int) |
74 | { |
75 | fb_assert(pos > 0); |
76 | iterator tmp = *this; |
77 | --pos; |
78 | return tmp; |
79 | } |
80 | T* operator->() |
81 | { |
82 | fb_assert(lst); |
83 | T* pointer = lst->getPointer(pos); |
84 | return pointer; |
85 | } |
86 | T& operator*() |
87 | { |
88 | fb_assert(lst); |
89 | T* pointer = lst->getPointer(pos); |
90 | return *pointer; |
91 | } |
92 | bool operator!=(const iterator& v) const |
93 | { |
94 | fb_assert(lst == v.lst); |
95 | return lst ? pos != v.pos : true; |
96 | } |
97 | bool operator==(const iterator& v) const |
98 | { |
99 | fb_assert(lst == v.lst); |
100 | return lst ? pos == v.pos : false; |
101 | } |
102 | }; |
103 | |
104 | class const_iterator |
105 | { |
106 | friend class ObjectsArray<T, A>; |
107 | private: |
108 | const ObjectsArray *lst; |
109 | size_t pos; |
110 | const_iterator(const ObjectsArray *l, size_t p) : lst(l), pos(p) { } |
111 | public: |
112 | const_iterator() : lst(0), pos(0) { } |
113 | const_iterator(const iterator& it) : lst(it.lst), pos(it.pos) { } |
114 | const_iterator(const const_iterator& it) : lst(it.lst), pos(it.pos) { } |
115 | |
116 | const_iterator& operator++() |
117 | { |
118 | ++pos; |
119 | return (*this); |
120 | } |
121 | const_iterator operator++(int) |
122 | { |
123 | const_iterator tmp = *this; |
124 | ++pos; |
125 | return tmp; |
126 | } |
127 | const_iterator& operator--() |
128 | { |
129 | fb_assert(pos > 0); |
130 | --pos; |
131 | return (*this); |
132 | } |
133 | const_iterator operator--(int) |
134 | { |
135 | fb_assert(pos > 0); |
136 | const_iterator tmp = *this; |
137 | --pos; |
138 | return tmp; |
139 | } |
140 | const T* operator->() |
141 | { |
142 | fb_assert(lst); |
143 | const T* pointer = lst->getPointer(pos); |
144 | return pointer; |
145 | } |
146 | const T& operator*() |
147 | { |
148 | fb_assert(lst); |
149 | const T* pointer = lst->getPointer(pos); |
150 | return *pointer; |
151 | } |
152 | bool operator!=(const const_iterator& v) const |
153 | { |
154 | fb_assert(lst == v.lst); |
155 | return lst ? pos != v.pos : true; |
156 | } |
157 | bool operator==(const const_iterator& v) const |
158 | { |
159 | fb_assert(lst == v.lst); |
160 | return lst ? pos == v.pos : false; |
161 | } |
162 | // Against iterator |
163 | bool operator!=(const iterator& v) const |
164 | { |
165 | fb_assert(lst == v.lst); |
166 | return lst ? pos != v.pos : true; |
167 | } |
168 | bool operator==(const iterator& v) const |
169 | { |
170 | fb_assert(lst == v.lst); |
171 | return lst ? pos == v.pos : false; |
172 | } |
173 | |
174 | }; |
175 | |
176 | public: |
177 | void insert(size_t index, const T& item) |
178 | { |
179 | T* dataL = FB_NEW(this->getPool()) T(this->getPool(), item); |
180 | inherited::insert(index, dataL); |
181 | } |
182 | T& insert(size_t index) |
183 | { |
184 | T* dataL = FB_NEW(this->getPool()) T(this->getPool()); |
185 | inherited::insert(index, dataL); |
186 | return *dataL; |
187 | } |
188 | size_t add(const T& item) |
189 | { |
190 | T* dataL = FB_NEW(this->getPool()) T(this->getPool(), item); |
191 | return inherited::add(dataL); |
192 | } |
193 | T& add() |
194 | { |
195 | T* dataL = FB_NEW(this->getPool()) T(this->getPool()); |
196 | inherited::add(dataL); |
197 | return *dataL; |
198 | } |
199 | void push(const T& item) |
200 | { |
201 | add(item); |
202 | } |
203 | T pop() |
204 | { |
205 | T* pntr = inherited::pop(); |
206 | T rc = *pntr; |
207 | delete pntr; |
208 | return rc; |
209 | } |
210 | void remove(size_t index) |
211 | { |
212 | fb_assert(index < getCount()); |
213 | delete getPointer(index); |
214 | inherited::remove(index); |
215 | } |
216 | void remove(iterator itr) |
217 | { |
218 | fb_assert(itr.lst == this); |
219 | remove(itr.pos); |
220 | } |
221 | void shrink(size_t newCount) |
222 | { |
223 | for (size_t i = newCount; i < getCount(); i++) { |
224 | delete getPointer(i); |
225 | } |
226 | inherited::shrink(newCount); |
227 | } |
228 | void grow(size_t newCount) |
229 | { |
230 | size_t oldCount = getCount(); |
231 | inherited::grow(newCount); |
232 | for (size_t i = oldCount; i < newCount; i++) { |
233 | inherited::getElement(i) = FB_NEW(this->getPool()) T(this->getPool()); |
234 | } |
235 | } |
236 | void resize(const size_t newCount, const T& val) |
237 | { |
238 | if (newCount > getCount()) |
239 | { |
240 | size_t oldCount = getCount(); |
241 | inherited::grow(newCount); |
242 | for (size_t i = oldCount; i < newCount; i++) { |
243 | inherited::getElement(i) = FB_NEW(this->getPool()) T(this->getPool(), val); |
244 | } |
245 | } |
246 | else { |
247 | shrink(newCount); |
248 | } |
249 | } |
250 | void resize(const size_t newCount) |
251 | { |
252 | if (newCount > getCount()) |
253 | { |
254 | grow(newCount); |
255 | } |
256 | else { |
257 | shrink(newCount); |
258 | } |
259 | } |
260 | iterator begin() |
261 | { |
262 | return iterator(this, 0); |
263 | } |
264 | iterator end() |
265 | { |
266 | return iterator(this, getCount()); |
267 | } |
268 | iterator back() |
269 | { |
270 | fb_assert(getCount() > 0); |
271 | return iterator(this, getCount() - 1); |
272 | } |
273 | const_iterator begin() const |
274 | { |
275 | return const_iterator(this, 0); |
276 | } |
277 | const_iterator end() const |
278 | { |
279 | return const_iterator(this, getCount()); |
280 | } |
281 | const T& operator[](size_t index) const |
282 | { |
283 | return *getPointer(index); |
284 | } |
285 | const T* getPointer(size_t index) const |
286 | { |
287 | return inherited::getElement(index); |
288 | } |
289 | T& operator[](size_t index) |
290 | { |
291 | return *getPointer(index); |
292 | } |
293 | T* getPointer(size_t index) |
294 | { |
295 | return inherited::getElement(index); |
296 | } |
297 | explicit ObjectsArray(MemoryPool& p) : A(p) { } |
298 | ObjectsArray() : A() { } |
299 | ~ObjectsArray() |
300 | { |
301 | for (size_t i = 0; i < getCount(); i++) { |
302 | delete getPointer(i); |
303 | } |
304 | } |
305 | |
306 | size_t getCount() const {return inherited::getCount();} |
307 | size_t getCapacity() const {return inherited::getCapacity();} |
308 | |
309 | bool hasData() const |
310 | { |
311 | return getCount() != 0; |
312 | } |
313 | |
314 | bool isEmpty() const |
315 | { |
316 | return getCount() == 0; |
317 | } |
318 | |
319 | void clear() |
320 | { |
321 | for (size_t i = 0; i < getCount(); i++) { |
322 | delete getPointer(i); |
323 | } |
324 | inherited::clear(); |
325 | } |
326 | ObjectsArray<T, A>& operator =(const ObjectsArray<T, A>& L) |
327 | { |
328 | while (this->count > L.count) |
329 | { |
330 | delete inherited::pop(); |
331 | } |
332 | for (size_t i = 0; i < L.count; i++) |
333 | { |
334 | if (i < this->count) |
335 | { |
336 | (*this)[i] = L[i]; |
337 | } |
338 | else |
339 | { |
340 | add(L[i]); |
341 | } |
342 | } |
343 | return *this; |
344 | } |
345 | }; |
346 | |
347 | // Template to convert object value to index directly |
348 | template <typename T> |
349 | class ObjectKeyValue |
350 | { |
351 | public: |
352 | static const T& generate(const T* item) { return item; } |
353 | }; |
354 | |
355 | // Template for default value comparator |
356 | template <typename T> |
357 | class ObjectComparator |
358 | { |
359 | public: |
360 | static bool greaterThan(const T i1, const T i2) |
361 | { |
362 | return *i1 > *i2; |
363 | } |
364 | }; |
365 | |
366 | // Dynamic sorted array of simple objects |
367 | template <typename ObjectValue, |
368 | typename ObjectStorage = InlineStorage<ObjectValue*, 32>, |
369 | typename ObjectKey = ObjectValue, |
370 | typename ObjectKeyOfValue = DefaultKeyValue<ObjectValue*>, |
371 | typename ObjectCmp = ObjectComparator<const ObjectKey*> > |
372 | class SortedObjectsArray : public ObjectsArray<ObjectValue, |
373 | SortedArray <ObjectValue*, ObjectStorage, const ObjectKey*, |
374 | ObjectKeyOfValue, ObjectCmp> > |
375 | { |
376 | private: |
377 | typedef ObjectsArray <ObjectValue, SortedArray<ObjectValue*, |
378 | ObjectStorage, const ObjectKey*, ObjectKeyOfValue, |
379 | ObjectCmp> > inherited; |
380 | |
381 | public: |
382 | explicit SortedObjectsArray(MemoryPool& p) : |
383 | ObjectsArray <ObjectValue, SortedArray<ObjectValue*, |
384 | ObjectStorage, const ObjectKey*, ObjectKeyOfValue, |
385 | ObjectCmp> >(p) |
386 | { } |
387 | |
388 | bool find(const ObjectKey& item, size_t& pos) const |
389 | { |
390 | const ObjectKey* const pItem = &item; |
391 | return static_cast<const SortedArray<ObjectValue*, |
392 | ObjectStorage, const ObjectKey*, ObjectKeyOfValue, |
393 | ObjectCmp>*>(this)->find(pItem, pos); |
394 | } |
395 | |
396 | bool exist(const ObjectKey& item) const |
397 | { |
398 | size_t pos; // ignored |
399 | return find(item, pos); |
400 | } |
401 | |
402 | size_t add(const ObjectValue& item) |
403 | { |
404 | return inherited::add(item); |
405 | } |
406 | |
407 | void setSortMode(int sm) |
408 | { |
409 | inherited::setSortMode(sm); |
410 | } |
411 | |
412 | void sort() |
413 | { |
414 | inherited::sort(); |
415 | } |
416 | |
417 | private: |
418 | ObjectValue& add(); // Unusable when sorted |
419 | }; |
420 | |
421 | // Sorted pointers array - contains 2 arrays: simple for values (POD) |
422 | // and sorted for pointers to them. Effective for big sizeof(POD). |
423 | template <typename Value, |
424 | typename Storage = EmptyStorage<Value>, |
425 | typename Key = Value, |
426 | typename KeyOfValue = DefaultKeyValue<Value*>, |
427 | typename Cmp = ObjectComparator<const Key*> > |
428 | class PointersArray |
429 | { |
430 | private: |
431 | Array<Value, Storage> values; |
432 | SortedArray<Value*, InlineStorage<Value*, 8>, const Key*, KeyOfValue, Cmp> pointers; |
433 | |
434 | void checkPointers(const Value* oldBegin) |
435 | { |
436 | Value* newBegin = values.begin(); |
437 | if (newBegin != oldBegin) |
438 | { |
439 | for (Value** ptr = pointers.begin(); ptr < pointers.end(); ++ptr) |
440 | { |
441 | *ptr = newBegin + (*ptr - oldBegin); |
442 | } |
443 | } |
444 | } |
445 | |
446 | public: |
447 | class const_iterator |
448 | { |
449 | private: |
450 | const Value* const* ptr; |
451 | |
452 | public: |
453 | const_iterator() : ptr(NULL) { } |
454 | const_iterator(const const_iterator& it) : ptr(it.ptr) { } |
455 | explicit const_iterator(const PointersArray& a) : ptr(a.pointers.begin()) { } |
456 | |
457 | const_iterator& operator++() |
458 | { |
459 | fb_assert(ptr); |
460 | ptr++; |
461 | return *this; |
462 | } |
463 | |
464 | const_iterator operator++(int) |
465 | { |
466 | fb_assert(ptr); |
467 | const_iterator tmp = *this; |
468 | ptr++; |
469 | return tmp; |
470 | } |
471 | |
472 | const_iterator& operator--() |
473 | { |
474 | fb_assert(ptr); |
475 | ptr--; |
476 | return *this; |
477 | } |
478 | |
479 | const_iterator operator--(int) |
480 | { |
481 | fb_assert(ptr); |
482 | const_iterator tmp = *this; |
483 | ptr--; |
484 | return tmp; |
485 | } |
486 | |
487 | const_iterator& operator+=(size_t v) |
488 | { |
489 | fb_assert(ptr); |
490 | ptr += v; |
491 | return *this; |
492 | } |
493 | |
494 | const_iterator& operator-=(size_t v) |
495 | { |
496 | fb_assert(ptr); |
497 | ptr -= v; |
498 | return *this; |
499 | } |
500 | |
501 | const Value* operator->() |
502 | { |
503 | fb_assert(ptr); |
504 | return *ptr; |
505 | } |
506 | |
507 | const Value& operator*() |
508 | { |
509 | fb_assert(ptr && *ptr); |
510 | return **ptr; |
511 | } |
512 | |
513 | bool operator==(const const_iterator& v) const |
514 | { |
515 | return ptr && ptr == v.ptr; |
516 | } |
517 | |
518 | bool operator!=(const const_iterator& v) const |
519 | { |
520 | return !operator==(v); |
521 | } |
522 | }; |
523 | |
524 | class iterator |
525 | { |
526 | private: |
527 | Value** ptr; |
528 | |
529 | public: |
530 | iterator() : ptr(NULL) { } |
531 | iterator(const iterator& it) : ptr(it.ptr) { } |
532 | explicit iterator(PointersArray& a) : ptr(a.pointers.begin()) { } |
533 | |
534 | iterator& operator++() |
535 | { |
536 | fb_assert(ptr); |
537 | ptr++; |
538 | return *this; |
539 | } |
540 | |
541 | iterator operator++(int) |
542 | { |
543 | fb_assert(ptr); |
544 | iterator tmp = *this; |
545 | ptr++; |
546 | return tmp; |
547 | } |
548 | |
549 | iterator& operator--() |
550 | { |
551 | fb_assert(ptr); |
552 | ptr--; |
553 | return *this; |
554 | } |
555 | |
556 | iterator operator--(int) |
557 | { |
558 | fb_assert(ptr); |
559 | iterator tmp = *this; |
560 | ptr--; |
561 | return tmp; |
562 | } |
563 | |
564 | iterator& operator+=(size_t v) |
565 | { |
566 | fb_assert(ptr); |
567 | ptr += v; |
568 | return *this; |
569 | } |
570 | |
571 | iterator& operator-=(size_t v) |
572 | { |
573 | fb_assert(ptr); |
574 | ptr -= v; |
575 | return *this; |
576 | } |
577 | |
578 | Value* operator->() |
579 | { |
580 | fb_assert(ptr); |
581 | return *ptr; |
582 | } |
583 | |
584 | Value& operator*() |
585 | { |
586 | fb_assert(ptr && *ptr); |
587 | return **ptr; |
588 | } |
589 | |
590 | bool operator==(const iterator& v) const |
591 | { |
592 | return ptr && ptr == v.ptr; |
593 | } |
594 | |
595 | bool operator!=(const iterator& v) const |
596 | { |
597 | return !operator==(v); |
598 | } |
599 | }; |
600 | |
601 | public: |
602 | size_t add(const Value& item) |
603 | { |
604 | const Value* oldBegin = values.begin(); |
605 | values.add(item); |
606 | checkPointers(oldBegin); |
607 | return pointers.add(values.end() - 1); |
608 | } |
609 | |
610 | const_iterator begin() const |
611 | { |
612 | return const_iterator(*this); |
613 | } |
614 | |
615 | const_iterator end() const |
616 | { |
617 | const_iterator rc(*this); |
618 | rc += getCount(); |
619 | return rc; |
620 | } |
621 | |
622 | iterator begin() |
623 | { |
624 | return iterator(*this); |
625 | } |
626 | |
627 | iterator end() |
628 | { |
629 | iterator rc(*this); |
630 | rc += getCount(); |
631 | return rc; |
632 | } |
633 | |
634 | const Value& operator[](size_t index) const |
635 | { |
636 | return *getPointer(index); |
637 | } |
638 | |
639 | const Value* getPointer(size_t index) const |
640 | { |
641 | return pointers[index]; |
642 | } |
643 | |
644 | Value& operator[](size_t index) |
645 | { |
646 | return *getPointer(index); |
647 | } |
648 | |
649 | Value* getPointer(size_t index) |
650 | { |
651 | return pointers[index]; |
652 | } |
653 | |
654 | explicit PointersArray(MemoryPool& p) : values(p), pointers(p) { } |
655 | PointersArray() : values(), pointers() { } |
656 | ~PointersArray() { } |
657 | |
658 | size_t getCount() const |
659 | { |
660 | fb_assert(values.getCount() == pointers.getCount()); |
661 | return values.getCount(); |
662 | } |
663 | |
664 | size_t getCapacity() const |
665 | { |
666 | return values.getCapacity(); |
667 | } |
668 | |
669 | void clear() |
670 | { |
671 | pointers.clear(); |
672 | values.clear(); |
673 | } |
674 | |
675 | PointersArray& operator=(const PointersArray& o) |
676 | { |
677 | values = o.values; |
678 | pointers = o.pointers; |
679 | checkPointers(o.values.begin()); |
680 | return *this; |
681 | } |
682 | |
683 | bool find(const Key& item, size_t& pos) const |
684 | { |
685 | return pointers.find(&item, pos); |
686 | } |
687 | |
688 | bool exist(const Key& item) const |
689 | { |
690 | return pointers.exist(item); |
691 | } |
692 | |
693 | void insert(size_t pos, const Value& item) |
694 | { |
695 | const Value* oldBegin = values.begin(); |
696 | values.add(item); |
697 | checkPointers(oldBegin); |
698 | pointers.insert(pos, values.end() - 1); |
699 | } |
700 | }; |
701 | |
702 | } // namespace Firebird |
703 | |
704 | #endif // CLASSES_OBJECTS_ARRAY_H |
705 | |