Blame

Date:
Message:
portable: portably #include siphash.h Now that siphash is being looked for in a portable way, don't assume <siphash.h> as this is most likely not going to be the case on non-BSD systems.
Actions:
History | Blob | Raw File
  1 54be8251 2018-06-04 stsp /*

  2 619de35f 2022-04-22 thomas  * Copyright (c) 2022 Stefan Sperling <stsp@openbsd.org>

  3 54be8251 2018-06-04 stsp  *

  4 54be8251 2018-06-04 stsp  * Permission to use, copy, modify, and distribute this software for any

  5 54be8251 2018-06-04 stsp  * purpose with or without fee is hereby granted, provided that the above

  6 54be8251 2018-06-04 stsp  * copyright notice and this permission notice appear in all copies.

  7 54be8251 2018-06-04 stsp  *

  8 54be8251 2018-06-04 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES

  9 54be8251 2018-06-04 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF

 10 54be8251 2018-06-04 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR

 11 54be8251 2018-06-04 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES

 12 54be8251 2018-06-04 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN

 13 54be8251 2018-06-04 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF

 14 54be8251 2018-06-04 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

 15 54be8251 2018-06-04 stsp  */

 16 54be8251 2018-06-04 stsp 

 17 54be8251 2018-06-04 stsp #include <stdlib.h>

 18 619de35f 2022-04-22 thomas #include <stdint.h>

 19 54be8251 2018-06-04 stsp #include <string.h>

 20 54be8251 2018-06-04 stsp #include <stdio.h>

 21 54be8251 2018-06-04 stsp #include <zlib.h>

 22 c6f420bf 2018-06-04 stsp #include <limits.h>

 23 788c352e 2018-06-16 stsp #include <time.h>

 24 619de35f 2022-04-22 thomas #include <errno.h>

 25 54be8251 2018-06-04 stsp 

 26 dd038bc6 2021-09-21 thomas.ad #include "got_compat.h"

 27 dd038bc6 2021-09-21 thomas.ad 

 28 54be8251 2018-06-04 stsp #include "got_object.h"

 29 54be8251 2018-06-04 stsp #include "got_error.h"

 30 54be8251 2018-06-04 stsp 

 31 54be8251 2018-06-04 stsp #include "got_lib_delta.h"

 32 63581804 2018-07-09 stsp #include "got_lib_inflate.h"

 33 54be8251 2018-06-04 stsp #include "got_lib_object.h"

 34 54be8251 2018-06-04 stsp #include "got_lib_object_idset.h"

 35 619de35f 2022-04-22 thomas #include "got_lib_object_parse.h"

 36 54be8251 2018-06-04 stsp 

 37 619de35f 2022-04-22 thomas #define GOT_OBJECT_IDSET_MIN_BUCKETS	64

 38 54be8251 2018-06-04 stsp 

 39 54be8251 2018-06-04 stsp struct got_object_idset {

 40 619de35f 2022-04-22 thomas 	struct got_object_id_queue *ids;

 41 619de35f 2022-04-22 thomas 	size_t nbuckets;

 42 619de35f 2022-04-22 thomas 	unsigned int totelem;

 43 619de35f 2022-04-22 thomas 	unsigned int flags;

 44 619de35f 2022-04-22 thomas #define GOT_OBJECT_IDSET_F_TRAVERSAL	0x01

 45 619de35f 2022-04-22 thomas #define GOT_OBJECT_IDSET_F_NOMEM	0x02

 46 619de35f 2022-04-22 thomas 	SIPHASH_KEY key;

 47 54be8251 2018-06-04 stsp };

 48 54be8251 2018-06-04 stsp 

 49 54be8251 2018-06-04 stsp struct got_object_idset *

 50 60f2eee1 2018-07-08 stsp got_object_idset_alloc(void)

 51 54be8251 2018-06-04 stsp {

 52 54be8251 2018-06-04 stsp 	struct got_object_idset *set;

 53 619de35f 2022-04-22 thomas 	int i;

 54 54be8251 2018-06-04 stsp 

 55 984e8a45 2018-11-05 stsp 	set = malloc(sizeof(*set));

 56 54be8251 2018-06-04 stsp 	if (set == NULL)

 57 54be8251 2018-06-04 stsp 		return NULL;

 58 54be8251 2018-06-04 stsp 

 59 619de35f 2022-04-22 thomas 	set->ids = calloc(sizeof(set->ids[0]), GOT_OBJECT_IDSET_MIN_BUCKETS);

 60 619de35f 2022-04-22 thomas 	if (set->ids == NULL) {

 61 619de35f 2022-04-22 thomas 		free(set);

 62 619de35f 2022-04-22 thomas 		return NULL;

 63 619de35f 2022-04-22 thomas 	}

 64 619de35f 2022-04-22 thomas 	for (i = 0; i < GOT_OBJECT_IDSET_MIN_BUCKETS; i++)

 65 619de35f 2022-04-22 thomas 		STAILQ_INIT(&set->ids[i]);

 66 54be8251 2018-06-04 stsp 

 67 619de35f 2022-04-22 thomas 	set->totelem = 0;

 68 619de35f 2022-04-22 thomas 	set->nbuckets = GOT_OBJECT_IDSET_MIN_BUCKETS;

 69 619de35f 2022-04-22 thomas 	set->flags = 0;

 70 619de35f 2022-04-22 thomas 	arc4random_buf(&set->key, sizeof(set->key));

 71 54be8251 2018-06-04 stsp 	return set;

 72 54be8251 2018-06-04 stsp }

 73 54be8251 2018-06-04 stsp 

 74 54be8251 2018-06-04 stsp void

 75 54be8251 2018-06-04 stsp got_object_idset_free(struct got_object_idset *set)

 76 54be8251 2018-06-04 stsp {

 77 619de35f 2022-04-22 thomas 	size_t i;

 78 619de35f 2022-04-22 thomas 	struct got_object_qid *qid;

 79 54be8251 2018-06-04 stsp 

 80 619de35f 2022-04-22 thomas 	for (i = 0; i < set->nbuckets; i++) {

 81 619de35f 2022-04-22 thomas 		while (!STAILQ_EMPTY(&set->ids[i])) {

 82 619de35f 2022-04-22 thomas 			qid = STAILQ_FIRST(&set->ids[i]);

 83 619de35f 2022-04-22 thomas 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);

 84 619de35f 2022-04-22 thomas 			got_object_qid_free(qid);

 85 619de35f 2022-04-22 thomas 		}

 86 54be8251 2018-06-04 stsp 	}

 87 619de35f 2022-04-22 thomas 	/* User data should be freed by caller. */

 88 619de35f 2022-04-22 thomas 	free(set->ids);

 89 54be8251 2018-06-04 stsp 	free(set);

 90 54be8251 2018-06-04 stsp }

 91 54be8251 2018-06-04 stsp 

 92 619de35f 2022-04-22 thomas static uint64_t

 93 619de35f 2022-04-22 thomas idset_hash(struct got_object_idset *set, struct got_object_id *id)

 94 54be8251 2018-06-04 stsp {

 95 619de35f 2022-04-22 thomas 	return SipHash24(&set->key, id->sha1, sizeof(id->sha1));

 96 619de35f 2022-04-22 thomas }

 97 54be8251 2018-06-04 stsp 

 98 619de35f 2022-04-22 thomas static const struct got_error *

 99 619de35f 2022-04-22 thomas idset_resize(struct got_object_idset *set, size_t nbuckets)

