commit f054b67ad04873dfbc5d2644a77c3cf422af3c67 from: Stefan Sperling date: Mon Nov 05 21:39:42 2018 UTC remove object_idcache; use object_idset instead commit - 984e8a45c4baf9764b411c634efe60ccb173097c commit + f054b67ad04873dfbc5d2644a77c3cf422af3c67 blob - 8ebd171f529c9d6c08c782f240742acb82235dab blob + a0db6ed9feeabdacaad31a547840dd969d114d4a --- got/Makefile +++ got/Makefile @@ -3,9 +3,8 @@ PROG= got SRCS= got.c blame.c commit_graph.c delta.c diff.c diffoffset.c \ diffreg.c error.c fileindex.c object.c object_cache.c \ - object_idcache.c object_idset.c object_parse.c opentemp.c \ - path.c pack.c privsep.c reference.c repository.c sha1.c \ - worktree.c inflate.c + object_idset.c object_parse.c opentemp.c path.c pack.c \ + privsep.c reference.c repository.c sha1.c worktree.c inflate.c CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib \ -DGOT_LIBEXECDIR=${GOT_LIBEXECDIR} blob - d574268b30620f1eb67c2f20275e6987b2248aaa blob + 067f6f0703d20cfe605969655056f62b9b24771b --- lib/got_lib_object_cache.h +++ lib/got_lib_object_cache.h @@ -31,7 +31,7 @@ struct got_object_cache_entry { struct got_object_cache { enum got_object_cache_type type; - struct got_object_idcache *idcache; + struct got_object_idset *idset; size_t size; int cache_searches; int cache_hit; blob - fef5ccdb782e53e96ac507c88172e730cf6a7758 blob + 166807be00c06035e060b331860e6024814f7fc9 --- lib/object.c +++ lib/object.c @@ -56,13 +56,6 @@ #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b)) #endif -int -got_object_id_cmp(const struct got_object_id *id1, - const struct got_object_id *id2) -{ - return memcmp(id1->sha1, id2->sha1, SHA1_DIGEST_LENGTH); -} - struct got_object_id * got_object_id_dup(struct got_object_id *id1) { blob - f965839f6718bfe2b1406cd88b5efd5f0f16cf72 blob + 1433b270d9cff4da6cfc70cea5a3dd0995e0663c --- lib/object_cache.c +++ lib/object_cache.c @@ -29,7 +29,7 @@ #include "got_lib_delta.h" #include "got_lib_inflate.h" #include "got_lib_object.h" -#include "got_lib_object_idcache.h" +#include "got_lib_object_idset.h" #include "got_lib_object_cache.h" #define GOT_OBJECT_CACHE_SIZE_OBJ 256 @@ -40,27 +40,24 @@ const struct got_error * got_object_cache_init(struct got_object_cache *cache, enum got_object_cache_type type) { - size_t size; - memset(cache, 0, sizeof(*cache)); + cache->idset = got_object_idset_alloc(); + if (cache->idset == NULL) + return got_error_from_errno(); + + cache->type = type; switch (type) { case GOT_OBJECT_CACHE_TYPE_OBJ: - size = GOT_OBJECT_CACHE_SIZE_OBJ; + cache->size = GOT_OBJECT_CACHE_SIZE_OBJ; break; case GOT_OBJECT_CACHE_TYPE_TREE: - size = GOT_OBJECT_CACHE_SIZE_TREE; + cache->size = GOT_OBJECT_CACHE_SIZE_TREE; break; case GOT_OBJECT_CACHE_TYPE_COMMIT: - size = GOT_OBJECT_CACHE_SIZE_COMMIT; + cache->size = GOT_OBJECT_CACHE_SIZE_COMMIT; break; } - - cache->idcache = got_object_idcache_alloc(size); - if (cache->idcache == NULL) - return got_error_from_errno(); - cache->type = type; - cache->size = size; return NULL; } @@ -71,10 +68,10 @@ got_object_cache_add(struct got_object_cache *cache, s struct got_object_cache_entry *ce; int nelem; - nelem = got_object_idcache_num_elements(cache->idcache); + nelem = got_object_idset_num_elements(cache->idset); if (nelem >= cache->size) { - err = got_object_idcache_remove_one((void **)&ce, - cache->idcache, id); + err = got_object_idset_remove((void **)&ce, + cache->idset, NULL); if (err) return err; switch (cache->type) { @@ -108,7 +105,7 @@ got_object_cache_add(struct got_object_cache *cache, s break; } - err = got_object_idcache_add(cache->idcache, id, ce); + err = got_object_idset_add(cache->idset, id, ce); if (err) { if (err->code == GOT_ERR_OBJ_EXISTS) { free(ce); @@ -124,7 +121,7 @@ got_object_cache_get(struct got_object_cache *cache, s struct got_object_cache_entry *ce; cache->cache_searches++; - ce = got_object_idcache_get(cache->idcache, id); + ce = got_object_idset_get(cache->idset, id); if (ce) { cache->cache_hit++; switch (cache->type) { @@ -147,7 +144,7 @@ print_cache_stats(struct got_object_cache *cache, cons { fprintf(stderr, "%s: %s cache: %d elements, %d searches, %d hits, " "%d missed, %d evicted\n", getprogname(), name, - got_object_idcache_num_elements(cache->idcache), + got_object_idset_num_elements(cache->idset), cache->cache_searches, cache->cache_hit, cache->cache_miss, cache->cache_evict); } @@ -207,12 +204,12 @@ got_object_cache_close(struct got_object_cache *cache) break; } - got_object_idcache_for_each(cache->idcache, check_refcount, cache); + got_object_idset_for_each(cache->idset, check_refcount, cache); #endif - if (cache->idcache) { - got_object_idcache_free(cache->idcache); - cache->idcache = NULL; + if (cache->idset) { + got_object_idset_free(cache->idset); + cache->idset = NULL; } cache->size = 0; } blob - 3206b9e9b4efd15c8f08b21fc609d788c1a658ea (mode 644) blob + /dev/null --- lib/object_idcache.c +++ /dev/null @@ -1,200 +0,0 @@ -/* - * Copyright (c) 2018 Stefan Sperling - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES - * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR - * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES - * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN - * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF - * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - */ - -#include - -#include -#include -#include -#include -#include -#include -#include - -#include "got_object.h" -#include "got_error.h" - -#include "got_lib_delta.h" -#include "got_lib_inflate.h" -#include "got_lib_object.h" -#include "got_lib_object_idcache.h" - -#ifndef nitems -#define nitems(_a) (sizeof(_a) / sizeof((_a)[0])) -#endif - -struct got_object_idcache_element { - TAILQ_ENTRY(got_object_idcache_element) entry; - struct got_object_id id; - void *data; /* API user data */ -}; - -TAILQ_HEAD(got_object_idcache_head, got_object_idcache_element); - -struct got_object_idcache { - /* - * The cache is implemented as a collection of 256 lists. - * The value of the first byte of an object ID determines - * which of these lists an object ID is stored in. - */ - struct got_object_idcache_head entries[0xff + 1]; - int nelem[0xff + 1]; - int totelem; - int maxelem; -}; - -struct got_object_idcache * -got_object_idcache_alloc(int maxelem) -{ - struct got_object_idcache *cache; - int i; - - cache = calloc(1, sizeof(*cache)); - if (cache == NULL) - return NULL; - - for (i = 0; i < nitems(cache->entries); i++) - TAILQ_INIT(&cache->entries[i]); - cache->maxelem = maxelem; - return cache; -} - -void -got_object_idcache_free(struct got_object_idcache *cache) -{ - struct got_object_idcache_element *entry; - int i; - - for (i = 0; i < nitems(cache->entries); i++) { - while (!TAILQ_EMPTY(&cache->entries[i])) { - entry = TAILQ_FIRST(&cache->entries[i]); - TAILQ_REMOVE(&cache->entries[i], entry, entry); - /* User data should be freed by caller. */ - free(entry); - } - } - free(cache); -} - -const struct got_error * -got_object_idcache_add(struct got_object_idcache *cache, - struct got_object_id *id, void *data) -{ - struct got_object_idcache_element *entry; - uint8_t i = id->sha1[0]; - - if (cache->totelem >= cache->maxelem) - return got_error(GOT_ERR_NO_SPACE); - - entry = malloc(sizeof(*entry)); - if (entry == NULL) - return got_error_from_errno(); - - memcpy(&entry->id, id, sizeof(entry->id)); - entry->data = data; - - TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry); - cache->nelem[i]++; - cache->totelem++; - return NULL; -} - -void * -got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id) -{ - struct got_object_idcache_element *entry; - uint8_t i = id->sha1[0]; - - TAILQ_FOREACH(entry, &cache->entries[i], entry) { - if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) != 0) - continue; - if (entry != TAILQ_FIRST(&cache->entries[i])) { - TAILQ_REMOVE(&cache->entries[i], entry, entry); - TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry); - } - return entry->data; - } - - return NULL; -} - -const struct got_error * -got_object_idcache_remove_one(void **data, struct got_object_idcache *cache, - struct got_object_id *id) -{ - struct got_object_idcache_element *entry; - uint8_t idx = id->sha1[0]; - - if (data) - *data = NULL; - - if (cache->totelem == 0) - return got_error(GOT_ERR_NO_OBJ); - - if (cache->nelem[idx] == 0) { - /* Remove an element from the longest list. */ - int i, maxelem = cache->nelem[0]; - idx = 0; - for (i = 0; i < nitems(cache->entries); i++) { - if (maxelem < cache->nelem[i]) { - idx = i; - maxelem = cache->nelem[i]; - } - } - } - - entry = TAILQ_LAST(&cache->entries[idx], got_object_idcache_head); - TAILQ_REMOVE(&cache->entries[idx], entry, entry); - if (data) - *data = entry->data; - free(entry); - cache->nelem[idx]--; - cache->totelem--; - return NULL; -} - -int -got_object_idcache_contains(struct got_object_idcache *cache, - struct got_object_id *id) -{ - struct got_object_idcache_element *entry; - uint8_t i = id->sha1[0]; - - TAILQ_FOREACH(entry, &cache->entries[i], entry) { - if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) == 0) - return 1; - } - - return 0; -} - -void got_object_idcache_for_each(struct got_object_idcache *cache, - void (*cb)(struct got_object_id *, void *, void *), void *arg) -{ - struct got_object_idcache_element *entry; - int i; - - for (i = 0; i < nitems(cache->entries); i++) { - TAILQ_FOREACH(entry, &cache->entries[i], entry) - cb(&entry->id, entry->data, arg); - } -} - -int -got_object_idcache_num_elements(struct got_object_idcache *cache) -{ - return cache->totelem; -} blob - 09fe0cf7c70523dc6ccd87e9f4beaa33af626a6d blob + a3873c07d34fa1c0650467bb32c20c84b15835ce --- lib/object_idset.c +++ lib/object_idset.c @@ -150,7 +150,10 @@ got_object_idset_remove(void **data, struct got_object if (set->totelem == 0) return got_error(GOT_ERR_NO_OBJ); - entry = find_element(set, id); + if (id == NULL) + entry = RBT_ROOT(got_object_idset_tree, &set->entries); + else + entry = find_element(set, id); if (entry == NULL) return got_error(GOT_ERR_NO_OBJ); blob - 6421da7af73f06844803dcd9acbd441d60b3bce1 blob + 6ec3f47303410607073404400c35d463ac0a47fb --- lib/object_parse.c +++ lib/object_parse.c @@ -62,6 +62,13 @@ #define GOT_COMMIT_TAG_AUTHOR "author " #define GOT_COMMIT_TAG_COMMITTER "committer " +int +got_object_id_cmp(const struct got_object_id *id1, + const struct got_object_id *id2) +{ + return memcmp(id1->sha1, id2->sha1, SHA1_DIGEST_LENGTH); +} + const struct got_error * got_object_qid_alloc_partial(struct got_object_qid **qid) { blob - 1d11b5ccacd8a00511e57a311e6be23aa1eb2c64 blob + a583c3bda2f147e19a2a8339f35418025143e345 --- libexec/got-read-pack/Makefile +++ libexec/got-read-pack/Makefile @@ -2,7 +2,7 @@ PROG= got-read-pack SRCS= got-read-pack.c delta.c error.c inflate.c object_cache.c \ - object_idcache.c object_parse.c opentemp.c pack.c path.c \ + object_idset.c object_parse.c opentemp.c pack.c path.c \ privsep.c sha1.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - f2a6a6e7f0c92f9293824327b06abd22fd96eb18 blob + 622918d65a3235175fbd16aaffcc60725d7d93cc --- regress/idset/Makefile +++ regress/idset/Makefile @@ -3,7 +3,7 @@ PROG = idset_test SRCS = error.c object.c privsep.c sha1.c pack.c inflate.c path.c opentemp.c \ delta.c repository.c reference.c worktree.c fileindex.c object_cache.c \ - object_idcache.c object_idset.c object_parse.c idset_test.c + object_idset.c object_parse.c idset_test.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib LDADD = -lutil -lz blob - a1659fdf01d1a4f3b580149ba7a7b6085bf74947 blob + 5da0a61342d57368a2ad4a97cf0cfcacf13e6028 --- regress/repository/Makefile +++ regress/repository/Makefile @@ -2,9 +2,9 @@ PROG = repository_test SRCS = path.c repository.c error.c reference.c object.c object_cache.c \ - object_idcache.c object_idset.c object_parse.c opentemp.c sha1.c \ - diff.c diffreg.c pack.c privsep.c delta.c fileindex.c worktree.c \ - inflate.c repository_test.c + object_idset.c object_parse.c opentemp.c sha1.c diff.c diffreg.c \ + pack.c privsep.c delta.c fileindex.c worktree.c inflate.c \ + repository_test.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib \ -DGOT_LIBEXECDIR=${GOT_LIBEXECDIR} blob - 325c30c3d1008e148dd347d12d236e406a822a8a blob + 967be5ea5fc6fb725eea04040ce5afa44a56ca59 --- regress/worktree/Makefile +++ regress/worktree/Makefile @@ -1,9 +1,9 @@ .PATH:${.CURDIR}/../../lib PROG = worktree_test -SRCS = worktree.c repository.c object.c object_cache.c object_idcache.c \ - object_idset.c object_parse.c opentemp.c path.c error.c reference.c \ - sha1.c pack.c privsep.c delta.c inflate.c fileindex.c worktree_test.c +SRCS = worktree.c repository.c object.c object_cache.c object_idset.c \ + object_parse.c opentemp.c path.c error.c reference.c sha1.c \ + pack.c privsep.c delta.c inflate.c fileindex.c worktree_test.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib \ -DGOT_LIBEXECDIR=${GOT_LIBEXECDIR} blob - 8b38788f426c570b7a06035a85bd800f07ef7cc3 blob + 72f8d6d7e4c381ebb68b1e052998d0843ff100aa --- tog/Makefile +++ tog/Makefile @@ -3,9 +3,9 @@ PROG= tog SRCS= tog.c blame.c commit_graph.c delta.c diff.c diffoffset.c \ diffreg.c error.c fileindex.c object.c object_cache.c \ - object_idcache.c object_idset.c object_parse.c opentemp.c \ - path.c pack.c privsep.c reference.c repository.c sha1.c \ - worktree.c utf8.c inflate.c + object_idset.c object_parse.c opentemp.c path.c pack.c \ + privsep.c reference.c repository.c sha1.c worktree.c \ + utf8.c inflate.c CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib \ -DGOT_LIBEXECDIR=${GOT_LIBEXECDIR}