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