VirtualBox

Changeset 1909 in kBuild


Ignore:
Timestamp:
Oct 22, 2008 6:49:48 PM (16 years ago)
Author:
bird
Message:

strcache2: Implemented collision resolution by chaining instead of open addressing. This is faster than the open addressing approach we're using.

Location:
trunk/src/kmk
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/kmk/incdep.c

    r1903 r1909  
    773773                                                     entry->length,
    774774                                                     entry->hash1,
     775#ifdef STRCACHE2_USE_CHAINING
     776                                                     1);
     777#else
    775778                                                     entry->hash2);
     779#endif
    776780  return (const char *)entry->user;
    777781}

  • trunk/src/kmk/strcache2.c

    r1908 r1909  
    7777/** Finds the closest primary number for power of two value (or something else
    7878 *  useful if not support).   */
    79 MY_INLINE strcache2_find_prime(unsigned int shift)
     79MY_INLINE unsigned int strcache2_find_prime(unsigned int shift)
    8080{
    8181  switch (shift)
    … …  
    235235strcache2_case_sensitive_hash_2 (const char *str, unsigned int len)
    236236{
     237#ifndef STRCACHE2_USE_CHAINING
    237238  unsigned int hash = 0;
    238239  if (MY_PREDICT_TRUE(len >= 2))
    … …  
    270271  hash |= 1;
    271272  return hash;
     273#else  /* STRCACHE2_USE_CHAINING */
     274  return 1;
     275#endif /* STRCACHE2_USE_CHAINING */
    272276}
    273277
    … …  
    318322strcache2_case_insensitive_hash_2 (const char *str, unsigned int len)
    319323{
     324#ifndef STRCACHE2_USE_CHAINING
    320325  unsigned int hash = 0;
    321326  if (MY_PREDICT_TRUE(len >= 2))
    … …  
    357362  hash |= 1;
    358363  return hash;
     364#else  /* STRCACHE2_USE_CHAINING */
     365  return 1;
     366#endif /* STRCACHE2_USE_CHAINING */
    359367}
    360368
    … …  
    592600  struct strcache2_entry **src_tab = cache->hash_tab;
    593601  struct strcache2_entry **dst_tab;
    594 #ifdef STRCACHE2_USE_MASK
    595   unsigned int hash_mask;
    596 #else
    597   unsigned int hash_div;
     602#ifndef STRCACHE2_USE_MASK
     603  unsigned int hash_shift;
    598604#endif
    599605
    … …  
    604610  cache->hash_mask |= 1;
    605611#else
    606   for (hash_div = 1; (1U << hash_div) < cache->hash_size; hash_div++)
     612  for (hash_shift = 1; (1U << hash_shift) < cache->hash_size; hash_shift++)
    607613    /* nothing */;
    608   cache->hash_div = strcache2_find_prime(hash_div);
     614  cache->hash_div = strcache2_find_prime (hash_shift);
    609615#endif
    610616  cache->rehash_count <<= 1;
    … …  
    614620
    615621  /* Copy the entries from the old to the new hash table. */
    616 #ifdef STRCACHE2_USE_MASK
    617   hash_mask = cache->hash_mask;
    618 #else
    619   hash_div = cache->hash_div;
    620 #endif
    621622  while (src-- > 0)
    622623    {
    … …  
    624625      if (entry)
    625626        {
    626 #ifdef STRCACHE2_USE_MASK
    627           unsigned int dst = entry->hash1 & hash_mask;
     627#ifdef STRCACHE2_USE_CHAINING
     628assert(!"todo");
    628629#else
    629           unsigned int dst = entry->hash1 % hash_div;
    630 #endif
     630          unsigned int dst = STRCACHE2_MOD_IT (cache, entry->hash1);
    631631          if (dst_tab[dst])
    632632            {
    … …  
    637637                  : strcache2_case_sensitive_hash_2 ((const char *)(entry + 1), entry->length);
    638638              dst += hash2;
    639 #ifdef STRCACHE2_USE_MASK
    640               dst &= hash_mask;
    641 #else
    642               dst %= hash_div;
    643 #endif
     639              dst = STRCACHE2_MOD_IT (cache, dst);
    644640              while (dst_tab[dst])
    645641                {
    646642                  dst += hash2;
    647 #ifdef STRCACHE2_USE_MASK
    648                   dst &= hash_mask;
    649 #else
    650                   dst %= hash_div;
    651 #endif
     643                  dst = STRCACHE2_MOD_IT (cache, dst);
    652644                }
    653645            }
    654646
    655647          dst_tab[dst] = entry;
     648#endif
    656649        }
    657650    }
    … …  
    697690  entry->length = length;
    698691  entry->hash1 = hash1;
     692#ifndef STRCACHE2_USE_CHAINING
    699693  entry->hash2 = hash2;
     694#endif
    700695  str_copy = (char *) memcpy (entry + 1, str, length);
    701696  str_copy[length] = '\0';
    702697
     698#ifndef STRCACHE2_USE_CHAINING
    703699  cache->hash_tab[idx] = entry;
     700#else  /* STRCACHE2_USE_CHAINING */
     701  if ((entry->next = cache->hash_tab[idx]) == 0)
     702    cache->hash_tab[idx] = entry;
     703  else
     704    {
     705      cache->hash_tab[idx] = entry;
     706      cache->collision_count++;
     707    }
     708#endif /* STRCACHE2_USE_CHAINING */
    704709  cache->count++;
    705710  if (cache->count >= cache->rehash_count)
    … …  
    714719{
    715720  struct strcache2_entry const *entry;
    716   unsigned int hash2;
    717721  unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
     722  unsigned int hash2 = 0;
    718723  unsigned int idx;
    719724
    … …  
    723728
    724729  /* Lookup the entry in the hash table, hoping for an
    725      early match. */
    726   idx = STRCACHE2_MOD_IT(cache, hash1);
     730     early match.  If not found, enter the string at IDX. */
     731  idx = STRCACHE2_MOD_IT (cache, hash1);
    727732  entry = cache->hash_tab[idx];
     733  if (!entry)
     734    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    728735  if (strcache2_is_equal (cache, entry, str, length, hash1))
    729736    return (const char *)(entry + 1);
     737  cache->collision_1st_count++;
     738
     739#ifdef STRCACHE2_USE_CHAINING
     740  entry = entry->next;
     741#else  /* !STRCACHE2_USE_CHAINING */
     742  hash2 = strcache2_case_sensitive_hash_2 (str, length);
     743  idx += hash2;
     744  idx = STRCACHE2_MOD_IT (cache, idx);
     745  entry = cache->hash_tab[idx];
     746#endif /* !STRCACHE2_USE_CHAINING */
    730747  if (!entry)
    731     hash2 = 0;
    732   else
    733     {
    734       cache->collision_1st_count++;
    735 
    736       hash2 = strcache2_case_sensitive_hash_2 (str, length);
     748    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     749  if (strcache2_is_equal (cache, entry, str, length, hash1))
     750    return (const char *)(entry + 1);
     751  cache->collision_2nd_count++;
     752
     753  /* (We've established hash2, so we can do a straight loop now.)  */
     754  for (;;)
     755    {
     756#ifdef STRCACHE2_USE_CHAINING
     757      entry = entry->next;
     758#else  /* !STRCACHE2_USE_CHAINING */
    737759      idx += hash2;
    738       idx = STRCACHE2_MOD_IT(cache, idx);
     760      idx = STRCACHE2_MOD_IT (cache, idx);
    739761      entry = cache->hash_tab[idx];
     762#endif /* !STRCACHE2_USE_CHAINING */
     763      if (!entry)
     764        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    740765      if (strcache2_is_equal (cache, entry, str, length, hash1))
    741766        return (const char *)(entry + 1);
    742 
    743       if (entry)
    744         {
    745           cache->collision_2nd_count++;
    746           do
    747             {
    748               idx += hash2;
    749               idx = STRCACHE2_MOD_IT(cache, idx);
    750               entry = cache->hash_tab[idx];
    751               cache->collision_3rd_count++;
    752               if (strcache2_is_equal (cache, entry, str, length, hash1))
    753                 return (const char *)(entry + 1);
    754             }
    755           while (entry);
    756         }
    757     }
    758 
    759   /* Not found, add it at IDX. */
    760   return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     767      cache->collision_3rd_count++;
     768    }
     769  /* not reached */
    761770}
    762771
    … …  
    785794
    786795  /* Lookup the entry in the hash table, hoping for an
    787      early match. */
    788   idx = STRCACHE2_MOD_IT(cache, hash1);
     796     early match.  If not found, enter the string at IDX. */
     797  idx = STRCACHE2_MOD_IT (cache, hash1);
    789798  entry = cache->hash_tab[idx];
     799  if (!entry)
     800    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    790801  if (strcache2_is_equal (cache, entry, str, length, hash1))
    791802    return (const char *)(entry + 1);
    792   if (entry)
    793     {
    794       cache->collision_1st_count++;
    795 
    796       if (!hash2)
    797         hash2 = cache->case_insensitive
    798           ? strcache2_case_insensitive_hash_2 (str, length)
    799           : strcache2_case_sensitive_hash_2 (str, length);
     803  cache->collision_1st_count++;
     804
     805#ifdef STRCACHE2_USE_CHAINING
     806  entry = entry->next;
     807#else  /* !STRCACHE2_USE_CHAINING */
     808  if (!hash2)
     809      hash2 = strcache2_case_sensitive_hash_2 (str, length);
     810  idx += hash2;
     811  idx = STRCACHE2_MOD_IT (cache, idx);
     812  entry = cache->hash_tab[idx];
     813#endif /* !STRCACHE2_USE_CHAINING */
     814  if (!entry)
     815    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     816  if (strcache2_is_equal (cache, entry, str, length, hash1))
     817    return (const char *)(entry + 1);
     818  cache->collision_2nd_count++;
     819
     820  /* (We've established hash2, so we can do a straight loop now.)  */
     821  for (;;)
     822    {
     823#ifdef STRCACHE2_USE_CHAINING
     824      entry = entry->next;
     825#else  /* !STRCACHE2_USE_CHAINING */
    800826      idx += hash2;
    801       idx = STRCACHE2_MOD_IT(cache, idx);
     827      idx = STRCACHE2_MOD_IT (cache, idx);
    802828      entry = cache->hash_tab[idx];
     829#endif /* !STRCACHE2_USE_CHAINING */
     830      if (!entry)
     831        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    803832      if (strcache2_is_equal (cache, entry, str, length, hash1))
    804833        return (const char *)(entry + 1);
    805 
    806       if (entry)
    807         {
    808           cache->collision_2nd_count++;
    809           do
    810             {
    811               idx += hash2;
    812               idx = STRCACHE2_MOD_IT(cache, idx);
    813               entry = cache->hash_tab[idx];
    814               cache->collision_3rd_count++;
    815               if (strcache2_is_equal (cache, entry, str, length, hash1))
    816                 return (const char *)(entry + 1);
    817             }
    818           while (entry);
    819         }
    820     }
    821 
    822   /* Not found, add it at IDX. */
    823   return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     834      cache->collision_3rd_count++;
     835    }
     836  /* not reached */
    824837}
    825838
    … …  
    829842{
    830843  struct strcache2_entry const *entry;
     844  unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
     845#ifndef STRCACHE2_USE_CHAINING
    831846  unsigned int hash2;
    832   unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
     847#endif
    833848  unsigned int idx;
    834849
    … …  
    839854  /* Lookup the entry in the hash table, hoping for an
    840855     early match. */
    841   idx = STRCACHE2_MOD_IT(cache, hash1);
     856  idx = STRCACHE2_MOD_IT (cache, hash1);
    842857  entry = cache->hash_tab[idx];
     858  if (!entry)
     859    return NULL;
    843860  if (strcache2_is_equal (cache, entry, str, length, hash1))
    844861    return (const char *)(entry + 1);
     862  cache->collision_1st_count++;
     863
     864#ifdef STRCACHE2_USE_CHAINING
     865  entry = entry->next;
     866#else  /* !STRCACHE2_USE_CHAINING */
     867  hash2 = strcache2_case_sensitive_hash_2 (str, length);
     868  idx += hash2;
     869  idx = STRCACHE2_MOD_IT (cache, idx);
     870  entry = cache->hash_tab[idx];
     871#endif /* !STRCACHE2_USE_CHAINING */
    845872  if (!entry)
    846     hash2 = 0;
    847   else
    848     {
    849       cache->collision_1st_count++;
    850 
    851       hash2 = strcache2_case_sensitive_hash_2 (str, length);
     873    return NULL;
     874  if (strcache2_is_equal (cache, entry, str, length, hash1))
     875    return (const char *)(entry + 1);
     876  cache->collision_2nd_count++;
     877
     878  /* (We've established hash2, so we can do a straight loop now.)  */
     879  for (;;)
     880    {
     881#ifdef STRCACHE2_USE_CHAINING
     882      entry = entry->next;
     883#else  /* !STRCACHE2_USE_CHAINING */
    852884      idx += hash2;
    853       idx = STRCACHE2_MOD_IT(cache, idx);
     885      idx = STRCACHE2_MOD_IT (cache, idx);
    854886      entry = cache->hash_tab[idx];
     887#endif /* !STRCACHE2_USE_CHAINING */
     888      if (!entry)
     889        return NULL;
    855890      if (strcache2_is_equal (cache, entry, str, length, hash1))
    856891        return (const char *)(entry + 1);
    857 
    858       if (entry)
    859         {
    860           cache->collision_2nd_count++;
    861           do
    862             {
    863               idx += hash2;
    864               idx = STRCACHE2_MOD_IT(cache, idx);
    865               entry = cache->hash_tab[idx];
    866               cache->collision_3rd_count++;
    867               if (strcache2_is_equal (cache, entry, str, length, hash1))
    868                 return (const char *)(entry + 1);
    869             }
    870           while (entry);
    871         }
    872     }
    873 
    874   /* Not found. */
    875   return NULL;
     892      cache->collision_3rd_count++;
     893    }
     894  /* not reached */
    876895}
    877896
    … …  
    883902{
    884903  struct strcache2_entry const *entry;
    885   unsigned int hash2;
    886904  unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
     905  unsigned int hash2 = 0;
    887906  unsigned int idx;
    888907
    889   assert (cache->case_insensitive);
     908  assert (!cache->case_insensitive);
     909
    890910  cache->lookup_count++;
    891911
    892912  /* Lookup the entry in the hash table, hoping for an
    893      early match. */
    894   idx = STRCACHE2_MOD_IT(cache, hash1);
     913     early match.  If not found, enter the string at IDX. */
     914  idx = STRCACHE2_MOD_IT (cache, hash1);
    895915  entry = cache->hash_tab[idx];
    896   if (strcache2_is_iequal (cache, entry, str, length, hash1))
     916  if (!entry)
     917    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     918  if (strcache2_is_equal (cache, entry, str, length, hash1))
    897919    return (const char *)(entry + 1);
     920  cache->collision_1st_count++;
     921
     922#ifdef STRCACHE2_USE_CHAINING
     923  entry = entry->next;
     924#else  /* !STRCACHE2_USE_CHAINING */
     925  hash2 = strcache2_case_insensitive_hash_2 (str, length);
     926  idx += hash2;
     927  idx = STRCACHE2_MOD_IT (cache, idx);
     928  entry = cache->hash_tab[idx];
     929#endif /* !STRCACHE2_USE_CHAINING */
    898930  if (!entry)
    899     hash2 = 0;
    900   else
    901     {
    902       cache->collision_1st_count++;
    903 
    904       hash2 = strcache2_case_insensitive_hash_2 (str, length);
     931    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     932  if (strcache2_is_equal (cache, entry, str, length, hash1))
     933    return (const char *)(entry + 1);
     934  cache->collision_2nd_count++;
     935
     936  /* (We've established hash2, so we can do a straight loop now.)  */
     937  for (;;)
     938    {
     939#ifdef STRCACHE2_USE_CHAINING
     940      entry = entry->next;
     941#else  /* !STRCACHE2_USE_CHAINING */
    905942      idx += hash2;
    906       idx = STRCACHE2_MOD_IT(cache, idx);
     943      idx = STRCACHE2_MOD_IT (cache, idx);
    907944      entry = cache->hash_tab[idx];
    908       if (strcache2_is_iequal (cache, entry, str, length, hash1))
     945#endif /* !STRCACHE2_USE_CHAINING */
     946      if (!entry)
     947        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     948      if (strcache2_is_equal (cache, entry, str, length, hash1))
    909949        return (const char *)(entry + 1);
    910 
    911       if (entry)
    912         {
    913           cache->collision_2nd_count++;
    914           do
    915             {
    916               idx += hash2;
    917               idx = STRCACHE2_MOD_IT(cache, idx);
    918               entry = cache->hash_tab[idx];
    919               cache->collision_3rd_count++;
    920               if (strcache2_is_iequal (cache, entry, str, length, hash1))
    921                 return (const char *)(entry + 1);
    922             }
    923           while (entry);
    924         }
    925     }
    926 
    927   /* Not found, add it at IDX. */
    928   return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     950      cache->collision_3rd_count++;
     951    }
     952  /* not reached */
    929953}
    930954
    … …  
    940964  unsigned correct_hash;
    941965
    942   assert (cache->case_insensitive);
     966  assert (!cache->case_insensitive);
    943967  correct_hash = strcache2_case_insensitive_hash_1 (str, length);
    944968  MY_ASSERT_MSG (hash1 == correct_hash, ("%#x != %#x\n", hash1, correct_hash));
    … …  
    953977
    954978  /* Lookup the entry in the hash table, hoping for an
    955      early match. */
    956   idx = STRCACHE2_MOD_IT(cache, hash1);
     979     early match.  If not found, enter the string at IDX. */
     980  idx = STRCACHE2_MOD_IT (cache, hash1);
    957981  entry = cache->hash_tab[idx];
    958   if (strcache2_is_iequal (cache, entry, str, length, hash1))
     982  if (!entry)
     983    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     984  if (strcache2_is_equal (cache, entry, str, length, hash1))
    959985    return (const char *)(entry + 1);
    960   if (entry)
    961     {
    962       cache->collision_1st_count++;
    963 
    964       if (!hash2)
    965         hash2 = strcache2_case_insensitive_hash_2 (str, length);
     986  cache->collision_1st_count++;
     987
     988#ifdef STRCACHE2_USE_CHAINING
     989  entry = entry->next;
     990#else  /* !STRCACHE2_USE_CHAINING */
     991  if (!hash2)
     992      hash2 = strcache2_case_insensitive_hash_2 (str, length);
     993  idx += hash2;
     994  idx = STRCACHE2_MOD_IT (cache, idx);
     995  entry = cache->hash_tab[idx];
     996#endif /* !STRCACHE2_USE_CHAINING */
     997  if (!entry)
     998    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     999  if (strcache2_is_equal (cache, entry, str, length, hash1))
     1000    return (const char *)(entry + 1);
     1001  cache->collision_2nd_count++;
     1002
     1003  /* (We've established hash2, so we can do a straight loop now.)  */
     1004  for (;;)
     1005    {
     1006#ifdef STRCACHE2_USE_CHAINING
     1007      entry = entry->next;
     1008#else  /* !STRCACHE2_USE_CHAINING */
    9661009      idx += hash2;
    967       idx = STRCACHE2_MOD_IT(cache, idx);
     1010      idx = STRCACHE2_MOD_IT (cache, idx);
    9681011      entry = cache->hash_tab[idx];
    969       if (strcache2_is_iequal (cache, entry, str, length, hash1))
     1012#endif /* !STRCACHE2_USE_CHAINING */
     1013      if (!entry)
     1014        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     1015      if (strcache2_is_equal (cache, entry, str, length, hash1))
    9701016        return (const char *)(entry + 1);
    971 
    972       if (entry)
    973         {
    974           cache->collision_2nd_count++;
    975           do
    976             {
    977               idx += hash2;
    978               idx = STRCACHE2_MOD_IT(cache, idx);
    979               entry = cache->hash_tab[idx];
    980               cache->collision_3rd_count++;
    981               if (strcache2_is_iequal (cache, entry, str, length, hash1))
    982                 return (const char *)(entry + 1);
    983             }
    984           while (entry);
    985         }
    986     }
    987 
    988   /* Not found, add it at IDX. */
    989   return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
     1017      cache->collision_3rd_count++;
     1018    }
     1019  /* not reached */
    9901020}
    9911021
    9921022/* The public lookup (case insensitive) string interface. */
    9931023const char *
    994 strcache2_lookup (struct strcache2 *cache, const char *str, unsigned int length)
     1024strcache2_ilookup (struct strcache2 *cache, const char *str, unsigned int length)
    9951025{
    9961026  struct strcache2_entry const *entry;
     1027  unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
     1028#ifndef STRCACHE2_USE_CHAINING
    9971029  unsigned int hash2;
    998   unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
     1030#endif
    9991031  unsigned int idx;
    10001032
    1001   assert (cache->case_insensitive);
     1033  assert (!cache->case_insensitive);
    10021034
    10031035  cache->lookup_count++;
    … …  
    10051037  /* Lookup the entry in the hash table, hoping for an
    10061038     early match. */
    1007   idx = STRCACHE2_MOD_IT(cache, hash1);
     1039  idx = STRCACHE2_MOD_IT (cache, hash1);
    10081040  entry = cache->hash_tab[idx];
    1009   if (strcache2_is_iequal (cache, entry, str, length, hash1))
     1041  if (!entry)
     1042    return NULL;
     1043  if (strcache2_is_equal (cache, entry, str, length, hash1))
    10101044    return (const char *)(entry + 1);
     1045  cache->collision_1st_count++;
     1046
     1047#ifdef STRCACHE2_USE_CHAINING
     1048  entry = entry->next;
     1049#else  /* !STRCACHE2_USE_CHAINING */
     1050  hash2 = strcache2_case_insensitive_hash_2 (str, length);
     1051  idx += hash2;
     1052  idx = STRCACHE2_MOD_IT (cache, idx);
     1053  entry = cache->hash_tab[idx];
     1054#endif /* !STRCACHE2_USE_CHAINING */
    10111055  if (!entry)
    1012     hash2 = 0;
    1013   else
    1014     {
    1015       cache->collision_1st_count++;
    1016 
    1017       hash2 = strcache2_case_insensitive_hash_2 (str, length);
     1056    return NULL;
     1057  if (strcache2_is_equal (cache, entry, str, length, hash1))
     1058    return (const char *)(entry + 1);
     1059  cache->collision_2nd_count++;
     1060
     1061  /* (We've established hash2, so we can do a straight loop now.)  */
     1062  for (;;)
     1063    {
     1064#ifdef STRCACHE2_USE_CHAINING
     1065      entry = entry->next;
     1066#else  /* !STRCACHE2_USE_CHAINING */
    10181067      idx += hash2;
    1019       idx = STRCACHE2_MOD_IT(cache, idx);
     1068      idx = STRCACHE2_MOD_IT (cache, idx);
    10201069      entry = cache->hash_tab[idx];
    1021       if (strcache2_is_iequal (cache, entry, str, length, hash1))
     1070#endif /* !STRCACHE2_USE_CHAINING */
     1071      if (!entry)
     1072        return NULL;
     1073      if (strcache2_is_equal (cache, entry, str, length, hash1))
    10221074        return (const char *)(entry + 1);
    1023 
    1024       if (entry)
    1025         {
    1026           cache->collision_2nd_count++;
    1027           do
    1028             {
    1029               idx += hash2;
    1030               idx = STRCACHE2_MOD_IT(cache, idx);
    1031               entry = cache->hash_tab[idx];
    1032               cache->collision_3rd_count++;
    1033               if (strcache2_is_iequal (cache, entry, str, length, hash1))
    1034                 return (const char *)(entry + 1);
    1035             }
    1036           while (entry);
    1037         }
    1038     }
    1039 
    1040   /* Not found. */
    1041   return NULL;
     1075      cache->collision_3rd_count++;
     1076    }
     1077  /* not reached */
    10421078}
    10431079
    … …  
    11001136    }
    11011137
     1138#ifndef STRCACHE2_USE_CHAINING
    11021139  if (entry->hash2)
    11031140    {
    … …  
    11131150        }
    11141151    }
     1152#endif
    11151153
    11161154  return 0;
    11171155}
    11181156
     1157#ifndef STRCACHE2_USE_CHAINING
    11191158/* Fallback for calculating and returning the 2nd hash. */
    11201159unsigned int
    … …  
    11281167  return hash2;
    11291168}
     1169#endif /* !STRCACHE2_USE_CHAINING */
    11301170
    11311171/* Calculates the case sensitive hash values of the string.
    … …  
    11331173unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p)
    11341174{
     1175#ifndef STRCACHE2_USE_CHAINING
    11351176  *hash2p = strcache2_case_sensitive_hash_2 (str, length);
     1177#else
     1178  *hash2p = 1;
     1179#endif
    11361180  return    strcache2_case_sensitive_hash_1 (str, length);
    11371181}
    … …  
    11411185unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p)
    11421186{
     1187#ifndef STRCACHE2_USE_CHAINING
    11431188  *hash2p = strcache2_case_insensitive_hash_2 (str, length);
     1189#else
     1190  *hash2p = 1;
     1191#endif
    11441192  return    strcache2_case_insensitive_hash_1 (str, length);
    11451193}
    … …  
    11821230#endif
    11831231  cache->count = 0;
     1232#ifdef STRCACHE2_USE_CHAINING
     1233  cache->collision_count = 0;
     1234#endif
    11841235  cache->lookup_count = 0;
    11851236  cache->collision_1st_count = 0;
    … …  
    12461297  unsigned long seg_max_bytes = 0;
    12471298  struct strcache2_seg *seg;
     1299  unsigned int  str_count = 0;
    12481300  unsigned long str_total_len = 0;
    12491301  unsigned int  str_avg_len;
    … …  
    12521304  unsigned int  idx;
    12531305  unsigned int  rehashes;
     1306#ifdef STRCACHE2_USE_CHAINING
     1307  unsigned int  chain_depths[32];
     1308#endif
    12541309
    12551310  printf (_("\n%s strcache2: %s\n"), prefix, cache->name);
    … …  
    12701325
    12711326  /* String statistics. */
     1327#ifdef STRCACHE2_USE_CHAINING
     1328  memset (chain_depths, '\0', sizeof (chain_depths));
     1329#endif
    12721330  idx = cache->hash_size;
    12731331  while (idx-- > 0)
    12741332    {
    12751333      struct strcache2_entry const *entry = cache->hash_tab[idx];
     1334#ifdef STRCACHE2_USE_CHAINING
     1335      unsigned int depth = 0;
     1336      for (; entry != 0; entry = entry->next, depth++)
     1337#else
    12761338      if (entry)
     1339#endif
    12771340        {
    12781341          unsigned int length = entry->length;
    … …  
    12821345          if (length < str_min_len)
    12831346            str_min_len = length;
    1284         }
     1347          str_count++;
     1348        }
     1349#ifdef STRCACHE2_USE_CHAINING
     1350      chain_depths[depth >= 32 ? 31 : depth]++;
     1351#endif
    12851352    }
    12861353  str_avg_len = cache->count ? str_total_len / cache->count : 0;
    12871354  printf (_("%s  %u strings: total len = %lu / max = %u / avg = %u / min = %u\n"),
    12881355          prefix, cache->count, str_total_len, str_max_len, str_avg_len, str_min_len);
     1356  if (str_count != cache->count)
     1357    printf (_("%s  string count mismatch! cache->count=%u, actual count is %u\n"), prefix,
     1358            cache->count, str_count);
    12891359
    12901360  /* Hash statistics. */
    … …  
    13061376  printf (_("%s  hash collisions 1st = %lu (%u%%)  2nd = %lu (%u%%)  3rd = %lu (%u%%)\n"),
    13071377          prefix,
    1308           cache->collision_1st_count, (unsigned int)((float)cache->collision_1st_count * 100 / cache->lookup_count),
    1309           cache->collision_2nd_count, (unsigned int)((float)cache->collision_2nd_count * 100 / cache->lookup_count),
    1310           cache->collision_3rd_count, (unsigned int)((float)cache->collision_3rd_count * 100 / cache->lookup_count));
     1378          cache->collision_1st_count, (unsigned int)((100.0 * cache->collision_1st_count) / cache->lookup_count),
     1379          cache->collision_2nd_count, (unsigned int)((100.0 * cache->collision_2nd_count) / cache->lookup_count),
     1380          cache->collision_3rd_count, (unsigned int)((100.0 * cache->collision_3rd_count) / cache->lookup_count));
     1381#ifdef STRCACHE2_USE_CHAINING
     1382  printf (_("%s  hash insert collisions = %u (%u%%)\n"),
     1383          prefix, cache->collision_count,(unsigned int)((100.0 * cache->collision_count) / cache->count));
     1384  printf (_("%s  %5u (%u%%) empty hash table slots\n"),
     1385          prefix, chain_depths[0],       (unsigned int)((100.0 * chain_depths[0])  / cache->hash_size));
     1386  printf (_("%s  %5u (%u%%) in used hash table slots\n"),
     1387          prefix, chain_depths[1],       (unsigned int)((100.0 * chain_depths[1])  / cache->hash_size));
     1388  for (idx = 2; idx < 32; idx++)
     1389    {
     1390      unsigned strs_at_this_depth = chain_depths[idx];
     1391      unsigned i;
     1392      for (i = idx + 1; i < 32; i++)
     1393        strs_at_this_depth += chain_depths[i];
     1394      if (strs_at_this_depth)
     1395        printf (_("%s  %5u (%2u%%) with %u string%s chained on; %5u (%2u%%) strings at depth %u.\n"),
     1396                prefix, chain_depths[idx], (unsigned int)((100.0 * chain_depths[idx]) / (cache->count - cache->collision_count)),
     1397                idx - 1, idx == 2 ? " " : "s",
     1398                strs_at_this_depth,        (unsigned int)((100.0 * strs_at_this_depth) / cache->count), idx - 1);
     1399    }
     1400#endif
    13111401}
    13121402

  • trunk/src/kmk/strcache2.h

    r1908 r1909  
    3333
    3434#define STRCACHE2_USE_MASK 1
     35#define STRCACHE2_USE_CHAINING 1
    3536
    3637/* string cache memory segment. */
    … …  
    4748struct strcache2_entry
    4849{
     50#ifdef STRCACHE2_USE_CHAINING
     51    struct strcache2_entry *next;       /* Collision chain. */
     52#endif
    4953    void *user;
    5054    unsigned int hash1;
     55#ifndef STRCACHE2_USE_CHAINING
    5156    unsigned int hash2;
     57#endif
    5258    unsigned int length;
    5359};
    … …  
    8389    unsigned long collision_3rd_count;  /* The number of 3rd level collisions. */
    8490    unsigned int count;                 /* Number entries in the cache. */
     91#ifdef STRCACHE2_USE_CHAINING
     92    unsigned int collision_count;       /* Number of entries in chains. */
     93#endif
    8594    unsigned int rehash_count;          /* When to rehash the table. */
    8695    unsigned int init_size;             /* The initial hash table size. */
    … …  
    146155}
    147156
     157#ifndef STRCACHE2_USE_CHAINING
    148158/* Get the second hash value for the string. */
    149159MY_INLINE unsigned int
    … …  
    155165  return hash2;
    156166}
     167#endif
    157168
    158169/* Get the pointer hash value for the string.
Note: See TracChangeset for help on using the changeset viewer.

© 2025 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette