Commit | Line | Data |
---|---|---|

03d53b73 | 1 | /* -*-c-*- |

2 | * | |

20eb516f | 3 | * $Id: hash.h,v 1.3 2000/06/17 10:37:39 mdw Exp $ |

03d53b73 | 4 | * |

5 | * General hashtable infrastructure | |

6 | * | |

7 | * (c) 1999 Straylight/Edgeware | |

8 | */ | |

9 | ||

10 | /*----- Licensing notice --------------------------------------------------* | |

11 | * | |

12 | * This file is part of the mLib utilities library. | |

13 | * | |

14 | * mLib is free software; you can redistribute it and/or modify | |

15 | * it under the terms of the GNU Library General Public License as | |

16 | * published by the Free Software Foundation; either version 2 of the | |

17 | * License, or (at your option) any later version. | |

18 | * | |

19 | * mLib is distributed in the hope that it will be useful, | |

20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |

21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |

22 | * GNU Library General Public License for more details. | |

23 | * | |

24 | * You should have received a copy of the GNU Library General Public | |

25 | * License along with mLib; if not, write to the Free | |

26 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |

27 | * MA 02111-1307, USA. | |

28 | */ | |

29 | ||

30 | /*----- Revision history --------------------------------------------------* | |

31 | * | |

32 | * $Log: hash.h,v $ | |

20eb516f | 33 | * Revision 1.3 2000/06/17 10:37:39 mdw |

34 | * Add support for arena management. | |

35 | * | |

c6e0eaf0 | 36 | * Revision 1.2 1999/12/10 23:42:04 mdw |

37 | * Change header file guard names. | |

38 | * | |

03d53b73 | 39 | * Revision 1.1 1999/08/02 14:45:48 mdw |

40 | * Break low-level hashtable code out from sym. | |

41 | * | |

42 | */ | |

43 | ||

c6e0eaf0 | 44 | #ifndef MLIB_HASH_H |

45 | #define MLIB_HASH_H | |

03d53b73 | 46 | |

47 | #ifdef __cplusplus | |

