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

- File List
- File Members

# skype-list.h

Go to the documentation of this file.

    00001 /*
    00002  * skype-list.h
    00003  *
    00004  *  Created on: Oct 5, 2010
    00005  *      Author: lauri
    00006  */
    00007
    00008 #ifndef SKYPELIST_H_
    00009 #define SKYPELIST_H_
    00010
    00011 #include <stdio.h>
    00012 #include <skype-string.h>
    00013
    00014 /** \cond INTERNAL */
    00015 template<class ElementType>
    00016 class SEList {
    00017 public:
    00018     /** Creates an empty list. */
    00019     SEList() :
    00020         d(0), empty(ElementType()) {
    00021     }
    00022
    00023     /** Constructs an implicitly shared copy of sl. */
    00024     SEList(const SEList<ElementType>& sl) :
    00025         d(0), empty(ElementType()) {
    00026         *this = sl;
    00027     }
    00028     /** Destroys the list and frees the data if this is the last reference to the list. */
    00029     ~SEList() {
    00030         d_unref();
    00031     }
    00032
    00033 protected:
    00034     class Element {
    00035     public:
    00036         Element() :
    00037             next(0) {
    00038         }
    00039         ;
    00040
    00041     public:
    00042         ElementType value;
    00043         Element* next;
    00044     };
    00045     class Data {
    00046     public:
    00047         unsigned int ref;
    00048         Element* list;
    00049         Element* last;
    00050         bool dirty;
    00051         Element** quick_list;
    00052         size_t size;
    00053         SEMutex lock;
    00054     };
    00055     Data* d;
    00056     ElementType empty;
    00057 /** \endcond */
    00058
    00059 public:
    00060     /** Appends a string at the end of the list. */
    00061     void push_back(const ElementType& str) {
    00062         append(str);
    00063     }
    00064     // specialize for string type
    00065     inline bool append_empty_string_if_param_isnull(const ElementType& param) {
    00066         return false;
    00067     }
    00068     /** Appends a element at the end of the list. */
    00069     SEList<ElementType>& append(const ElementType& param) {
    00070         if (append_empty_string_if_param_isnull(param))
    00071             return *this;
    00072
    00073         detach();
    00074         if (0 == d) {
    00075             init();
    00076
    00077             d->list = new Element();
    00078             d->list->value = param;
    00079             d->last = d->list;
    00080         } else {
    00081             d->dirty = true;
    00082             d->last->next = new Element();
    00083             d->last->next->value = param;
    00084             d->last = d->last->next;
    00085         }
    00086
    00087         return *this;
    00088     }
    00089     /** Removes the first element from the list and returns it. */
    00090     ElementType peek() {
    00091         detach();
    00092
    00093         if (0 == d)
    00094             return ElementType();
    00095
    00096         d->dirty = true;
    00097
    00098         ElementType ret = d->list->value;
    00099
    00100         Element* next = d->list->next;
    00101
    00102         delete d->list;
    00103
    00104         d->list = next;
    00105
    00106         if (0 == d->list) {
    00107             delete d;
    00108             d = 0;
    00109         }
    00110
    00111         return ret;
    00112     }
    00113     /** Returns the size of the list. */
    00114     size_t size() const {
    00115         if (0 == d)
    00116             return 0;
    00117
    00118         if (!d->dirty)
    00119             return d->size;
    00120
    00121         if (d->quick_list)
    00122             delete[] d->quick_list;
    00123
    00124         // first pass - count elements
    00125         d->size = 0;
    00126
    00127         Element* e = d->list;
    00128
    00129         do {
    00130             d->size++;
    00131         } while ((e = e->next));
    00132
    00133         // second pass - fill quick access vector
    00134         d->quick_list = new Element*[d->size];
    00135
    00136         e = d->list;
    00137         size_t n = 0;
    00138
    00139         while (e) {
    00140             d->quick_list[n++] = e;
    00141
    00142             e = e->next;
    00143         }
    00144
    00145         d->dirty = false;
    00146
    00147         return d->size;
    00148     }
    00149     /** Returns the string specified by its index. */
    00150     /*  ElementType operator[](size_t n) {
    00151      if ((0 == d) || (n >= size()))
    00152      return ElementType();
    00153
    00154      return d->quick_list[n]->param;
    00155      }*/
    00156
    00157     /** Returns a string reference specified by its index. */
    00158     const ElementType &operator[](size_t n) const {
    00159         if ((0 == d) || (n >= size()))
    00160             return empty;
    00161
    00162         // we have already called size() so we are supposed to be "clean"
    00163         return d->quick_list[n]->value;
    00164     }
    00165     /** Assigns a shallow copy of sl to this list and returns a reference to it.
    00166      * This is very fast because the list isn't actually copied.
    00167      */
    00168     SEList<ElementType>& operator=(const SEList<ElementType>& sl) {
    00169         const_cast<SEList&> (sl).d_ref();
    00170         d_unref();
    00171
    00172         d = sl.d;
    00173
    00174         return *this;
    00175
    00176     }
    00177     /** Creates a string out of the list of strings by joining them.
    00178      * \param sep String to use as a separator between each joined string.
    00179      * \param escape_args Should the parameters be escaped before joining them.
    00180      */
    00181     ElementType join(const ElementType& sep, bool escape_args = true) const {
    00182         ElementType ret;
    00183
    00184         if (!size())
    00185             return ret;
    00186
    00187         ret += escape_args ? operator[](0).escape() : operator[](0);
    00188
    00189         for (size_t n = 1; n < size(); n++)
    00190             ret += sep + (escape_args ? operator[](n).escape() : operator[](n));
    00191
    00192         return ret;
    00193     }
    00194
    00195     bool contains(const ElementType& val) {
    00196         return (find_pos(val) >= 0);
    00197     }
    00198
    00199     bool remove_val(const ElementType& val) {
    00200         int pos = find_pos(val);
    00201         if (pos >= 0)
    00202             return remove_pos(pos);
    00203
    00204         return false;
    00205     }
    00206
    00207     bool remove_pos(const unsigned int pos) {
    00208         if (0 == d || pos >= size())
    00209             return false;
    00210
    00211         detach();
    00212         unsigned int cursize = size();//updates quick_list
    00213
    00214         Element* elem_del = d->quick_list[pos];
    00215         Element* elem_next = elem_del->next;
    00216         Element* elem_prev = pos == 0 ? 0 : d->quick_list[pos - 1];
    00217
    00218         if (pos == 0) {//first
    00219             delete elem_del;
    00220             d->list = elem_next;
    00221         } else if (pos == cursize - 1) { //last
    00222             delete elem_del;
    00223             elem_prev->next = 0;
    00224             d->last = elem_prev;
    00225         } else {
    00226             delete elem_del;
    00227             elem_prev->next = elem_next;
    00228         }
    00229
    00230         d->dirty = true;
    00231         if (0 == d->list) {
    00232             delete d;
    00233             d = 0;
    00234         }
    00235
    00236         return true;
    00237     }
    00238
    00239     int find_pos(const ElementType& val) {
    00240         int len = size();
    00241         for (int n = 0; n < len; n++) {
    00242             if (d->quick_list[n]->value == val) {
    00243                 return n;
    00244             }
    00245         }
    00246
    00247         return -1;
    00248     }
    00249
    00250     void resize(const unsigned int new_size) {
    00251         if (size() == new_size)
    00252             return;
    00253         if (new_size == 0) {
    00254             clear();
    00255             return;
    00256         }
    00257
    00258         detach();
    00259         unsigned int cursize = size(); //updates quick_list
    00260
    00261         if (cursize > new_size) { //shrink
    00262
    00263             Element* elem_last = d->quick_list[new_size - 1];
    00264             elem_last->next = 0;
    00265             d->last = elem_last;
    00266
    00267             for (unsigned int n = new_size; n < cursize; n++) {
    00268                 delete d->quick_list[n];
    00269             }
    00270
    00271         } else { //grow
    00272
    00273             while (cursize < new_size) {
    00274                 if (0 == d) {
    00275                     init();
    00276                     d->list = new Element();
    00277                     d->list->value = ElementType();
    00278                     d->last = d->list;
    00279                 } else {
    00280                     d->last->next = new Element();
    00281                     d->last->next->value = ElementType();
    00282                     d->last = d->last->next;
    00283                 }
    00284
    00285                 cursize++;
    00286             }
    00287         }
    00288
    00289         d->dirty = true;
    00290     }
    00291     void clear() {
    00292         if (0 == d) {
    00293             return;
    00294         }
    00295
    00296         detach();
    00297
    00298         for (unsigned int n = 0; n < size(); n++) {
    00299             delete d->quick_list[n];
    00300         }
    00301
    00302         if (d->quick_list)
    00303             delete[] d->quick_list;
    00304
    00305         delete d;
    00306
    00307         d = 0;
    00308     }
    00309     /** \cond INTERNAL */
    00310 protected:
    00311     void init() {
    00312         if (d)
    00313             return;
    00314
    00315         d = new Data();
    00316         d->ref = 1;
    00317         d->list = 0;
    00318         d->dirty = true;
    00319         d->size = 0;
    00320         d->quick_list = 0;
    00321     }
    00322     void d_ref() {
    00323         if (0 == d)
    00324             return;
    00325
    00326         d->lock.Acquire();
    00327
    00328         d->ref++;
    00329
    00330         d->lock.Release();
    00331     }
    00332     void d_unref() {
    00333         if (0 == d)
    00334             return;
    00335
    00336         SEMutex* lock = &d->lock;
    00337
    00338         lock->Acquire();
    00339
    00340         if (d->ref > 1)
    00341             d->ref--;
    00342         else {
    00343             Data* tmp_d = d;
    00344             d = 0;
    00345             lock->Release();
    00346
    00347             Element* tmp = tmp_d->list;
    00348
    00349             while (tmp) {
    00350                 Element* next = tmp->next;
    00351
    00352                 delete tmp;
    00353
    00354                 tmp = next;
    00355             }
    00356
    00357             if (tmp_d->quick_list)
    00358                 delete[] tmp_d->quick_list;
    00359
    00360             delete tmp_d;
    00361             return;
    00362         }
    00363
    00364         lock->Release();
    00365     }
    00366     void detach() {
    00367         if (0 == d)
    00368             return;
    00369
    00370         d->lock.Acquire();
    00371
    00372         if (1 != d->ref) {
    00373
    00374             Data* d_new = new Data();
    00375
    00376             d_new->ref = 1;
    00377             d_new->dirty = true;
    00378             d_new->quick_list = 0;
    00379
    00380             d_new->list = new Element;
    00381             d_new->list->value = d->list->value;
    00382
    00383             Element* from = d->list->next;
    00384             Element* to = d_new->list;
    00385
    00386             while (from) {
    00387                 to->next = new Element;
    00388                 to->next->value = from->value;
    00389
    00390                 to = to->next;
    00391                 from = from->next;
    00392             }
    00393
    00394             d_new->last = to;
    00395
    00396             d->lock.Release();
    00397
    00398             d_unref();
    00399
    00400             d = d_new;
    00401
    00402             return;
    00403         }
    00404
    00405         d->lock.Release();
    00406     }
    00407     /** \endcond */
    00408 };
    00409
    00410 template<>
    00411 inline bool SEList< SEString >::append_empty_string_if_param_isnull(const SEString& elem) {
    00412     if (elem.isNull()) {
    00413         append("");
    00414         return true;
    00415     }
    00416     return false;
    00417 }
    00418
    00419 #endif /* SKYPELIST_H_ */

All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

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

Last updated: Fri Jan 27 2012