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