48 | extern "C" { | |

49 | #endif | |

50 | ||

51 | /*----- Notes -------------------------------------------------------------* | |

52 | * | |

53 | * This isn't a complete implementation of anything. It's a collection of | |

54 | * useful types and functions which will help when building hashtables of | |

55 | * things. The general-purpose hashtable is provided by the @sym@ functions. | |

56 | */ | |

57 | ||

58 | /*----- Header files ------------------------------------------------------*/ | |

59 | ||

60 | #include <stddef.h> | |

61 | ||

20eb516f | 62 | #ifndef MLIB_ARENA_H |

63 | # include "arena.h" | |

64 | #endif | |

65 | ||

c6e0eaf0 | 66 | #ifndef MLIB_BITS_H |

03d53b73 | 67 | # include "bits.h" |

68 | #endif | |

69 | ||

70 | /*----- Data structures ---------------------------------------------------*/ | |

71 | ||

72 | /* --- Hashtable basics --- * | |

73 | * | |

74 | * This contains the bare minimum to actually get anything useful done. In | |

75 | * particular it doesn't maintain any weighting information: when to extend | |

76 | * the table is left up to the particular implementation. | |

77 | */ | |

78 | ||

79 | typedef struct hash_table { | |

80 | uint32 mask; /* Bit mask of hash bits */ | |

81 | struct hash_base **v; /* Vector of hash bins */ | |

20eb516f | 82 | arena *a; /* Allocation arena */ |

03d53b73 | 83 | } hash_table; |

84 | ||

85 | /* --- A hashtable entry --- * | |

86 | * | |

87 | * This is the bare minimum of what needs to be remembered in each hashtable | |

88 | * entry. Comparison of elements is left to the implementation, so I don't | |

89 | * need to know anything about how to represent hash keys here. | |

90 | */ | |

91 | ||

92 | typedef struct hash_base { | |

93 | struct hash_base *next; /* Next entry in hash bin */ | |

94 | uint32 hash; /* Hash value for this entry */ | |

95 | } hash_base; | |

96 | ||

97 | /* --- A hashtable iterator --- */ | |

98 | ||

99 | typedef struct hash_iter { | |

100 | hash_table *t; /* Hashtable being iterated */ | |

101 | hash_base *p; /* Address of next item to return */ | |

102 | size_t i; /* Index of next hash bin to use */ | |

103 | } hash_iter; | |

104 | ||

105 | /*----- Functions provided ------------------------------------------------*/ | |

106 | ||

107 | /* --- @hash_create@ --- * | |

108 | * | |

109 | * Arguments: @hash_table *t@ = pointer to hashtable to initialize | |

110 | * @size_t n@ = number of bins to allocate (zero initially) | |

111 | * | |

112 | * Returns: --- | |

113 | * | |

114 | * Use: Initializes a hashtable with a given number of bins. The | |

115 | * bins are initially empty. The number of bins must be a power | |

116 | * of two. This is not checked. | |

117 | */ | |

118 | ||

119 | extern void hash_create(hash_table */*t*/, size_t /*n*/); | |

120 | ||

121 | /* --- @hash_destroy@ --- * | |

122 | * | |

123 | * Arguments: @hash_table *t@ = pointer to hashtable to destroy | |

124 | * | |

125 | * Returns: --- | |

126 | * | |

127 | * Use: Frees a hashtable. The items are not freed: they are the | |

128 | * responsibility of the implementation. | |

129 | */ | |

130 | ||

131 | extern void hash_destroy(hash_table */*t*/); | |

132 | ||

133 | /* --- @hash_bin@ --- * | |

134 | * | |

135 | * Arguments: @hash_table *t@ = pointer to hashtable | |

136 | * @uint32 hash@ = hash value to look up | |

137 | * | |

138 | * Returns: Pointer to the bin's list head. | |

139 | * | |

140 | * Use: Given a hash value return the address of the appropriate list | |

141 | * head. It is safe to remove the current entry from the table. | |

142 | */ | |

143 | ||

144 | #define HASH_BIN(t, hash) ((t)->v + ((hash) & (t)->mask)) | |

145 | ||

146 | extern hash_base **hash_bin(hash_table */*t*/, uint32 /*hash*/); | |

147 | ||

148 | /* --- @hash_extend@ --- * | |

149 | * | |

150 | * Arguments: @hash_table *t@ = pointer to hashtable to extend | |

151 | * | |

152 | * Returns: Nonzero if extension was successful. | |

153 | * | |

154 | * Use: Extends a hashtable. The number of bins is doubled and the | |

155 | * entries are redistributed. | |

156 | */ | |

157 | ||

158 | extern int hash_extend(hash_table */*t*/); | |

159 | ||

160 | /* --- @hash_remove@ --- * | |

161 | * | |

162 | * Arguments: @hash_table *t@ = pointer to hashtable | |

163 | * @hash_base *p@ = pointer to item to remove | |

164 | * | |

165 | * Returns: --- | |

166 | * | |

167 | * Use: Removes an item from a hashtable. The item itself is not | |

168 | * freed, although it is removed from the data structure and is | |

169 | * safe to free. | |

170 | */ | |

171 | ||

172 | extern void hash_remove(hash_table */*t*/, hash_base */*p*/); | |

173 | ||

174 | /* --- @hash_mkiter@ --- * | |

175 | * | |

176 | * Arguments: @hash_iter *i@ = pointer to iterator to create | |

177 | * @hash_table *t@ = pointer to hashtable to iterate | |

178 | * | |

179 | * Returns: --- | |

180 | * | |

181 | * Use: Initializes a hashtable iterator. | |

182 | */ | |

183 | ||

184 | #define HASH_MKITER(i_, t_) ((i_)->t = (t_), (i_)->p = 0, (i_)->i = 0) | |

185 | ||

186 | extern void hash_mkiter(hash_iter */*i*/, hash_table */*t*/); | |

187 | ||

188 | /* --- @hash_next@ --- * | |

189 | * | |

190 | * Arguments: @hash_iter *i@ = pointer to iterator | |

191 | * | |

192 | * Returns: Pointer to the next hashtable entry found, or null. | |

193 | * | |

194 | * Use: Returns the next entry from the hashtable. | |

195 | */ | |

196 | ||

197 | #define HASH_NEXT(i_, b_) do { \ | |

198 | hash_iter *_i = (i_); \ | |

199 | hash_base *_p; \ | |

200 | hash_table *_t = _i->t; \ | |

201 | uint32 _m = _t->mask; \ | |

202 | \ | |

203 | for (;;) { \ | |

204 | if (_i->p) { \ | |

205 | _p = _i->p; \ | |

206 | _i->p = _p->next; \ | |

207 | break; \ | |

208 | } else if (_i->i > _m) { \ | |

209 | _p = 0; \ | |

210 | break; \ | |

211 | } else \ | |

212 | _i->p = _t->v[_i->i++]; \ | |

213 | } \ | |

214 | (b_) = _p; \ | |

215 | } while (0) | |

216 | ||

217 | extern hash_base *hash_next(hash_iter */*i*/); | |

218 | ||

219 | /*----- That's all, folks -------------------------------------------------*/ | |

220 | ||

221 | #ifdef __cplusplus | |

222 | } | |

223 | #endif | |

224 | ||

225 | #endif |