The world's most popular open source database

MySQL 5.1: mysql/src/5.1-dbg/storage/ndb/src/common/util/ConfigValues.cpp Source File
mysql/src/5.1-dbg/storage/ndb/src/common/util/ConfigValues.cpp

00001 
00002 #include <ndb_global.h>
00003 #include <ConfigValues.hpp>
00004 #include <NdbOut.hpp>
00005 #include <NdbTCP.h>
00006 
00007 static Uint32 hash(Uint32 key, Uint32 size);
00008 static Uint32 nextHash(Uint32 key, Uint32 size, Uint32 pos, Uint32 count);
00009 static bool findKey(const Uint32 * vals, Uint32 sz, Uint32 key, Uint32 * pos);
00010 
00022 #define KP_TYPE_MASK     (15)
00023 #define KP_TYPE_SHIFT    (28)
00024 #define KP_SECTION_MASK  (0x3FFF)
00025 #define KP_SECTION_SHIFT (14)
00026 #define KP_KEYVAL_MASK   (0x3FFF)
00027 #define KP_KEYVAL_SHIFT  (0)
00028 #define KP_MASK          (0x0FFFFFFF)
00029 
00030 static const Uint32 CFV_KEY_PARENT = (KP_KEYVAL_MASK - 1);
00031 static const Uint32 CFV_KEY_FREE   = ~0;
00032 
00033 static const char Magic[] = { 'N', 'D', 'B', 'C', 'O', 'N', 'F', 'V' };
00034 
00035 //#define DEBUG_CV
00036 #ifdef DEBUG_CV
00037 #define DEBUG
00038 #else
00039 #define DEBUG if(0)
00040 #endif
00041 
00042 inline
00043 ConfigValues::ValueType
00044 getTypeOf(Uint32 k) {
00045   return (ConfigValues::ValueType)((k >> KP_TYPE_SHIFT) & KP_TYPE_MASK);
00046 }
00047 
00048 ConfigValues::ConfigValues(Uint32 sz, Uint32 dsz){
00049   m_size = sz;
00050   m_dataSize = dsz;
00051   m_stringCount = 0;
00052   m_int64Count = 0;
00053   for(Uint32 i = 0; i<m_size; i++){
00054     m_values[i << 1] = CFV_KEY_FREE;
00055   }
00056 }
00057 
00058 ConfigValues::~ConfigValues(){
00059   for(Uint32 i = 0; i<m_stringCount; i++){
00060     free(* getString(i));
00061   }
00062 }
00063 
00064 bool
00065 ConfigValues::ConstIterator::get(Uint32 key, Entry * result) const {
00066   Uint32 pos;
00067   if(!findKey(m_cfg.m_values, m_cfg.m_size, key | m_currentSection, &pos)){
00068     return false;
00069   }
00070   
00071   result->m_key = key;
00072   return m_cfg.getByPos(pos, result);
00073 }
00074 
00075 bool
00076 ConfigValues::getByPos(Uint32 pos, Entry * result) const {
00077   assert(pos < (2 * m_size));
00078   Uint32 keypart = m_values[pos];
00079   Uint32 val = m_values[pos+1];
00080 
00081   switch(::getTypeOf(keypart)){
00082   case IntType:
00083   case SectionType:
00084     result->m_int = val;
00085     break;
00086   case StringType:
00087     result->m_string = * getString(val);
00088     break;
00089   case Int64Type:
00090     result->m_int64 = * get64(val);
00091     break;
00092   case InvalidType: 
00093   default:
00094     return false;
00095   }
00096 
00097   result->m_type = ::getTypeOf(keypart);
00098   
00099   return true;
00100 }
00101 
00102 Uint64 *
00103 ConfigValues::get64(Uint32 index) const {
00104   assert(index < m_int64Count);
00105   const Uint32 * data = m_values + (m_size << 1);
00106   Uint64 * ptr = (Uint64*)data;
00107   ptr += index;
00108   return ptr;
00109 }
00110 
00111 char **
00112 ConfigValues::getString(Uint32 index) const {
00113   assert(index < m_stringCount); 
00114   const Uint32 * data = m_values + (m_size << 1);
00115   char * ptr = (char*)data;
00116   ptr += m_dataSize; 
00117   ptr -= (index * sizeof(char *));
00118   return (char**)ptr;
00119 }
00120 
00121 bool
00122 ConfigValues::ConstIterator::openSection(Uint32 key, Uint32 no){
00123   Uint32 curr = m_currentSection;
00124   
00125   Entry tmp;
00126   if(get(key, &tmp) && tmp.m_type == SectionType){
00127     m_currentSection = tmp.m_int;
00128     if(get(no, &tmp) && tmp.m_type == IntType){
00129       m_currentSection = tmp.m_int;
00133       if(get(CFV_KEY_PARENT, &tmp)){
00134         return true;
00135       }
00136     }
00137   }
00138   
00139   m_currentSection = curr;
00140   return false;
00141 }
00142 
00143 bool
00144 ConfigValues::ConstIterator::closeSection() {
00145   
00146   Entry tmp;
00147   if(get(CFV_KEY_PARENT, &tmp) && tmp.m_type == IntType){
00148     m_currentSection = tmp.m_int;
00149     return true;
00150   }
00151 
00152   return false;
00153 }
00154 
00155 bool
00156 ConfigValues::Iterator::set(Uint32 key, Uint32 value){
00157   Uint32 pos;
00158   if(!findKey(m_cfg.m_values, m_cfg.m_size, key | m_currentSection, &pos)){
00159     return false;
00160   }
00161 
00162   if(::getTypeOf(m_cfg.m_values[pos]) != IntType){
00163     return false;
00164   }
00165 
00166   m_cfg.m_values[pos+1] = value;
00167   return true;
00168 }
00169 
00170 bool
00171 ConfigValues::Iterator::set(Uint32 key, Uint64 value){
00172   Uint32 pos;
00173   if(!findKey(m_cfg.m_values, m_cfg.m_size, key | m_currentSection, &pos)){
00174     return false;
00175   }
00176 
00177   if(::getTypeOf(m_cfg.m_values[pos]) != Int64Type){
00178     return false;
00179   }
00180   
00181   * m_cfg.get64(m_cfg.m_values[pos+1]) = value;
00182   return true;
00183 }
00184 
00185 bool
00186 ConfigValues::Iterator::set(Uint32 key, const char * value){
00187   Uint32 pos;
00188   if(!findKey(m_cfg.m_values, m_cfg.m_size, key | m_currentSection, &pos)){
00189     return false;
00190   }
00191 
00192   if(::getTypeOf(m_cfg.m_values[pos]) != StringType){
00193     return false;
00194   }
00195 
00196   char **  str = m_cfg.getString(m_cfg.m_values[pos+1]);
00197   free(* str);
00198   * str = strdup(value ? value : "");
00199   return true;
00200 }
00201 
00202 static
00203 bool
00204 findKey(const Uint32 * values, Uint32 sz, Uint32 key, Uint32 * _pos){
00205   Uint32 pos = hash(key, sz);
00206   Uint32 count = 0;
00207   while((values[pos] & KP_MASK) != key && count < sz){
00208     pos = nextHash(key, sz, pos, ++count);
00209   }
00210 
00211   if((values[pos] & KP_MASK)== key){
00212     *_pos = pos;
00213     return true;
00214   }
00215   return false;
00216 }
00217 
00218 static
00219 Uint32
00220 hash(Uint32 key, Uint32 size){
00221   Uint32 tmp = (key >> 16) ^ (key & 0xFFFF);
00222   return (((tmp << 16) | tmp) % size) << 1;
00223 }
00224 
00225 static
00226 Uint32
00227 nextHash(Uint32 key, Uint32 size, Uint32 pos, Uint32 count){
00228   Uint32 p = (pos >> 1);
00229   if((key % size) != 0)
00230     p += key;
00231   else
00232     p += 1;
00233   return (p % size) << 1;
00234 }
00235 
00236 static
00237 Uint32
00238 directory(Uint32 sz){
00239   const Uint32 _input = sz;
00240   if((sz & 1) == 0)
00241     sz ++;
00242   
00243   bool prime = false;
00244   while(!prime){
00245     prime = true;
00246     for(Uint32 n = 3; n*n <= sz; n += 2){
00247       if((sz % n) == 0){
00248         prime = false;
00249         sz += 2;
00250         break;
00251       }
00252     }
00253   }
00254   DEBUG printf("directory %d -> %d\n", _input, sz);
00255   return sz;
00256 }
00257 
00258 ConfigValuesFactory::ConfigValuesFactory(Uint32 keys, Uint32 data){
00259   m_sectionCounter = (1 << KP_SECTION_SHIFT);
00260   m_freeKeys = directory(keys);
00261   m_freeData = (data + 7) & ~7;
00262   m_currentSection = 0;
00263   m_cfg = create(m_freeKeys, m_freeData);
00264 }
00265 
00266 ConfigValuesFactory::ConfigValuesFactory(ConfigValues * cfg){
00267   m_cfg = cfg;
00268   m_freeKeys = 0;
00269   m_freeData = m_cfg->m_dataSize;
00270   m_sectionCounter = (1 << KP_SECTION_SHIFT);  
00271   m_currentSection = 0;
00272   const Uint32 sz = 2 * m_cfg->m_size;
00273   for(Uint32 i = 0; i<sz; i += 2){
00274     const Uint32 key = m_cfg->m_values[i];
00275     if(key == CFV_KEY_FREE){
00276       m_freeKeys++;
00277     } else {
00278       switch(::getTypeOf(key)){
00279       case ConfigValues::IntType:
00280       case ConfigValues::SectionType:
00281         break;
00282       case ConfigValues::Int64Type:
00283         m_freeData -= sizeof(Uint64);
00284         break;
00285       case ConfigValues::StringType:
00286         m_freeData -= sizeof(char *);
00287         break;
00288       case ConfigValues::InvalidType:
00289         abort();
00290       }
00291       Uint32 sec = key & (KP_SECTION_MASK << KP_SECTION_SHIFT);
00292       m_sectionCounter = (sec > m_sectionCounter ? sec : m_sectionCounter);
00293     }
00294   }
00295 }
00296 
00297 ConfigValuesFactory::~ConfigValuesFactory()
00298 {
00299   if(m_cfg)
00300     free(m_cfg);
00301 }
00302 
00303 ConfigValues *
00304 ConfigValuesFactory::create(Uint32 keys, Uint32 data){
00305   Uint32 sz = sizeof(ConfigValues);
00306   sz += (2 * keys * sizeof(Uint32)); 
00307   sz += data;
00308   
00309   void * tmp = malloc(sz);
00310   return new (tmp) ConfigValues(keys, data);
00311 }
00312 
00313 void
00314 ConfigValuesFactory::expand(Uint32 fk, Uint32 fs){
00315   if(m_freeKeys >= fk && m_freeData >= fs){
00316     return ;
00317   }
00318 
00319   m_freeKeys = (m_freeKeys >= fk ? m_cfg->m_size : fk + m_cfg->m_size);
00320   m_freeData = (m_freeData >= fs ? m_cfg->m_dataSize : fs + m_cfg->m_dataSize);
00321   m_freeKeys = directory(m_freeKeys);
00322   m_freeData = (m_freeData + 7) & ~7;
00323  
00324   ConfigValues * m_tmp = m_cfg;
00325   m_cfg = create(m_freeKeys, m_freeData);
00326   put(* m_tmp);
00327   m_tmp->~ConfigValues();
00328   free(m_tmp);
00329 }
00330 
00331 void
00332 ConfigValuesFactory::shrink(){
00333   if(m_freeKeys == 0 && m_freeData == 0){
00334     return ;
00335   }
00336 
00337   m_freeKeys = m_cfg->m_size - m_freeKeys;
00338   m_freeData = m_cfg->m_dataSize - m_freeData;
00339   m_freeKeys = directory(m_freeKeys);
00340   m_freeData = (m_freeData + 7) & ~7;
00341 
00342   ConfigValues * m_tmp = m_cfg;
00343   m_cfg = create(m_freeKeys, m_freeData);
00344   put(* m_tmp);
00345   m_tmp->~ConfigValues();
00346   free(m_tmp);
00347 }
00348 
00349 bool
00350 ConfigValuesFactory::openSection(Uint32 key, Uint32 no){
00351   ConfigValues::Entry tmp;
00352   const Uint32 parent = m_currentSection;
00353 
00354   ConfigValues::ConstIterator iter(* m_cfg);
00355   iter.m_currentSection = m_currentSection;
00356   if(!iter.get(key, &tmp)){
00357 
00358     tmp.m_key  = key;
00359     tmp.m_type = ConfigValues::SectionType;
00360     tmp.m_int  = m_sectionCounter;
00361     m_sectionCounter += (1 << KP_SECTION_SHIFT);
00362 
00363     if(!put(tmp)){
00364       return false;
00365     }
00366   }
00367 
00368   if(tmp.m_type != ConfigValues::SectionType){
00369     return false;
00370   }
00371 
00372   m_currentSection = tmp.m_int;
00373 
00374   tmp.m_key = no;
00375   tmp.m_type = ConfigValues::IntType;
00376   tmp.m_int = m_sectionCounter;
00377   if(!put(tmp)){
00378     m_currentSection = parent;
00379     return false;
00380   }
00381   m_sectionCounter += (1 << KP_SECTION_SHIFT);
00382   
00383   m_currentSection = tmp.m_int;
00384   tmp.m_type = ConfigValues::IntType;
00385   tmp.m_key = CFV_KEY_PARENT;
00386   tmp.m_int = parent;
00387   if(!put(tmp)){
00388     m_currentSection = parent;
00389     return false;
00390   }
00391 
00392   return true;
00393 }
00394 
00395 bool
00396 ConfigValuesFactory::closeSection(){
00397   ConfigValues::ConstIterator iter(* m_cfg);
00398   iter.m_currentSection = m_currentSection;
00399   const bool b = iter.closeSection();
00400   m_currentSection = iter.m_currentSection;
00401   return b;
00402 }
00403   
00404 bool
00405 ConfigValuesFactory::put(const ConfigValues::Entry & entry){
00406   
00407   if(m_freeKeys == 0 ||
00408      (entry.m_type == ConfigValues::StringType && m_freeData < sizeof(char *))
00409      || (entry.m_type == ConfigValues::Int64Type && m_freeData < 8 )){ 
00410     
00411     DEBUG ndbout_c("m_freeKeys = %d, m_freeData = %d -> expand",
00412                    m_freeKeys, m_freeData);
00413     
00414     expand(31, 20);
00415   }
00416   
00417   const Uint32 tmp = entry.m_key | m_currentSection;
00418   const Uint32 sz = m_cfg->m_size;
00419   Uint32 pos = hash(tmp, sz);
00420   Uint32 count = 0;
00421   Uint32 val = m_cfg->m_values[pos];
00422 
00423   while((val & KP_MASK) != tmp && val != CFV_KEY_FREE && count < sz){
00424     pos = nextHash(tmp, sz, pos, ++count);
00425     val = m_cfg->m_values[pos];
00426   }
00427 
00428   if((val & KP_MASK) == tmp){
00429     DEBUG ndbout_c("key %x already found at pos: %d", tmp, pos);
00430     return false;
00431   }
00432 
00433   if(count >= sz){
00434     pos = hash(tmp, sz);    
00435     count = 0;
00436     Uint32 val = m_cfg->m_values[pos];
00437    
00438     printf("key: %d, (key %% size): %d\n", entry.m_key, (entry.m_key % sz));
00439     printf("pos: %d", pos);
00440     while((val & KP_MASK) != tmp && val != CFV_KEY_FREE && count < sz){
00441       pos = nextHash(tmp, sz, pos, ++count);
00442       val = m_cfg->m_values[pos];
00443       printf(" %d", pos);
00444     }
00445     printf("\n");
00446 
00447     abort();
00448     printf("Full\n");
00449     return false;
00450   }
00451 
00452   assert(pos < (sz << 1));
00453 
00454   Uint32 key = tmp;
00455   key |= (entry.m_type << KP_TYPE_SHIFT);
00456   m_cfg->m_values[pos] = key;
00457   switch(entry.m_type){
00458   case ConfigValues::IntType:
00459   case ConfigValues::SectionType:
00460     m_cfg->m_values[pos+1] = entry.m_int;    
00461     m_freeKeys--;
00462     DEBUG printf("Putting at: %d(%d) (loop = %d) key: %d value: %d\n", 
00463                    pos, sz, count, 
00464                    (key >> KP_KEYVAL_SHIFT) & KP_KEYVAL_MASK,
00465                    entry.m_int);
00466     return true;
00467   case ConfigValues::StringType:{
00468     Uint32 index = m_cfg->m_stringCount++;
00469     m_cfg->m_values[pos+1] = index;
00470     char **  ref = m_cfg->getString(index);
00471     * ref = strdup(entry.m_string ? entry.m_string : "");
00472     m_freeKeys--;
00473     m_freeData -= sizeof(char *);
00474     DEBUG printf("Putting at: %d(%d) (loop = %d) key: %d value(%d): %s\n", 
00475                    pos, sz, count, 
00476                    (key >> KP_KEYVAL_SHIFT) & KP_KEYVAL_MASK,
00477                    index,
00478                    entry.m_string);
00479     return true;
00480   }
00481   case ConfigValues::Int64Type:{
00482     Uint32 index = m_cfg->m_int64Count++;
00483     m_cfg->m_values[pos+1] = index;
00484     * m_cfg->get64(index) = entry.m_int64;
00485     m_freeKeys--;
00486     m_freeData -= 8;
00487     DEBUG printf("Putting at: %d(%d) (loop = %d) key: %d value64(%d): %lld\n", 
00488                    pos, sz, count, 
00489                    (key >> KP_KEYVAL_SHIFT) & KP_KEYVAL_MASK,
00490                    index,
00491                    entry.m_int64);
00492     return true;
00493   }
00494   case ConfigValues::InvalidType:
00495   default:
00496     return false;
00497   }
00498   return false;
00499 }
00500 
00501 void
00502 ConfigValuesFactory::put(const ConfigValues & cfg){
00503   
00504   Uint32 curr = m_currentSection;
00505   m_currentSection = 0;
00506 
00507   ConfigValues::Entry tmp;
00508   for(Uint32 i = 0; i < 2 * cfg.m_size; i += 2){
00509     if(cfg.m_values[i] != CFV_KEY_FREE){
00510       tmp.m_key = cfg.m_values[i];
00511       cfg.getByPos(i, &tmp);
00512       put(tmp);
00513     }
00514   }
00515 
00516   m_currentSection = curr;
00517 }
00518 
00519 ConfigValues *
00520 ConfigValuesFactory::extractCurrentSection(const ConfigValues::ConstIterator & cfg){
00521   ConfigValuesFactory * fac = new ConfigValuesFactory(20, 20);
00522   Uint32 curr = cfg.m_currentSection;
00523  
00524   ConfigValues::Entry tmp;
00525   for(Uint32 i = 0; i < 2 * cfg.m_cfg.m_size; i += 2){
00526     Uint32 keypart = cfg.m_cfg.m_values[i];
00527     const Uint32 sec = keypart & (KP_SECTION_MASK << KP_SECTION_SHIFT);
00528     const Uint32 key = keypart & KP_KEYVAL_MASK;
00529     if(sec == curr && key != CFV_KEY_PARENT){
00530       tmp.m_key = cfg.m_cfg.m_values[i];
00531       cfg.m_cfg.getByPos(i, &tmp);
00532       tmp.m_key = key;
00533       fac->put(tmp);
00534     }
00535   }
00536   
00537   ConfigValues * ret = fac->getConfigValues();
00538   delete fac;
00539   return ret;
00540 }
00541 
00542 ConfigValues *
00543 ConfigValuesFactory::getConfigValues(){
00544   ConfigValues * ret = m_cfg;
00545   m_cfg = create(10, 10);
00546   return ret;
00547 }
00548 
00549 static int
00550 mod4(unsigned int i){
00551   int res = i + (4 - (i % 4));
00552   return res;
00553 }
00554 
00555 Uint32
00556 ConfigValues::getPackedSize() const {
00557 
00558   Uint32 size = 0;
00559   for(Uint32 i = 0; i < 2 * m_size; i += 2){
00560     Uint32 key = m_values[i];
00561     if(key != CFV_KEY_FREE){
00562       switch(::getTypeOf(key)){
00563       case IntType:
00564       case SectionType:
00565         size += 8;
00566         break;
00567       case Int64Type:
00568         size += 12;
00569         break;
00570       case StringType:
00571         size += 8; // key + len
00572         size += mod4(strlen(* getString(m_values[i+1])) + 1);
00573         break;
00574       case InvalidType:
00575       default:
00576         abort();
00577       }
00578     }
00579   }
00580 
00581   return size + sizeof(Magic) + 4; // checksum also
00582 }
00583 
00584 Uint32
00585 ConfigValues::pack(void * _dst, Uint32 _len) const {
00586   Uint32 i;
00587   char * dst = (char*)_dst;
00588   memcpy(dst, Magic, sizeof(Magic)); dst += sizeof(Magic);
00589 
00590   for(i = 0; i < 2 * m_size; i += 2){
00591     Uint32 key = m_values[i];
00592     Uint32 val = m_values[i+1];
00593     if(key != CFV_KEY_FREE){
00594       switch(::getTypeOf(key)){
00595       case IntType:
00596       case SectionType:
00597         * (Uint32*)dst = htonl(key); dst += 4;
00598         * (Uint32*)dst = htonl(val); dst += 4;
00599         break;
00600       case Int64Type:{
00601         Uint64 i64 = * get64(val); 
00602         Uint32 hi = (i64 >> 32);
00603         Uint32 lo = (i64 & 0xFFFFFFFF);
00604         * (Uint32*)dst = htonl(key); dst += 4;
00605         * (Uint32*)dst = htonl(hi); dst += 4;
00606         * (Uint32*)dst = htonl(lo); dst += 4;
00607       }
00608         break;
00609       case StringType:{
00610         const char * str = * getString(val);
00611         Uint32 len = strlen(str) + 1;
00612         * (Uint32*)dst = htonl(key); dst += 4;
00613         * (Uint32*)dst = htonl(len); dst += 4;
00614         memcpy(dst, str, len); 
00615         memset(dst+len, 0, mod4(len) - len);
00616         dst += mod4(len);
00617       }
00618         break;
00619       case InvalidType:
00620       default:
00621         abort();
00622       }
00623     }
00624   }
00625 
00626   const Uint32 * sum = (Uint32*)_dst;
00627   const Uint32 len = ((Uint32*)dst) - sum;
00628   Uint32 chk = 0;
00629   for(i = 0; i<len; i++){
00630     chk ^= htonl(sum[i]);
00631   }
00632 
00633   * (Uint32*)dst = htonl(chk); dst += 4;
00634   return 4 * (len + 1);
00635 }
00636 
00637 bool
00638 ConfigValuesFactory::unpack(const void * _src, Uint32 len){
00639 
00640   if(len < sizeof(Magic) + 4){
00641     DEBUG abort();
00642     return false;
00643   }
00644 
00645   if(memcmp(_src, Magic, sizeof(Magic)) != 0){
00646     DEBUG abort();
00647     return false;
00648   }
00649 
00650   const char * src = (const char *)_src;
00651 
00652   {
00653     Uint32 len32 = (len >> 2);
00654     const Uint32 * tmp = (const Uint32*)_src;
00655     Uint32 chk = 0;
00656     for(Uint32 i = 0; (i+1)<len32; i++){
00657       chk ^= ntohl(tmp[i]);
00658     }
00659 
00660     if(chk != ntohl(tmp[len32-1])){
00661       DEBUG abort();
00662       return false;
00663     }
00664   }
00665 
00666   const char * end = src + len - 4;
00667   src += sizeof(Magic);
00668  
00669   ConfigValues::Entry entry;
00670   while(end - src > 4){
00671     Uint32 tmp = ntohl(* (const Uint32 *)src); src += 4;
00672     entry.m_key = tmp  & KP_MASK;
00673     entry.m_type = ::getTypeOf(tmp);
00674     switch(entry.m_type){
00675     case ConfigValues::IntType:
00676     case ConfigValues::SectionType:
00677       entry.m_int = ntohl(* (const Uint32 *)src); src += 4;
00678       break;
00679     case ConfigValues::Int64Type:{
00680       Uint64 hi = ntohl(* (const Uint32 *)src); src += 4;
00681       Uint64 lo = ntohl(* (const Uint32 *)src); src += 4;
00682       entry.m_int64 = (hi <<32) | lo;
00683     }
00684       break;
00685     case ConfigValues::StringType:{
00686       Uint32 s_len = ntohl(* (const Uint32 *)src); src += 4;
00687       size_t s_len2 = strlen((const char*)src);
00688       if(s_len2 + 1 != s_len){
00689         DEBUG abort();
00690         return false;
00691       }
00692 
00693       entry.m_string = (const char*)src; src+= mod4(s_len);
00694     }
00695       break;
00696     case ConfigValues::InvalidType:
00697     default:
00698       DEBUG abort();
00699       return false;
00700     }
00701     if(!put(entry)){
00702       DEBUG abort();
00703       return false;
00704     }
00705   }
00706   if(src != end){
00707     DEBUG abort();
00708     return false;
00709   }
00710   return true;
00711 }
00712 
00713 #ifdef __TEST_CV_HASH_HPP
00714 
00715 int
00716 main(void){
00717   srand(time(0));
00718   for(int t = 0; t<100; t++){
00719     const size_t len = directory(rand() % 1000);
00720 
00721     printf("size = %d\n", len);
00722     unsigned * buf = new unsigned[len];
00723     for(size_t key = 0; key<len; key++){
00724       Uint32 p = hash(key, len);
00725       for(size_t j = 0; j<len; j++){
00726         buf[j] = p;
00727         p = nextHash(key, len, p, j+1);
00728       }
00729     
00730       for(size_t j = 0; j<len; j++){
00731         Uint32 pos = buf[j];
00732         int unique = 0;
00733         for(size_t k = j + 1; k<len; k++){
00734           if(pos == buf[k]){
00735             if(unique > 0)
00736               printf("size=%d key=%d pos(%d)=%d buf[%d]=%d\n", len, key, j, pos, k, buf[k]);
00737             unique ++;
00738           }
00739         }
00740         if(unique > 1){
00741           printf("key = %d size = %d not uniqe!!\n", key, len);
00742           for(size_t k = 0; k<len; k++){
00743             printf("%d ", buf[k]);
00744           }
00745           printf("\n");
00746         }
00747       }
00748     }
00749     delete[] buf;
00750   }
00751   return 0;
00752 }
00753 
00754 #endif
Generated on Sat Sep 9 00:50:40 2006 for MySQL 5.1 by
1.4.7