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

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

2 | * | |

c6e0eaf0 | 3 | * $Id: hash.h,v 1.2 1999/12/10 23:42:04 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 $ | |

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

34 | * Change header file guard names. | |

35 | * | |

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

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

38 | * | |

39 | */ | |

40 | ||

c6e0eaf0 | 41 | #ifndef MLIB_HASH_H |

42 | #define MLIB_HASH_H | |

03d53b73 | 43 | |

44 | #ifdef __cplusplus | |

45 | extern "C" { | |

46 | #endif | |

47 | ||

48 | /*----- Notes -------------------------------------------------------------* | |

49 | * | |

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

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

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

53 | */ | |

54 | ||

55 | /*----- Header files ------------------------------------------------------*/ | |

56 | ||

57 | #include <stddef.h> | |

58 | ||

c6e0eaf0 | 59 | #ifndef MLIB_BITS_H |

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

61 | #endif | |

62 | ||

63 | /*----- Data structures ---------------------------------------------------*/ | |

64 | ||

65 | /* --- Hashtable basics --- * | |

66 | * | |

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

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

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

70 | */ | |

71 | ||

72 | typedef struct hash_table { | |

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

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

75 | } hash_table; | |

76 | ||

77 | /* --- A hashtable entry --- * | |

78 | * | |

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

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

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

82 | */ | |

83 | ||

84 | typedef struct hash_base { | |

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

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

87 | } hash_base; | |

88 | ||

89 | /* --- A hashtable iterator --- */ | |

90 | ||

91 | typedef struct hash_iter { | |

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

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

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

95 | } hash_iter; | |

96 | ||

97 | /*----- Functions provided ------------------------------------------------*/ | |

98 | ||

99 | /* --- @hash_create@ --- * | |

100 | * | |

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

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

103 | * | |

104 | * Returns: --- | |

105 | * | |

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

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

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

109 | */ | |

110 | ||

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

112 | ||

113 | /* --- @hash_destroy@ --- * | |

114 | * | |

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

116 | * | |

117 | * Returns: --- | |

118 | * | |

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

120 | * responsibility of the implementation. | |

121 | */ | |

122 | ||

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

124 | ||

125 | /* --- @hash_bin@ --- * | |

126 | * | |

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

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

129 | * | |

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

131 | * | |

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

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

134 | */ | |

135 | ||

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

137 | ||

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

139 | ||

140 | /* --- @hash_extend@ --- * | |

141 | * | |

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

143 | * | |

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

145 | * | |

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

147 | * entries are redistributed. | |

148 | */ | |

149 | ||

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

151 | ||

152 | /* --- @hash_remove@ --- * | |

153 | * | |

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

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

156 | * | |

157 | * Returns: --- | |

158 | * | |

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

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

161 | * safe to free. | |

162 | */ | |

163 | ||

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

165 | ||

166 | /* --- @hash_mkiter@ --- * | |

167 | * | |

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

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

170 | * | |

171 | * Returns: --- | |

172 | * | |

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

174 | */ | |

175 | ||

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

177 | ||

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

179 | ||

180 | /* --- @hash_next@ --- * | |

181 | * | |

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

183 | * | |

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

185 | * | |

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

187 | */ | |

188 | ||

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

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

191 | hash_base *_p; \ | |

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

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

194 | \ | |

195 | for (;;) { \ | |

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

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

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

199 | break; \ | |

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

201 | _p = 0; \ | |

202 | break; \ | |

203 | } else \ | |

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

205 | } \ | |

206 | (b_) = _p; \ | |

207 | } while (0) | |

208 | ||

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

210 | ||

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

212 | ||

213 | #ifdef __cplusplus | |

214 | } | |

215 | #endif | |

216 | ||

217 | #endif |