sortedcache.c 8.43 KB
Newer Older
1 2
#include "sortedcache.h"

3
GIT__USE_STRMAP
4 5 6 7 8 9 10 11 12 13

int git_sortedcache_new(
	git_sortedcache **out,
	size_t item_path_offset,
	git_sortedcache_free_item_fn free_item,
	void *free_item_payload,
	git_vector_cmp item_cmp,
	const char *path)
{
	git_sortedcache *sc;
14
	size_t pathlen, alloclen;
15 16 17

	pathlen = path ? strlen(path) : 0;

18 19 20
	GITERR_CHECK_ALLOC_ADD(&alloclen, sizeof(git_sortedcache), pathlen);
	GITERR_CHECK_ALLOC_ADD(&alloclen, alloclen, 1);
	sc = git__calloc(1, alloclen);
21 22 23 24
	GITERR_CHECK_ALLOC(sc);

	if (git_pool_init(&sc->pool, 1, 0) < 0 ||
		git_vector_init(&sc->items, 4, item_cmp) < 0 ||
25
		git_strmap_alloc(&sc->map) < 0)
26 27
		goto fail;

28 29
	if (git_rwlock_init(&sc->lock)) {
		giterr_set(GITERR_OS, "Failed to initialize lock");
30 31 32
		goto fail;
	}

33 34
	sc->item_path_offset  = item_path_offset;
	sc->free_item         = free_item;
35 36 37 38 39 40 41 42 43
	sc->free_item_payload = free_item_payload;
	GIT_REFCOUNT_INC(sc);
	if (pathlen)
		memcpy(sc->path, path, pathlen);

	*out = sc;
	return 0;

fail:
44
	git_strmap_free(sc->map);
45 46 47 48 49 50 51 52 53 54 55
	git_vector_free(&sc->items);
	git_pool_clear(&sc->pool);
	git__free(sc);
	return -1;
}

void git_sortedcache_incref(git_sortedcache *sc)
{
	GIT_REFCOUNT_INC(sc);
}

56 57 58 59 60
const char *git_sortedcache_path(git_sortedcache *sc)
{
	return sc->path;
}

61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
static void sortedcache_clear(git_sortedcache *sc)
{
	git_strmap_clear(sc->map);

	if (sc->free_item) {
		size_t i;
		void *item;

		git_vector_foreach(&sc->items, i, item) {
			sc->free_item(sc->free_item_payload, item);
		}
	}

	git_vector_clear(&sc->items);

	git_pool_clear(&sc->pool);
}

static void sortedcache_free(git_sortedcache *sc)
{
81 82
	/* acquire write lock to make sure everyone else is done */
	if (git_sortedcache_wlock(sc) < 0)
83 84 85 86 87 88
		return;

	sortedcache_clear(sc);
	git_vector_free(&sc->items);
	git_strmap_free(sc->map);

89
	git_sortedcache_wunlock(sc);
90

91
	git_rwlock_free(&sc->lock);
92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
	git__free(sc);
}

void git_sortedcache_free(git_sortedcache *sc)
{
	if (!sc)
		return;
	GIT_REFCOUNT_DEC(sc, sortedcache_free);
}

static int sortedcache_copy_item(void *payload, void *tgt_item, void *src_item)
{
	git_sortedcache *sc = payload;
	/* path will already have been copied by upsert */
	memcpy(tgt_item, src_item, sc->item_path_offset);
	return 0;
}

