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
34namespace 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