1 // -*-c++-*- 2 /* $Id$ */ 3 4 /* 5 * 6 * Copyright (C) 1998 David Mazieres (dm@uun.org) 7 * 8 * This program is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU General Public License as 10 * published by the Free Software Foundation; either version 2, or (at 11 * your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, but 14 * WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with this program; if not, write to the Free Software 20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 21 * USA 22 * 23 */ 24 25 #ifndef _KEYFUNC_H_ 26 #define _KEYFUNC_H_ 1 27 28 template<class T> struct unref_t { 29 typedef T base_type; 30 typedef T unref_type; 31 typedef const T &ref_type; 32 typedef T &ncref_type; 33 }; 34 template<class T> struct unref_t<const T> { 35 typedef T base_type; 36 typedef const T unref_type; 37 typedef const T &ref_type; 38 typedef T &ncref_type; 39 }; 40 template<class T> struct unref_t<T &> { 41 typedef T base_type; 42 typedef T unref_type; 43 typedef const T &ref_type; 44 typedef T &ncref_type; 45 }; 46 template<class T> struct unref_t<const T &> { 47 typedef T base_type; 48 typedef const T unref_type; 49 typedef const T &ref_type; 50 typedef T &ncref_type; 51 }; 52 #define CREF(T) unref_t<T>::ref_type 53 #define UNREF(T) unref_t<T>::unref_type 54 #define UNCREF(T) unref_t<T>::base_type 55 #define NCREF(T) unref_t<T>::ncref_type 56 57 #define HASHSEED 5381 58 inline u_int 59 hash_bytes (const void *_key, int len, u_int seed = HASHSEED) 60 { 61 const u_char *key = (const u_char *) _key; 62 const u_char *end; 63 64 for (end = key + len; key < end; key++) 65 seed = ((seed << 5) + seed) ^ *key; 66 return seed; 67 } 68 69 inline u_int 70 hash_string (const void *_p, u_int v = HASHSEED) 71 { 72 const char *p = (const char *) _p; 73 while (*p) 74 v = (33 * v) ^ (unsigned char) *p++; 75 return v; 76 } 77 78 inline u_int 79 hash_rotate (u_int val, u_int rot) 80 { 81 rot %= 8 * sizeof (val); 82 return (val << rot) | (val >> (8 * sizeof (val) - rot)); 83 } 84 85 class hash_t { 86 u_int val; 87 public: 88 hash_t () {} 89 hash_t (u_int v) : val (v) {} 90 operator u_int() const { return val; } 91 }; 92 93 template<class T> 94 struct compare { 95 compare () {} 96 int operator() (typename CREF (T) a, typename CREF (T) b) const 97 { return a < b ? -1 : b < a; } 98 }; 99 template<class T> 100 struct compare<const T> : compare<T> 101 { 102 compare () {} 103 }; 104 105 template<class T> 106 struct equals { 107 equals () {} 108 bool operator() (typename CREF (T) a, typename CREF (T) b) const 109 { return a == b; } 110 }; 111 template<class T> 112 struct equals<const T> : equals<T> 113 { 114 equals () {} 115 }; 116 117 template<class T> 118 struct hashfn { 119 hashfn () {} 120 hash_t operator() (typename CREF (T) a) const 121 { return a; } 122 }; 123 template<class T> 124 struct hashfn<const T> : hashfn<T> 125 { 126 hashfn () {} 127 }; 128 129 template<class T1, class T2> 130 struct hash2fn { 131 hashfn<T1> h1; 132 hashfn<T2> h2; 133 hash2fn () {} 134 hash_t operator() (typename CREF (T1) t1, typename CREF (T2) t2) const 135 { return h1 (t1) ^ h2 (t2); } 136 }; 137 138 /* Don't compare pointers by accident */ 139 template<class T> struct compare<T *>; 140 template<class T> struct hashfn<T *>; 141 142 /* Specializations for (char *) */ 143 #define _CHAR_PTR(T, u) \ 144 template<> \ 145 struct compare<T> { \ 146 compare () {} \ 147 int operator() (const u char *a, const u char *b) const \ 148 { return strcmp ((char *) a, (char *) b); } \ 149 }; \ 150 template<> \ 151 struct equals<T> { \ 152 equals () {} \ 153 bool operator() (const u char *a, const u char *b) const \ 154 { return !strcmp ((char *) a, (char *) b); } \ 155 }; \ 156 template<> \ 157 struct hashfn<T> { \ 158 hashfn () {} \ 159 hash_t operator() (const u char *a) const \ 160 { return hash_string (a); } \ 161 }; 162 #define CHAR_PTR(T, u) _CHAR_PTR(T, u) _CHAR_PTR(T const, u) 163 CHAR_PTR(char *,) 164 CHAR_PTR(const char *,) 165 CHAR_PTR(signed char *, signed) 166 CHAR_PTR(const signed char *, signed) 167 CHAR_PTR(unsigned char *, unsigned) 168 CHAR_PTR(const unsigned char *, unsigned) 169 170 template<class R, class V, class K, K V::*key, class F> 171 class keyfunc_1 { 172 public: 173 const F kf; 174 keyfunc_1 () {} 175 keyfunc_1 (const F &f) : kf (f) {} 176 R operator() (typename CREF (V) a) const 177 { return kf (a.*key); } 178 }; 179 180 template<class R, class V, class K, K V::*key, class F> 181 class keyfunc_2 { 182 public: 183 const F kf; 184 keyfunc_2 () {} 185 keyfunc_2 (const F &f) : kf (f) {} 186 R operator() (typename CREF (V) a, typename CREF (V) b) const 187 { return kf (a.*key, b.*key); } 188 }; 189 190 #endif /* !KEYFUNC_H_ */ 191