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