1 | % (c) 2009-2019 Lehrstuhl fuer Softwaretechnik und Programmiersprachen, | |
2 | % Heinrich Heine Universitaet Duesseldorf | |
3 | % This software is licenced under EPL 1.0 (http://www.eclipse.org/org/documents/epl-v10.html) | |
4 | ||
5 | :- module(hashing,[my_term_hash/2, efficient_index/1]). | |
6 | ||
7 | :- use_module(library(terms),[term_hash/3]). | |
8 | ||
9 | ||
10 | :- use_module(module_information,[module_info/2]). | |
11 | ||
12 | :- module_info(group,animator). | |
13 | :- module_info(description,'This module computes hash values (mainly for states) for efficient indexing.'). | |
14 | ||
15 | % -------------------------------------------- | |
16 | ||
17 | :- use_module(self_check). | |
18 | ||
19 | :- assert_must_succeed(( hashing:my_term_hash([1,2,3],X), hashing:efficient_index(X) )). | |
20 | :- assert_must_succeed(( hashing:my_term_hash([1,2,3],X), hashing:my_term_hash([1,2,4],Y), X\=Y )). | |
21 | ||
22 | :- if(tools:platform_is_64_bit). | |
23 | :- format("64-bit platform~n",[]). | |
24 | my_term_hash(T,Res) :- super_hash(T,Res). | |
25 | :- else. | |
26 | :- format("32-bit platform~n",[]). | |
27 | my_term_hash(T,Res) :- term_hash(T, | |
28 | [range(smallint), /* will use full 32 bit on 64 bit systems, 28 bit on 32 bit system */ | |
29 | algorithm(sdbm), % other options jenkins, hsieh, default | |
30 | depth(infinite),if_var(ignore)],Res). | |
31 | % collisions seem with more recent versions of SICStus to no longer be a problem !? | |
32 | % sdbm seems to generate less collisions | |
33 | :- endif. | |
34 | ||
35 | % check if a hash value is an efficient for first argument indexing | |
36 | efficient_index(X) :- number(X), | |
37 | prolog_flag(max_tagged_integer,Max), X=<Max, | |
38 | prolog_flag(min_tagged_integer,Min), X>=Min. | |
39 | ||
40 | % On 64-bit machines we can use the following for efficient indexing: | |
41 | :- public super_hash/2. | |
42 | super_hash(Term,Hash) :- | |
43 | term_hash(Term,[range(smallint),algorithm(sdbm),depth(infinite),if_var(ignore)],H1), | |
44 | term_hash(Term,[range(smallint32),algorithm(jenkins),depth(infinite),if_var(ignore)],H2), | |
45 | Hash is H1 + (H2 << 32). % should be in range 0.. 2**60 | |
46 | % we could still try and use negative numbers | |
47 |