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_ */
(c) Skype Technologies S.A. Confidential/Proprietary
Last updated: Fri Jan 27 2012