Home | History | Annotate | Download | only in src 
      1 /* ------------------------------------------------------------------
      2  * Copyright (C) 1998-2009 PacketVideo
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
     13  * express or implied.
     14  * See the License for the specific language governing permissions
     15  * and limitations under the License.
     16  * -------------------------------------------------------------------
     17  */
     18 // class for encapsulating string based key-value pair handlings
     19 #include "string_keyvalue_store.h"
     20 #include "oscl_variablesize_mem_pool.h"
     21 
     22 #define STRINGKEYVALUESTOREOVERHEAD 100
     23 
     24 uint32 StringKeyValueStore::getCurrentMemoryUsage()
     25 {
     26     return iVariableSizeMemPool->getCurrMemoryUsage();
     27 }
     28 
     29 uint32 StringKeyValueStore::getStoreSize()
     30 {
     31     return iVariableSizeMemPool->getPoolSize();
     32 }
     33 
     34 uint32 StringKeyValueStore::getAvailableSize()
     35 {
     36     return (iVariableSizeMemPool->getTotalAvailableSize() - STRINGKEYVALUESTOREOVERHEAD);
     37 }
     38 
     39 ///////////////////////////////////////////////////////////////////////////////////////////////////
     40 bool StringKeyValueStore::storeNewKeyValueItem(const char *aItem, const int32 aItemLength, char *&aNewLocation)
     41 {
     42     int32 err = 0;
     43     OSCL_TRY(err, aNewLocation = (char*)iVariableSizeMemPool->allocate(aItemLength + 1););
     44     if (err || aNewLocation == NULL) return false;
     45     oscl_memcpy(aNewLocation, aItem, aItemLength);
     46     aNewLocation[aItemLength] = 0;
     47     return true;
     48 }
     49 
     50 void StringKeyValueStore::releaseOldKeyValueItem(const char *aItem, const int32 aItemLength)
     51 {
     52     OSCL_UNUSED_ARG(aItemLength);
     53 
     54     int32 err = 0;
     55     OSCL_TRY(err, iVariableSizeMemPool->deallocate((OsclAny*)aItem););
     56 }
     57 
     58 int32 StringKeyValueStore::addKeyToStore(const StrCSumPtrLen &aNewKey, int32 tableIndex)
     59 {
     60     if (!iFieldKeys[tableIndex].empty()) return StringKeyValueStore_Success;
     61 
     62     // new field
     63     // save this checksum
     64     int32 err = 0;
     65     OSCL_TRY(err, iFieldKeyTableIndexVector.push_back(tableIndex));
     66     if (err) return StringKeyValueStore_NoMemory;
     67 
     68     // add new field key
     69     char *newLocation = NULL;
     70     int32 aKeyLength = aNewKey.length();
     71     if (!storeNewKeyValueItem(aNewKey.c_str(), aKeyLength, newLocation)) return StringKeyValueStore_NoMemory;
     72     iFieldKeys[tableIndex].setPtrLen(newLocation, aKeyLength);
     73     iTotalKeyValueLength += aKeyLength;
     74     return StringKeyValueStore_Success;
     75 }
     76 
     77 ///////////////////////////////////////////////////////////////////////////////////////////////////
     78 int32 StringKeyValueStore::addKeyValuePair(const StrCSumPtrLen &aNewKey, const StrPtrLen &aNewValue, const bool aNeedReplaceOldValue)
     79 {
     80     int32 tableIndex;
     81     if ((tableIndex = getHashTableIndex(aNewKey, false)) < 0) return false; // false in getHashTableIndex means for adding an element
     82 
     83     // add the field key if it is new
     84     if (addKeyToStore(aNewKey, tableIndex)) return StringKeyValueStore_NoMemory;
     85 
     86     // add or append new field value
     87     char *newLocation = NULL;
     88     int32 aValueLength = aNewValue.length();
     89     if (!storeNewKeyValueItem(aNewValue.c_str(), aValueLength, newLocation)) return StringKeyValueStore_NoMemory;
     90 
     91     if (iFieldVals[tableIndex].length() == 0)
     92     {
     93         // empty value field
     94 
     95         iFieldVals[tableIndex].setPtrLen(newLocation, aValueLength);
     96     }
     97     else if (aNeedReplaceOldValue)
     98     {
     99         // overrite
    100         // first, release the memory for the old value
    101         releaseOldKeyValueItem(iFieldVals[tableIndex].c_str(), aValueLength);
    102         // then replace the old value with the new value
    103         iTotalKeyValueLength -= iFieldVals[tableIndex].length();
    104         iFieldVals[tableIndex].setPtrLen(newLocation, aValueLength);
    105         iTotalNumberOfKeyValuePairs--; // for the following iTotalNumberOfKeyValuePairs++;
    106     }
    107     else
    108     {
    109         // append
    110         // create StrCSumPtrLenWrapper
    111         StrCSumPtrLenWrapper aMewValueWrapper(newLocation, aValueLength);
    112         int32 err = 0;
    113         OSCL_TRY(err, iStrCSumPtrLenWrapperVector.push_back(aMewValueWrapper));
    114         if (err) return StringKeyValueStore_NoMemory;
    115         // link this new field value to the existing field key
    116         iFieldKeys[tableIndex].push_back(&iStrCSumPtrLenWrapperVector[iStrCSumPtrLenWrapperVector.size()-1]);
    117         iTotalKeyValueLength += iFieldKeys[tableIndex].length();  // field key still needs to be taken into account
    118     }
    119 
    120     // update iTotalKeyValueLength and iTotalNumberOfKeyValuePairs
    121     iTotalKeyValueLength += aValueLength;
    122     iTotalNumberOfKeyValuePairs++;
    123     return StringKeyValueStore_Success;
    124 }
    125 
    126 int32 StringKeyValueStore::addKeyValuePair(const StrCSumPtrLen &aNewKey, const char *aNewValue, const bool aNeedReplaceOldValue)
    127 {
    128     if (!aNewValue) return StringKeyValueStore_Failure;
    129     StrPtrLen newValue(aNewValue);
    130     return addKeyValuePair(aNewKey, newValue, aNeedReplaceOldValue);
    131 }
    132 
    133 int32 StringKeyValueStore::addKeyValuePair(const char *aNewKey, const uint32 aKeyLength, const char *aNewValue, const uint32 aValueLength,
    134         const bool aNeedReplaceOldValue)
    135 {
    136     StrCSumPtrLen newKey(aNewKey, aKeyLength);
    137     StrPtrLen newValue(aNewValue, aValueLength);
    138     return addKeyValuePair(newKey, newValue, aNeedReplaceOldValue);
    139 }
    140 
    141 ///////////////////////////////////////////////////////////////////////////////////////////////////
    142 // get
    143 uint32 StringKeyValueStore::getCurrentKeyList(StrPtrLen *&aFieldKeyList, const uint32 aListSize)
    144 {
    145     uint32 requestListSize = (aListSize == 0 ? iFieldKeyTableIndexVector.size() :
    146                               OSCL_MIN(aListSize, iFieldKeyTableIndexVector.size()));
    147     uint32 i;
    148     for (i = 0; i < requestListSize; i++)
    149     {
    150         aFieldKeyList[i].setPtrLen(iFieldKeys[iFieldKeyTableIndexVector[i]].c_str(),
    151                                    iFieldKeys[iFieldKeyTableIndexVector[i]].length());
    152     }
    153 
    154     return requestListSize;
    155 }
    156 
    157 ///////////////////////////////////////////////////////////////////////////////////////////////////
    158 bool StringKeyValueStore::getValueByKey(const StrCSumPtrLen &aKey, StrPtrLen &aValue, uint32 index)
    159 {
    160     // reset aValue
    161     aValue.setPtrLen("", 0);
    162 
    163     int32 tableIndex = getHashTableIndex(aKey);
    164     if (tableIndex < 0 || tableIndex > KEYVALUESTORE_HASH_TABLE_SIZE_FOR_KEYS) return false; // no such key in the store
    165 
    166     if (index == 0)
    167     {
    168         aValue = iFieldVals[tableIndex];
    169         return true;
    170     }
    171     else
    172     {
    173         // index > 0
    174         uint32 count = 1;
    175         StrCSumPtrLenWrapper *pStrWrapper = iFieldKeys[tableIndex].getNext();
    176         while (count < index && pStrWrapper != NULL)
    177         {
    178             pStrWrapper = pStrWrapper->getNext();
    179             count++;
    180         }
    181 
    182         if (!pStrWrapper) return false;
    183         if (count == index && pStrWrapper != NULL)
    184         {
    185             // find the right one
    186             aValue.setPtrLen(pStrWrapper->c_str(), pStrWrapper->length());
    187             return true;
    188         }
    189     }
    190     return false;
    191 }
    192 
    193 ///////////////////////////////////////////////////////////////////////////////////////////////////
    194 uint32 StringKeyValueStore::getNumberOfValuesByKey(const StrCSumPtrLen &aKey)
    195 {
    196     int32 tableIndex = getHashTableIndex(aKey);
    197     if (tableIndex < 0) return 0; // no such key in the store
    198 
    199     uint32 count = 1;
    200     StrCSumPtrLenWrapper *pStrWrapper = iFieldKeys[tableIndex].getNext();
    201     while (pStrWrapper)
    202     {
    203         count++;
    204         pStrWrapper = pStrWrapper->getNext();
    205     }
    206     return count;
    207 }
    208 
    209 
    210 ///////////////////////////////////////////////////////////////////////////////////////////////////
    211 // search
    212 bool StringKeyValueStore::isKeyValueAvailable(const StrCSumPtrLen &aKey)
    213 {
    214     return (getHashTableIndex(aKey) >= 0);
    215 }
    216 
    217 ///////////////////////////////////////////////////////////////////////////////////////////////////
    218 // remove
    219 bool StringKeyValueStore::removeKeyValuePair(const StrCSumPtrLen &aKey)
    220 {
    221     // update iTotalNumberOfKeyValuePairs
    222     uint32 numValues = getNumberOfValuesByKey(aKey);
    223     if (numValues == 0) return true; //false; // no such key
    224     iTotalNumberOfKeyValuePairs -= numValues;
    225 
    226     // update iTotalKeyValueLength
    227     int32 tableIndex = getHashTableIndex(aKey);
    228     iTotalKeyValueLength -= (iFieldKeys[tableIndex].length() * numValues + iFieldVals[tableIndex].length());
    229     StrCSumPtrLenWrapper *pStrWrapper = iFieldKeys[tableIndex].getNext();
    230     while (pStrWrapper)  // for the mulitple values
    231     {
    232         // release the key and all appending values
    233         releaseOldKeyValueItem(pStrWrapper->c_str(), pStrWrapper->length());
    234         iTotalKeyValueLength -= pStrWrapper->length();
    235         pStrWrapper = pStrWrapper->getNext();
    236     }
    237     // release the value
    238     releaseOldKeyValueItem(iFieldVals[tableIndex].c_str(), iFieldVals[tableIndex].length());
    239 
    240     // remove the index in iFieldKeyTableIndexVector
    241     uint32 i = 0;
    242     for (i = 0; i < iFieldKeyTableIndexVector.size(); i++)
    243     {
    244         if (iFieldKeys[iFieldKeyTableIndexVector[i]].isCIEquivalentTo(aKey))
    245         {
    246             iFieldKeyTableIndexVector.erase(iFieldKeyTableIndexVector.begin() + i);
    247         }
    248     }
    249 
    250     // clear key-value
    251     iFieldKeys[tableIndex].clear();
    252     iFieldVals[tableIndex].setPtrLen("", 0);
    253 
    254     // note that we need to upgrade to use resizable memory pool to return the memory for the key-value pair;
    255     // otherwise we waste the memory.
    256     return true;
    257 }
    258 
    259 ///////////////////////////////////////////////////////////////////////////////////////////////////
    260 // clear
    261 void StringKeyValueStore::clear()
    262 {
    263     iTotalNumberOfKeyValuePairs = 0;
    264     iTotalKeyValueLength        = 0;
    265     iNumConflicts               = 0;
    266 
    267     // clear field key and value tables
    268     uint32 i;
    269     for (i = 0; i < KEYVALUESTORE_HASH_TABLE_SIZE_FOR_KEYS; i++)
    270     {
    271         iFieldKeys[i].clear();
    272         iFieldVals[i].setPtrLen("", 0);
    273     }
    274     iStrCSumPtrLenWrapperVector.clear();
    275     iFieldKeyTableIndexVector.clear();
    276     if (iVariableSizeMemPool) iVariableSizeMemPool->clear();
    277 }
    278 
    279 ///////////////////////////////////////////////////////////////////////////////////////////////////
    280 // copy
    281 bool StringKeyValueStore::copy(StringKeyValueStore& aStore)
    282 {
    283     uint32 numKeyValuePairs = aStore.getNumberOfKeyValuePairs();
    284     uint32 numKeys = aStore.getNumberOfKeys();
    285     if (numKeyValuePairs == 0 || numKeys == 0) return true;
    286     OSCL_ASSERT(numKeyValuePairs >= numKeys);
    287 
    288     StrPtrLen *keyList = OSCL_ARRAY_NEW(StrPtrLen, numKeys);
    289     if (!keyList) return false;
    290     aStore.getCurrentKeyList(keyList);
    291     for (uint32 i = 0; i < numKeyValuePairs; i++)
    292     {
    293         uint32 numValuesByKey = aStore.getNumberOfValuesByKey(keyList[i]);
    294         for (uint32 j = 0; j < numValuesByKey; j++)
    295         {
    296             StrPtrLen fieldValue;
    297             if (!aStore.getValueByKey(keyList[i], fieldValue, j))
    298             {
    299                 OSCL_ARRAY_DELETE(keyList);
    300                 return false;
    301             }
    302             if (addKeyValuePair(keyList[i], fieldValue))
    303             {
    304                 OSCL_ARRAY_DELETE(keyList);
    305                 return false;
    306             }
    307         }
    308     }
    309 
    310     OSCL_ARRAY_DELETE(keyList);
    311     return true;
    312 }
    313 
    314 ///////////////////////////////////////////////////////////////////////////////////////////////////
    315 // factory method
    316 StringKeyValueStore* StringKeyValueStore::create(const uint32 aStoreSize)
    317 {
    318     StringKeyValueStore *store = OSCL_NEW(StringKeyValueStore, ());
    319     if (!store) return NULL;
    320     if (!store->construct(aStoreSize))
    321     {
    322         OSCL_DELETE(store);
    323         return NULL;
    324     }
    325     return store;
    326 }
    327 
    328 bool StringKeyValueStore::construct(const uint32 aStoreSize)
    329 {
    330     clear();
    331 
    332     // create two vectors
    333     int32 err = 0;
    334     OSCL_TRY(err, iStrCSumPtrLenWrapperVector.reserve(KEYVALUESTORE_VECTOR_RESERVE_VALUE);
    335              iFieldKeyTableIndexVector.reserve(KEYVALUESTORE_VECTOR_RESERVE_VALUE);
    336             );
    337     if (err)
    338     {
    339         iStrCSumPtrLenWrapperVector.clear();
    340         iFieldKeyTableIndexVector.clear();
    341         return false;
    342     }
    343 
    344     // create iVariableSizeMemPool
    345     OSCL_TRY(err, iVariableSizeMemPool = new OsclMemPoolVariableChunkAllocator(aStoreSize););
    346     if (err || iVariableSizeMemPool == NULL) return false;
    347 
    348 
    349     return true;
    350 }
    351 
    352 ///////////////////////////////////////////////////////////////////////////////////////////////////
    353 // destructor
    354 StringKeyValueStore::~StringKeyValueStore()
    355 {
    356     clear();
    357 
    358     // delete memory pool
    359     OSCL_DELETE(iVariableSizeMemPool);
    360     iVariableSizeMemPool = NULL;
    361 }
    362 
    363 ////////////////////////////////////////////////////////////////////////////////////
    364 uint32 StringKeyValueStore::calculateChecksum(const char *aBuffer, uint32 aBufferLength)
    365 {
    366     uint32 checkSum = 0;
    367     for (uint32 i = 0; i < aBufferLength; i++)
    368     {
    369         if (oscl_isLetter(aBuffer[i]))
    370         {
    371             checkSum += (uint32)(aBuffer[i] | OSCL_ASCII_CASE_MAGIC_BIT);
    372         }
    373         else
    374         {
    375             checkSum += aBuffer[i];
    376         }
    377     }
    378 
    379     return (checkSum % KEYVALUESTORE_HASH_TABLE_SIZE_FOR_KEYS) / 2;
    380 }
    381 
    382 ///////////////////////////////////////////////////////////////////////////////////////////////////
    383 int32 StringKeyValueStore::getHashTableIndex(const StrCSumPtrLen &aKey, const bool aFindKey)
    384 {
    385     StrCSumPtrLenWrapper keyWrapper(aKey);
    386     int32 aTableIndex = keyWrapper.getChecksum();
    387 
    388     if (iFieldKeys[aTableIndex].empty())
    389     {
    390         if (!aFindKey)
    391         {
    392             return aTableIndex; // for add, new key to be added
    393         }
    394         return query(aKey); // for search, need to check linear search table
    395     }
    396 
    397     if (iFieldKeys[aTableIndex].isCIEquivalentTo(aKey))
    398     {
    399         return aTableIndex;
    400     }
    401     int32 index = query(aKey);
    402     if (aFindKey)
    403     {
    404         return index; // for search
    405     }
    406     // for add
    407     if (index >= 0)
    408     {
    409         return index; // find an existing one to add
    410     }
    411     // create a new index for this new conllision
    412     if (iNumConflicts + 1 >= KEYVALUESTORE_HASH_TABLE_SIZE_FOR_KEYS / 2)
    413     {
    414         return -1;
    415     }
    416     return KEYVALUESTORE_HASH_TABLE_SIZE_FOR_KEYS / 2 + (iNumConflicts++);
    417 }
    418 
    419 ///////////////////////////////////////////////////////////////////////////////////////////////////
    420 int32 StringKeyValueStore::query(const StrCSumPtrLen &aKey)
    421 {
    422     StrCSumPtrLenWrapper *LSTable = iFieldKeys + KEYVALUESTORE_HASH_TABLE_SIZE_FOR_KEYS / 2; // LSTable= Linear Search Table
    423     uint32 i = 0;
    424     for (i = 0; i < iNumConflicts; i++)
    425     {
    426         if (LSTable[i].isCIEquivalentTo(aKey))
    427         {
    428             return (int32)(KEYVALUESTORE_HASH_TABLE_SIZE_FOR_KEYS / 2 + i);
    429         }
    430     }
    431     return -1;
    432 }
    433 
    434