sortedcache.c 8.46 KB
Newer Older
1 2 3 4 5 6 7
/*
 * Copyright (C) the libgit2 contributors. All rights reserved.
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */

8 9 10 11 12 13 14 15 16 17 18
#include "sortedcache.h"

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;
19
	size_t pathlen, alloclen;
20 21 22

	pathlen = path ? strlen(path) : 0;

23 24
	GIT_ERROR_CHECK_ALLOC_ADD(&alloclen, sizeof(git_sortedcache), pathlen);
	GIT_ERROR_CHECK_ALLOC_ADD(&alloclen, alloclen, 1);
25
	sc = git__calloc(1, alloclen);
26
	GIT_ERROR_CHECK_ALLOC(sc);
27

28 29
	if (git_pool_init(&sc->pool, 1) < 0 ||
	    git_vector_init(&sc->items, 4, item_cmp) < 0 ||
30
	    git_strmap_new(&sc->map) < 0)
31 32
		goto fail;

33
	if (git_rwlock_init(&sc->lock)) {
34
		git_error_set(GIT_ERROR_OS, "failed to initialize lock");
35 36 37
		goto fail;
	}

38 39
	sc->item_path_offset  = item_path_offset;
	sc->free_item         = free_item;
40 41 42 43 44 45 46 47 48
	sc->free_item_payload = free_item_payload;
	GIT_REFCOUNT_INC(sc);
	if (pathlen)
		memcpy(sc->path, path, pathlen);

	*out = sc;
	return 0;

fail:
49
	git_strmap_free(sc->map);
50 51 52 53 54 55 56 57 58 59 60
	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);
}

61 62 63 64 65
const char *git_sortedcache_path(git_sortedcache *sc)
{
	return sc->path;
}

66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
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)
{
86 87
	/* acquire write lock to make sure everyone else is done */
	if (git_sortedcache_wlock(sc) < 0)
88 89 90 91 92 93
		return;

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

94
	git_sortedcache_wunlock(sc);
95

96
	git_rwlock_free(&sc->lock);
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
	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,
119
	bool lock,
120 121 122
	int (*copy_item)(void *payload, void *tgt_item, void *src_item),
	void *payload)
{
123
	int error = 0;
124 125 126 127
	git_sortedcache *tgt;
	size_t i;
	void *src_item, *tgt_item;

128
	/* just use memcpy if no special copy fn is passed in */
129 130 131 132 133
	if (!copy_item) {
		copy_item = sortedcache_copy_item;
		payload   = src;
	}

134
	if ((error = git_sortedcache_new(
135 136
			&tgt, src->item_path_offset,
			src->free_item, src->free_item_payload,
137 138
			src->items._cmp, src->path)) < 0)
		return error;
139

140
	if (lock && git_sortedcache_rlock(src) < 0) {
141 142 143 144 145
		git_sortedcache_free(tgt);
		return -1;
	}

	git_vector_foreach(&src->items, i, src_item) {
146 147 148 149 150
		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;
151 152
	}

153 154
	if (lock)
		git_sortedcache_runlock(src);
155 156
	if (error)
		git_sortedcache_free(tgt);
157

158
	*out = !error ? tgt : NULL;
159

160
	return error;
161 162
}

163 164
/* lock sortedcache while making modifications */
int git_sortedcache_wlock(git_sortedcache *sc)
165
{
166
	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
167

168
	if (git_rwlock_wrlock(&sc->lock) < 0) {
169
		git_error_set(GIT_ERROR_OS, "unable to acquire write lock on cache");
170 171 172
		return -1;
	}
	return 0;
173 174
}

175 176
/* unlock sorted cache when done with modifications */
void git_sortedcache_wunlock(git_sortedcache *sc)
177
{
178 179
	git_vector_sort(&sc->items);
	git_rwlock_wrunlock(&sc->lock);
180 181
}

182 183
/* lock sortedcache for read */
int git_sortedcache_rlock(git_sortedcache *sc)
184
{
185
	GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
186

187
	if (git_rwlock_rdlock(&sc->lock) < 0) {
188
		git_error_set(GIT_ERROR_OS, "unable to acquire read lock on cache");
189 190 191 192 193
		return -1;
	}
	return 0;
}

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

