satsolver 0.16.3
|
00001 /* 00002 * Copyright (c) 2007, Novell Inc. 00003 * 00004 * This program is licensed under the BSD license, read LICENSE.BSD 00005 * for further information 00006 */ 00007 00008 /* 00009 * hash.h 00010 * generic hash functions 00011 */ 00012 00013 #ifndef SATSOLVER_HASH_H 00014 #define SATSOLVER_HASH_H 00015 00016 #include "pooltypes.h" 00017 00018 /* value of a hash */ 00019 typedef unsigned int Hashval; 00020 /* mask for hash, used as modulo operator to ensure 'wrapping' of hash 00021 values -> hash table */ 00022 typedef unsigned int Hashmask; 00023 00024 /* inside the hash table, Ids are stored. Hash maps: string -> hash -> Id */ 00025 typedef Id *Hashtable; 00026 00027 /* hash chain */ 00028 #define HASHCHAIN_START 7 00029 #define HASHCHAIN_NEXT(h, hh, mask) (((h) + (hh)++) & (mask)) 00030 00031 /* very simple hash function 00032 * string -> hash 00033 */ 00034 static inline Hashval 00035 strhash(const char *str) 00036 { 00037 Hashval r = 0; 00038 unsigned int c; 00039 while ((c = *(const unsigned char *)str++) != 0) 00040 r += (r << 3) + c; 00041 return r; 00042 } 00043 00044 static inline Hashval 00045 strnhash(const char *str, unsigned len) 00046 { 00047 Hashval r = 0; 00048 unsigned int c; 00049 while (len-- && (c = *(const unsigned char *)str++) != 0) 00050 r += (r << 3) + c; 00051 return r; 00052 } 00053 00054 static inline Hashval 00055 strhash_cont(const char *str, Hashval r) 00056 { 00057 unsigned int c; 00058 while ((c = *(const unsigned char *)str++) != 0) 00059 r += (r << 3) + c; 00060 return r; 00061 } 00062 00063 00064 /* hash for rel 00065 * rel -> hash 00066 */ 00067 static inline Hashval 00068 relhash(Id name, Id evr, int flags) 00069 { 00070 return name + 7 * evr + 13 * flags; 00071 } 00072 00073 00074 /* compute bitmask for value 00075 * returns smallest (2^n-1) > num 00076 * 00077 * used for Hashtable 'modulo' operation 00078 */ 00079 static inline Hashmask 00080 mkmask(unsigned int num) 00081 { 00082 num *= 2; 00083 while (num & (num - 1)) 00084 num &= num - 1; 00085 return num * 2 - 1; 00086 } 00087 00088 #endif /* SATSOLVER_HASH_H */