Blame

Date:
Message:
remove dependency of gitwrapper, gotctl, and gotsh on object_parse.c Move some functions from object_parse.c into hash.c. These functions either require hash.c code anyway or contain object ID implementation internals. Add a new file object_qid.c, for got_object_id_queue and got_object_qid. This new file must be linked to virtually every program.
Actions:
History | Blob | Raw File
  1 54be8251 2018-06-04 stsp /*

  2 cbc287dc 2022-04-19 stsp  * 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 <sys/queue.h>

 18 54be8251 2018-06-04 stsp 

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

 20 cbc287dc 2022-04-19 stsp #include <stdint.h>

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

 22 54be8251 2018-06-04 stsp #include <sha1.h>

 23 5822e79e 2023-02-23 op #include <sha2.h>

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

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

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

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

 28 cbc287dc 2022-04-19 stsp #include <errno.h>

 29 cbc287dc 2022-04-19 stsp #include <siphash.h>

 30 54be8251 2018-06-04 stsp 

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

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

 33 54be8251 2018-06-04 stsp 

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

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

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

 37 2f43cd69 2023-04-14 stsp #include "got_lib_object_qid.h"

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

 39 cbc287dc 2022-04-19 stsp #include "got_lib_object_parse.h"

 40 54be8251 2018-06-04 stsp 

 41 cbc287dc 2022-04-19 stsp #define GOT_OBJECT_IDSET_MIN_BUCKETS	64

 42 54be8251 2018-06-04 stsp 

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

 44 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *ids;

 45 cbc287dc 2022-04-19 stsp 	size_t nbuckets;

 46 cbc287dc 2022-04-19 stsp 	unsigned int totelem;

 47 cbc287dc 2022-04-19 stsp 	unsigned int flags;

 48 cbc287dc 2022-04-19 stsp #define GOT_OBJECT_IDSET_F_TRAVERSAL	0x01

 49 cbc287dc 2022-04-19 stsp #define GOT_OBJECT_IDSET_F_NOMEM	0x02

 50 cbc287dc 2022-04-19 stsp 	SIPHASH_KEY key;

 51 54be8251 2018-06-04 stsp };

 52 54be8251 2018-06-04 stsp 

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

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

 55 54be8251 2018-06-04 stsp {

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

 57 cbc287dc 2022-04-19 stsp 	int i;

 58 54be8251 2018-06-04 stsp 

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

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

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

 62 54be8251 2018-06-04 stsp 

 63 cbc287dc 2022-04-19 stsp 	set->ids = calloc(sizeof(set->ids[0]), GOT_OBJECT_IDSET_MIN_BUCKETS);

 64 cbc287dc 2022-04-19 stsp 	if (set->ids == NULL) {

 65 cbc287dc 2022-04-19 stsp 		free(set);

 66 cbc287dc 2022-04-19 stsp 		return NULL;

 67 cbc287dc 2022-04-19 stsp 	}

 68 cbc287dc 2022-04-19 stsp 	for (i = 0; i < GOT_OBJECT_IDSET_MIN_BUCKETS; i++)

 69 cbc287dc 2022-04-19 stsp 		STAILQ_INIT(&set->ids[i]);

 70 54be8251 2018-06-04 stsp 

 71 cbc287dc 2022-04-19 stsp 	set->totelem = 0;

 72 cbc287dc 2022-04-19 stsp 	set->nbuckets = GOT_OBJECT_IDSET_MIN_BUCKETS;

 73 cbc287dc 2022-04-19 stsp 	set->flags = 0;

 74 cbc287dc 2022-04-19 stsp 	arc4random_buf(&set->key, sizeof(set->key));

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

 76 54be8251 2018-06-04 stsp }

 77 54be8251 2018-06-04 stsp 

 78 54be8251 2018-06-04 stsp void

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

 80 54be8251 2018-06-04 stsp {

 81 cbc287dc 2022-04-19 stsp 	size_t i;

 82 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid;

 83 54be8251 2018-06-04 stsp 

 84 cbc287dc 2022-04-19 stsp 	for (i = 0; i < set->nbuckets; i++) {

 85 cbc287dc 2022-04-19 stsp 		while (!STAILQ_EMPTY(&set->ids[i])) {

 86 cbc287dc 2022-04-19 stsp 			qid = STAILQ_FIRST(&set->ids[i]);

 87 cbc287dc 2022-04-19 stsp 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);

 88 cbc287dc 2022-04-19 stsp 			got_object_qid_free(qid);

 89 cbc287dc 2022-04-19 stsp 		}

 90 54be8251 2018-06-04 stsp 	}

 91 cbc287dc 2022-04-19 stsp 	/* User data should be freed by caller. */

 92 cbc287dc 2022-04-19 stsp 	free(set->ids);

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

 94 54be8251 2018-06-04 stsp }

 95 54be8251 2018-06-04 stsp 

 96 cbc287dc 2022-04-19 stsp static uint64_t

 97 cbc287dc 2022-04-19 stsp idset_hash(struct got_object_idset *set, struct got_object_id *id)

 98 54be8251 2018-06-04 stsp {

 99 cbc287dc 2022-04-19 stsp 	return SipHash24(&set->key, id->sha1, sizeof(id->sha1));

100 cbc287dc 2022-04-19 stsp }

