1/*
2 * PROGRAM: Client/Server Common Code
3 * MODULE: vector.h
4 * DESCRIPTION: static array of simple elements
5 *
6 * The contents of this file are subject to the Initial
7 * Developer's Public License Version 1.0 (the "License");
8 * you may not use this file except in compliance with the
9 * License. You may obtain a copy of the License at
10 * http://www.ibphoenix.com/main.nfs?a=ibphoenix&page=ibp_idpl.
11 *
12 * Software distributed under the License is distributed AS IS,
13 * WITHOUT WARRANTY OF ANY KIND, either express or implied.
14 * See the License for the specific language governing rights
15 * and limitations under the License.
16 *
17 * The Original Code was created by Nickolay Samofatov
18 * for the Firebird Open Source RDBMS project.
19 *
20 * Copyright (c) 2004 Nickolay Samofatov <nickolay@broadviewsoftware.com>
21 * and all contributors signed below.
22 *
23 * All Rights Reserved.
24 * Contributor(s): ______________________________________.
25 *
26 *
27 *
28 */
29
30#ifndef VECTOR_H
31#define VECTOR_H
32
33#include "../common/gdsassert.h"
34#include <string.h>
35
36namespace Firebird {
37
38// Very fast static array of simple types
39template <typename T, size_t Capacity>
40class Vector
41{
42public:
43 Vector() : count(0) {}
44
45 T& operator[](size_t index)
46 {
47 fb_assert(index < count);
48 return data[index];
49 }
50
51 const T& operator[](size_t index) const
52 {
53 fb_assert(index < count);
54 return data[index];
55 }
56
57 T* begin() { return data; }
58 T* end() { return data + count; }
59 const T* begin() const { return data; }
60 const T* end() const { return data + count; }
61 bool hasData() const { return (count != 0); }
62 size_t getCount() const { return count; }
63 size_t getCapacity() const { return Capacity; }
64 void clear() { count = 0; }
65
66 void insert(size_t index, const T& item)
67 {
68 fb_assert(index <= count);
69 fb_assert(count < Capacity);
70 memmove(data + index + 1, data + index, sizeof(T) * (count++ - index));
71 data[index] = item;
72 }
73
74 size_t add(const T& item)
75 {
76 fb_assert(count < Capacity);
77 data[count] = item;
78 return ++count;
79 }
80
81 T* remove(size_t index)
82 {
83 fb_assert(index < count);
84 memmove(data + index, data + index + 1, sizeof(T) * (--count - index));
85 return &data[index];
86 }
87
88 void shrink(size_t newCount)
89 {
90 fb_assert(newCount <= count);
91 count = newCount;
92 }
93
94 void join(const Vector<T, Capacity>& L)
95 {
96 fb_assert(count + L.count <= Capacity);
97 memcpy(data + count, L.data, sizeof(T) * L.count);
98 count += L.count;
99 }
100
101 // prepare vector to be used as a buffer of capacity items
102 T* getBuffer(size_t capacityL)
103 {
104 fb_assert(capacityL <= Capacity);
105 count = capacityL;
106 return data;
107 }
108
109 void push(const T& item)
110 {
111 add(item);
112 }
113
114 T pop()
115 {
116 fb_assert(count > 0);
117 count--;
118 return data[count];
119 }
120
121protected:
122 size_t count;
123 T data[Capacity];
124};
125
126// Template for default value comparsion
127template <typename T>
128class DefaultComparator
129{
130public:
131 static bool greaterThan(const T& i1, const T& i2)
132 {
133 return i1 > i2;
134 }
135};
136
137// Template to convert value to index directly
138template <typename T>
139class DefaultKeyValue
140{
141public:
142 static const T& generate(const void* /*sender*/, const T& item) { return item; }
143 static const T& generate(const T& item) { return item; }
144};
145
146// Fast sorted array of simple objects
147// It is used for B+ tree nodes lower, but can still be used by itself
148template <typename Value, size_t Capacity, typename Key = Value,
149 typename KeyOfValue = DefaultKeyValue<Value>,
150 typename Cmp = DefaultComparator<Key> >
151class SortedVector : public Vector<Value, Capacity>
152{
153public:
154 SortedVector() : Vector<Value, Capacity>() {}
155 bool find(const Key& item, size_t& pos) const
156 {
157 size_t highBound = this->count, lowBound = 0;
158 while (highBound > lowBound)
159 {
160 const size_t temp = (highBound + lowBound) >> 1;
161 if (Cmp::greaterThan(item, KeyOfValue::generate(this, this->data[temp])))
162 lowBound = temp + 1;
163 else
164 highBound = temp;
165 }
166 pos = lowBound;
167 return highBound != this->count &&
168 !Cmp::greaterThan(KeyOfValue::generate(this, this->data[lowBound]), item);
169 }
170 size_t add(const Value& item)
171 {
172 size_t pos;
173 find(KeyOfValue::generate(this, item), pos);
174 this->insert(pos, item);
175 return pos;
176 }
177};
178
179} // namespace Firebird
180
181#endif
182