Mercurial > hg > xemacs-beta

comparison src/symbols.c @ 490:38fb9ae12edd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[xemacs-hg @ 2001-04-30 09:12:03 by martinb] a better string hash function
author martinb
date Mon, 30 Apr 2001 09:12:04 +0000
parents c33ae14dd6d0
children 183866b06e0b
comparison
equal deleted inserted replaced
489:4a8bb4aa9740 490:38fb9ae12edd
339 Also store the bucket number in oblookup_last_bucket_number. */ 339 Also store the bucket number in oblookup_last_bucket_number. */
340 340
341 Lisp_Object 341 Lisp_Object
342 oblookup (Lisp_Object obarray, const Bufbyte *ptr, Bytecount size) 342 oblookup (Lisp_Object obarray, const Bufbyte *ptr, Bytecount size)
343 { 343 {
344 int hash, obsize; 344 unsigned int hash, obsize;
345 Lisp_Symbol *tail; 345 Lisp_Symbol *tail;
346 Lisp_Object bucket; 346 Lisp_Object bucket;
347 347
348 if (!VECTORP (obarray) || 348 if (!VECTORP (obarray) ||
349 (obsize = XVECTOR_LENGTH (obarray)) == 0) 349 (obsize = XVECTOR_LENGTH (obarray)) == 0)
372 break; 372 break;
373 } 373 }
374 return make_int (hash); 374 return make_int (hash);
375 } 375 }
376 376
377 #if 0 /* Emacs 19.34 */ 377 /* An excellent string hashing function.
378 int 378 Adapted from glib's g_str_hash().
379 Investigation by Karl Nelson <kenelson@ece.ucdavis.edu>.
380 Do a web search for "g_str_hash X31_HASH" if you want to know more. */
381 unsigned int
379 hash_string (const Bufbyte *ptr, Bytecount len) 382 hash_string (const Bufbyte *ptr, Bytecount len)
380 { 383 {
381 const Bufbyte *p = ptr; 384 unsigned int hash;
382 const Bufbyte *end = p + len; 385
383 Bufbyte c; 386 for (hash = 0; len; len--, ptr++)
384 int hash = 0; 387 /* (31 * hash) will probably be optimized to ((hash << 5) - hash). */
385 388 hash = 31 * hash + *ptr;
386 while (p != end) 389
387 { 390 return hash;
388 c = *p++;
389 if (c >= 0140) c -= 40;
390 hash = ((hash<<3) + (hash>>28) + c);
391 }
392 return hash & 07777777777;
393 }
394 #endif
395
396 /* derived from hashpjw, Dragon Book P436. */
397 int
398 hash_string (const Bufbyte *ptr, Bytecount len)
399 {
400 int hash = 0;
401
402 while (len-- > 0)
403 {
404 int g;
405 hash = (hash << 4) + *ptr++;
406 g = hash & 0xf0000000;
407 if (g)
408 hash = (hash ^ (g >> 24)) ^ g;
409 }
410 return hash & 07777777777;
411 } 391 }
412 392
413 /* Map FN over OBARRAY. The mapping is stopped when FN returns a 393 /* Map FN over OBARRAY. The mapping is stopped when FN returns a
414 non-zero value. */ 394 non-zero value. */
415 void 395 void
3248 Vobarray = make_vector (OBARRAY_SIZE, Qzero); 3228 Vobarray = make_vector (OBARRAY_SIZE, Qzero);
3249 initial_obarray = Vobarray; 3229 initial_obarray = Vobarray;
3250 staticpro (&initial_obarray); 3230 staticpro (&initial_obarray);
3251 /* Intern nil in the obarray */ 3231 /* Intern nil in the obarray */
3252 { 3232 {
3253 int hash = hash_string (string_data (XSYMBOL (Qnil)->name), 3); 3233 unsigned int hash = hash_string (string_data (XSYMBOL (Qnil)->name), 3);
3254 XVECTOR_DATA (Vobarray)[hash % OBARRAY_SIZE] = Qnil; 3234 XVECTOR_DATA (Vobarray)[hash % OBARRAY_SIZE] = Qnil;
3255 } 3235 }
3256 3236
3257 { 3237 {
3258 /* Required to get around a GCC syntax error on certain 3238 /* Required to get around a GCC syntax error on certain