Drizzled Public API Documentation

CSStorage.cc
00001 /* Copyright (C) 2008 PrimeBase Technologies GmbH, Germany
00002  *
00003  * PrimeBase Media Stream for MySQL
00004  *
00005  * This program is free software; you can redistribute it and/or modify
00006  * it under the terms of the GNU General Public License as published by
00007  * the Free Software Foundation; either version 2 of the License, or
00008  * (at your option) any later version.
00009  *
00010  * This program is distributed in the hope that it will be useful,
00011  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013  * GNU General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU General Public License
00016  * along with this program; if not, write to the Free Software
00017  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
00018  *
00019  * Original author: Paul McCullagh (H&G2JCtL)
00020  * Continued development: Barry Leslie
00021  *
00022  * 2007-06-15
00023  *
00024  * CORE SYSTEM STORAGE
00025  * Basic storage structures.
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  * HASH TABLE
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       /* Remove the object: */
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  * SORTED LIST
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  * LINK ITEM
00240  */
00241 
00242 /*
00243  * ---------------------------------------------------------------
00244  * LINK LIST
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     /* Must do this or I will have one reference too
00268      * many!
00269      * The input object was given to me referenced,
00270      * but I already have the object on my list, and
00271      * referenced!
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     /* Must do this or I will have one reference too
00292      * many!
00293      * The input object was given to me referenced,
00294      * but I already have the object on my list, and
00295      * referenced!
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     /* Removing dereferences the object! */
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     /* Removing dereferences the object! */
00352     remove(RETAIN(item));
00353   }
00354   return item;
00355 }
00356 
00357 CSObject *CSLinkedList::getFront()
00358 {
00359   return iListFront;
00360 }
00361 
00362 /*
00363  * ---------------------------------------------------------------
00364  * VECTOR
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  * SPARSE ARRAY
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   // If search fails then pos will be > iUsage
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  * ORDERED LIST
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