00001 /* 00002 * skype-dict.h 00003 * 00004 * Created on: Oct 5, 2010 00005 * Author: lauri 00006 */ 00007 00008 #ifndef SKYPEDICT_H_ 00009 #define SKYPEDICT_H_ 00010 00011 #include "skype-string.h" 00012 #include "skype-list.h" 00013 00014 // specialize for string type 00015 template <class KeyType> 00016 inline bool param_is_empty_string(const KeyType& key) { 00017 return false; 00018 } 00019 00020 // specialize this for string type 00021 template <class KeyType> 00022 inline int key_to_index(const KeyType & key, int size) { 00023 return key % size; 00024 } 00025 00026 00027 /** \class SEDict skype-dict.h "skype-dict.h" 00028 * \brief SEDict is a dictionary class of KeyType associated to ValueType. 00029 */ 00030 template<class KeyType, class ValueType> 00031 class SEDict { 00032 public: 00033 /** Creates an empty dictionary of KeyType/ValueType. */ 00034 SEDict(int size) : 00035 d(0), m_size(size) { 00036 } 00037 /** Constructs an implicitly shared copy of dict. */ 00038 SEDict(const SEDict& dict) : 00039 d(0) { 00040 *this = dict; 00041 } 00042 /** Destroys the dictionary and frees the data if this is the last reference to it. */ 00043 ~SEDict() { 00044 d_unref(); 00045 } 00046 00047 /// \cond INTERNAL 00048 protected: 00049 class Element { 00050 public: 00051 Element(const KeyType& k, const ValueType& v) : 00052 next(0), key(k), value(v) { 00053 } 00054 00055 public: 00056 Element* next; 00057 KeyType key; 00058 ValueType value; 00059 }; 00060 00061 class Data { 00062 public: 00063 Data(int size) : 00064 dirty(true), quick_list(0) { 00065 dict = new Element*[size]; 00066 } 00067 ~Data() { 00068 delete[] dict; 00069 } 00070 00071 public: 00072 Element** dict; 00073 unsigned int ref; 00074 size_t size; 00075 bool dirty; 00076 Element** quick_list; 00077 SEMutex lock; 00078 }; 00079 Data* d; 00080 size_t m_size; 00081 /// \endcond 00082 00083 public: 00084 /** Inserts the key with the value into the dictionary. 00085 * Multiple items can have the same key, they are not overwritten. 00086 * You can access them with the offset parameter of the find() function. 00087 * If key is null, nothing is inserted. 00088 */ 00089 void insert(const KeyType& key, const ValueType& value) { 00090 00091 if (param_is_empty_string<KeyType>(key)) 00092 return; 00093 00094 detach(); 00095 00096 if (0 == d) { 00097 d = new Data(m_size); 00098 00099 d->ref = 1; 00100 00101 for (size_t n = 0; n < m_size; n++) 00102 d->dict[n] = 0; 00103 } 00104 00105 d->dirty = true; 00106 00107 unsigned int h = key_to_index<KeyType>(key, m_size); 00108 00109 Element** e = &(d->dict[h]); 00110 00111 while (*e) 00112 e = &((*e)->next); 00113 00114 *e = new Element(key, value); 00115 } 00116 00117 /** Finds the specified key in the dictionary. 00118 * \param key Key to search. 00119 * Default is to search for 0, which is the most often used key name 00120 * in the Embedded API. 00121 * \param offset When the dictionary contains several entries with the same key, 00122 * use the offset param to indicate which key you want. 00123 * \return null string if the key is not found. 00124 */ 00125 ValueType find(const KeyType& key, unsigned int offset = 0) const { 00126 if (0 == d) 00127 return ValueType(); 00128 00129 unsigned int h = key_to_index<KeyType>(key, m_size); 00130 00131 Element** e = &(d->dict[h]); 00132 00133 while (*e) { 00134 if ((*e)->key == key) { 00135 if (0 == offset) 00136 return (*e)->value; 00137 else 00138 offset--; 00139 } 00140 00141 e = &((*e)->next); 00142 } 00143 00144 return ValueType(); 00145 } 00146 /** Assigns a shallow copy of dict to this dictionary and returns a reference to it. 00147 * This is very fast because the dictionary isn't actually copied. 00148 */ 00149 SEDict<KeyType, ValueType>& operator=( 00150 const SEDict<KeyType, ValueType>& dict) { 00151 const_cast<SEDict<KeyType, ValueType> &> (dict).d_ref(); 00152 d_unref(); 00153 d = dict.d; 00154 00155 return *this; 00156 } 00157 00158 /** Returns how many elements are in the dictionary. */ 00159 size_t size() const { 00160 if (0 == d) 00161 return 0; 00162 00163 if (d->dirty) { 00164 if (d->quick_list) 00165 delete[] d->quick_list; 00166 00167 d->size = 0; 00168 00169 size_t n; 00170 for (n = 0; n < m_size; n++) { 00171 Element** e = &(d->dict[n]); 00172 00173 while (*e) { 00174 d->size++; 00175 00176 e = &((*e)->next); 00177 } 00178 } 00179 00180 d->quick_list = new Element*[d->size]; 00181 00182 size_t c = 0; 00183 00184 for (n = 0; n < m_size; n++) { 00185 Element** e = &(d->dict[n]); 00186 00187 while (*e) { 00188 d->quick_list[c++] = *e; 00189 00190 e = &((*e)->next); 00191 } 00192 } 00193 00194 d->dirty = false; 00195 } 00196 00197 return d->size; 00198 } 00199 00200 /** Use this function to iterate through the dictionary. 00201 * It doesn't make sense to use this functions outside of an iteration (i.e. a loop). 00202 * See also keyAt() 00203 */ 00204 ValueType operator[](size_t i) const { 00205 if (0 == d) 00206 return KeyType(); 00207 00208 if (i >= size()) 00209 return KeyType(); 00210 00211 // we have already called size() so we are supposed to be "clean" 00212 return d->quick_list[i]->value; 00213 } 00214 /** Use this function to iterate through the dictionary. 00215 * It doesn't make sense to use this functions outside of an iteration (i.e. a loop). 00216 * See also operator[]() 00217 */ 00218 KeyType keyAt(size_t i) const { 00219 if (0 == d) 00220 return KeyType(); 00221 00222 if (i >= size()) 00223 return KeyType(); 00224 00225 // we have already called size() so we are supposed to be "clean" 00226 return d->quick_list[i]->key; 00227 } 00228 00229 ValueType value(const KeyType& key) { 00230 return find(key); 00231 } 00232 00233 bool remove(const KeyType &key) { 00234 detach(); 00235 00236 if (0 == d) { 00237 d = new Data(m_size); 00238 00239 d->ref = 1; 00240 00241 for (size_t n = 0; n < m_size; n++) 00242 d->dict[n] = 0; 00243 } 00244 00245 d->dirty = true; 00246 00247 unsigned int h = key_to_index<KeyType>(key, m_size); 00248 00249 Element** e = &(d->dict[h]); 00250 00251 while (*e) { 00252 if ((*e)->key == key) { 00253 Element* tmp = *e; 00254 *e = (*e)->next; 00255 delete tmp; 00256 00257 return true; 00258 } 00259 e = &((*e)->next); 00260 } 00261 00262 return false; 00263 } 00264 00265 SEList<KeyType> keys() { 00266 SEList<KeyType> result; 00267 int d_size = size(); 00268 if (d && d->quick_list) { 00269 for (int i = 0; i < d_size; i++) { 00270 result.append(d->quick_list[i]->key); 00271 } 00272 } 00273 return result; 00274 } 00275 protected: 00276 /// \cond INTERNAL 00277 void d_ref() { 00278 if (0 == d) 00279 return; 00280 00281 d->lock.Acquire(); 00282 00283 d->ref++; 00284 00285 d->lock.Release(); 00286 } 00287 00288 void d_unref() { 00289 if (0 == d) 00290 return; 00291 00292 SEMutex* lock = &d->lock; 00293 00294 lock->Acquire(); 00295 00296 if (d->ref > 1) 00297 d->ref--; 00298 else { 00299 Data* tmp_d = d; 00300 d = 0; 00301 lock->Release(); 00302 00303 for (size_t n = 0; n < m_size; n++) { 00304 while (tmp_d->dict[n]) { 00305 Element* tmp = tmp_d->dict[n]->next; 00306 00307 delete tmp_d->dict[n]; 00308 00309 tmp_d->dict[n] = tmp; 00310 } 00311 } 00312 00313 if (tmp_d->quick_list) 00314 delete[] tmp_d->quick_list; 00315 00316 delete tmp_d; 00317 return; 00318 } 00319 00320 lock->Release(); 00321 } 00322 00323 void detach() { 00324 if (0 == d) 00325 return; 00326 00327 d->lock.Acquire(); 00328 00329 if (1 != d->ref) { 00330 00331 Data* d_new = new Data(m_size); 00332 00333 d_new->ref = 1; 00334 00335 size_t n; 00336 for (n = 0; n < m_size; n++) 00337 d_new->dict[n] = 0; 00338 00339 for (n = 0; n < m_size; n++) { 00340 Element** from = &(d->dict[n]); 00341 Element** to = &(d_new->dict[n]); 00342 00343 while (*from) { 00344 *to = new Element((*from)->key, (*from)->value); 00345 00346 from = &((*from)->next); 00347 to = &((*to)->next); 00348 } 00349 } 00350 00351 d->lock.Release(); 00352 00353 d_unref(); 00354 00355 d = d_new; 00356 00357 return; 00358 } 00359 00360 d->lock.Release(); 00361 } 00362 00363 /// \endcond 00364 }; 00365 00366 template<> 00367 inline bool param_is_empty_string<SEString>(const SEString& key) { 00368 return key.isNull(); 00369 } 00370 00371 template <> 00372 inline int key_to_index<SEString>(const SEString & key, int size) { 00373 return key.hash(size); 00374 } 00375 00376 #endif /* SKYPEDICT_H_ */
(c) Skype Technologies S.A. Confidential/Proprietary
Last updated: Fri Jan 27 2012