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
35namespace Firebird {
36
37const size_t FB_MAX_SIZEOF = ~size_t(0);
38const size_t FB_HALF_MAX_SIZEOF = FB_MAX_SIZEOF >> 1;
39
40// Static part of the array
41template <typename T, size_t Capacity>
42class InlineStorage : public AutoStorage
43{
44public:
45 explicit InlineStorage(MemoryPool& p) : AutoStorage(p) { }
46 InlineStorage() : AutoStorage() { }
47protected:
48 T* getStorage()
49 {
50 return buffer;
51 }
52 size_t getStorageSize() const
53 {
54 return Capacity;
55 }
56private:
57 T buffer[Capacity];
58};
59
60// Used when array doesn't have static part
61template <typename T>
62class EmptyStorage : public AutoStorage
63{
64public:
65 explicit EmptyStorage(MemoryPool& p) : AutoStorage(p) { }
66 EmptyStorage() : AutoStorage() { }
67protected:
68 T* getStorage() { return NULL; }
69 size_t getStorageSize() const { return 0; }
70};
71
72// Dynamic array of simple types
73template <typename T, typename Storage = EmptyStorage<T> >
74class Array : protected Storage
75{
76public:
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
114protected:
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
142public:
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
432protected:
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
469const static int FB_ARRAY_SORT_MANUAL = 0;
470const 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
474template <typename Value,
475 typename Storage = EmptyStorage<Value>,
476 typename Key = Value,
477 typename KeyOfValue = DefaultKeyValue<Value>,
478 typename Cmp = DefaultComparator<Key> >
479class SortedArray : public Array<Value, Storage>
480{
481public:
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
556private:
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
575template <typename T, size_t InlineCapacity>
576class HalfStaticArray : public Array<T, InlineStorage<T, InlineCapacity> >
577{
578public:
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
587typedef HalfStaticArray<UCHAR, BUFFER_TINY> UCharBuffer;
588
589} // namespace Firebird
590
591#endif // CLASSES_ARRAY_H
592