100 619de35f 2022-04-22 thomas {

101 619de35f 2022-04-22 thomas 	struct got_object_id_queue *ids;

102 619de35f 2022-04-22 thomas 	size_t i;

103 c6f420bf 2018-06-04 stsp 

104 619de35f 2022-04-22 thomas 	ids = calloc(nbuckets, sizeof(ids[0]));

105 619de35f 2022-04-22 thomas 	if (ids == NULL) {

106 619de35f 2022-04-22 thomas 		if (errno != ENOMEM)

107 619de35f 2022-04-22 thomas 			return got_error_from_errno("calloc");

108 619de35f 2022-04-22 thomas 		/* Proceed with our current amount of hash buckets. */

109 619de35f 2022-04-22 thomas 		set->flags |= GOT_OBJECT_IDSET_F_NOMEM;

110 619de35f 2022-04-22 thomas 		return NULL;

111 619de35f 2022-04-22 thomas 	}

112 54be8251 2018-06-04 stsp 

113 619de35f 2022-04-22 thomas 	for (i = 0; i < nbuckets; i++)

114 619de35f 2022-04-22 thomas 		STAILQ_INIT(&ids[i]);

115 54be8251 2018-06-04 stsp 

116 619de35f 2022-04-22 thomas 	arc4random_buf(&set->key, sizeof(set->key));

117 619de35f 2022-04-22 thomas 

118 619de35f 2022-04-22 thomas 	for (i = 0; i < set->nbuckets; i++) {

119 619de35f 2022-04-22 thomas 		while (!STAILQ_EMPTY(&set->ids[i])) {

120 619de35f 2022-04-22 thomas 			struct got_object_qid *qid;

121 619de35f 2022-04-22 thomas 			uint64_t idx;

122 619de35f 2022-04-22 thomas 			qid = STAILQ_FIRST(&set->ids[i]);

123 619de35f 2022-04-22 thomas 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);

124 ec242592 2022-04-22 thomas 			idx = idset_hash(set, &qid->id) % nbuckets;

125 619de35f 2022-04-22 thomas 			STAILQ_INSERT_HEAD(&ids[idx], qid, entry);

126 619de35f 2022-04-22 thomas 		}

127 9fad5d8c 2022-04-16 thomas 	}