/* if the file has changed, lock cache and load file contents into buf;
 * returns <0 on error, >0 if file has not changed
 */
204
int git_sortedcache_lockandload(git_sortedcache *sc, git_str *buf)
205 206
{
	int error, fd;
207
	struct stat st;
208

209
	if ((error = git_sortedcache_wlock(sc)) < 0)
210 211 212 213 214
		return error;

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

215 216 217 218 219 220
	if ((fd = git_futils_open_ro(sc->path)) < 0) {
		error = fd;
		goto unlock;
	}

	if (p_fstat(fd, &st) < 0) {
221
		git_error_set(GIT_ERROR_OS, "failed to stat file");
222
		error = -1;
223
		(void)p_close(fd);
224 225 226
		goto unlock;
	}

227
	if (!git__is_sizet(st.st_size)) {
228
		git_error_set(GIT_ERROR_INVALID, "unable to load file larger than size_t");
229 230
		error = -1;
		(void)p_close(fd);
231 232 233 234
		goto unlock;
	}

	if (buf)
235
		error = git_futils_readbuffer_fd(buf, fd, (size_t)st.st_size);
236 237 238 239 240 241 242 243 244

	(void)p_close(fd);

	if (error < 0)
		goto unlock;

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

unlock:
245
	git_sortedcache_wunlock(sc);
246 247 248
	return error;
}

249 250
void git_sortedcache_updated(git_sortedcache *sc)
{
251 252
	/* update filestamp to latest value */
	git_futils_filestamp_check(&sc->stamp, sc->path);
253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268
}

/* 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;
}

269
/* find and/or insert item, returning pointer to item data */
270
int git_sortedcache_upsert(void **out, git_sortedcache *sc, const char *key)
271
{
272
	size_t keylen, itemlen;
273
	int error = 0;
274
	char *item_key;
275
	void *item;
276

277
	if ((item = git_strmap_get(sc->map, key)) != NULL)
278 279
		goto done;

280 281 282 283
	keylen  = strlen(key);
	itemlen = sc->item_path_offset + keylen + 1;
	itemlen = (itemlen + 7) & ~7;

284
	if ((item = git_pool_mallocz(&sc->pool, itemlen)) == NULL) {
285
		/* don't use GIT_ERROR_CHECK_ALLOC b/c of lock */
286 287 288
		error = -1;
		goto done;
	}
289 290 291 292 293 294 295 296

	/* 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);

297
	if ((error = git_strmap_set(sc->map, item_key, item)) < 0)
298 299
		goto done;

300 301
	if ((error = git_vector_insert(&sc->items, item)) < 0)
		git_strmap_delete(sc->map, item_key);
302 303 304 305 306 307 308 309 310 311

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

/* lookup item by key */
void *git_sortedcache_lookup(const git_sortedcache *sc, const char *key)
{
312
	return git_strmap_get(sc->map, key);
313 314 315 316 317 318 319 320 321
}

/* 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 */
322
void *git_sortedcache_entry(git_sortedcache *sc, size_t pos)
323
{
324
	/* make sure the items are sorted so this gets the correct item */
325
	if (!git_vector_is_sorted(&sc->items))
326 327
		git_vector_sort(&sc->items);

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

331
/* helper struct so bsearch callback can know offset + key value for cmp */
332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356
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 */
357
int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
358 359 360
{
	char *item;

361 362
	/*
	 * Because of pool allocation, this can't actually remove the item,
363 364 365 366
	 * but we can remove it from the items vector and the hash table.
	 */

	if ((item = git_vector_get(&sc->items, pos)) == NULL) {
367
		git_error_set(GIT_ERROR_INVALID, "removing item out of range");
368
		return GIT_ENOTFOUND;
369 370 371 372
	}

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

373
	git_strmap_delete(sc->map, item + sc->item_path_offset);
374 375 376 377

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

378
	return 0;
379 380
}