1 /*
2 * Copyright (C) 2005 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef ANDROID_KEYED_VECTOR_H
18 #define ANDROID_KEYED_VECTOR_H
19
20 #include <assert.h>
21 #include <stdint.h>
22 #include <sys/types.h>
23
24 #include <log/log.h>
25 #include <utils/Errors.h>
26 #include <utils/SortedVector.h>
27 #include <utils/TypeHelpers.h>
28
29 // ---------------------------------------------------------------------------
30
31 namespace android {
32
33 template <typename KEY, typename VALUE>
34 class KeyedVector
35 {
36 public:
37 typedef KEY key_type;
38 typedef VALUE value_type;
39
40 inline KeyedVector();
41
42 /*
43 * empty the vector
44 */
45
clear()46 inline void clear() { mVector.clear(); }
47
48 /*!
49 * vector stats
50 */
51
52 //! returns number of items in the vector
size()53 inline size_t size() const { return mVector.size(); }
54 //! returns whether or not the vector is empty
isEmpty()55 inline bool isEmpty() const { return mVector.isEmpty(); }
56 //! returns how many items can be stored without reallocating the backing store
capacity()57 inline size_t capacity() const { return mVector.capacity(); }
58 //! sets the capacity. capacity can never be reduced less than size()
setCapacity(size_t size)59 inline ssize_t setCapacity(size_t size) { return mVector.setCapacity(size); }
60
61 // returns true if the arguments is known to be identical to this vector
62 inline bool isIdenticalTo(const KeyedVector& rhs) const;
63
64 /*!
65 * accessors
66 */
67 const VALUE& valueFor(const KEY& key) const;
68 const VALUE& valueAt(size_t index) const;
69 const KEY& keyAt(size_t index) const;
70 ssize_t indexOfKey(const KEY& key) const;
71 const VALUE& operator[] (size_t index) const;
72
73 /*!
74 * modifying the array
75 */
76
77 VALUE& editValueFor(const KEY& key);
78 VALUE& editValueAt(size_t index);
79
80 /*!
81 * add/insert/replace items
82 */
83
84 ssize_t add(const KEY& key, const VALUE& item);
85 ssize_t replaceValueFor(const KEY& key, const VALUE& item);
86 ssize_t replaceValueAt(size_t index, const VALUE& item);
87
88 /*!
89 * remove items
90 */
91
92 ssize_t removeItem(const KEY& key);
93 ssize_t removeItemsAt(size_t index, size_t count = 1);
94
95 private:
96 SortedVector< key_value_pair_t<KEY, VALUE> > mVector;
97 };
98
99 // ---------------------------------------------------------------------------
100
101 /**
102 * Variation of KeyedVector that holds a default value to return when
103 * valueFor() is called with a key that doesn't exist.
104 */
105 template <typename KEY, typename VALUE>
106 class DefaultKeyedVector : public KeyedVector<KEY, VALUE>
107 {
108 public:
109 inline DefaultKeyedVector(const VALUE& defValue = VALUE());
110 const VALUE& valueFor(const KEY& key) const;
111
112 private:
113 VALUE mDefault;
114 };
115
116 // ---------------------------------------------------------------------------
117
118 template<typename KEY, typename VALUE> inline
KeyedVector()119 KeyedVector<KEY,VALUE>::KeyedVector()
120 {
121 }
122
123 template<typename KEY, typename VALUE> inline
isIdenticalTo(const KeyedVector<KEY,VALUE> & rhs)124 bool KeyedVector<KEY,VALUE>::isIdenticalTo(const KeyedVector<KEY,VALUE>& rhs) const {
125 return mVector.array() == rhs.mVector.array();
126 }
127
128 template<typename KEY, typename VALUE> inline
indexOfKey(const KEY & key)129 ssize_t KeyedVector<KEY,VALUE>::indexOfKey(const KEY& key) const {
130 return mVector.indexOf( key_value_pair_t<KEY,VALUE>(key) );
131 }
132
133 template<typename KEY, typename VALUE> inline
valueFor(const KEY & key)134 const VALUE& KeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
135 ssize_t i = this->indexOfKey(key);
136 LOG_ALWAYS_FATAL_IF(i<0, "%s: key not found", __PRETTY_FUNCTION__);
137 return mVector.itemAt(i).value;
138 }
139
140 template<typename KEY, typename VALUE> inline
valueAt(size_t index)141 const VALUE& KeyedVector<KEY,VALUE>::valueAt(size_t index) const {
142 return mVector.itemAt(index).value;
143 }
144
145 template<typename KEY, typename VALUE> inline
146 const VALUE& KeyedVector<KEY,VALUE>::operator[] (size_t index) const {
147 return valueAt(index);
148 }
149
150 template<typename KEY, typename VALUE> inline
keyAt(size_t index)151 const KEY& KeyedVector<KEY,VALUE>::keyAt(size_t index) const {
152 return mVector.itemAt(index).key;
153 }
154
155 template<typename KEY, typename VALUE> inline
editValueFor(const KEY & key)156 VALUE& KeyedVector<KEY,VALUE>::editValueFor(const KEY& key) {
157 ssize_t i = this->indexOfKey(key);
158 LOG_ALWAYS_FATAL_IF(i<0, "%s: key not found", __PRETTY_FUNCTION__);
159 return mVector.editItemAt(static_cast<size_t>(i)).value;
160 }
161
162 template<typename KEY, typename VALUE> inline
editValueAt(size_t index)163 VALUE& KeyedVector<KEY,VALUE>::editValueAt(size_t index) {
164 return mVector.editItemAt(index).value;
165 }
166
167 template<typename KEY, typename VALUE> inline
add(const KEY & key,const VALUE & value)168 ssize_t KeyedVector<KEY,VALUE>::add(const KEY& key, const VALUE& value) {
169 return mVector.add( key_value_pair_t<KEY,VALUE>(key, value) );
170 }
171
172 template<typename KEY, typename VALUE> inline
replaceValueFor(const KEY & key,const VALUE & value)173 ssize_t KeyedVector<KEY,VALUE>::replaceValueFor(const KEY& key, const VALUE& value) {
174 key_value_pair_t<KEY,VALUE> pair(key, value);
175 mVector.remove(pair);
176 return mVector.add(pair);
177 }
178
179 template<typename KEY, typename VALUE> inline
replaceValueAt(size_t index,const VALUE & item)180 ssize_t KeyedVector<KEY,VALUE>::replaceValueAt(size_t index, const VALUE& item) {
181 if (index<size()) {
182 mVector.editItemAt(index).value = item;
183 return static_cast<ssize_t>(index);
184 }
185 return BAD_INDEX;
186 }
187
188 template<typename KEY, typename VALUE> inline
removeItem(const KEY & key)189 ssize_t KeyedVector<KEY,VALUE>::removeItem(const KEY& key) {
190 return mVector.remove(key_value_pair_t<KEY,VALUE>(key));
191 }
192
193 template<typename KEY, typename VALUE> inline
removeItemsAt(size_t index,size_t count)194 ssize_t KeyedVector<KEY, VALUE>::removeItemsAt(size_t index, size_t count) {
195 return mVector.removeItemsAt(index, count);
196 }
197
198 // ---------------------------------------------------------------------------
199
200 template<typename KEY, typename VALUE> inline
DefaultKeyedVector(const VALUE & defValue)201 DefaultKeyedVector<KEY,VALUE>::DefaultKeyedVector(const VALUE& defValue)
202 : mDefault(defValue)
203 {
204 }
205
206 template<typename KEY, typename VALUE> inline
valueFor(const KEY & key)207 const VALUE& DefaultKeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
208 ssize_t i = this->indexOfKey(key);
209 return i >= 0 ? KeyedVector<KEY,VALUE>::valueAt(i) : mDefault;
210 }
211
212 }; // namespace android
213
214 // ---------------------------------------------------------------------------
215
216 #endif // ANDROID_KEYED_VECTOR_H
217