128 9fad5d8c 2022-04-16 thomas 

129 619de35f 2022-04-22 thomas 	free(set->ids);

130 619de35f 2022-04-22 thomas 	set->ids = ids;

131 619de35f 2022-04-22 thomas 	set->nbuckets = nbuckets;

132 b36429ab 2018-11-05 stsp 	return NULL;

133 54be8251 2018-06-04 stsp }

134 54be8251 2018-06-04 stsp 

135 619de35f 2022-04-22 thomas static const struct got_error *

136 619de35f 2022-04-22 thomas idset_grow(struct got_object_idset *set)

137 54be8251 2018-06-04 stsp {

138 619de35f 2022-04-22 thomas 	size_t nbuckets;

139 54be8251 2018-06-04 stsp 

140 619de35f 2022-04-22 thomas 	if (set->flags & GOT_OBJECT_IDSET_F_NOMEM)

141 619de35f 2022-04-22 thomas 		return NULL;

142 619de35f 2022-04-22 thomas 

143 619de35f 2022-04-22 thomas 	if (set->nbuckets >= UINT_MAX / 2)

144 619de35f 2022-04-22 thomas 		nbuckets = UINT_MAX;

145 619de35f 2022-04-22 thomas 	else

146 619de35f 2022-04-22 thomas 		nbuckets = set->nbuckets * 2;

147 619de35f 2022-04-22 thomas 

148 619de35f 2022-04-22 thomas 	return idset_resize(set, nbuckets);

149 619de35f 2022-04-22 thomas }

150 619de35f 2022-04-22 thomas 

151 619de35f 2022-04-22 thomas const struct got_error *

152 619de35f 2022-04-22 thomas got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,

153 619de35f 2022-04-22 thomas     void *data)

154 619de35f 2022-04-22 thomas {

155 619de35f 2022-04-22 thomas 	const struct got_error *err;

156 619de35f 2022-04-22 thomas 	struct got_object_qid *qid;

157 619de35f 2022-04-22 thomas 	uint64_t idx;

158 619de35f 2022-04-22 thomas 	struct got_object_id_queue *head;

159 619de35f 2022-04-22 thomas 

160 619de35f 2022-04-22 thomas 	/* This function may resize the set. */

161 619de35f 2022-04-22 thomas 	if (set->flags & GOT_OBJECT_IDSET_F_TRAVERSAL)

162 619de35f 2022-04-22 thomas 		return got_error_msg(GOT_ERR_NOT_IMPL,

163 619de35f 2022-04-22 thomas 		    "cannot add elements to idset during traversal");

164 619de35f 2022-04-22 thomas 

165 619de35f 2022-04-22 thomas 	if (set->totelem == UINT_MAX)

166 619de35f 2022-04-22 thomas 		return got_error(GOT_ERR_NO_SPACE);

167 619de35f 2022-04-22 thomas 		

168 619de35f 2022-04-22 thomas 	err = got_object_qid_alloc_partial(&qid);

169 619de35f 2022-04-22 thomas 	if (err)

170 619de35f 2022-04-22 thomas 		return err;

171 ec242592 2022-04-22 thomas 	memcpy(&qid->id, id, sizeof(qid->id));

172 619de35f 2022-04-22 thomas 	qid->data = data;

173 619de35f 2022-04-22 thomas 

174 619de35f 2022-04-22 thomas 	idx = idset_hash(set, id) % set->nbuckets;

175 619de35f 2022-04-22 thomas 	head = &set->ids[idx];

176 619de35f 2022-04-22 thomas 	STAILQ_INSERT_HEAD(head, qid, entry);

177 619de35f 2022-04-22 thomas 	set->totelem++;

178 619de35f 2022-04-22 thomas 

179 619de35f 2022-04-22 thomas 	if (set->nbuckets < set->totelem)

180 619de35f 2022-04-22 thomas 		err = idset_grow(set);

181 619de35f 2022-04-22 thomas 

182 619de35f 2022-04-22 thomas 	return err;

183 619de35f 2022-04-22 thomas }

