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