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 */ 94