src/sortedcache.c

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