src/sortedcache.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "sortedcache.h"
   9
  10 int git_sortedcache_new(
  11         git_sortedcache **out,
  12         size_t item_path_offset,
  13         git_sortedcache_free_item_fn free_item,
  14         void *free_item_payload,
  15         git_vector_cmp item_cmp,
  16         const char *path)
  17 {
  18         git_sortedcache *sc;
  19         size_t pathlen, alloclen;
  20
  21         pathlen = path ? strlen(path) : 0;
  22
  23         GIT_ERROR_CHECK_ALLOC_ADD(&alloclen, sizeof(git_sortedcache), pathlen);
  24         GIT_ERROR_CHECK_ALLOC_ADD(&alloclen, alloclen, 1);
  25         sc = git__calloc(1, alloclen);
  26         GIT_ERROR_CHECK_ALLOC(sc);
  27
  28         git_pool_init(&sc->pool, 1);
  29
  30         if (git_vector_init(&sc->items, 4, item_cmp) < 0 ||
  31             git_strmap_new(&sc->map) < 0)
  32                 goto fail;
  33
  34         if (git_rwlock_init(&sc->lock)) {
  35                 git_error_set(GIT_ERROR_OS, "failed to initialize lock");
  36                 goto fail;
  37         }
  38
  39         sc->item_path_offset  = item_path_offset;
  40         sc->free_item         = free_item;
  41         sc->free_item_payload = free_item_payload;
  42         GIT_REFCOUNT_INC(sc);
  43         if (pathlen)
  44                 memcpy(sc->path, path, pathlen);
  45
  46         *out = sc;
  47         return 0;
  48
  49 fail:
  50         git_strmap_free(sc->map);
  51         git_vector_free(&sc->items);
  52         git_pool_clear(&sc->pool);
  53         git__free(sc);
  54         return -1;
  55 }
  56
  57 void git_sortedcache_incref(git_sortedcache *sc)
  58 {
  59         GIT_REFCOUNT_INC(sc);
  60 }
  61
  62 const char *git_sortedcache_path(git_sortedcache *sc)
  63 {
  64         return sc->path;
  65 }
  66
  67 static void sortedcache_clear(git_sortedcache *sc)
  68 {
  69         git_strmap_clear(sc->map);
  70
  71         if (sc->free_item) {
  72                 size_t i;
  73                 void *item;
  74
  75                 git_vector_foreach(&sc->items, i, item) {
  76                         sc->free_item(sc->free_item_payload, item);
  77                 }
  78         }
  79
  80         git_vector_clear(&sc->items);
  81
  82         git_pool_clear(&sc->pool);
  83 }
  84
  85 static void sortedcache_free(git_sortedcache *sc)
  86 {
  87         /* acquire write lock to make sure everyone else is done */
  88         if (git_sortedcache_wlock(sc) < 0)
  89                 return;
  90
  91         sortedcache_clear(sc);
  92         git_vector_free(&sc->items);
  93         git_strmap_free(sc->map);
  94
  95         git_sortedcache_wunlock(sc);
  96
  97         git_rwlock_free(&sc->lock);
  98         git__free(sc);
  99 }
 100
 101 void git_sortedcache_free(git_sortedcache *sc)
 102 {
 103         if (!sc)
 104                 return;
 105         GIT_REFCOUNT_DEC(sc, sortedcache_free);
 106 }
 107
 108 static int sortedcache_copy_item(void *payload, void *tgt_item, void *src_item)
 109 {
 110         git_sortedcache *sc = payload;
 111         /* path will already have been copied by upsert */
 112         memcpy(tgt_item, src_item, sc->item_path_offset);
 113         return 0;
 114 }
 115
 116 /* copy a sorted cache */
 117 int git_sortedcache_copy(
 118         git_sortedcache **out,
 119         git_sortedcache *src,
 120         bool lock,
 121         int (*copy_item)(void *payload, void *tgt_item, void *src_item),
 122         void *payload)
 123 {
 124         int error = 0;
 125         git_sortedcache *tgt;
 126         size_t i;
 127         void *src_item, *tgt_item;
 128
 129         /* just use memcpy if no special copy fn is passed in */
 130         if (!copy_item) {
 131                 copy_item = sortedcache_copy_item;
 132                 payload   = src;
 133         }
 134
 135         if ((error = git_sortedcache_new(
 136                         &tgt, src->item_path_offset,
 137                         src->free_item, src->free_item_payload,
 138                         src->items._cmp, src->path)) < 0)
 139                 return error;
 140
 141         if (lock && git_sortedcache_rlock(src) < 0) {
 142                 git_sortedcache_free(tgt);
 143                 return -1;
 144         }
 145
 146         git_vector_foreach(&src->items, i, src_item) {
 147                 char *path = ((char *)src_item) + src->item_path_offset;
 148
 149                 if ((error = git_sortedcache_upsert(&tgt_item, tgt, path)) < 0 ||
 150                         (error = copy_item(payload, tgt_item, src_item)) < 0)
 151                         break;
 152         }
 153
 154         if (lock)
 155                 git_sortedcache_runlock(src);
 156         if (error)
 157                 git_sortedcache_free(tgt);
 158
 159         *out = !error ? tgt : NULL;
 160
 161         return error;
 162 }
 163
 164 /* lock sortedcache while making modifications */
 165 int git_sortedcache_wlock(git_sortedcache *sc)
 166 {
 167         GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
 168
 169         if (git_rwlock_wrlock(&sc->lock) < 0) {
 170                 git_error_set(GIT_ERROR_OS, "unable to acquire write lock on cache");
 171                 return -1;
 172         }
 173         return 0;
 174 }
 175
 176 /* unlock sorted cache when done with modifications */
 177 void git_sortedcache_wunlock(git_sortedcache *sc)
 178 {
 179         git_vector_sort(&sc->items);
 180         git_rwlock_wrunlock(&sc->lock);
 181 }
 182
 183 /* lock sortedcache for read */
 184 int git_sortedcache_rlock(git_sortedcache *sc)
 185 {
 186         GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
 187
 188         if (git_rwlock_rdlock(&sc->lock) < 0) {
 189                 git_error_set(GIT_ERROR_OS, "unable to acquire read lock on cache");
 190                 return -1;
 191         }
 192         return 0;
 193 }
 194
 195 /* unlock sorted cache when done reading */
 196 void git_sortedcache_runlock(git_sortedcache *sc)
 197 {
 198         GIT_UNUSED(sc); /* prevent warning when compiled w/o threads */
 199         git_rwlock_rdunlock(&sc->lock);
 200 }
 201
 202 /* if the file has changed, lock cache and load file contents into buf;
 203  * returns <0 on error, >0 if file has not changed
 204  */
 205 int git_sortedcache_lockandload(git_sortedcache *sc, git_buf *buf)
 206 {
 207         int error, fd;
 208         struct stat st;
 209
 210         if ((error = git_sortedcache_wlock(sc)) < 0)
 211                 return error;
 212
 213         if ((error = git_futils_filestamp_check(&sc->stamp, sc->path)) <= 0)
 214                 goto unlock;
 215
 216         if ((fd = git_futils_open_ro(sc->path)) < 0) {
 217                 error = fd;
 218                 goto unlock;
 219         }
 220
 221         if (p_fstat(fd, &st) < 0) {
 222                 git_error_set(GIT_ERROR_OS, "failed to stat file");
 223                 error = -1;
 224                 (void)p_close(fd);
 225                 goto unlock;
 226         }
 227
 228         if (!git__is_sizet(st.st_size)) {
 229                 git_error_set(GIT_ERROR_INVALID, "unable to load file larger than size_t");
 230                 error = -1;
 231                 (void)p_close(fd);
 232                 goto unlock;
 233         }
 234
 235         if (buf)
 236                 error = git_futils_readbuffer_fd(buf, fd, (size_t)st.st_size);
 237
 238         (void)p_close(fd);
 239
 240         if (error < 0)
 241                 goto unlock;
 242
 243         return 1; /* return 1 -> file needs reload and was successfully loaded */
 244
 245 unlock:
 246         git_sortedcache_wunlock(sc);
 247         return error;
 248 }
 249
 250 void git_sortedcache_updated(git_sortedcache *sc)
 251 {
 252         /* update filestamp to latest value */
 253         git_futils_filestamp_check(&sc->stamp, sc->path);
 254 }
 255
 256 /* release all items in sorted cache */
 257 int git_sortedcache_clear(git_sortedcache *sc, bool wlock)
 258 {
 259         if (wlock && git_sortedcache_wlock(sc) < 0)
 260                 return -1;
 261
 262         sortedcache_clear(sc);
 263
 264         if (wlock)
 265                 git_sortedcache_wunlock(sc);
 266
 267         return 0;
 268 }
 269
 270 /* find and/or insert item, returning pointer to item data */
 271 int git_sortedcache_upsert(void **out, git_sortedcache *sc, const char *key)
 272 {
 273         size_t keylen, itemlen;
 274         int error = 0;
 275         char *item_key;
 276         void *item;
 277
 278         if ((item = git_strmap_get(sc->map, key)) != NULL)
 279                 goto done;
 280
 281         keylen  = strlen(key);
 282         itemlen = sc->item_path_offset + keylen + 1;
 283         itemlen = (itemlen + 7) & ~7;
 284
 285         if ((item = git_pool_mallocz(&sc->pool, itemlen)) == NULL) {
 286                 /* don't use GIT_ERROR_CHECK_ALLOC b/c of lock */
 287                 error = -1;
 288                 goto done;
 289         }
 290
 291         /* one strange thing is that even if the vector or hash table insert
 292          * fail, there is no way to free the pool item so we just abandon it
 293          */
 294
 295         item_key = ((char *)item) + sc->item_path_offset;
 296         memcpy(item_key, key, keylen);
 297
 298         if ((error = git_strmap_set(sc->map, item_key, item)) < 0)
 299                 goto done;
 300
 301         if ((error = git_vector_insert(&sc->items, item)) < 0)
 302                 git_strmap_delete(sc->map, item_key);
 303
 304 done:
 305         if (out)
 306                 *out = !error ? item : NULL;
 307         return error;
 308 }
 309
 310 /* lookup item by key */
 311 void *git_sortedcache_lookup(const git_sortedcache *sc, const char *key)
 312 {
 313         return git_strmap_get(sc->map, key);
 314 }
 315
 316 /* find out how many items are in the cache */
 317 size_t git_sortedcache_entrycount(const git_sortedcache *sc)
 318 {
 319         return git_vector_length(&sc->items);
 320 }
 321
 322 /* lookup item by index */
 323 void *git_sortedcache_entry(git_sortedcache *sc, size_t pos)
 324 {
 325         /* make sure the items are sorted so this gets the correct item */
 326         if (!git_vector_is_sorted(&sc->items))
 327                 git_vector_sort(&sc->items);
 328
 329         return git_vector_get(&sc->items, pos);
 330 }
 331
 332 /* helper struct so bsearch callback can know offset + key value for cmp */
 333 struct sortedcache_magic_key {
 334         size_t offset;
 335         const char *key;
 336 };
 337
 338 static int sortedcache_magic_cmp(const void *key, const void *value)
 339 {
 340         const struct sortedcache_magic_key *magic = key;
 341         const char *value_key = ((const char *)value) + magic->offset;
 342         return strcmp(magic->key, value_key);
 343 }
 344
 345 /* lookup index of item by key */
 346 int git_sortedcache_lookup_index(
 347         size_t *out, git_sortedcache *sc, const char *key)
 348 {
 349         struct sortedcache_magic_key magic;
 350
 351         magic.offset = sc->item_path_offset;
 352         magic.key    = key;
 353
 354         return git_vector_bsearch2(out, &sc->items, sortedcache_magic_cmp, &magic);
 355 }
 356
 357 /* remove entry from cache */
 358 int git_sortedcache_remove(git_sortedcache *sc, size_t pos)
 359 {
 360         char *item;
 361
 362         /*
 363          * Because of pool allocation, this can't actually remove the item,
 364          * but we can remove it from the items vector and the hash table.
 365          */
 366
 367         if ((item = git_vector_get(&sc->items, pos)) == NULL) {
 368                 git_error_set(GIT_ERROR_INVALID, "removing item out of range");
 369                 return GIT_ENOTFOUND;
 370         }
 371
 372         (void)git_vector_remove(&sc->items, pos);
 373
 374         git_strmap_delete(sc->map, item + sc->item_path_offset);
 375
 376         if (sc->free_item)
 377                 sc->free_item(sc->free_item_payload, item);
 378
 379         return 0;
 380 }
 381