101 54be8251 2018-06-04 stsp 

102 cbc287dc 2022-04-19 stsp static const struct got_error *

103 cbc287dc 2022-04-19 stsp idset_resize(struct got_object_idset *set, size_t nbuckets)

104 cbc287dc 2022-04-19 stsp {

105 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *ids;

106 cbc287dc 2022-04-19 stsp 	size_t i;

107 c6f420bf 2018-06-04 stsp 

108 cbc287dc 2022-04-19 stsp 	ids = calloc(nbuckets, sizeof(ids[0]));

109 cbc287dc 2022-04-19 stsp 	if (ids == NULL) {

110 cbc287dc 2022-04-19 stsp 		if (errno != ENOMEM)

111 cbc287dc 2022-04-19 stsp 			return got_error_from_errno("calloc");

112 cbc287dc 2022-04-19 stsp 		/* Proceed with our current amount of hash buckets. */

113 cbc287dc 2022-04-19 stsp 		set->flags |= GOT_OBJECT_IDSET_F_NOMEM;

114 cbc287dc 2022-04-19 stsp 		return NULL;

115 cbc287dc 2022-04-19 stsp 	}

116 54be8251 2018-06-04 stsp 

117 cbc287dc 2022-04-19 stsp 	for (i = 0; i < nbuckets; i++)

118 cbc287dc 2022-04-19 stsp 		STAILQ_INIT(&ids[i]);

119 54be8251 2018-06-04 stsp 

120 cbc287dc 2022-04-19 stsp 	arc4random_buf(&set->key, sizeof(set->key));

121 cbc287dc 2022-04-19 stsp 

122 cbc287dc 2022-04-19 stsp 	for (i = 0; i < set->nbuckets; i++) {

123 cbc287dc 2022-04-19 stsp 		while (!STAILQ_EMPTY(&set->ids[i])) {

124 cbc287dc 2022-04-19 stsp 			struct got_object_qid *qid;

125 cbc287dc 2022-04-19 stsp 			uint64_t idx;

126 cbc287dc 2022-04-19 stsp 			qid = STAILQ_FIRST(&set->ids[i]);

127 cbc287dc 2022-04-19 stsp 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);

128 d7b5a0e8 2022-04-20 stsp 			idx = idset_hash(set, &qid->id) % nbuckets;

129 cbc287dc 2022-04-19 stsp 			STAILQ_INSERT_HEAD(&ids[idx], qid, entry);

130 cbc287dc 2022-04-19 stsp 		}

131 a7472cb3 2022-04-14 stsp 	}

132 a7472cb3 2022-04-14 stsp 

133 cbc287dc 2022-04-19 stsp 	free(set->ids);

134 cbc287dc 2022-04-19 stsp 	set->ids = ids;

135 cbc287dc 2022-04-19 stsp 	set->nbuckets = nbuckets;

136 b36429ab 2018-11-05 stsp 	return NULL;

137 54be8251 2018-06-04 stsp }

138 54be8251 2018-06-04 stsp 

139 cbc287dc 2022-04-19 stsp static const struct got_error *

140 cbc287dc 2022-04-19 stsp idset_grow(struct got_object_idset *set)

