00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #include "CSConfig.h"
00030
00031 #include <assert.h>
00032 #include <string.h>
00033
00034 #include "CSMemory.h"
00035 #include "CSUTF8.h"
00036 #include "CSStorage.h"
00037 #include "CSGlobal.h"
00038
00039
00040
00041
00042
00043
00044 CSHashTable::~CSHashTable()
00045 {
00046 clear();
00047 iSize = 0;
00048 if (iTable) {
00049 cs_free(iTable);
00050 iTable = NULL;
00051 }
00052
00053 }
00054
00055 void CSHashTable::setSize(uint32_t size)
00056 {
00057 enter_();
00058 if (size == 0) {
00059 if (iTable) {
00060 cs_free(iTable);
00061 iTable = NULL;
00062 }
00063 }
00064 else {
00065 cs_realloc((void **) &iTable, sizeof(CSObject *) * size);
00066 memset(iTable, 0, sizeof(CSObject *) * size);
00067 }
00068 iSize = size;
00069 exit_();
00070 }
00071
00072 void CSHashTable::add(CSObject *item)
00073 {
00074 uint32_t h = item->hashKey();
00075
00076 remove(item->getKey());
00077 item->setHashLink(iTable[h % iSize]);
00078 iTable[h % iSize] = item;
00079 }
00080
00081 CSObject *CSHashTable::find(CSObject *key)
00082 {
00083 uint32_t h = key->hashKey();
00084 CSObject *item;
00085
00086 item = iTable[h % iSize];
00087 while (item) {
00088 if (item->hashKey() == h && item->compareKey(key) == 0)
00089 return item;
00090 item = item->getHashLink();
00091 }
00092 return NULL;
00093 }
00094
00095 bool CSHashTable::remove(CSObject *key)
00096 {
00097 uint32_t h = key->hashKey();
00098 CSObject *item, *prev_item;
00099
00100 prev_item = NULL;
00101 item = iTable[h % iSize];
00102 while (item) {
00103 if (item->hashKey() == h && item->compareKey(key) == 0) {
00104
00105 if (prev_item)
00106 prev_item->setHashLink(item->getHashLink());
00107 else
00108 iTable[h % iSize] = item->getHashLink();
00109 item->release();
00110 return true;
00111 }
00112 prev_item = item;
00113 item = item->getHashLink();
00114 }
00115 return false;
00116 }
00117
00118 void CSHashTable::clear()
00119 {
00120 CSObject *item, *tmp_item;
00121
00122 for (uint32_t i=0; i<iSize; i++) {
00123 item = iTable[i];
00124 while ((tmp_item = item)) {
00125 item = tmp_item->getHashLink();
00126 tmp_item->release();
00127 }
00128 }
00129 }
00130
00131
00132
00133
00134
00135
00136 void CSSortedList::clear()
00137 {
00138 if (iList) {
00139 for (uint32_t i=0; i<iInUse; i++)
00140 iList[i]->release();
00141 cs_free(iList);
00142 iList = NULL;
00143 }
00144 iInUse = 0;
00145 iListSize = 0;
00146 }
00147
00148 void CSSortedList::add(CSObject *item)
00149 {
00150 CSObject *old_item;
00151 uint32_t idx;
00152
00153 enter_();
00154 if ((old_item = search(item->getKey(), idx))) {
00155 iList[idx] = item;
00156 old_item->release();
00157 }
00158 else {
00159 if (iInUse == iListSize) {
00160 push_(item);
00161 cs_realloc((void **) &iList, (iListSize + SC_SORT_LIST_INC_SIZE) * sizeof(CSObject *));
00162 pop_(item);
00163 iListSize += SC_SORT_LIST_INC_SIZE;
00164 }
00165 memmove(&iList[idx+1], &iList[idx], (iInUse - idx) * sizeof(CSObject *));
00166 iInUse++;
00167 iList[idx] = item;
00168 }
00169 exit_();
00170 }
00171
00172 CSObject *CSSortedList::find(CSObject *key)
00173 {
00174 uint32_t idx;
00175
00176 return search(key, idx);
00177 }
00178
00179 CSObject *CSSortedList::itemAt(uint32_t idx)
00180 {
00181 if (idx >= iInUse)
00182 return NULL;
00183 return iList[idx];
00184 }
00185
00186 CSObject *CSSortedList::takeItemAt(uint32_t idx)
00187 {
00188 CSObject *item;
00189
00190 if (idx >= iInUse)
00191 return NULL;
00192
00193 item = iList[idx];
00194
00195 iInUse--;
00196 memmove(&iList[idx], &iList[idx+1], (iInUse - idx) * sizeof(CSObject *));
00197 return item;
00198 }
00199
00200 void CSSortedList::remove(CSObject *key)
00201 {
00202 CSObject *item;
00203 uint32_t idx;
00204
00205 if ((item = search(key, idx))) {
00206 iInUse--;
00207 memmove(&iList[idx], &iList[idx+1], (iInUse - idx) * sizeof(CSObject *));
00208 item->release();
00209 }
00210 }
00211
00212 CSObject *CSSortedList::search(CSObject *key, uint32_t& idx)
00213 {
00214 register uint32_t count = iInUse;
00215 register uint32_t i;
00216 register uint32_t guess;
00217 register int r;
00218
00219 i = 0;
00220 while (i < count) {
00221 guess = (i + count - 1) >> 1;
00222 r = iList[guess]->compareKey(key);
00223 if (r == 0) {
00224 idx = guess;
00225 return iList[guess];
00226 }
00227 if (r < 0)
00228 count = guess;
00229 else
00230 i = guess + 1;
00231 }
00232
00233 idx = i;
00234 return NULL;
00235 }
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247 void CSLinkedList::clear()
00248 {
00249 while (iListFront)
00250 remove(iListFront);
00251 }
00252
00253 void CSLinkedList::addFront(CSObject *item)
00254 {
00255 if (iListFront != item) {
00256 remove(item);
00257 item->setNextLink(NULL);
00258 item->setPrevLink(iListFront);
00259 if (iListFront)
00260 iListFront->setNextLink(item);
00261 else
00262 iListBack = item;
00263 iListFront = item;
00264 iSize++;
00265 }
00266 else
00267
00268
00269
00270
00271
00272
00273 item->release();
00274 }
00275
00276 void CSLinkedList::addBack(CSObject *item)
00277 {
00278 if (iListBack != item) {
00279 remove(item);
00280 item->setNextLink(iListBack);
00281 item->setPrevLink(NULL);
00282
00283 if (iListBack)
00284 iListBack->setPrevLink(item);
00285 else
00286 iListFront = item;
00287 iListBack = item;
00288 iSize++;
00289 }
00290 else
00291
00292
00293
00294
00295
00296
00297 item->release();
00298 }
00299
00300 bool CSLinkedList::remove(CSObject *item)
00301 {
00302 bool on_list = false;
00303
00304 if (item->getNextLink()) {
00305 item->getNextLink()->setPrevLink(item->getPrevLink());
00306 on_list = true;
00307 }
00308 if (item->getPrevLink()) {
00309 item->getPrevLink()->setNextLink(item->getNextLink());
00310 on_list = true;
00311 }
00312 if (iListFront == item) {
00313 iListFront = item->getPrevLink();
00314 on_list = true;
00315 }
00316 if (iListBack == item) {
00317 iListBack = item->getNextLink();
00318 on_list = true;
00319 }
00320 item->setNextLink(NULL);
00321 item->setPrevLink(NULL);
00322 if (on_list) {
00323 item->release();
00324 iSize--;
00325 return true;
00326 }
00327 return false;
00328 }
00329
00330 CSObject *CSLinkedList::removeBack()
00331 {
00332 CSObject *item = iListBack;
00333
00334 if (item) {
00335
00336 remove(RETAIN(item));
00337 }
00338 return item;
00339 }
00340
00341 CSObject *CSLinkedList::getBack()
00342 {
00343 return iListBack;
00344 }
00345
00346 CSObject *CSLinkedList::removeFront()
00347 {
00348 CSObject *item = iListFront;
00349
00350 if (item) {
00351
00352 remove(RETAIN(item));
00353 }
00354 return item;
00355 }
00356
00357 CSObject *CSLinkedList::getFront()
00358 {
00359 return iListFront;
00360 }
00361
00362
00363
00364
00365
00366
00367 void CSVector::free()
00368 {
00369 clear();
00370 iMaxSize = 0;
00371 if (iArray) {
00372 cs_free(iArray);
00373 iArray = NULL;
00374 }
00375 }
00376
00377 void CSVector::clear()
00378 {
00379 uint32_t i = iUsage;
00380
00381 for (;;) {
00382 if (i == 0)
00383 break;
00384 i--;
00385 if (iArray[i]) {
00386 CSObject *obj;
00387
00388 obj = iArray[i];
00389 iArray[i] = NULL;
00390 obj->release();
00391 }
00392 }
00393 iUsage = 0;
00394 }
00395
00396 CSObject *CSVector::take(uint32_t idx)
00397 {
00398 CSObject *obj;
00399
00400 if (idx >= iUsage)
00401 return NULL;
00402
00403 obj = iArray[idx];
00404 iUsage--;
00405 memmove(&iArray[idx], &iArray[idx+1], (iUsage - idx) * sizeof(CSObject *));
00406 return obj;
00407 }
00408
00409 void CSVector::remove(uint32_t idx)
00410 {
00411 CSObject *obj;
00412
00413 if (idx >= iUsage)
00414 return;
00415
00416 obj = iArray[idx];
00417 iUsage--;
00418 memmove(&iArray[idx], &iArray[idx+1], (iUsage - idx) * sizeof(CSObject *));
00419 obj->release();
00420 }
00421
00422 CSObject *CSVector::get(uint32_t idx)
00423 {
00424 if (idx >= iUsage)
00425 return NULL;
00426 return iArray[idx];
00427 }
00428
00429 void CSVector::set(uint32_t idx, CSObject *val)
00430 {
00431 enter_();
00432 if (idx >= iMaxSize) {
00433 push_(val);
00434 cs_realloc((void **) &iArray, sizeof(CSObject *) * (idx + iGrowSize - 1));
00435 pop_(val);
00436 iMaxSize = idx + iGrowSize - 1;
00437 }
00438 if (idx >= iUsage) {
00439 if (idx > iUsage)
00440 memset(&iArray[iUsage], 0, sizeof(CSObject *) * (idx - iUsage));
00441 iUsage = idx + 1;
00442 }
00443 else if (iArray[idx]) {
00444 push_(val);
00445 iArray[idx]->release();
00446 pop_(val);
00447 }
00448 iArray[idx] = val;
00449 exit_();
00450 }
00451
00452 void CSVector::add(CSObject *obj)
00453 {
00454 enter_();
00455 if (iUsage == iMaxSize) {
00456 push_(obj);
00457 cs_realloc((void **) &iArray, sizeof(CSObject *) * (iMaxSize + iGrowSize));
00458 pop_(obj);
00459 iMaxSize += iGrowSize;
00460 }
00461 iArray[iUsage] = obj;
00462 iUsage++;
00463 exit_();
00464 }
00465
00466
00467
00468
00469
00470
00471 void CSSparseArray::free()
00472 {
00473 clear();
00474 iMaxSize = 0;
00475 if (iArray) {
00476 cs_free(iArray);
00477 iArray = NULL;
00478 }
00479 }
00480
00481 void CSSparseArray::clear()
00482 {
00483 uint32_t i = iUsage;
00484
00485 for (;;) {
00486 if (i == 0)
00487 break;
00488 i--;
00489 if (iArray[i].sa_object) {
00490 CSObject *obj;
00491
00492 obj = iArray[i].sa_object;
00493 iArray[i].sa_object = NULL;
00494 obj->release();
00495 }
00496 }
00497 iUsage = 0;
00498 }
00499
00500 CSObject *CSSparseArray::take(uint32_t idx)
00501 {
00502 uint32_t pos;
00503 CSObject *obj;
00504
00505 if (!(obj = search(idx, pos)))
00506 return NULL;
00507 iUsage--;
00508 memmove(&iArray[pos], &iArray[pos+1], (iUsage - pos) * sizeof(CSSpareArrayItemRec));
00509 return obj;
00510 }
00511
00512 void CSSparseArray::remove(uint32_t idx)
00513 {
00514 uint32_t pos;
00515 CSObject *obj;
00516
00517 if (!(obj = search(idx, pos)))
00518 return;
00519 iUsage--;
00520 memmove(&iArray[pos], &iArray[pos+1], (iUsage - pos) * sizeof(CSSpareArrayItemRec));
00521 obj->release();
00522 }
00523
00524 CSObject *CSSparseArray::itemAt(uint32_t idx)
00525 {
00526 if (idx >= iUsage)
00527 return NULL;
00528 return iArray[idx].sa_object;
00529 }
00530
00531 CSObject *CSSparseArray::get(uint32_t idx)
00532 {
00533 uint32_t pos;
00534
00535 return search(idx, pos);
00536 }
00537
00538 uint32_t CSSparseArray::getIndex(uint32_t idx)
00539 {
00540 uint32_t pos;
00541
00542
00543 search(idx, pos);
00544 return pos;
00545 }
00546
00547 void CSSparseArray::set(uint32_t idx, CSObject *val)
00548 {
00549 uint32_t pos;
00550 CSObject *obj;
00551
00552 enter_();
00553 push_(val);
00554
00555 if ((obj = search(idx, pos)))
00556 obj->release();
00557 else {
00558 if (iUsage == iMaxSize) {
00559 cs_realloc((void **) &iArray, (iMaxSize + iGrowSize) * sizeof(CSSpareArrayItemRec));
00560 iMaxSize += iGrowSize;
00561 }
00562 memmove(&iArray[pos+1], &iArray[pos], (iUsage - pos) * sizeof(CSSpareArrayItemRec));
00563 iUsage++;
00564 iArray[pos].sa_index = idx;
00565 }
00566 pop_(val);
00567 iArray[pos].sa_object = val;
00568 exit_();
00569 }
00570
00571 void CSSparseArray::removeFirst()
00572 {
00573 if (iUsage > 0)
00574 remove(iArray[0].sa_index);
00575 }
00576
00577 CSObject *CSSparseArray::first()
00578 {
00579 if (iUsage == 0)
00580 return NULL;
00581 return iArray[0].sa_object;
00582 }
00583
00584 CSObject *CSSparseArray::last()
00585 {
00586 if (iUsage == 0)
00587 return NULL;
00588 return iArray[iUsage-1].sa_object;
00589 }
00590
00591 CSObject *CSSparseArray::search(uint32_t idx, uint32_t& pos)
00592 {
00593 register uint32_t count = iUsage;
00594 register uint32_t i;
00595 register uint32_t guess;
00596
00597 i = 0;
00598 while (i < count) {
00599 guess = (i + count - 1) >> 1;
00600 if (idx == iArray[guess].sa_index) {
00601 pos = guess;
00602 return iArray[guess].sa_object;
00603 }
00604 if (idx < iArray[guess].sa_index)
00605 count = guess;
00606 else
00607 i = guess + 1;
00608 }
00609
00610 pos = i;
00611 return NULL;
00612 }
00613
00614
00615
00616
00617
00618
00619 void CSOrderedList::clear()
00620 {
00621 if (iList) {
00622 for (uint32_t i=0; i<iInUse; i++) {
00623 if (iList[i].li_key)
00624 iList[i].li_key->release();
00625 if (iList[i].li_item)
00626 iList[i].li_item->release();
00627 }
00628 cs_free(iList);
00629 iList = NULL;
00630 }
00631 iInUse = 0;
00632 iListSize = 0;
00633 }
00634
00635 CSObject *CSOrderedList::itemAt(uint32_t idx)
00636 {
00637 if (idx >= iInUse)
00638 return NULL;
00639 return iList[idx].li_item;
00640 }
00641
00642
00643 void CSOrderedList::add(CSOrderKey *key, CSObject *item)
00644 {
00645 CSOrderedListItemPtr old_item;
00646 uint32_t idx;
00647
00648 enter_();
00649 if ((old_item = search(key, &idx))) {
00650 iList[idx].li_key = key;
00651 iList[idx].li_item = item;
00652 if (old_item->li_key)
00653 old_item->li_key->release();
00654 if (old_item->li_item)
00655 old_item->li_item->release();
00656 }
00657 else {
00658 if (iInUse == iListSize) {
00659 push_(key);
00660 push_(item);
00661 cs_realloc((void **) &iList, (iListSize + SC_SORT_LIST_INC_SIZE) * sizeof(CSOrderedListItemRec));
00662 pop_(item);
00663 pop_(key);
00664 iListSize += SC_SORT_LIST_INC_SIZE;
00665 }
00666 memmove(&iList[idx+1], &iList[idx], (iInUse - idx) * sizeof(CSOrderedListItemRec));
00667 iInUse++;
00668 iList[idx].li_key = key;
00669 iList[idx].li_item = item;
00670 }
00671 exit_();
00672 }
00673
00674 CSObject *CSOrderedList::find(CSOrderKey *key)
00675 {
00676 uint32_t idx;
00677 CSOrderedListItemPtr ptr;
00678
00679 if ((ptr = search(key, &idx)))
00680 return ptr->li_item;
00681 return NULL;
00682 }
00683
00684 void CSOrderedList::remove(CSOrderKey *key)
00685 {
00686 CSOrderedListItemPtr item;
00687 uint32_t idx;
00688
00689 if ((item = search(key, &idx))) {
00690 CSOrderedListItemRec ir;
00691
00692 memcpy(&ir, item, sizeof(CSOrderedListItemRec));
00693 iInUse--;
00694 memmove(&iList[idx], &iList[idx+1], (iInUse - idx) * sizeof(CSOrderedListItemRec));
00695 if (ir.li_key)
00696 ir.li_key->release();
00697 if (ir.li_item)
00698 ir.li_item->release();
00699 }
00700 }
00701
00702 CSOrderedListItemPtr CSOrderedList::search(CSOrderKey *key, uint32_t *idx)
00703 {
00704 register uint32_t count = iInUse;
00705 register uint32_t i;
00706 register uint32_t guess;
00707 register int r;
00708
00709 i = 0;
00710 while (i < count) {
00711 guess = (i + count - 1) >> 1;
00712 r = iList[guess].li_key->compareKey(key);
00713 if (r == 0) {
00714 *idx = guess;
00715 return &iList[guess];
00716 }
00717 if (r < 0)
00718 count = guess;
00719 else
00720 i = guess + 1;
00721 }
00722
00723 *idx = i;
00724 return NULL;
00725 }
00726
00727