satsolver
0.17.2
Main Page
Related Pages
Classes
Files
File List
File Members
src
hash.h
Go to the documentation of this file.
1
/*
2
* Copyright (c) 2007, Novell Inc.
3
*
4
* This program is licensed under the BSD license, read LICENSE.BSD
5
* for further information
6
*/
7
8
/*
9
* hash.h
10
* generic hash functions
11
*/
12
13
#ifndef SATSOLVER_HASH_H
14
#define SATSOLVER_HASH_H
15
16
#include "
pooltypes.h
"
17
18
/* value of a hash */
19
typedef
unsigned
int
Hashval
;
20
/* mask for hash, used as modulo operator to ensure 'wrapping' of hash
21
values -> hash table */
22
typedef
unsigned
int
Hashmask
;
23
24
/* inside the hash table, Ids are stored. Hash maps: string -> hash -> Id */
25
typedef
Id
*
Hashtable
;
26
27
/* hash chain */
28
#define HASHCHAIN_START 7
29
#define HASHCHAIN_NEXT(h, hh, mask) (((h) + (hh)++) & (mask))
30
31
/* very simple hash function
32
* string -> hash
33
*/
34
static
inline
Hashval
35
strhash
(
const
char
*str)
36
{
37
Hashval
r = 0;
38
unsigned
int
c;
39
while
((c = *(
const
unsigned
char
*)str++) != 0)
40
r += (r << 3) + c;
41
return
r;
42
}
43
44
static
inline
Hashval
45
strnhash
(
const
char
*str,
unsigned
len)
46
{
47
Hashval
r = 0;
48
unsigned
int
c;
49
while
(len-- && (c = *(
const
unsigned
char
*)str++) != 0)
50
r += (r << 3) + c;
51
return
r;
52
}
53
54
static
inline
Hashval
55
strhash_cont
(
const
char
*str,
Hashval
r)
56
{
57
unsigned
int
c;
58
while
((c = *(
const
unsigned
char
*)str++) != 0)
59
r += (r << 3) + c;
60
return
r;
61
}
62
63
64
/* hash for rel
65
* rel -> hash
66
*/
67
static
inline
Hashval
68
relhash
(
Id
name,
Id
evr,
int
flags)
69
{
70
return
name + 7 * evr + 13 * flags;
71
}
72
73
74
/* compute bitmask for value
75
* returns smallest (2^n-1) > num
76
*
77
* used for Hashtable 'modulo' operation
78
*/
79
static
inline
Hashmask
80
mkmask
(
unsigned
int
num)
81
{
82
num *= 2;
83
while
(num & (num - 1))
84
num &= num - 1;
85
return
num * 2 - 1;
86
}
87
88
#endif
/* SATSOLVER_HASH_H */
Generated by
1.8.4