00001 00002 #include "skype-ptrint-dict.h" 00003 #include <stdio.h> 00004 00005 #define SIZE 8123 00006 00007 /** \cond INTERNAL */ 00008 class SEPtrIntDict::Element 00009 { 00010 public: 00011 Element(const int k, const void* v); 00012 00013 public: 00014 Element* next; 00015 int key; 00016 const void* value; 00017 }; 00018 00019 class SEPtrIntDict::Data 00020 { 00021 public: 00022 Data(); 00023 00024 public: 00025 Element* dict[SIZE]; 00026 unsigned int ref; 00027 size_t size; 00028 bool dirty; 00029 Element** quick_list; 00030 SEMutex lock; 00031 }; 00032 00033 SEPtrIntDict::Element::Element(const int k, const void* v) 00034 :next(0), 00035 key(k), 00036 value(v) 00037 { 00038 00039 } 00040 00041 SEPtrIntDict::Data::Data() 00042 :dirty(true), 00043 quick_list(0) 00044 { 00045 00046 } 00047 /** \endcond */ 00048 00049 SEPtrIntDict::SEPtrIntDict() 00050 :d(0) 00051 { 00052 00053 } 00054 00055 SEPtrIntDict::SEPtrIntDict(const SEPtrIntDict& dict) 00056 :d(0) 00057 { 00058 *this = dict; 00059 } 00060 00061 SEPtrIntDict::~SEPtrIntDict() 00062 { 00063 d_unref(); 00064 } 00065 00066 void SEPtrIntDict::insert(const int key, const void* new_value) 00067 { 00068 detach(); 00069 00070 if (0 == d) { 00071 d = new Data(); 00072 00073 d->ref = 1; 00074 00075 for (size_t n = 0; n < SIZE; n++) 00076 d->dict[n] = 0; 00077 } 00078 00079 d->dirty = true; 00080 00081 unsigned int h = (unsigned int)key % SIZE; 00082 00083 Element** e = &(d->dict[h]); 00084 00085 while (*e) 00086 e = &((*e)->next); 00087 00088 *e = new Element(key, new_value); 00089 } 00090 00091 const void*& SEPtrIntDict::find(const int key, unsigned int offset) const 00092 { 00093 static const void* null = 0; 00094 00095 if (0 == d) 00096 return null; 00097 00098 unsigned int h = (unsigned int)key % SIZE; 00099 00100 Element** e = &(d->dict[h]); 00101 00102 while (*e) { 00103 if ((*e)->key == key) { 00104 if (0 == offset) { 00105 return (*e)->value; 00106 } else 00107 offset--; 00108 } 00109 00110 e = &((*e)->next); 00111 } 00112 00113 return null; 00114 } 00115 00116 SEPtrIntDict& SEPtrIntDict::operator=(const SEPtrIntDict& dict) 00117 { 00118 const_cast<SEPtrIntDict&>(dict).d_ref(); 00119 00120 d_unref(); 00121 00122 d = dict.d; 00123 00124 00125 return *this; 00126 } 00127 00128 /** \cond INTERNAL */ 00129 void SEPtrIntDict::d_ref() 00130 { 00131 if (0 == d) 00132 return; 00133 00134 d->lock.Acquire(); 00135 00136 d->ref++; 00137 00138 d->lock.Release(); 00139 } 00140 00141 void SEPtrIntDict::d_unref() 00142 { 00143 if (0 == d) 00144 return; 00145 00146 SEMutex* lock = &d->lock; 00147 00148 lock->Acquire(); 00149 00150 if (d->ref > 1) 00151 d->ref--; 00152 else { 00153 Data* tmp_d = d; 00154 d = 0; 00155 00156 lock->Release(); 00157 00158 for (size_t n = 0; n < SIZE; n++) { 00159 while (tmp_d->dict[n]) { 00160 Element* tmp = tmp_d->dict[n]->next; 00161 00162 delete tmp_d->dict[n]; 00163 00164 tmp_d->dict[n] = tmp; 00165 } 00166 } 00167 00168 if (tmp_d->quick_list) 00169 delete[] tmp_d->quick_list; 00170 00171 delete tmp_d; 00172 00173 return; 00174 } 00175 00176 lock->Release(); 00177 } 00178 00179 void SEPtrIntDict::detach() 00180 { 00181 if (0 == d) 00182 return; 00183 00184 d->lock.Acquire(); 00185 00186 if (1 != d->ref) { 00187 00188 Data* d_new = new Data(); 00189 00190 d_new->ref = 1; 00191 00192 size_t n; 00193 for (n = 0; n < SIZE; n++) 00194 d_new->dict[n] = 0; 00195 00196 for (n = 0; n < SIZE; n++) { 00197 Element** from = &(d->dict[n]); 00198 Element** to = &(d_new->dict[n]); 00199 00200 while (*from) { 00201 *to = new Element((*from)->key, (*from)->value); 00202 00203 from = &((*from)->next); 00204 to = &((*to)->next); 00205 } 00206 } 00207 00208 d->lock.Release(); 00209 00210 d_unref(); 00211 00212 d = d_new; 00213 00214 return; 00215 } 00216 00217 d->lock.Release(); 00218 } 00219 00220 /** \endcond */ 00221 00222 size_t SEPtrIntDict::size() const 00223 { 00224 if (0 == d) 00225 return 0; 00226 00227 if (d->dirty) { 00228 if (d->quick_list) 00229 delete[] d->quick_list; 00230 00231 d->size = 0; 00232 00233 size_t n; 00234 for (n = 0; n < SIZE; n++) { 00235 Element** e = &(d->dict[n]); 00236 00237 while (*e) { 00238 d->size++; 00239 00240 e = &((*e)->next); 00241 } 00242 } 00243 00244 d->quick_list = new Element*[d->size]; 00245 00246 size_t c = 0; 00247 00248 for (n = 0; n < SIZE; n++) { 00249 Element** e = &(d->dict[n]); 00250 00251 while (*e) { 00252 d->quick_list[c++] = *e; 00253 00254 e = &((*e)->next); 00255 } 00256 } 00257 00258 d->dirty = false; 00259 } 00260 00261 return d->size; 00262 } 00263 00264 const void*& SEPtrIntDict::operator[](size_t i) const 00265 { 00266 static const void* null = 0; 00267 00268 if (0 == d) 00269 return null; 00270 00271 if (i >= size()) 00272 return null;; 00273 00274 return d->quick_list[i]->value; 00275 } 00276 00277 int SEPtrIntDict::keyAt(size_t i) const 00278 { 00279 if (0 == d) 00280 return -1; 00281 00282 if (i >= size()) 00283 return 0; 00284 00285 return d->quick_list[i]->key; 00286 } 00287 00288 bool SEPtrIntDict::remove(const int key) 00289 { 00290 detach(); 00291 00292 if (0 == d) { 00293 d = new Data(); 00294 00295 d->ref = 1; 00296 00297 for (size_t n = 0; n < SIZE; n++) 00298 d->dict[n] = 0; 00299 } 00300 00301 d->dirty = true; 00302 00303 unsigned int h = (unsigned int)key % SIZE; 00304 00305 Element** e = &(d->dict[h]); 00306 00307 while (*e) { 00308 if ((*e)->key == key) { 00309 Element* tmp = *e; 00310 *e = (*e)->next; 00311 delete tmp; 00312 00313 return true; 00314 } 00315 e = &((*e)->next); 00316 } 00317 00318 return false; 00319 } 00320 00321 SEIntList SEPtrIntDict::keys() { 00322 SEIntList result; 00323 int d_size = size(); 00324 if (d && d->quick_list) { 00325 for (int i = 0; i < d_size; i++) { 00326 result.append(d->quick_list[i]->key); 00327 } 00328 } 00329 return result; 00330 } 00331 00332 00333 00334 00335 00336
(c) Skype Technologies S.A. Confidential/Proprietary
Last updated: Fri Mar 16 2012