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 | |
36 | namespace Firebird { |
37 | |
38 | // Very fast static array of simple types |
39 | template <typename T, size_t Capacity> |
40 | class Vector |
41 | { |
42 | public: |
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 | |
121 | protected: |
122 | size_t count; |
123 | T data[Capacity]; |
124 | }; |
125 | |
126 | // Template for default value comparsion |
127 | template <typename T> |
128 | class DefaultComparator |
129 | { |
130 | public: |
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 |
138 | template <typename T> |
139 | class DefaultKeyValue |
140 | { |
141 | public: |
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 |
148 | template <typename Value, size_t Capacity, typename Key = Value, |
149 | typename KeyOfValue = DefaultKeyValue<Value>, |
150 | typename Cmp = DefaultComparator<Key> > |
151 | class SortedVector : public Vector<Value, Capacity> |
152 | { |
153 | public: |
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 | |