1 | /* |
2 | * PROGRAM: Client/Server Common Code |
3 | * MODULE: array.h |
4 | * DESCRIPTION: dynamic array of simple elements |
5 | * |
6 | * The contents of this file are subject to the Interbase Public |
7 | * License Version 1.0 (the "License"); you may not use this file |
8 | * except in compliance with the License. You may obtain a copy |
9 | * of the License at http://www.Inprise.com/IPL.html |
10 | * |
11 | * Software distributed under the License is distributed on an |
12 | * "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, either express |
13 | * or implied. See the License for the specific language governing |
14 | * rights and limitations under the License. |
15 | * |
16 | * The Original Code was created by Inprise Corporation |
17 | * and its predecessors. Portions created by Inprise Corporation are |
18 | * Copyright (C) Inprise Corporation. |
19 | * |
20 | * Created by: Alex Peshkov <peshkoff@mail.ru> |
21 | * |
22 | * All Rights Reserved. |
23 | * Contributor(s): ______________________________________. |
24 | * Adriano dos Santos Fernandes |
25 | */ |
26 | |
27 | #ifndef CLASSES_ARRAY_H |
28 | #define CLASSES_ARRAY_H |
29 | |
30 | #include "../common/gdsassert.h" |
31 | #include <string.h> |
32 | #include "../common/classes/vector.h" |
33 | #include "../common/classes/alloc.h" |
34 | |
35 | namespace Firebird { |
36 | |
37 | const size_t FB_MAX_SIZEOF = ~size_t(0); |
38 | const size_t FB_HALF_MAX_SIZEOF = FB_MAX_SIZEOF >> 1; |
39 | |
40 | // Static part of the array |
41 | template <typename T, size_t Capacity> |
42 | class InlineStorage : public AutoStorage |
43 | { |
44 | public: |
45 | explicit InlineStorage(MemoryPool& p) : AutoStorage(p) { } |
46 | InlineStorage() : AutoStorage() { } |
47 | protected: |
48 | T* getStorage() |
49 | { |
50 | return buffer; |
51 | } |
52 | size_t getStorageSize() const |
53 | { |
54 | return Capacity; |
55 | } |
56 | private: |
57 | T buffer[Capacity]; |
58 | }; |
59 | |
60 | // Used when array doesn't have static part |
61 | template <typename T> |
62 | class EmptyStorage : public AutoStorage |
63 | { |
64 | public: |
65 | explicit EmptyStorage(MemoryPool& p) : AutoStorage(p) { } |
66 | EmptyStorage() : AutoStorage() { } |
67 | protected: |
68 | T* getStorage() { return NULL; } |
69 | size_t getStorageSize() const { return 0; } |
70 | }; |
71 | |
72 | // Dynamic array of simple types |
73 | template <typename T, typename Storage = EmptyStorage<T> > |
74 | class Array : protected Storage |
75 | { |
76 | public: |
77 | explicit Array(MemoryPool& p) |
78 | : Storage(p), count(0), capacity(this->getStorageSize()), data(this->getStorage()) |
79 | { |
80 | // Ensure we can carry byte copy operations. |
81 | fb_assert(capacity < FB_MAX_SIZEOF / sizeof(T)); |
82 | } |
83 | |
84 | Array(MemoryPool& p, const size_t InitialCapacity) |
85 | : Storage(p), count(0), capacity(this->getStorageSize()), data(this->getStorage()) |
86 | { |
87 | ensureCapacity(InitialCapacity); |
88 | } |
89 | |
90 | Array() : count(0), |
91 | capacity(this->getStorageSize()), data(this->getStorage()) { } |
92 | explicit Array(const size_t InitialCapacity) |
93 | : Storage(), count(0), capacity(this->getStorageSize()), data(this->getStorage()) |
94 | { |
95 | ensureCapacity(InitialCapacity); |
96 | } |
97 | |
98 | Array(const Array<T, Storage>& source) |
99 | : Storage(), count(0), capacity(this->getStorageSize()), data(this->getStorage()) |
100 | { |
101 | copyFrom(source); |
102 | } |
103 | |
104 | ~Array() |
105 | { |
106 | freeData(); |
107 | } |
108 | |
109 | void clear() throw() |
110 | { |
111 | count = 0; |
112 | } |
113 | |
114 | protected: |
115 | const T& getElement(size_t index) const throw() |
116 | { |
117 | fb_assert(index < count); |
118 | return data[index]; |
119 | } |
120 | |
121 | T& getElement(size_t index) throw() |
122 | { |
123 | fb_assert(index < count); |
124 | return data[index]; |
125 | } |
126 | |
127 | void freeData() |
128 | { |
129 | // CVC: Warning, after this call, "data" is an invalid pointer, be sure to reassign it |
130 | // or make it equal to this->getStorage() |
131 | if (data != this->getStorage()) |
132 | this->getPool().deallocate(data); |
133 | } |
134 | |
135 | void copyFrom(const Array<T, Storage>& source) |
136 | { |
137 | ensureCapacity(source.count, false); |
138 | memcpy(data, source.data, sizeof(T) * source.count); |
139 | count = source.count; |
140 | } |
141 | |
142 | public: |
143 | typedef size_t size_type; |
144 | typedef ptrdiff_t difference_type; |
145 | typedef T* pointer; |
146 | typedef const T* const_pointer; |
147 | typedef T& reference; |
148 | typedef const T& const_reference; |
149 | typedef T value_type; |
150 | typedef pointer iterator; |
151 | typedef const_pointer const_iterator; |
152 | |
153 | Array<T, Storage>& operator =(const Array<T, Storage>& source) |
154 | { |
155 | copyFrom(source); |
156 | return *this; |
157 | } |
158 | |
159 | const T& operator[](size_t index) const throw() |
160 | { |
161 | return getElement(index); |
162 | } |
163 | |
164 | T& operator[](size_t index) throw() |
165 | { |
166 | return getElement(index); |
167 | } |
168 | |
169 | const T& front() const |
170 | { |
171 | fb_assert(count > 0); |
172 | return *data; |
173 | } |
174 | |
175 | const T& back() const |
176 | { |
177 | fb_assert(count > 0); |
178 | return *(data + count - 1); |
179 | } |
180 | |
181 | const T* begin() const { return data; } |
182 | |
183 | const T* end() const { return data + count; } |
184 | |
185 | T& front() |
186 | { |
187 | fb_assert(count > 0); |
188 | return *data; |
189 | } |
190 | |
191 | T& back() |
192 | { |
193 | fb_assert(count > 0); |
194 | return *(data + count - 1); |
195 | } |
196 | |
197 | T* begin() { return data; } |
198 | |
199 | T* end() { return data + count; } |
200 | |
201 | void insert(const size_t index, const T& item) |
202 | { |
203 | fb_assert(index <= count); |
204 | fb_assert(count < FB_MAX_SIZEOF); |
205 | ensureCapacity(count + 1); |
206 | memmove(data + index + 1, data + index, sizeof(T) * (count++ - index)); |
207 | data[index] = item; |
208 | } |
209 | |
210 | void insert(const size_t index, const Array<T, Storage>& items) |
211 | { |
212 | fb_assert(index <= count); |
213 | fb_assert(count <= FB_MAX_SIZEOF - items.count); |
214 | ensureCapacity(count + items.count); |
215 | memmove(data + index + items.count, data + index, sizeof(T) * (count - index)); |
216 | memcpy(data + index, items.data, items.count); |
217 | count += items.count; |
218 | } |
219 | |
220 | void insert(const size_t index, const T* items, const size_t itemsCount) |
221 | { |
222 | fb_assert(index <= count); |
223 | fb_assert(count <= FB_MAX_SIZEOF - itemsCount); |
224 | ensureCapacity(count + itemsCount); |
225 | memmove(data + index + itemsCount, data + index, sizeof(T) * (count - index)); |
226 | memcpy(data + index, items, sizeof(T) * itemsCount); |
227 | count += itemsCount; |
228 | } |
229 | |
230 | size_t add(const T& item) |
231 | { |
232 | ensureCapacity(count + 1); |
233 | data[count] = item; |
234 | return count++; |
235 | } |
236 | |
237 | void add(const T* items, const size_t itemsCount) |
238 | { |
239 | fb_assert(count <= FB_MAX_SIZEOF - itemsCount); |
240 | ensureCapacity(count + itemsCount); |
241 | memcpy(data + count, items, sizeof(T) * itemsCount); |
242 | count += itemsCount; |
243 | } |
244 | |
245 | T* remove(const size_t index) throw() |
246 | { |
247 | fb_assert(index < count); |
248 | memmove(data + index, data + index + 1, sizeof(T) * (--count - index)); |
249 | return &data[index]; |
250 | } |
251 | |
252 | T* removeRange(const size_t from, const size_t to) throw() |
253 | { |
254 | fb_assert(from <= to); |
255 | fb_assert(to <= count); |
256 | memmove(data + from, data + to, sizeof(T) * (count - to)); |
257 | count -= (to - from); |
258 | return &data[from]; |
259 | } |
260 | |
261 | T* removeCount(const size_t index, const size_t n) throw() |
262 | { |
263 | fb_assert(index + n <= count); |
264 | memmove(data + index, data + index + n, sizeof(T) * (count - index - n)); |
265 | count -= n; |
266 | return &data[index]; |
267 | } |
268 | |
269 | T* remove(T* itr) throw() |
270 | { |
271 | const size_t index = itr - begin(); |
272 | fb_assert(index < count); |
273 | memmove(data + index, data + index + 1, sizeof(T) * (--count - index)); |
274 | return &data[index]; |
275 | } |
276 | |
277 | T* remove(T* itrFrom, T* itrTo) throw() |
278 | { |
279 | return removeRange(itrFrom - begin(), itrTo - begin()); |
280 | } |
281 | |
282 | void shrink(size_t newCount) throw() |
283 | { |
284 | fb_assert(newCount <= count); |
285 | count = newCount; |
286 | } |
287 | |
288 | // Grow size of our array and zero-initialize new items |
289 | void grow(const size_t newCount) |
290 | { |
291 | fb_assert(newCount >= count); |
292 | ensureCapacity(newCount); |
293 | memset(data + count, 0, sizeof(T) * (newCount - count)); |
294 | count = newCount; |
295 | } |
296 | |
297 | // Resize array according to STL's vector::resize() rules |
298 | void resize(const size_t newCount, const T& val) |
299 | { |
300 | if (newCount > count) |
301 | { |
302 | ensureCapacity(newCount); |
303 | while (count < newCount) { |
304 | data[count++] = val; |
305 | } |
306 | } |
307 | else { |
308 | count = newCount; |
309 | } |
310 | } |
311 | |
312 | // Resize array according to STL's vector::resize() rules |
313 | void resize(const size_t newCount) |
314 | { |
315 | if (newCount > count) { |
316 | grow(newCount); |
317 | } |
318 | else { |
319 | count = newCount; |
320 | } |
321 | } |
322 | |
323 | void join(const Array<T, Storage>& L) |
324 | { |
325 | fb_assert(count <= FB_MAX_SIZEOF - L.count); |
326 | ensureCapacity(count + L.count); |
327 | memcpy(data + count, L.data, sizeof(T) * L.count); |
328 | count += L.count; |
329 | } |
330 | |
331 | void assign(const Array<T, Storage>& source) |
332 | { |
333 | copyFrom(source); |
334 | } |
335 | |
336 | void assign(const T* items, const size_t itemsCount) |
337 | { |
338 | resize(itemsCount); |
339 | memcpy(data, items, sizeof(T) * count); |
340 | } |
341 | |
342 | // NOTE: getCount method must be signal safe |
343 | // Used as such in GlobalRWLock::blockingAstHandler |
344 | size_t getCount() const { return count; } |
345 | |
346 | bool isEmpty() const { return count == 0; } |
347 | |
348 | bool hasData() const { return count != 0; } |
349 | |
350 | size_t getCapacity() const { return capacity; } |
351 | |
352 | void push(const T& item) |
353 | { |
354 | add(item); |
355 | } |
356 | |
357 | void push(const T* items, const size_t itemsSize) |
358 | { |
359 | fb_assert(count <= FB_MAX_SIZEOF - itemsSize); |
360 | ensureCapacity(count + itemsSize); |
361 | memcpy(data + count, items, sizeof(T) * itemsSize); |
362 | count += itemsSize; |
363 | } |
364 | |
365 | void append(const T* items, const size_t itemsSize) |
366 | { |
367 | push(items, itemsSize); |
368 | } |
369 | |
370 | void append(const Array<T, Storage>& source) |
371 | { |
372 | push(source.begin(), source.getCount()); |
373 | } |
374 | |
375 | T pop() |
376 | { |
377 | fb_assert(count > 0); |
378 | count--; |
379 | return data[count]; |
380 | } |
381 | |
382 | // prepare array to be used as a buffer of capacity items |
383 | T* getBuffer(const size_t capacityL, bool preserve = true) |
384 | { |
385 | ensureCapacity(capacityL, preserve); |
386 | count = capacityL; |
387 | return data; |
388 | } |
389 | |
390 | // clear array and release dinamically allocated memory |
391 | void free() |
392 | { |
393 | clear(); |
394 | freeData(); |
395 | capacity = this->getStorageSize(); |
396 | data = this->getStorage(); |
397 | } |
398 | |
399 | // This method only assigns "pos" if the element is found. |
400 | // Maybe we should modify it to iterate directy with "pos". |
401 | bool find(const T& item, size_t& pos) const |
402 | { |
403 | for (size_t i = 0; i < count; i++) |
404 | { |
405 | if (data[i] == item) |
406 | { |
407 | pos = i; |
408 | return true; |
409 | } |
410 | } |
411 | return false; |
412 | } |
413 | |
414 | bool exist(const T& item) const |
415 | { |
416 | size_t pos; // ignored |
417 | return find(item, pos); |
418 | } |
419 | |
420 | // Member function only for some debugging tests. Hope nobody is bothered. |
421 | void swapElems() |
422 | { |
423 | const size_t limit = count / 2; |
424 | for (size_t i = 0; i < limit; ++i) |
425 | { |
426 | T temp = data[i]; |
427 | data[i] = data[count - 1 - i]; |
428 | data[count - 1 - i] = temp; |
429 | } |
430 | } |
431 | |
432 | protected: |
433 | size_t count, capacity; |
434 | T* data; |
435 | |
436 | void ensureCapacity(size_t newcapacity, bool preserve = true) |
437 | { |
438 | if (newcapacity > capacity) |
439 | { |
440 | if (capacity <= FB_HALF_MAX_SIZEOF) |
441 | { |
442 | if (newcapacity < capacity * 2) |
443 | newcapacity = capacity * 2; |
444 | } |
445 | else |
446 | { |
447 | newcapacity = FB_MAX_SIZEOF; |
448 | } |
449 | |
450 | // Ensure we can carry byte copy operations. |
451 | // What to do here, throw in release build? |
452 | fb_assert(newcapacity < FB_MAX_SIZEOF / sizeof(T)); |
453 | |
454 | T* newdata = static_cast<T*> |
455 | (this->getPool().allocate(sizeof(T) * newcapacity |
456 | #ifdef DEBUG_GDS_ALLOC |
457 | , __FILE__, __LINE__ |
458 | #endif |
459 | )); |
460 | if (preserve) |
461 | memcpy(newdata, data, sizeof(T) * count); |
462 | freeData(); |
463 | data = newdata; |
464 | capacity = newcapacity; |
465 | } |
466 | } |
467 | }; |
468 | |
469 | const static int FB_ARRAY_SORT_MANUAL = 0; |
470 | const static int FB_ARRAY_SORT_WHEN_ADD = 1; |
471 | // const static int FB_ARRAY_SORT_ON_FIND |
472 | |
473 | // Dynamic sorted array of simple objects |
474 | template <typename Value, |
475 | typename Storage = EmptyStorage<Value>, |
476 | typename Key = Value, |
477 | typename KeyOfValue = DefaultKeyValue<Value>, |
478 | typename Cmp = DefaultComparator<Key> > |
479 | class SortedArray : public Array<Value, Storage> |
480 | { |
481 | public: |
482 | SortedArray(MemoryPool& p, size_t s) |
483 | : Array<Value, Storage>(p, s), sortMode(FB_ARRAY_SORT_WHEN_ADD), sorted(true) |
484 | { } |
485 | |
486 | explicit SortedArray(MemoryPool& p) |
487 | : Array<Value, Storage>(p), sortMode(FB_ARRAY_SORT_WHEN_ADD), sorted(true) |
488 | { } |
489 | |
490 | explicit SortedArray(size_t s) |
491 | : Array<Value, Storage>(s), sortMode(FB_ARRAY_SORT_WHEN_ADD), sorted(true) |
492 | { } |
493 | |
494 | SortedArray() |
495 | : Array<Value, Storage>(), sortMode(FB_ARRAY_SORT_WHEN_ADD), sorted(true) |
496 | { } |
497 | |
498 | // When item is not found, set pos to the position where the element should be |
499 | // stored if/when added. |
500 | bool find(const Key& item, size_t& pos) const |
501 | { |
502 | fb_assert(sorted); |
503 | |
504 | size_t highBound = this->count, lowBound = 0; |
505 | while (highBound > lowBound) |
506 | { |
507 | const size_t temp = (highBound + lowBound) >> 1; |
508 | if (Cmp::greaterThan(item, KeyOfValue::generate(this->data[temp]))) |
509 | lowBound = temp + 1; |
510 | else |
511 | highBound = temp; |
512 | } |
513 | pos = lowBound; |
514 | return highBound != this->count && |
515 | !Cmp::greaterThan(KeyOfValue::generate(this->data[lowBound]), item); |
516 | } |
517 | |
518 | bool exist(const Key& item) const |
519 | { |
520 | size_t pos; // ignored |
521 | return find(item, pos); |
522 | } |
523 | |
524 | size_t add(const Value& item) |
525 | { |
526 | size_t pos; |
527 | if (sortMode == FB_ARRAY_SORT_WHEN_ADD) |
528 | find(KeyOfValue::generate(item), pos); |
529 | else |
530 | { |
531 | sorted = false; |
532 | pos = this->getCount(); |
533 | } |
534 | this->insert(pos, item); |
535 | return pos; |
536 | } |
537 | |
538 | void setSortMode(int sm) |
539 | { |
540 | if (sortMode != FB_ARRAY_SORT_WHEN_ADD && sm == FB_ARRAY_SORT_WHEN_ADD && !sorted) |
541 | { |
542 | sort(); |
543 | } |
544 | sortMode = sm; |
545 | } |
546 | |
547 | void sort() |
548 | { |
549 | if (sorted) |
550 | return; |
551 | |
552 | qsort(this->begin(), this->getCount(), sizeof(Value), compare); |
553 | sorted = true; |
554 | } |
555 | |
556 | private: |
557 | int sortMode; |
558 | bool sorted; |
559 | |
560 | static int compare(const void* a, const void* b) |
561 | { |
562 | const Key& first(KeyOfValue::generate(*static_cast<const Value*>(a))); |
563 | const Key& second(KeyOfValue::generate(*static_cast<const Value*>(b))); |
564 | |
565 | if (Cmp::greaterThan(first, second)) |
566 | return 1; |
567 | if (Cmp::greaterThan(second, first)) |
568 | return -1; |
569 | |
570 | return 0; |
571 | } |
572 | }; |
573 | |
574 | // Nice shorthand for arrays with static part |
575 | template <typename T, size_t InlineCapacity> |
576 | class HalfStaticArray : public Array<T, InlineStorage<T, InlineCapacity> > |
577 | { |
578 | public: |
579 | explicit HalfStaticArray(MemoryPool& p) : Array<T, InlineStorage<T, InlineCapacity> > (p) {} |
580 | HalfStaticArray(MemoryPool& p, size_t InitialCapacity) : |
581 | Array<T, InlineStorage<T, InlineCapacity> > (p, InitialCapacity) {} |
582 | HalfStaticArray() : Array<T, InlineStorage<T, InlineCapacity> > () {} |
583 | explicit HalfStaticArray(size_t InitialCapacity) : |
584 | Array<T, InlineStorage<T, InlineCapacity> > (InitialCapacity) {} |
585 | }; |
586 | |
587 | typedef HalfStaticArray<UCHAR, BUFFER_TINY> UCharBuffer; |
588 | |
589 | } // namespace Firebird |
590 | |
591 | #endif // CLASSES_ARRAY_H |
592 | |