sortedcache.c 8.38 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 23 24 25
#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 ||
		(sc->map = git_strmap_alloc()) == NULL)
		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 42 43 44 45 46 47 48 49 50 51 52 53 54
	sc->free_item_payload = free_item_payload;
	GIT_REFCOUNT_INC(sc);
	if (pathlen)
		memcpy(sc->path, path, pathlen);

	*out = sc;
	return 0;

fail:
	if (sc->map)
		git_strmap_free(sc->map);
	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);
}

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

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

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

88
	git_sortedcache_wunlock(sc);
89

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

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

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

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

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

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

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

154
	return error;
155 156
}

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

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

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

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

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

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

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

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

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

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