Ignore:
Timestamp:
Mar 30, 2008, 1:08:23 PM (17 years ago)
Author:
bird
Message:

Fixed massive collision issue with variable_hash_1i.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/kmk/variable.c

    r1444 r1449  
    114114static inline unsigned long variable_hash_2i(register const char *var, register int length)
    115115{
     116# define UPDATE_HASH(ch) hash = (ch) + (hash << 6) + (hash << 16) - hash
     117# ifndef CONFIG_WITH_OPTIMIZATION_HACKS
     118#  if 1
    116119    register const unsigned char *uvar = (const unsigned char *)var;
    117     register unsigned int hash = 0;
    118     uvar += length;
     120    register unsigned long hash = 0;
     121    while (length-- > 0)
     122        UPDATE_HASH(*uvar++);
     123    return hash;
     124#  else
     125    return_STRING_N_HASH_2 (var, length);
     126#  endif
     127# else /* CONFIG_WITH_OPTIMIZATION_HACKS */
     128    register unsigned long hash = 0;
     129    register const unsigned char *uvar = (const unsigned char *)var;
     130    register const unsigned char *uvar_end = uvar + length;
    119131    switch (length)
    120132    {
    121         default:
    122         case 16: hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    123         case 15: hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    124         case 14: hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    125         case 13: hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    126         case 12: hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    127         case 11: hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    128         case 10: hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    129         case 9:  hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    130         case 8:  hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    131         case 7:  hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    132         case 6:  hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    133         case 5:  hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    134         case 4:  hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    135         case 3:  hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    136         case 2:  hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    137         case 1:  hash = *--uvar + (hash << 6) + (hash << 16) - hash;
    138         case 0:
    139             break;
    140     }
     133        default:
     134        case 32: //UPDATE_HASH(uvar_end[-16]);
     135        case 31: UPDATE_HASH(uvar_end[-15]);
     136        case 30: //UPDATE_HASH(uvar_end[-14]);
     137        case 29: UPDATE_HASH(uvar_end[-13]);
     138        case 28: //UPDATE_HASH(uvar_end[-12]);
     139        case 27: UPDATE_HASH(uvar_end[-11]);
     140        case 26: //UPDATE_HASH(uvar_end[-10]);
     141        case 25: UPDATE_HASH(uvar_end[-9]);
     142        case 24: //UPDATE_HASH(uvar[15]);
     143        case 23: UPDATE_HASH(uvar[14]);
     144        case 22: //UPDATE_HASH(uvar[13]);
     145        case 21: UPDATE_HASH(uvar[12]);
     146        case 20: //UPDATE_HASH(uvar[11]);
     147        case 19: UPDATE_HASH(uvar[10]);
     148        case 18: //UPDATE_HASH(uvar[9]);
     149        case 17: UPDATE_HASH(uvar[8]);
     150        case 16: //UPDATE_HASH(uvar_end[-8]);
     151        case 15: UPDATE_HASH(uvar_end[-7]);
     152        case 14: //UPDATE_HASH(uvar_end[-6]);
     153        case 13: UPDATE_HASH(uvar_end[-5]);
     154        case 12: //UPDATE_HASH(uvar_end[-4]);
     155        case 11: UPDATE_HASH(uvar_end[-3]);
     156        case 10: //UPDATE_HASH(uvar_end[-2]);
     157        case 9:  UPDATE_HASH(uvar_end[-1]);
     158        case 8:  //UPDATE_HASH(uvar[7]);
     159        case 7:  UPDATE_HASH(uvar[6]);
     160        case 6:  //UPDATE_HASH(uvar[5]);
     161        case 5:  UPDATE_HASH(uvar[4]);
     162        case 4:  //UPDATE_HASH(uvar[3]);
     163        case 3:  UPDATE_HASH(uvar[2]);
     164        case 2:  //UPDATE_HASH(uvar[1]);
     165        case 1:  UPDATE_HASH(uvar[0]);
     166        case 0: 
     167            return hash;
     168    }
     169# endif /* CONFIG_WITH_OPTIMIZATION_HACKS*/
     170# undef UPDATE_HASH
     171}
     172
     173static inline unsigned long variable_hash_1i(register const char *var, register int length)
     174{
     175# define UPDATE_HASH(ch) hash = ((hash << 5) + hash) + (ch)
     176# ifndef CONFIG_WITH_OPTIMIZATION_HACKS
     177#  if 1
     178    register const unsigned char *uvar = (const unsigned char *)var;
     179    register unsigned long hash = 5381;
     180    while (length-- > 0)
     181      UPDATE_HASH(*uvar++);
    141182    return hash;
    142 }
    143 
    144 static inline unsigned long variable_hash_1i(register const char *var, register int length)
    145 {
     183#  else
     184    return_STRING_N_HASH_1 (var, length);
     185#  endif
     186# else /* CONFIG_WITH_OPTIMIZATION_HACKS */
    146187    register const unsigned char *uvar = (const unsigned char *)var;
    147     register unsigned int hash = ((5381 << 5) + 5381) + *uvar;
     188    register const unsigned char *uvar_end = (const unsigned char *)var + length;
     189    register unsigned long hash = ((5381 << 5) + 5381) + *uvar;
    148190    switch (length)
    149191    {
    150         default:
    151         case 8: hash = ((hash << 5) + hash) + uvar[7];
    152         case 7: hash = ((hash << 5) + hash) + uvar[6];
    153         case 6: hash = ((hash << 5) + hash) + uvar[5];
    154         case 5: hash = ((hash << 5) + hash) + uvar[4];
    155         case 4: hash = ((hash << 5) + hash) + uvar[3];
    156         case 3: hash = ((hash << 5) + hash) + uvar[2];
    157         case 2: hash = ((hash << 5) + hash) + uvar[1];
    158         case 1: return hash;
    159         case 0: return 5381; /* shouldn't happen */
    160     }
     192        default:
     193#if 0 /* seems to be a waste of time. */
     194        case 97: UPDATE_HASH(uvar_end[-77]);
     195        case 96: //UPDATE_HASH(uvar_end[-76]);
     196        case 95: //UPDATE_HASH(uvar_end[-75]);
     197        case 94: //UPDATE_HASH(uvar_end[-74]);
     198        case 93: UPDATE_HASH(uvar_end[-73]);
     199        case 92: //UPDATE_HASH(uvar_end[-72]);
     200        case 91: //UPDATE_HASH(uvar_end[-71]);
     201        case 90: //UPDATE_HASH(uvar_end[-70]);
     202        case 89: UPDATE_HASH(uvar_end[-69]);
     203        case 88: //UPDATE_HASH(uvar_end[-68]);
     204        case 87: //UPDATE_HASH(uvar_end[-67]);
     205        case 86: //UPDATE_HASH(uvar_end[-66]);
     206        case 85: UPDATE_HASH(uvar_end[-65]);
     207        case 84: //UPDATE_HASH(uvar_end[-64]);
     208        case 83: //UPDATE_HASH(uvar_end[-63]);
     209        case 82: //UPDATE_HASH(uvar_end[-62]);
     210        case 81: UPDATE_HASH(uvar_end[-61]);
     211        case 80: //UPDATE_HASH(uvar_end[-60]);
     212        case 79: //UPDATE_HASH(uvar_end[-59]);
     213        case 78: //UPDATE_HASH(uvar_end[-58]);
     214        case 77: UPDATE_HASH(uvar_end[-57]);
     215        case 76: //UPDATE_HASH(uvar_end[-56]);
     216        case 75: //UPDATE_HASH(uvar_end[-55]);
     217        case 74: //UPDATE_HASH(uvar_end[-54]);
     218        case 73: UPDATE_HASH(uvar_end[-53]);
     219        case 72: //UPDATE_HASH(uvar_end[-52]);
     220        case 71: //UPDATE_HASH(uvar_end[-51]);
     221        case 70: //UPDATE_HASH(uvar_end[-50]);
     222        case 69: UPDATE_HASH(uvar_end[-49]);
     223        case 68: //UPDATE_HASH(uvar_end[-48]);
     224        case 67: //UPDATE_HASH(uvar_end[-47]);
     225        case 66: //UPDATE_HASH(uvar_end[-46]);
     226        case 65: UPDATE_HASH(uvar_end[-49]);
     227        case 64: //UPDATE_HASH(uvar_end[-48]);
     228        case 63: //UPDATE_HASH(uvar_end[-47]);
     229        case 62: //UPDATE_HASH(uvar_end[-46]);
     230        case 61: UPDATE_HASH(uvar_end[-45]);
     231        case 60: //UPDATE_HASH(uvar_end[-44]);
     232        case 59: //UPDATE_HASH(uvar_end[-43]);
     233        case 58: //UPDATE_HASH(uvar_end[-42]);
     234        case 57: UPDATE_HASH(uvar_end[-41]);
     235        case 56: //UPDATE_HASH(uvar_end[-40]);
     236        case 55: //UPDATE_HASH(uvar_end[-39]);
     237        case 54: //UPDATE_HASH(uvar_end[-38]);
     238        case 53: UPDATE_HASH(uvar_end[-37]);
     239        case 52: //UPDATE_HASH(uvar_end[-36]);
     240        case 51: UPDATE_HASH(uvar_end[-35]);
     241        case 50: //UPDATE_HASH(uvar_end[-34]);
     242        case 49: UPDATE_HASH(uvar_end[-33]);
     243#endif
     244        case 48: //UPDATE_HASH(uvar_end[-32]);
     245        case 47: UPDATE_HASH(uvar_end[-31]);
     246        case 46: //UPDATE_HASH(uvar_end[-30]);
     247        case 45: UPDATE_HASH(uvar_end[-29]);
     248        case 44: //UPDATE_HASH(uvar_end[-28]);
     249        case 43: UPDATE_HASH(uvar_end[-27]);
     250        case 42: //UPDATE_HASH(uvar_end[-26]);
     251        case 41: UPDATE_HASH(uvar_end[-25]);
     252        case 40: //UPDATE_HASH(uvar_end[-24]);
     253        case 39: UPDATE_HASH(uvar_end[-23]);
     254        case 38: //UPDATE_HASH(uvar_end[-22]);
     255        case 37: UPDATE_HASH(uvar_end[-21]);
     256        case 36: //UPDATE_HASH(uvar_end[-20]);
     257        case 35: UPDATE_HASH(uvar_end[-19]);
     258        case 34: //UPDATE_HASH(uvar_end[-18]);
     259        case 33: UPDATE_HASH(uvar_end[-17]);
     260
     261        case 32: UPDATE_HASH(uvar_end[-16]);
     262        case 31: UPDATE_HASH(uvar_end[-15]);
     263        case 30: UPDATE_HASH(uvar_end[-14]);
     264        case 29: UPDATE_HASH(uvar_end[-13]);
     265        case 28: UPDATE_HASH(uvar[15]);
     266        case 27: UPDATE_HASH(uvar[14]);
     267        case 26: UPDATE_HASH(uvar[13]);
     268        case 25: UPDATE_HASH(uvar[12]);
     269
     270        case 24: UPDATE_HASH(uvar_end[-12]);
     271        case 23: UPDATE_HASH(uvar_end[-11]);
     272        case 22: UPDATE_HASH(uvar_end[-10]);
     273        case 21: UPDATE_HASH(uvar_end[-9]);
     274        case 20: UPDATE_HASH(uvar[7]);
     275        case 19: UPDATE_HASH(uvar[6]); 
     276        case 18: UPDATE_HASH(uvar[5]);
     277        case 17: UPDATE_HASH(uvar[4]);
     278
     279        case 16: UPDATE_HASH(uvar_end[-8]);
     280        case 15: UPDATE_HASH(uvar_end[-7]);
     281        case 14: UPDATE_HASH(uvar_end[-6]);
     282        case 13: UPDATE_HASH(uvar_end[-5]);
     283        case 12: UPDATE_HASH(uvar[11]);
     284        case 11: UPDATE_HASH(uvar[10]);
     285        case 10: UPDATE_HASH(uvar[9]);
     286        case 9:  UPDATE_HASH(uvar[8]);
     287
     288        case 8:  UPDATE_HASH(uvar_end[-4]);
     289        case 7:  UPDATE_HASH(uvar_end[-3]);
     290        case 6:  UPDATE_HASH(uvar_end[-2]);
     291        case 5:  UPDATE_HASH(uvar_end[-1]);
     292        case 4:  UPDATE_HASH(uvar[3]);
     293        case 3:  UPDATE_HASH(uvar[2]);
     294        case 2:  UPDATE_HASH(uvar[1]);
     295        case 1:  return hash;
     296        case 0:  return 5381; /* shouldn't happen */
     297    }
     298# endif /* CONFIG_WITH_OPTIMIZATION_HACKS */
     299# undef UPDATE_HASH
    161300}
    162301#endif /* CONFIG_WITH_OPTIMIZATION_HACKS */
    … …  
    289428#endif
    290429#ifndef PERFILE_VARIABLE_BUCKETS
     430# ifdef KMK /* Move to Makefile.kmk? */
     431#  define PERFILE_VARIABLE_BUCKETS      64
     432# else
    291433#define PERFILE_VARIABLE_BUCKETS        23
     434# endif
    292435#endif
    293436#ifndef SMALL_SCOPE_VARIABLE_BUCKETS
    294437# ifdef KMK /* Move to Makefile.kmk? */
    295 #  define SMALL_SCOPE_VARIABLE_BUCKETS  31
     438#  define SMALL_SCOPE_VARIABLE_BUCKETS  32
    296439# else
    297440#define SMALL_SCOPE_VARIABLE_BUCKETS    13
Note: See TracChangeset for help on using the changeset viewer.