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 // DO NOT USE: please use std::map
34
35 template <typename KEY, typename VALUE>
36 class KeyedVector
37 {
38 public:
39 typedef KEY key_type;
40 typedef VALUE value_type;
41
42 inline KeyedVector();
43
44 /*
45 * empty the vector
46 */
47
clear()48 inline void clear() { mVector.clear(); }
49
50 /*!
51 * vector stats
52 */
53
54 //! returns number of items in the vector
size()55 inline size_t size() const { return mVector.size(); }
56 //! returns whether or not the vector is empty
isEmpty()57 inline bool isEmpty() const { return mVector.isEmpty(); }
58 //! returns how many items can be stored without reallocating the backing store
capacity()59 inline size_t capacity() const { return mVector.capacity(); }
60 //! sets the capacity. capacity can never be reduced less than size()
setCapacity(size_t size)61 inline ssize_t setCapacity(size_t size) { return mVector.setCapacity(size); }
62
63 // returns true if the arguments is known to be identical to this vector
64 inline bool isIdenticalTo(const KeyedVector& rhs) const;
65
66 /*!
67 * accessors
68 */
69 const VALUE& valueFor(const KEY& key) const;
70 const VALUE& valueAt(size_t index) const;
71 const KEY& keyAt(size_t index) const;
72 ssize_t indexOfKey(const KEY& key) const;
73 const VALUE& operator[] (size_t index) const;
74
75 /*!
76 * modifying the array
77 */
78
79 VALUE& editValueFor(const KEY& key);
80 VALUE& editValueAt(size_t index);
81
82 /*!
83 * add/insert/replace items
84 */
85
86 ssize_t add(const KEY& key, const VALUE& item);
87 ssize_t replaceValueFor(const KEY& key, const VALUE& item);
88 ssize_t replaceValueAt(size_t index, const VALUE& item);
89
90 /*!
91 * remove items
92 */
93
94 ssize_t removeItem(const KEY& key);
95 ssize_t removeItemsAt(size_t index, size_t count = 1);
96
97 private:
98 SortedVector< key_value_pair_t<KEY, VALUE> > mVector;
99 };
100
101 // ---------------------------------------------------------------------------
102
103 /**
104 * Variation of KeyedVector that holds a default value to return when
105 * valueFor() is called with a key that doesn't exist.
106 */
107 template <typename KEY, typename VALUE>
108 class DefaultKeyedVector : public KeyedVector<KEY, VALUE>
109 {
110 public:
111 inline DefaultKeyedVector(const VALUE& defValue = VALUE());
112 const VALUE& valueFor(const KEY& key) const;
113
114 private:
115 VALUE mDefault;
116 };
117
118 // ---------------------------------------------------------------------------
119
120 template<typename KEY, typename VALUE> inline
KeyedVector()121 KeyedVector<KEY,VALUE>::KeyedVector()
122 {
123 }
124
125 template<typename KEY, typename VALUE> inline
isIdenticalTo(const KeyedVector<KEY,VALUE> & rhs)126 bool KeyedVector<KEY,VALUE>::isIdenticalTo(const KeyedVector<KEY,VALUE>& rhs) const {
127 return mVector.array() == rhs.mVector.array();
128 }
129
130 template<typename KEY, typename VALUE> inline
indexOfKey(const KEY & key)131 ssize_t KeyedVector<KEY,VALUE>::indexOfKey(const KEY& key) const {
132 return mVector.indexOf( key_value_pair_t<KEY,VALUE>(key) );
133 }
134
135 template<typename KEY, typename VALUE> inline
valueFor(const KEY & key)136 const VALUE& KeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
137 ssize_t i = this->indexOfKey(key);
138 LOG_ALWAYS_FATAL_IF(i<0, "%s: key not found", __PRETTY_FUNCTION__);
139 return mVector.itemAt(i).value;
140 }
141
142 template<typename KEY, typename VALUE> inline
valueAt(size_t index)143 const VALUE& KeyedVector<KEY,VALUE>::valueAt(size_t index) const {
144 return mVector.itemAt(index).value;
145 }
146
147 template<typename KEY, typename VALUE> inline
148 const VALUE& KeyedVector<KEY,VALUE>::operator[] (size_t index) const {
149 return valueAt(index);
150 }
151
152 template<typename KEY, typename VALUE> inline
keyAt(size_t index)153 const KEY& KeyedVector<KEY,VALUE>::keyAt(size_t index) const {
154 return mVector.itemAt(index).key;
155 }
156
157 template<typename KEY, typename VALUE> inline
editValueFor(const KEY & key)158 VALUE& KeyedVector<KEY,VALUE>::editValueFor(const KEY& key) {
159 ssize_t i = this->indexOfKey(key);
160 LOG_ALWAYS_FATAL_IF(i<0, "%s: key not found", __PRETTY_FUNCTION__);
161 return mVector.editItemAt(static_cast<size_t>(i)).value;
162 }
163
164 template<typename KEY, typename VALUE> inline
editValueAt(size_t index)165 VALUE& KeyedVector<KEY,VALUE>::editValueAt(size_t index) {
166 return mVector.editItemAt(index).value;
167 }
168
169 template<typename KEY, typename VALUE> inline
add(const KEY & key,const VALUE & value)170 ssize_t KeyedVector<KEY,VALUE>::add(const KEY& key, const VALUE& value) {
171 return mVector.add( key_value_pair_t<KEY,VALUE>(key, value) );
172 }
173
174 template<typename KEY, typename VALUE> inline
replaceValueFor(const KEY & key,const VALUE & value)175 ssize_t KeyedVector<KEY,VALUE>::replaceValueFor(const KEY& key, const VALUE& value) {
176 key_value_pair_t<KEY,VALUE> pair(key, value);
177 mVector.remove(pair);
178 return mVector.add(pair);
179 }
180
181 template<typename KEY, typename VALUE> inline
replaceValueAt(size_t index,const VALUE & item)182 ssize_t KeyedVector<KEY,VALUE>::replaceValueAt(size_t index, const VALUE& item) {
183 if (index<size()) {
184 mVector.editItemAt(index).value = item;
185 return static_cast<ssize_t>(index);
186 }
187 return BAD_INDEX;
188 }
189
190 template<typename KEY, typename VALUE> inline
removeItem(const KEY & key)191 ssize_t KeyedVector<KEY,VALUE>::removeItem(const KEY& key) {
192 return mVector.remove(key_value_pair_t<KEY,VALUE>(key));
193 }
194
195 template<typename KEY, typename VALUE> inline
removeItemsAt(size_t index,size_t count)196 ssize_t KeyedVector<KEY, VALUE>::removeItemsAt(size_t index, size_t count) {
197 return mVector.removeItemsAt(index, count);
198 }
199
200 // ---------------------------------------------------------------------------
201
202 template<typename KEY, typename VALUE> inline
DefaultKeyedVector(const VALUE & defValue)203 DefaultKeyedVector<KEY,VALUE>::DefaultKeyedVector(const VALUE& defValue)
204 : mDefault(defValue)
205 {
206 }
207
208 template<typename KEY, typename VALUE> inline
valueFor(const KEY & key)209 const VALUE& DefaultKeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
210 ssize_t i = this->indexOfKey(key);
211 return i >= 0 ? KeyedVector<KEY,VALUE>::valueAt(i) : mDefault;
212 }
213
214 } // namespace android
215
216 // ---------------------------------------------------------------------------
217
218 #endif // ANDROID_KEYED_VECTOR_H
219