184 619de35f 2022-04-22 thomas 

185 619de35f 2022-04-22 thomas static struct got_object_qid *

186 619de35f 2022-04-22 thomas find_element(struct got_object_idset *set, struct got_object_id *id)

187 619de35f 2022-04-22 thomas {

188 619de35f 2022-04-22 thomas 	uint64_t idx = idset_hash(set, id) % set->nbuckets;

189 619de35f 2022-04-22 thomas 	struct got_object_id_queue *head = &set->ids[idx];

190 619de35f 2022-04-22 thomas 	struct got_object_qid *qid;

191 619de35f 2022-04-22 thomas 

192 619de35f 2022-04-22 thomas 	STAILQ_FOREACH(qid, head, entry) {

193 ec242592 2022-04-22 thomas 		if (got_object_id_cmp(&qid->id, id) == 0)

194 619de35f 2022-04-22 thomas 			return qid;

195 54be8251 2018-06-04 stsp 	}

196 54be8251 2018-06-04 stsp 

197 619de35f 2022-04-22 thomas 	return NULL;

198 54be8251 2018-06-04 stsp }

199 54be8251 2018-06-04 stsp 

200 984e8a45 2018-11-05 stsp void *

201 984e8a45 2018-11-05 stsp got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)

202 984e8a45 2018-11-05 stsp {

203 619de35f 2022-04-22 thomas 	struct got_object_qid *qid = find_element(set, id);

204 619de35f 2022-04-22 thomas 	return qid ? qid->data : NULL;

205 984e8a45 2018-11-05 stsp }

206 984e8a45 2018-11-05 stsp 

207 54be8251 2018-06-04 stsp const struct got_error *

208 e7c810ea 2018-06-22 stsp got_object_idset_remove(void **data, struct got_object_idset *set,

209 54be8251 2018-06-04 stsp     struct got_object_id *id)