141 54be8251 2018-06-04 stsp {

142 cbc287dc 2022-04-19 stsp 	size_t nbuckets;

143 54be8251 2018-06-04 stsp 

144 cbc287dc 2022-04-19 stsp 	if (set->flags & GOT_OBJECT_IDSET_F_NOMEM)

145 cbc287dc 2022-04-19 stsp 		return NULL;

146 cbc287dc 2022-04-19 stsp 

147 cbc287dc 2022-04-19 stsp 	if (set->nbuckets >= UINT_MAX / 2)

148 cbc287dc 2022-04-19 stsp 		nbuckets = UINT_MAX;

149 cbc287dc 2022-04-19 stsp 	else

150 cbc287dc 2022-04-19 stsp 		nbuckets = set->nbuckets * 2;

151 cbc287dc 2022-04-19 stsp 

152 cbc287dc 2022-04-19 stsp 	return idset_resize(set, nbuckets);

153 cbc287dc 2022-04-19 stsp }

154 cbc287dc 2022-04-19 stsp 

155 cbc287dc 2022-04-19 stsp const struct got_error *

156 cbc287dc 2022-04-19 stsp got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,

157 cbc287dc 2022-04-19 stsp     void *data)

158 cbc287dc 2022-04-19 stsp {

159 cbc287dc 2022-04-19 stsp 	const struct got_error *err;

160 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid;

161 cbc287dc 2022-04-19 stsp 	uint64_t idx;

162 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *head;

163 cbc287dc 2022-04-19 stsp 

164 cbc287dc 2022-04-19 stsp 	/* This function may resize the set. */

165 cbc287dc 2022-04-19 stsp 	if (set->flags & GOT_OBJECT_IDSET_F_TRAVERSAL)

166 cbc287dc 2022-04-19 stsp 		return got_error_msg(GOT_ERR_NOT_IMPL,

167 cbc287dc 2022-04-19 stsp 		    "cannot add elements to idset during traversal");

168 cbc287dc 2022-04-19 stsp 

169 cbc287dc 2022-04-19 stsp 	if (set->totelem == UINT_MAX)

170 cbc287dc 2022-04-19 stsp 		return got_error(GOT_ERR_NO_SPACE);

171 5e91dae4 2022-08-30 stsp 

172 cbc287dc 2022-04-19 stsp 	err = got_object_qid_alloc_partial(&qid);

173 cbc287dc 2022-04-19 stsp 	if (err)

174 cbc287dc 2022-04-19 stsp 		return err;

175 d7b5a0e8 2022-04-20 stsp 	memcpy(&qid->id, id, sizeof(qid->id));

176 cbc287dc 2022-04-19 stsp 	qid->data = data;

177 cbc287dc 2022-04-19 stsp 

178 cbc287dc 2022-04-19 stsp 	idx = idset_hash(set, id) % set->nbuckets;

179 cbc287dc 2022-04-19 stsp 	head = &set->ids[idx];

180 cbc287dc 2022-04-19 stsp 	STAILQ_INSERT_HEAD(head, qid, entry);

181 cbc287dc 2022-04-19 stsp 	set->totelem++;

182 cbc287dc 2022-04-19 stsp 

183 cbc287dc 2022-04-19 stsp 	if (set->nbuckets < set->totelem)

184 cbc287dc 2022-04-19 stsp 		err = idset_grow(set);

185 cbc287dc 2022-04-19 stsp 

186 cbc287dc 2022-04-19 stsp 	return err;

187 cbc287dc 2022-04-19 stsp }

188 cbc287dc 2022-04-19 stsp 

189 cbc287dc 2022-04-19 stsp static struct got_object_qid *

190 cbc287dc 2022-04-19 stsp find_element(struct got_object_idset *set, struct got_object_id *id)

191 cbc287dc 2022-04-19 stsp {

192 cbc287dc 2022-04-19 stsp 	uint64_t idx = idset_hash(set, id) % set->nbuckets;

193 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *head = &set->ids[idx];

194 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid;

195 cbc287dc 2022-04-19 stsp 

196 cbc287dc 2022-04-19 stsp 	STAILQ_FOREACH(qid, head, entry) {

197 d7b5a0e8 2022-04-20 stsp 		if (got_object_id_cmp(&qid->id, id) == 0)

198 cbc287dc 2022-04-19 stsp 			return qid;

199 54be8251 2018-06-04 stsp 	}

200 54be8251 2018-06-04 stsp 

201 cbc287dc 2022-04-19 stsp 	return NULL;

202 54be8251 2018-06-04 stsp }

203 54be8251 2018-06-04 stsp 

204 984e8a45 2018-11-05 stsp void *

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

206 984e8a45 2018-11-05 stsp {

207 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid = find_element(set, id);

208 cbc287dc 2022-04-19 stsp 	return qid ? qid->data : NULL;

209 984e8a45 2018-11-05 stsp }

