OpenRtsp源码剖析之hashtable解析

            OpenRtsp源码剖析：hashtable

       这是主要保存数据value和key的结构体：         

    class TableEntry {       
    public:
       TableEntry* fNext;
       char const* key;
       void* value;
    }; 

      这是操作hashtable的类，里面包括一系列操作函数，下面只列出主要的数据成员：

     TableEntry** fBuckets; // pointer to bucket array
     TableEntry* fStaticBuckets[SMALL_HASH_TABLE_SIZE];// used for small tables
     unsigned fNumBuckets;  //桶的个数，初始化时等于SMALL_HASH_TABLE_SIZE
     unsigned fNumEntries;   //数据entry的个数
     unsigned fRebuildSize;  //当fNumEntries的个数大于等于它时就要重建rebuild，初始化时等于3*SMALL_HASH_TABLE_SIZE
     int fKeyType;  //key的类型

        主要的设计模型：

     添加成员部分源代码：  

   void* BasicHashTable::Add(char const* key, void* value) {
   void* oldValue;
   unsigned index;
   TableEntry* entry = lookupKey(key, index);
   if (entry != NULL) {
      // There's already an item with this key
      oldValue = entry->value;
     } else {
      // There's no existing entry; create a new one:
      entry = insertNewEntry(index, key);
      oldValue = NULL;
     }
   entry->value = value;

   // If the table has become too large, rebuild it with more buckets:
   if (fNumEntries >= fRebuildSize) rebuild();

   return oldValue;
  }

      对应的图：

       当添加到一定数量的时候重建：

       部分源代码：   

    void BasicHashTable::rebuild() {
      // Remember the existing table size:
    unsigned oldSize = fNumBuckets;
    TableEntry** oldBuckets = fBuckets;

    // Create the new sized table:
    fNumBuckets *= 4;
    fBuckets = new TableEntry*[fNumBuckets];
    for (unsigned i = 0; i       fBuckets[i] = NULL;
    }
    fRebuildSize *= 4;
    fDownShift -= 2;
    fMask = (fMask<<2)|0x3;

    // Rehash the existing entries into the new table:
    for (TableEntry** oldChainPtr = oldBuckets; oldSize > 0;
         --oldSize, ++oldChainPtr) {
      for (TableEntry* hPtr = *oldChainPtr; hPtr != NULL;
   hPtr = *oldChainPtr) {
        *oldChainPtr = hPtr->fNext;

        unsigned index = hashIndexFromKey(hPtr->key);

        hPtr->fNext = fBuckets[index];
        fBuckets[index] = hPtr;
      }
    }

    // Free the old bucket array, if it was dynamically allocated:
    if (oldBuckets != fStaticBuckets) delete[] oldBuckets;
  }

      重建图 模型：