/* copy a sorted cache */
int git_sortedcache_copy(
	git_sortedcache **out,
	git_sortedcache *src,
114
	bool lock,
115 116 117
	int (*copy_item)(void *payload, void *tgt_item, void *src_item),
	void *payload)
{
118
	int error = 0;
119 120 121 122
	git_sortedcache *tgt;
	size_t i;
	void *src_item, *tgt_item;

123
	/* just use memcpy if no special copy fn is passed in */
124 125 126 127 128
	if (!copy_item) {
		copy_item = sortedcache_copy_item;
		payload   = src;
	}

129
	if ((error = git_sortedcache_new(
130 131
			&tgt, src->item_path_offset,
			src->free_item, src->free_item_payload,
132 133
			src->items._cmp, src->path)) < 0)
		return error;
134

135
	if (lock && git_sortedcache_rlock(src) < 0) {
136 137 138 139 140
		git_sortedcache_free(tgt);
		return -1;
	}

	git_vector_foreach(&src->items, i, src_item) {
141 142 143 144 145
		char *path = ((char *)src_item) + src->item_path_offset;

		if ((error = git_sortedcache_upsert(&tgt_item, tgt, path)) < 0 ||
			(error = copy_item(payload, tgt_item, src_item)) < 0)
			break;
146 147
	}

148 149
	if (lock)
		git_sortedcache_runlock(src);
150 151
	if (error)
		git_sortedcache_free(tgt);
152

153
	*out = !error ? tgt : NULL;
154

155
	return error;
156 157
}

158 159
/* lock sortedcache while making modifications */
int git_sortedcache_wlock(git_sortedcache *sc)
160
{
161
	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
162

163 164 165 166 167
	if (git_rwlock_wrlock(&sc->lock) < 0) {
		giterr_set(GITERR_OS, "Unable to acquire write lock on cache");
		return -1;
	}
	return 0;
168 169
}

170 171
/* unlock sorted cache when done with modifications */
void git_sortedcache_wunlock(git_sortedcache *sc)
172
{
173 174
	git_vector_sort(&sc->items);
	git_rwlock_wrunlock(&sc->lock);
175 176
}

177 178
/* lock sortedcache for read */
int git_sortedcache_rlock(git_sortedcache *sc)
179
{
180
	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
181

182 183
	if (git_rwlock_rdlock(&sc->lock) < 0) {
		giterr_set(GITERR_OS, "Unable to acquire read lock on cache");
184 185 186 187 188
		return -1;
	}
	return 0;
}

189 190
/* unlock sorted cache when done reading */
void git_sortedcache_runlock(git_sortedcache *sc)
191
{
192 193
	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
	git_rwlock_rdunlock(&sc->lock);
194 195 196 197 198 199 200 201 202
}

/* if the file has changed, lock cache and load file contents into buf;
 * returns <0 on error, >0 if file has not changed
 */
int git_sortedcache_lockandload(git_sortedcache *sc, git_buf *buf)
{
	int error, fd;

203
	if ((error = git_sortedcache_wlock(sc)) < 0)
204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230
		return error;

	if ((error = git_futils_filestamp_check(&sc->stamp, sc->path)) <= 0)
		goto unlock;

	if (!git__is_sizet(sc->stamp.size)) {
		giterr_set(GITERR_INVALID, "Unable to load file larger than size_t");
		error = -1;
		goto unlock;
	}

	if ((fd = git_futils_open_ro(sc->path)) < 0) {
		error = fd;
		goto unlock;
	}

	if (buf)
		error = git_futils_readbuffer_fd(buf, fd, (size_t)sc->stamp.size);

	(void)p_close(fd);

	if (error < 0)
		goto unlock;

	return 1; /* return 1 -> file needs reload and was successfully loaded */

unlock:
231
	git_sortedcache_wunlock(sc);
232 233 234
	return error;
}

235 236
void git_sortedcache_updated(git_sortedcache *sc)
{
237 238
	/* update filestamp to latest value */
	git_futils_filestamp_check(&sc->stamp, sc->path);
239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254
}

/* release all items in sorted cache */
int git_sortedcache_clear(git_sortedcache *sc, bool wlock)
{
	if (wlock && git_sortedcache_wlock(sc) < 0)
		return -1;

	sortedcache_clear(sc);

	if (wlock)
		git_sortedcache_wunlock(sc);

	return 0;
}

