- Main Page
- Related Pages
- Classes
- Files
- Examples

- File List
- File Members

# skype-dict.h

Go to the documentation of this file.

    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_ */

All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

(c) Skype Technologies S.A. Confidential/Proprietary

Last updated: Fri Jan 27 2012