00001 00002 #include "skype-uint64-list.h" 00003 00004 /** \cond INTERNAL */ 00005 class SEUInt64List::Element 00006 { 00007 public: 00008 Element(); 00009 00010 public: 00011 SEUInt64List::uint64 i; 00012 Element* next; 00013 }; 00014 00015 class SEUInt64List::Data 00016 { 00017 public: 00018 unsigned int ref; 00019 Element* list; 00020 Element* last; 00021 bool dirty; 00022 Element** quick_list; 00023 size_t size; 00024 SEMutex lock; 00025 }; 00026 00027 SEUInt64List::Element::Element() 00028 :next(0) 00029 { 00030 00031 } 00032 /** \endcond */ 00033 00034 SEUInt64List::SEUInt64List() 00035 :d(0) 00036 { 00037 00038 } 00039 00040 SEUInt64List::SEUInt64List(const SEUInt64List& sl) 00041 :d(0) 00042 { 00043 *this = sl; 00044 } 00045 00046 SEUInt64List::~SEUInt64List() 00047 { 00048 d_unref(); 00049 } 00050 00051 /** \cond INTERNAL */ 00052 void SEUInt64List::init() 00053 { 00054 if (d) 00055 return; 00056 00057 d = new Data(); 00058 d->ref = 1; 00059 d->list = 0; 00060 d->dirty = true; 00061 d->size = 0; 00062 d->quick_list = 0; 00063 } 00064 /** \endcond */ 00065 00066 SEUInt64List& SEUInt64List::append(const SEUInt64List::uint64 i) 00067 { 00068 detach(); 00069 00070 if (0 == d) { 00071 init(); 00072 00073 d->list = new Element(); 00074 d->list->i = i; 00075 d->last = d->list; 00076 } else { 00077 d->dirty = true; 00078 d->last->next = new Element(); 00079 d->last->next->i = i; 00080 d->last = d->last->next; 00081 } 00082 // printf("added to intlist %d\n",i); 00083 return *this; 00084 } 00085 00086 #if 0 00087 SEUInt64List& SEUInt64List::prepend(const SEUInt64List::uint64 i) 00088 { 00089 detach(); 00090 00091 if (0 == d) { 00092 init(); 00093 00094 d->list = new Element(); 00095 d->list->i = i; 00096 d->last = d->list; 00097 } else { 00098 d->dirty = true; 00099 00100 Element* n = new Element(); 00101 00102 n->i = i; 00103 n->next = d->list; 00104 d->list = n; 00105 } 00106 00107 return *this; 00108 } 00109 #endif 00110 00111 SEUInt64List::uint64 SEUInt64List::peek() 00112 { 00113 detach(); 00114 00115 if (0 == d) 00116 return 0; 00117 00118 d->dirty = true; 00119 00120 uint64 ret = d->list->i; 00121 00122 Element* next = d->list->next; 00123 00124 delete d->list; 00125 00126 d->list = next; 00127 00128 if (0 == d->list) { 00129 delete d; 00130 d = 0; 00131 } 00132 00133 return ret; 00134 } 00135 00136 size_t SEUInt64List::size() const 00137 { 00138 if (0 == d) 00139 return 0; 00140 00141 if (!d->dirty) 00142 return d->size; 00143 00144 if (d->quick_list) 00145 delete[] d->quick_list; 00146 00147 // first pass - count elements 00148 d->size = 0; 00149 00150 Element* e = d->list; 00151 00152 do { 00153 d->size++; 00154 e = e->next; 00155 } while (e); 00156 00157 // second pass - fill quick access vector 00158 d->quick_list = new Element*[d->size]; 00159 00160 e = d->list; 00161 size_t n = 0; 00162 00163 while (e) { 00164 d->quick_list[n++] = e; 00165 00166 e = e->next; 00167 } 00168 00169 d->dirty = false; 00170 00171 return d->size; 00172 } 00173 00174 SEUInt64List::uint64 & SEUInt64List::operator [](size_t index) 00175 { 00176 static uint64 null = 0; 00177 Element* cur = d->list; 00178 unsigned int i = 0; 00179 while ((cur)) { 00180 if (i == index) return cur->i; 00181 i++; 00182 cur = cur->next; 00183 } 00184 00185 return null; 00186 } 00187 00188 SEUInt64List& SEUInt64List::operator=(const SEUInt64List& sl) 00189 { 00190 const_cast<SEUInt64List&>(sl).d_ref(); 00191 00192 d_unref(); 00193 00194 d = sl.d; 00195 00196 return *this; 00197 } 00198 00199 /** \cond INTERNAL */ 00200 void SEUInt64List::d_ref() 00201 { 00202 if (0 == d) 00203 return; 00204 00205 d->lock.Acquire(); 00206 00207 d->ref++; 00208 00209 d->lock.Release(); 00210 } 00211 00212 void SEUInt64List::d_unref() 00213 { 00214 if (0 == d) 00215 return; 00216 00217 SEMutex* lock = &d->lock; 00218 00219 lock->Acquire(); 00220 00221 if (d->ref > 1) 00222 d->ref--; 00223 else { 00224 Data* tmp_d = d; 00225 00226 d = 0; 00227 00228 lock->Release(); 00229 00230 Element* tmp = tmp_d->list; 00231 00232 while (tmp) { 00233 Element* next = tmp->next; 00234 00235 delete tmp; 00236 00237 tmp = next; 00238 } 00239 00240 if (tmp_d->quick_list) 00241 delete[] tmp_d->quick_list; 00242 00243 delete tmp_d; 00244 00245 return; 00246 } 00247 00248 lock->Release(); 00249 } 00250 00251 void SEUInt64List::detach() 00252 { 00253 if (0 == d) 00254 return; 00255 00256 d->lock.Acquire(); 00257 00258 if (1 != d->ref) { 00259 00260 Data* d_new = new Data(); 00261 00262 d_new->ref = 1; 00263 d_new->dirty = true; 00264 d_new->quick_list = 0; 00265 00266 d_new->list = new Element; 00267 d_new->list->i = d->list->i; 00268 00269 Element* from = d->list->next; 00270 Element* to = d_new->list; 00271 00272 while (from) { 00273 to->next = new Element; 00274 to->next->i = from->i; 00275 00276 to = to->next; 00277 from = from->next; 00278 } 00279 00280 d_new->last = to; 00281 00282 d->lock.Release(); 00283 00284 d_unref(); 00285 00286 d = d_new; 00287 00288 return; 00289 } 00290 00291 d->lock.Release(); 00292 } 00293 /** \endcond */ 00294 00295 SEUInt64List SEUInt64List::split(const SEString& str, char sep, char esc) 00296 { 00297 SEUInt64List ret; 00298 int from = 0; 00299 int cur = 0; 00300 int len = (int)str.length(); 00301 00302 // skip trailing separators 00303 while (str[cur] == sep) { 00304 from++; 00305 cur++; 00306 } 00307 00308 cur++; 00309 00310 while (cur <= len) { 00311 // the case when we go out of bounds is when we have escaped separator 00312 // before end of the string 00313 if (cur == len) { 00314 ret.append(str.substr((int)from, (int)cur - 1).toUInt64()); 00315 00316 break; 00317 } 00318 00319 if (str[cur] == sep) { 00320 // here we may go out of bounds (handled above) 00321 if (esc && (str[cur - 1] == esc)) { 00322 cur++; 00323 00324 continue; 00325 } 00326 00327 ret.append(str.substr(from, cur - 1).toUInt64()); 00328 00329 while ((str[cur] == sep) && (cur < len)) cur++; 00330 00331 if (cur >= (len - 1)) 00332 break; 00333 00334 from = cur++; 00335 00336 continue; 00337 } 00338 00339 if (cur == (len - 1)) { 00340 ret.append(str.substr(from, cur).toUInt64()); 00341 00342 break; 00343 } 00344 00345 cur++; 00346 } 00347 00348 return ret; 00349 } 00350 00351 int SEUInt64List::find_pos(const SEUInt64List::uint64 val) 00352 { 00353 int len = size(); 00354 for (int n = 0; n < len; n++) { 00355 if (d->quick_list[n]->i == val) { 00356 return n; 00357 } 00358 } 00359 00360 return -1; 00361 } 00362 00363 bool SEUInt64List::contains(const SEUInt64List::uint64 val) 00364 { 00365 return (find_pos(val) >= 0); 00366 } 00367 00368 bool SEUInt64List::remove_val(const SEUInt64List::uint64 val) 00369 { 00370 int pos = find_pos(val); 00371 if (pos >= 0) return remove_pos(pos); 00372 00373 return false; 00374 } 00375 00376 bool SEUInt64List::remove_pos(const unsigned int pos) 00377 { 00378 if (0 == d || pos >= size()) return false; 00379 00380 detach(); 00381 unsigned int cursize = size();//updates quick_list 00382 00383 Element* elem_del = d->quick_list[pos]; 00384 Element* elem_next = elem_del->next; 00385 Element* elem_prev = pos == 0 ? 0 : d->quick_list[pos-1]; 00386 00387 if (pos == 0) {//first 00388 delete elem_del; 00389 d->list = elem_next; 00390 } else if (pos == cursize -1) { //last 00391 delete elem_del; 00392 elem_prev->next = 0; 00393 d->last = elem_prev; 00394 } else { 00395 delete elem_del; 00396 elem_prev->next = elem_next; 00397 } 00398 00399 d->dirty = true; 00400 if (0 == d->list) { 00401 delete d; 00402 d = 0; 00403 } 00404 00405 return true; 00406 } 00407 00408 void SEUInt64List::resize(const unsigned int new_size) 00409 { 00410 if (size() == new_size) return; 00411 if (new_size == 0) { 00412 clear(); 00413 return; 00414 } 00415 00416 detach(); 00417 unsigned int cursize = size(); //updates quick_list 00418 00419 if (cursize > new_size) { //shrink 00420 00421 Element* elem_last = d->quick_list[new_size-1]; 00422 elem_last->next = 0; 00423 d->last = elem_last; 00424 00425 for (unsigned int n = new_size; n < cursize; n++) { 00426 delete d->quick_list[n]; 00427 } 00428 00429 } else { //grow 00430 00431 while (cursize < new_size) { 00432 if (0 == d) { 00433 init(); 00434 d->list = new Element(); 00435 d->list->i = 0; 00436 d->last = d->list; 00437 } else { 00438 d->last->next = new Element(); 00439 d->last->next->i = 0; 00440 d->last = d->last->next; 00441 } 00442 00443 cursize++; 00444 } 00445 } 00446 00447 d->dirty = true; 00448 } 00449 00450 void SEUInt64List::clear() 00451 { 00452 if (0 == d) { 00453 return; 00454 } 00455 00456 detach(); 00457 00458 for (unsigned int n = 0; n < size(); n++) { 00459 delete d->quick_list[n]; 00460 } 00461 00462 if (d->quick_list) 00463 delete[] d->quick_list; 00464 00465 delete d; 00466 00467 d = 0; 00468 } 00469 00470 00471 00472 00473 00474 00475 00476 00477 00478 00479 00480
(c) Skype Technologies S.A. Confidential/Proprietary
Last updated: Fri Mar 16 2012