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