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