255
/* find and/or insert item, returning pointer to item data */
256
int git_sortedcache_upsert(void **out, git_sortedcache *sc, const char *key)
257 258 259 260
{
	int error = 0;
	khiter_t pos;
	void *item;
261
	size_t keylen, itemlen;
262 263 264 265 266 267 268 269
	char *item_key;

	pos = git_strmap_lookup_index(sc->map, key);
	if (git_strmap_valid_index(sc->map, pos)) {
		item = git_strmap_value_at(sc->map, pos);
		goto done;
	}

270 271 272 273
	keylen  = strlen(key);
	itemlen = sc->item_path_offset + keylen + 1;
	itemlen = (itemlen + 7) & ~7;

274
	if ((item = git_pool_mallocz(&sc->pool, (uint32_t)itemlen)) == NULL) {
275
		/* don't use GITERR_CHECK_ALLOC b/c of lock */
276 277 278
		error = -1;
		goto done;
	}
279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320

	/* one strange thing is that even if the vector or hash table insert
	 * fail, there is no way to free the pool item so we just abandon it
	 */

	item_key = ((char *)item) + sc->item_path_offset;
	memcpy(item_key, key, keylen);

	pos = kh_put(str, sc->map, item_key, &error);
	if (error < 0)
		goto done;

	if (!error)
		kh_key(sc->map, pos) = item_key;
	kh_val(sc->map, pos) = item;

	error = git_vector_insert(&sc->items, item);
	if (error < 0)
		git_strmap_delete_at(sc->map, pos);

done:
	if (out)
		*out = !error ? item : NULL;
	return error;
}

/* lookup item by key */
void *git_sortedcache_lookup(const git_sortedcache *sc, const char *key)
{
	khiter_t pos = git_strmap_lookup_index(sc->map, key);
	if (git_strmap_valid_index(sc->map, pos))
		return git_strmap_value_at(sc->map, pos);
	return NULL;
}

/* find out how many items are in the cache */
size_t git_sortedcache_entrycount(const git_sortedcache *sc)
{
	return git_vector_length(&sc->items);
}

/* lookup item by index */
321
void *git_sortedcache_entry(git_sortedcache *sc, size_t pos)
322
{
323
	/* make sure the items are sorted so this gets the correct item */
324
	if (!git_vector_is_sorted(&sc->items))
325 326
		git_vector_sort(&sc->items);

327 328
	return git_vector_get(&sc->items, pos);
}
329

330
/* helper struct so bsearch callback can know offset + key value for cmp */
331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355
struct sortedcache_magic_key {
	size_t offset;
	const char *key;
};

static int sortedcache_magic_cmp(const void *key, const void *value)
{
	const struct sortedcache_magic_key *magic = key;
	const char *value_key = ((const char *)value) + magic->offset;
	return strcmp(magic->key, value_key);
}

/* lookup index of item by key */
int git_sortedcache_lookup_index(
	size_t *out, git_sortedcache *sc, const char *key)
{
	struct sortedcache_magic_key magic;

	magic.offset = sc->item_path_offset;
	magic.key    = key;

	return git_vector_bsearch2(out, &sc->items, sortedcache_magic_cmp, &magic);
}

/* remove entry from cache */
356
int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
357 358 359 360 361 362 363 364 365 366
{
	char *item;
	khiter_t mappos;

	/* because of pool allocation, this can't actually remove the item,
	 * but we can remove it from the items vector and the hash table.
	 */

	if ((item = git_vector_get(&sc->items, pos)) == NULL) {
		giterr_set(GITERR_INVALID, "Removing item out of range");
367
		return GIT_ENOTFOUND;
368 369 370 371 372 373 374 375 376 377
	}

	(void)git_vector_remove(&sc->items, pos);

	mappos = git_strmap_lookup_index(sc->map, item + sc->item_path_offset);
	git_strmap_delete_at(sc->map, mappos);

	if (sc->free_item)
		sc->free_item(sc->free_item_payload, item);

378
	return 0;
379 380
}