1 /***********************************************************************/
5 /* Xavier Leroy, projet Cristal, INRIA Rocquencourt */
7 /* Copyright 1996 Institut National de Recherche en Informatique et */
8 /* en Automatique. All rights reserved. This file is distributed */
9 /* under the terms of the GNU Library General Public License, with */
10 /* the special exception on linking described in file ../LICENSE. */
12 /***********************************************************************/
14 /* $Id: hash.c 12149 2012-02-10 16:15:24Z doligez $ */
16 /* The generic hashing primitive */
18 /* The interface of this file is in "mlvalues.h" (for [caml_hash_variant])
19 and in "hash.h" (for the other exported functions). */
25 #include "address_class.h"
27 /*#ifdef ARCH_INT64_TYPE
28 #include "int64_native.h"
30 #include "int64_emul.h"
33 /* The old implementation */
35 static uintnat hash_accu;
36 static intnat hash_univ_limit, hash_univ_count;
38 static void hash_aux(value obj);
40 CAMLprim value caml_hash_univ_param(value count, value limit, value obj)
42 hash_univ_limit = Long_val(limit);
43 hash_univ_count = Long_val(count);
46 return Val_long(hash_accu & 0x3FFFFFFF);
47 /* The & has two purposes: ensure that the return value is positive
48 and give the same result on 32 bit and 64 bit architectures. */
53 #define Combine(new) (hash_accu = hash_accu * Alpha + (new))
54 #define Combine_small(new) (hash_accu = hash_accu * Beta + (new))
56 static void hash_aux(value obj)
63 if (hash_univ_count < 0 || hash_univ_limit < 0) return;
68 Combine(Long_val(obj));
72 /* Pointers into the heap are well-structured blocks. So are atoms.
73 We can inspect the block contents. */
75 CAMLassert (Is_block (obj));
76 if (Is_in_value_area(obj)) {
81 i = caml_string_length(obj);
82 for (p = &Byte_u(obj, 0); i > 0; i--, p++)
86 /* For doubles, we inspect their binary representation, LSB first.
87 The results are consistent among all platforms with IEEE floats. */
89 #ifdef ARCH_BIG_ENDIAN
90 for (p = &Byte_u(obj, sizeof(double) - 1), i = sizeof(double);
94 for (p = &Byte_u(obj, 0), i = sizeof(double);
100 case Double_array_tag:
102 for (j = 0; j < Bosize_val(obj); j += sizeof(double)) {
103 #ifdef ARCH_BIG_ENDIAN
104 for (p = &Byte_u(obj, j + sizeof(double) - 1), i = sizeof(double);
108 for (p = &Byte_u(obj, j), i = sizeof(double);
116 /* We don't know anything about the contents of the block.
117 Better do nothing. */
120 hash_aux(obj - Infix_offset_val(obj));
123 obj = Forward_val (obj);
127 Combine(Oid_val(obj));
130 /* If no hashing function provided, do nothing */
131 if (Custom_ops_val(obj)->hash != NULL) {
133 Combine(Custom_ops_val(obj)->hash(obj));
142 hash_aux(Field(obj, i));
149 /* Otherwise, obj is a pointer outside the heap, to an object with
150 a priori unknown structure. Use its physical address as hash key. */
151 Combine((intnat) obj);