sortedcache.c 8.33 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
#include "sortedcache.h"

GIT__USE_STRMAP;

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;
	size_t pathlen;

	pathlen = path ? strlen(path) : 0;

	sc = git__calloc(sizeof(git_sortedcache) + pathlen + 1, 1);
	GITERR_CHECK_ALLOC(sc);

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

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

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

	*out = sc;
	return 0;

fail:
42
	git_strmap_free(sc->map);
43 44 45 46 47 48 49 50 51 52 53
	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);
}

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

59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
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)
{
79 80
	/* acquire write lock to make sure everyone else is done */
	if (git_sortedcache_wlock(sc) < 0)
81 82 83 84 85 86
		return;

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

87
	git_sortedcache_wunlock(sc);
88

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

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

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

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

	git_vector_foreach(&src->items, i, src_item) {
139 140 141 142 143
		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;
144 145
	}

146 147
	if (lock)
		git_sortedcache_runlock(src);
148 149
	if (error)
		git_sortedcache_free(tgt);
150

151
	*out = !error ? tgt : NULL;
152

153
	return error;
154 155
}

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

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

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

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

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

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

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

201
	if ((error = git_sortedcache_wlock(sc)) < 0)
202 203 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
		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:
229
	git_sortedcache_wunlock(sc);
230 231 232
	return error;
}

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

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

253
/* find and/or insert item, returning pointer to item data */
254
int git_sortedcache_upsert(void **out, git_sortedcache *sc, const char *key)
255 256 257 258
{
	int error = 0;
	khiter_t pos;
	void *item;
259
	size_t keylen, itemlen;
260 261 262 263 264 265 266 267
	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;
	}

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

272
	if ((item = git_pool_mallocz(&sc->pool, (uint32_t)itemlen)) == NULL) {
273
		/* don't use GITERR_CHECK_ALLOC b/c of lock */
274 275 276
		error = -1;
		goto done;
	}
277 278 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

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

325 326
	return git_vector_get(&sc->items, pos);
}
327

328
/* helper struct so bsearch callback can know offset + key value for cmp */
329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353
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 */
354
int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
355 356 357 358 359 360 361 362 363 364
{
	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");
365
		return GIT_ENOTFOUND;
366 367 368 369 370 371 372 373 374 375
	}

	(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);

376
	return 0;
377 378
}