210 984e8a45 2018-11-05 stsp 

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

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

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

214 54be8251 2018-06-04 stsp {

215 cbc287dc 2022-04-19 stsp 	uint64_t idx;

216 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *head;

217 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid;

218 54be8251 2018-06-04 stsp 

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

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

221 441e144c 2018-06-22 stsp 

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

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

224 c6f420bf 2018-06-04 stsp 

225 0ae61b79 2022-03-21 stsp 	if (id == NULL) {

226 cbc287dc 2022-04-19 stsp 		/* Remove a "random" element. */

227 cbc287dc 2022-04-19 stsp 		for (idx = 0; idx < set->nbuckets; idx++) {

228 cbc287dc 2022-04-19 stsp 			head = &set->ids[idx];

229 cbc287dc 2022-04-19 stsp 			qid = STAILQ_FIRST(head);

230 cbc287dc 2022-04-19 stsp 			if (qid)

231 cbc287dc 2022-04-19 stsp 				break;

232 cbc287dc 2022-04-19 stsp 		}

233 0ae61b79 2022-03-21 stsp 	} else {

234 cbc287dc 2022-04-19 stsp 		idx = idset_hash(set, id) % set->nbuckets;

235 cbc287dc 2022-04-19 stsp 		head = &set->ids[idx];

236 cbc287dc 2022-04-19 stsp 		STAILQ_FOREACH(qid, head, entry) {

237 d7b5a0e8 2022-04-20 stsp 			if (got_object_id_cmp(&qid->id, id) == 0)

238 cbc287dc 2022-04-19 stsp 				break;

239 cbc287dc 2022-04-19 stsp 		}

240 cbc287dc 2022-04-19 stsp 		if (qid == NULL)

241 0ae61b79 2022-03-21 stsp 			return got_error_no_obj(id);

242 0ae61b79 2022-03-21 stsp 	}

243 54be8251 2018-06-04 stsp 

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

245 cbc287dc 2022-04-19 stsp 		*data = qid->data;

246 cbc287dc 2022-04-19 stsp 	STAILQ_REMOVE(head, qid, got_object_qid, entry);

247 cbc287dc 2022-04-19 stsp 	got_object_qid_free(qid);

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

249 cbc287dc 2022-04-19 stsp 

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

251 54be8251 2018-06-04 stsp }

252 54be8251 2018-06-04 stsp 

253 54be8251 2018-06-04 stsp int

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

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

256 54be8251 2018-06-04 stsp {

257 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid = find_element(set, id);

258 cbc287dc 2022-04-19 stsp 	return qid ? 1 : 0;

259 54be8251 2018-06-04 stsp }

260 54be8251 2018-06-04 stsp 

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

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

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

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

265 54be8251 2018-06-04 stsp {

266 cbc287dc 2022-04-19 stsp 	const struct got_error *err = NULL;

267 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *head;

268 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid, *tmp;

269 cbc287dc 2022-04-19 stsp 	size_t i;

270 54be8251 2018-06-04 stsp 

271 cbc287dc 2022-04-19 stsp 	set->flags |= GOT_OBJECT_IDSET_F_TRAVERSAL;

272 cbc287dc 2022-04-19 stsp 	for (i = 0; i < set->nbuckets; i++) {

273 cbc287dc 2022-04-19 stsp 		head = &set->ids[i];

274 cbc287dc 2022-04-19 stsp 		STAILQ_FOREACH_SAFE(qid, head, entry, tmp) {

275 d7b5a0e8 2022-04-20 stsp 			err = (*cb)(&qid->id, qid->data, arg);

276 cbc287dc 2022-04-19 stsp 			if (err)

277 cbc287dc 2022-04-19 stsp 				goto done;

278 cbc287dc 2022-04-19 stsp 		}

279 cb103d04 2018-11-07 stsp 	}

280 cbc287dc 2022-04-19 stsp done:

281 cbc287dc 2022-04-19 stsp 	set->flags &= ~GOT_OBJECT_IDSET_F_TRAVERSAL;

282 cbc287dc 2022-04-19 stsp 	return err;

283 54be8251 2018-06-04 stsp }

284 c6f420bf 2018-06-04 stsp 

285 069f84d5 2018-06-11 stsp int

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

287 c6f420bf 2018-06-04 stsp {

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

289 c6f420bf 2018-06-04 stsp }