210 54be8251 2018-06-04 stsp {

211 619de35f 2022-04-22 thomas 	uint64_t idx;

212 619de35f 2022-04-22 thomas 	struct got_object_id_queue *head;

213 619de35f 2022-04-22 thomas 	struct got_object_qid *qid;

214 54be8251 2018-06-04 stsp 

215 441e144c 2018-06-22 stsp 	if (data)

216 441e144c 2018-06-22 stsp 		*data = NULL;

217 441e144c 2018-06-22 stsp 

218 984e8a45 2018-11-05 stsp 	if (set->totelem == 0)

219 c6f420bf 2018-06-04 stsp 		return got_error(GOT_ERR_NO_OBJ);

220 c6f420bf 2018-06-04 stsp 

221 3a4790b6 2022-03-22 thomas 	if (id == NULL) {

222 619de35f 2022-04-22 thomas 		/* Remove a "random" element. */

223 619de35f 2022-04-22 thomas 		for (idx = 0; idx < set->nbuckets; idx++) {

224 619de35f 2022-04-22 thomas 			head = &set->ids[idx];

225 619de35f 2022-04-22 thomas 			qid = STAILQ_FIRST(head);

226 619de35f 2022-04-22 thomas 			if (qid)

227 619de35f 2022-04-22 thomas 				break;

228 619de35f 2022-04-22 thomas 		}

229 3a4790b6 2022-03-22 thomas 	} else {

230 619de35f 2022-04-22 thomas 		idx = idset_hash(set, id) % set->nbuckets;

231 619de35f 2022-04-22 thomas 		head = &set->ids[idx];

232 619de35f 2022-04-22 thomas 		STAILQ_FOREACH(qid, head, entry) {

233 ec242592 2022-04-22 thomas 			if (got_object_id_cmp(&qid->id, id) == 0)

234 619de35f 2022-04-22 thomas 				break;

235 619de35f 2022-04-22 thomas 		}

236 619de35f 2022-04-22 thomas 		if (qid == NULL)

237 3a4790b6 2022-03-22 thomas 			return got_error_no_obj(id);

238 3a4790b6 2022-03-22 thomas 	}

239 54be8251 2018-06-04 stsp 

240 984e8a45 2018-11-05 stsp 	if (data)

241 619de35f 2022-04-22 thomas 		*data = qid->data;

242 619de35f 2022-04-22 thomas 	STAILQ_REMOVE(head, qid, got_object_qid, entry);

243 619de35f 2022-04-22 thomas 	got_object_qid_free(qid);

244 984e8a45 2018-11-05 stsp 	set->totelem--;

245 619de35f 2022-04-22 thomas 

246 984e8a45 2018-11-05 stsp 	return NULL;

247 54be8251 2018-06-04 stsp }

248 54be8251 2018-06-04 stsp 

249 54be8251 2018-06-04 stsp int

250 54be8251 2018-06-04 stsp got_object_idset_contains(struct got_object_idset *set,

251 54be8251 2018-06-04 stsp     struct got_object_id *id)

252 54be8251 2018-06-04 stsp {

253 619de35f 2022-04-22 thomas 	struct got_object_qid *qid = find_element(set, id);

254 619de35f 2022-04-22 thomas 	return qid ? 1 : 0;

255 54be8251 2018-06-04 stsp }

256 54be8251 2018-06-04 stsp 

257 cb103d04 2018-11-07 stsp const struct got_error *

258 cb103d04 2018-11-07 stsp got_object_idset_for_each(struct got_object_idset *set,

259 cb103d04 2018-11-07 stsp     const struct got_error *(*cb)(struct got_object_id *, void *, void *),

260 cb103d04 2018-11-07 stsp     void *arg)

261 54be8251 2018-06-04 stsp {

262 619de35f 2022-04-22 thomas 	const struct got_error *err = NULL;

263 619de35f 2022-04-22 thomas 	struct got_object_id_queue *head;

264 619de35f 2022-04-22 thomas 	struct got_object_qid *qid, *tmp;

265 619de35f 2022-04-22 thomas 	size_t i;

266 54be8251 2018-06-04 stsp 

267 619de35f 2022-04-22 thomas 	set->flags |= GOT_OBJECT_IDSET_F_TRAVERSAL;

268 619de35f 2022-04-22 thomas 	for (i = 0; i < set->nbuckets; i++) {

269 619de35f 2022-04-22 thomas 		head = &set->ids[i];

270 619de35f 2022-04-22 thomas 		STAILQ_FOREACH_SAFE(qid, head, entry, tmp) {

271 ec242592 2022-04-22 thomas 			err = (*cb)(&qid->id, qid->data, arg);

272 619de35f 2022-04-22 thomas 			if (err)

273 619de35f 2022-04-22 thomas 				goto done;

274 619de35f 2022-04-22 thomas 		}

275 cb103d04 2018-11-07 stsp 	}

276 619de35f 2022-04-22 thomas done:

277 619de35f 2022-04-22 thomas 	set->flags &= ~GOT_OBJECT_IDSET_F_TRAVERSAL;

278 619de35f 2022-04-22 thomas 	return err;

279 54be8251 2018-06-04 stsp }

280 c6f420bf 2018-06-04 stsp 

281 069f84d5 2018-06-11 stsp int

282 c6f420bf 2018-06-04 stsp got_object_idset_num_elements(struct got_object_idset *set)

283 c6f420bf 2018-06-04 stsp {

284 2bd394ff 2018-06-22 stsp 	return set->totelem;

285 c6f420bf 2018-06-04 stsp }