VirtualBox

Changeset 1912 in kBuild


Ignore:
Timestamp:
Oct 22, 2008 9:17:27 PM (16 years ago)
Author:
bird
Message:

strcache2: collapsed the STRCACHE2_USE_CHAINING checks.

Location:
trunk/src/kmk
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/kmk/incdep.c

    r1909 r1912  
    773773                                                     entry->length,
    774774                                                     entry->hash1,
    775 #ifdef STRCACHE2_USE_CHAINING
    776775                                                     1);
    777 #else
    778                                                      entry->hash2);
    779 #endif
    780776  return (const char *)entry->user;
    781777}

  • trunk/src/kmk/strcache2.c

    r1910 r1912  
    287287
    288288MY_INLINE unsigned int
    289 strcache2_case_sensitive_hash_2 (const char *str, unsigned int len)
    290 {
    291 #ifndef STRCACHE2_USE_CHAINING
    292   unsigned int hash = 0;
    293   if (MY_PREDICT_TRUE(len >= 2))
    294     {
    295       unsigned int ch0 = *str++;
    296       hash = 0;
    297       len--;
    298       while (len >= 2)
    299         {
    300           unsigned int ch1 = *str++;
    301           hash += ch0 << (ch1 & 0x7);
    302 
    303           ch0 = *str++;
    304           hash += ch1 << (ch0 & 0x7);
    305 
    306           len -= 2;
    307         }
    308       if (len == 1)
    309         {
    310           unsigned ch1 = *str;
    311           hash += ch0 << (ch1 & 0x7);
    312 
    313           hash += ch1;
    314         }
    315       else
    316         hash += ch0;
    317     }
    318   else if (len)
    319     {
    320       hash = *str;
    321       hash += hash << (hash & 0x7);
    322     }
    323   else
    324     hash = 1;
    325   hash |= 1;
    326   return hash;
    327 #else  /* STRCACHE2_USE_CHAINING */
    328   return 1;
    329 #endif /* STRCACHE2_USE_CHAINING */
    330 }
    331 
    332 MY_INLINE unsigned int
    333289strcache2_case_insensitive_hash_1 (const char *str, unsigned int len)
    334290{
    … …  
    371327    hash = 0;
    372328  return hash;
    373 }
    374 
    375 MY_INLINE unsigned int
    376 strcache2_case_insensitive_hash_2 (const char *str, unsigned int len)
    377 {
    378 #ifndef STRCACHE2_USE_CHAINING
    379   unsigned int hash = 0;
    380   if (MY_PREDICT_TRUE(len >= 2))
    381     {
    382       unsigned int ch0 = *str++;
    383       ch0 = tolower (ch0);
    384       hash = 0;
    385       len--;
    386       while (len >= 2)
    387         {
    388           unsigned int ch1 = *str++;
    389           ch1 = tolower (ch1);
    390           hash += ch0 << (ch1 & 0x7);
    391 
    392           ch0 = *str++;
    393           ch0 = tolower (ch0);
    394           hash += ch1 << (ch0 & 0x7);
    395 
    396           len -= 2;
    397         }
    398       if (len == 1)
    399         {
    400           unsigned ch1 = *str;
    401           ch1 = tolower (ch1);
    402           hash += ch0 << (ch1 & 0x7);
    403 
    404           hash += ch1;
    405         }
    406       else
    407         hash += ch0;
    408     }
    409   else if (len)
    410     {
    411       hash = *str;
    412       hash += hash << (hash & 0x7);
    413     }
    414   else
    415     hash = 1;
    416   hash |= 1;
    417   return hash;
    418 #else  /* STRCACHE2_USE_CHAINING */
    419   return 1;
    420 #endif /* STRCACHE2_USE_CHAINING */
    421329}
    422330
    … …  
    666574
    667575  /* Copy the entries from the old to the new hash table. */
    668 #ifdef STRCACHE2_USE_CHAINING
    669576  cache->collision_count = 0;
    670577  while (src-- > 0)
    … …  
    682589        }
    683590    }
    684 #else  /* !STRCACHE2_USE_CHAINING */
    685   while (src-- > 0)
    686     {
    687       struct strcache2_entry *entry = src_tab[src];
    688       if (entry)
    689         {
    690           unsigned int dst = STRCACHE2_MOD_IT (cache, entry->hash1);
    691           if (dst_tab[dst])
    692             {
    693               unsigned int hash2 = entry->hash2;
    694               if (!hash2)
    695                 entry->hash2 = hash2 = cache->case_insensitive
    696                   ? strcache2_case_insensitive_hash_2 ((const char *)(entry + 1), entry->length)
    697                   : strcache2_case_sensitive_hash_2 ((const char *)(entry + 1), entry->length);
    698               dst += hash2;
    699               dst = STRCACHE2_MOD_IT (cache, dst);
    700               while (dst_tab[dst])
    701                 {
    702                   dst += hash2;
    703                   dst = STRCACHE2_MOD_IT (cache, dst);
    704                 }
    705             }
    706           dst_tab[dst] = entry;
    707         }
    708     }
    709 #endif /* !STRCACHE2_USE_CHAINING */
    710591
    711592  /* That's it, just free the old table and we're done. */
    … …  
    782663  entry->length = length;
    783664  entry->hash1 = hash1;
    784 #ifndef STRCACHE2_USE_CHAINING
    785   entry->hash2 = hash2;
    786 #endif
    787665  str_copy = (char *) memcpy (entry + 1, str, length);
    788666  str_copy[length] = '\0';
    789667
    790 #ifdef STRCACHE2_USE_CHAINING
    791668  if ((entry->next = cache->hash_tab[idx]) != 0)
    792669    cache->collision_count++;
    793 #endif /* STRCACHE2_USE_CHAINING */
    794670  cache->hash_tab[idx] = entry;
    795671  cache->count++;
    … …  
    823699  cache->collision_1st_count++;
    824700
    825 #ifdef STRCACHE2_USE_CHAINING
    826701  entry = entry->next;
    827 #else  /* !STRCACHE2_USE_CHAINING */
    828   hash2 = strcache2_case_sensitive_hash_2 (str, length);
    829   idx += hash2;
    830   idx = STRCACHE2_MOD_IT (cache, idx);
    831   entry = cache->hash_tab[idx];
    832 #endif /* !STRCACHE2_USE_CHAINING */
    833702  if (!entry)
    834703    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    … …  
    840709  for (;;)
    841710    {
    842 #ifdef STRCACHE2_USE_CHAINING
    843711      entry = entry->next;
    844 #else  /* !STRCACHE2_USE_CHAINING */
    845       idx += hash2;
    846       idx = STRCACHE2_MOD_IT (cache, idx);
    847       entry = cache->hash_tab[idx];
    848 #endif /* !STRCACHE2_USE_CHAINING */
    849712      if (!entry)
    850713        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    … …  
    889752  cache->collision_1st_count++;
    890753
    891 #ifdef STRCACHE2_USE_CHAINING
    892754  entry = entry->next;
    893 #else  /* !STRCACHE2_USE_CHAINING */
    894   if (!hash2)
    895       hash2 = strcache2_case_sensitive_hash_2 (str, length);
    896   idx += hash2;
    897   idx = STRCACHE2_MOD_IT (cache, idx);
    898   entry = cache->hash_tab[idx];
    899 #endif /* !STRCACHE2_USE_CHAINING */
    900755  if (!entry)
    901756    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    … …  
    907762  for (;;)
    908763    {
    909 #ifdef STRCACHE2_USE_CHAINING
    910764      entry = entry->next;
    911 #else  /* !STRCACHE2_USE_CHAINING */
    912       idx += hash2;
    913       idx = STRCACHE2_MOD_IT (cache, idx);
    914       entry = cache->hash_tab[idx];
    915 #endif /* !STRCACHE2_USE_CHAINING */
    916765      if (!entry)
    917766        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    … …  
    929778  struct strcache2_entry const *entry;
    930779  unsigned int hash1 = strcache2_case_sensitive_hash_1 (str, length);
    931 #ifndef STRCACHE2_USE_CHAINING
    932   unsigned int hash2;
    933 #endif
    934780  unsigned int idx;
    935781
    … …  
    948794  cache->collision_1st_count++;
    949795
    950 #ifdef STRCACHE2_USE_CHAINING
    951796  entry = entry->next;
    952 #else  /* !STRCACHE2_USE_CHAINING */
    953   hash2 = strcache2_case_sensitive_hash_2 (str, length);
    954   idx += hash2;
    955   idx = STRCACHE2_MOD_IT (cache, idx);
    956   entry = cache->hash_tab[idx];
    957 #endif /* !STRCACHE2_USE_CHAINING */
    958797  if (!entry)
    959798    return NULL;
    … …  
    965804  for (;;)
    966805    {
    967 #ifdef STRCACHE2_USE_CHAINING
    968806      entry = entry->next;
    969 #else  /* !STRCACHE2_USE_CHAINING */
    970       idx += hash2;
    971       idx = STRCACHE2_MOD_IT (cache, idx);
    972       entry = cache->hash_tab[idx];
    973 #endif /* !STRCACHE2_USE_CHAINING */
    974807      if (!entry)
    975808        return NULL;
    … …  
    1006839  cache->collision_1st_count++;
    1007840
    1008 #ifdef STRCACHE2_USE_CHAINING
    1009841  entry = entry->next;
    1010 #else  /* !STRCACHE2_USE_CHAINING */
    1011   hash2 = strcache2_case_insensitive_hash_2 (str, length);
    1012   idx += hash2;
    1013   idx = STRCACHE2_MOD_IT (cache, idx);
    1014   entry = cache->hash_tab[idx];
    1015 #endif /* !STRCACHE2_USE_CHAINING */
    1016842  if (!entry)
    1017843    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    … …  
    1023849  for (;;)
    1024850    {
    1025 #ifdef STRCACHE2_USE_CHAINING
    1026851      entry = entry->next;
    1027 #else  /* !STRCACHE2_USE_CHAINING */
    1028       idx += hash2;
    1029       idx = STRCACHE2_MOD_IT (cache, idx);
    1030       entry = cache->hash_tab[idx];
    1031 #endif /* !STRCACHE2_USE_CHAINING */
    1032852      if (!entry)
    1033853        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    … …  
    1072892  cache->collision_1st_count++;
    1073893
    1074 #ifdef STRCACHE2_USE_CHAINING
    1075894  entry = entry->next;
    1076 #else  /* !STRCACHE2_USE_CHAINING */
    1077   if (!hash2)
    1078       hash2 = strcache2_case_insensitive_hash_2 (str, length);
    1079   idx += hash2;
    1080   idx = STRCACHE2_MOD_IT (cache, idx);
    1081   entry = cache->hash_tab[idx];
    1082 #endif /* !STRCACHE2_USE_CHAINING */
    1083895  if (!entry)
    1084896    return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    … …  
    1090902  for (;;)
    1091903    {
    1092 #ifdef STRCACHE2_USE_CHAINING
    1093904      entry = entry->next;
    1094 #else  /* !STRCACHE2_USE_CHAINING */
    1095       idx += hash2;
    1096       idx = STRCACHE2_MOD_IT (cache, idx);
    1097       entry = cache->hash_tab[idx];
    1098 #endif /* !STRCACHE2_USE_CHAINING */
    1099905      if (!entry)
    1100906        return strcache2_enter_string (cache, idx, str, length, hash1, hash2);
    … …  
    1112918  struct strcache2_entry const *entry;
    1113919  unsigned int hash1 = strcache2_case_insensitive_hash_1 (str, length);
    1114 #ifndef STRCACHE2_USE_CHAINING
    1115   unsigned int hash2;
    1116 #endif
    1117920  unsigned int idx;
    1118921
    … …  
    1131934  cache->collision_1st_count++;
    1132935
    1133 #ifdef STRCACHE2_USE_CHAINING
    1134936  entry = entry->next;
    1135 #else  /* !STRCACHE2_USE_CHAINING */
    1136   hash2 = strcache2_case_insensitive_hash_2 (str, length);
    1137   idx += hash2;
    1138   idx = STRCACHE2_MOD_IT (cache, idx);
    1139   entry = cache->hash_tab[idx];
    1140 #endif /* !STRCACHE2_USE_CHAINING */
    1141937  if (!entry)
    1142938    return NULL;
    … …  
    1148944  for (;;)
    1149945    {
    1150 #ifdef STRCACHE2_USE_CHAINING
    1151946      entry = entry->next;
    1152 #else  /* !STRCACHE2_USE_CHAINING */
    1153       idx += hash2;
    1154       idx = STRCACHE2_MOD_IT (cache, idx);
    1155       entry = cache->hash_tab[idx];
    1156 #endif /* !STRCACHE2_USE_CHAINING */
    1157947      if (!entry)
    1158948        return NULL;
    … …  
    12221012    }
    12231013
    1224 #ifndef STRCACHE2_USE_CHAINING
    1225   if (entry->hash2)
    1226     {
    1227       hash = cache->case_insensitive
    1228         ? strcache2_case_insensitive_hash_2 (str, entry->length)
    1229         : strcache2_case_sensitive_hash_2 (str, entry->length);
    1230       if (hash != entry->hash2)
    1231         {
    1232           fprintf (stderr,
    1233                    "strcache2[%s]: corrupt entry %p, hash#2: %x, expected %x;\nstring: %s\n",
    1234                    cache->name, (void *)entry, hash, entry->hash2, str);
    1235           return -1;
    1236         }
    1237     }
    1238 #endif
    1239 
    12401014  return 0;
    12411015}
    12421016
    1243 #ifndef STRCACHE2_USE_CHAINING
    1244 /* Fallback for calculating and returning the 2nd hash. */
    1245 unsigned int
    1246 strcache2_get_hash2_fallback (struct strcache2 *cache, const char *str)
    1247 {
    1248   struct strcache2_entry *entry = (struct strcache2_entry *) str - 1;
    1249   unsigned hash2 = cache->case_insensitive
    1250       ? strcache2_case_insensitive_hash_2 (str, entry->length)
    1251       : strcache2_case_sensitive_hash_2 (str, entry->length);
    1252   entry->hash2 = hash2;
    1253   return hash2;
    1254 }
    1255 #endif /* !STRCACHE2_USE_CHAINING */
    12561017
    12571018/* Calculates the case sensitive hash values of the string.
    … …  
    12591020unsigned int strcache2_hash_str (const char *str, unsigned int length, unsigned int *hash2p)
    12601021{
    1261 #ifndef STRCACHE2_USE_CHAINING
    1262   *hash2p = strcache2_case_sensitive_hash_2 (str, length);
    1263 #else
    12641022  *hash2p = 1;
    1265 #endif
    12661023  return    strcache2_case_sensitive_hash_1 (str, length);
    12671024}
    … …  
    12711028unsigned int strcache2_hash_istr (const char *str, unsigned int length, unsigned int *hash2p)
    12721029{
    1273 #ifndef STRCACHE2_USE_CHAINING
    1274   *hash2p = strcache2_case_insensitive_hash_2 (str, length);
    1275 #else
    12761030  *hash2p = 1;
    1277 #endif
    12781031  return    strcache2_case_insensitive_hash_1 (str, length);
    12791032}
    … …  
    13161069#endif
    13171070  cache->count = 0;
    1318 #ifdef STRCACHE2_USE_CHAINING
    13191071  cache->collision_count = 0;
    1320 #endif
    13211072  cache->lookup_count = 0;
    13221073  cache->collision_1st_count = 0;
    … …  
    13901141  unsigned int  idx;
    13911142  unsigned int  rehashes;
    1392 #ifdef STRCACHE2_USE_CHAINING
    13931143  unsigned int  chain_depths[32];
    1394 #endif
    13951144
    13961145  printf (_("\n%s strcache2: %s\n"), prefix, cache->name);
    … …  
    14111160
    14121161  /* String statistics. */
    1413 #ifdef STRCACHE2_USE_CHAINING
    14141162  memset (chain_depths, '\0', sizeof (chain_depths));
    1415 #endif
    14161163  idx = cache->hash_size;
    14171164  while (idx-- > 0)
    14181165    {
    14191166      struct strcache2_entry const *entry = cache->hash_tab[idx];
    1420 #ifdef STRCACHE2_USE_CHAINING
    14211167      unsigned int depth = 0;
    14221168      for (; entry != 0; entry = entry->next, depth++)
    1423 #else
    1424       if (entry)
    1425 #endif
    14261169        {
    14271170          unsigned int length = entry->length;
    … …  
    14331176          str_count++;
    14341177        }
    1435 #ifdef STRCACHE2_USE_CHAINING
    14361178      chain_depths[depth >= 32 ? 31 : depth]++;
    1437 #endif
    14381179    }
    14391180  str_avg_len = cache->count ? str_total_len / cache->count : 0;
    … …  
    14651206          cache->collision_2nd_count, (unsigned int)((100.0 * cache->collision_2nd_count) / cache->lookup_count),
    14661207          cache->collision_3rd_count, (unsigned int)((100.0 * cache->collision_3rd_count) / cache->lookup_count));
    1467 #ifdef STRCACHE2_USE_CHAINING
    14681208  printf (_("%s  hash insert collisions = %u (%u%%)\n"),
    14691209          prefix, cache->collision_count,(unsigned int)((100.0 * cache->collision_count) / cache->count));
    … …  
    14841224                strs_at_this_depth,        (unsigned int)((100.0 * strs_at_this_depth) / cache->count), idx - 1);
    14851225    }
    1486 #endif
    14871226}
    14881227

  • trunk/src/kmk/strcache2.h

    r1909 r1912  
    3333
    3434#define STRCACHE2_USE_MASK 1
    35 #define STRCACHE2_USE_CHAINING 1
    3635
    3736/* string cache memory segment. */
    … …  
    4847struct strcache2_entry
    4948{
    50 #ifdef STRCACHE2_USE_CHAINING
    5149    struct strcache2_entry *next;       /* Collision chain. */
    52 #endif
    5350    void *user;
    5451    unsigned int hash1;
    55 #ifndef STRCACHE2_USE_CHAINING
    56     unsigned int hash2;
    57 #endif
    5852    unsigned int length;
    5953};
    … …  
    8983    unsigned long collision_3rd_count;  /* The number of 3rd level collisions. */
    9084    unsigned int count;                 /* Number entries in the cache. */
    91 #ifdef STRCACHE2_USE_CHAINING
    9285    unsigned int collision_count;       /* Number of entries in chains. */
    93 #endif
    9486    unsigned int rehash_count;          /* When to rehash the table. */
    9587    unsigned int init_size;             /* The initial hash table size. */
    … …  
    155147}
    156148
    157 #ifndef STRCACHE2_USE_CHAINING
    158 /* Get the second hash value for the string. */
    159 MY_INLINE unsigned int
    160 strcache2_get_hash2 (struct strcache2 *cache, const char *str)
    161 {
    162   unsigned int hash2 = strcache2_get_entry (cache, str)->hash2;
    163   if (!hash2)
    164     hash2 = strcache2_get_hash2_fallback (cache, str);
    165   return hash2;
    166 }
    167 #endif
    168 
    169149/* Get the pointer hash value for the string.
    170150
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