neovim

Neovim text editor
git clone https://git.dasho.dev/neovim.git
Log | Files | Refs | README

map_glyph_cache.c (3173B)

      1 // Specialized version of Set() where interned strings is stored in a compact,
      2 // NUL-separated char array.
      3 // `String key` lookup keys don't need to be NULL terminated, but they
      4 // must not contain embedded NUL:s. When reading a key from set->keys, they
      5 // are always NUL terminated, though. Thus, it is enough to store an index into
      6 // this array, and use strlen(), to retrieve an interned key.
      7 
      8 #include <assert.h>
      9 #include <stdbool.h>
     10 #include <stdint.h>
     11 #include <stdlib.h>
     12 #include <string.h>
     13 
     14 #include "nvim/api/private/defs.h"
     15 #include "nvim/api/private/helpers.h"
     16 #include "nvim/ascii_defs.h"
     17 #include "nvim/macros_defs.h"
     18 #include "nvim/map_defs.h"
     19 #include "nvim/memory.h"
     20 
     21 uint32_t mh_find_bucket_glyph(Set(glyph) *set, String key, bool put)
     22 {
     23  MapHash *h = &set->h;
     24  uint32_t step = 0;
     25  uint32_t mask = h->n_buckets - 1;
     26  uint32_t k = hash_String(key);
     27  uint32_t i = k & mask;
     28  uint32_t last = i;
     29  uint32_t site = put ? last : MH_TOMBSTONE;
     30  while (!mh_is_empty(h, i)) {
     31    if (mh_is_del(h, i)) {
     32      if (site == last) {
     33        site = i;
     34      }
     35    } else if (equal_String(cstr_as_string(&set->keys[h->hash[i] - 1]), key)) {
     36      return i;
     37    }
     38    i = (i + (++step)) & mask;
     39    if (i == last) {
     40      abort();
     41    }
     42  }
     43  if (site == last) {
     44    site = i;
     45  }
     46  return site;
     47 }
     48 
     49 /// @return index into set->keys if found, MH_TOMBSTONE otherwise
     50 uint32_t mh_get_glyph(Set(glyph) *set, String key)
     51 {
     52  if (set->h.n_buckets == 0) {
     53    return MH_TOMBSTONE;
     54  }
     55  uint32_t idx = mh_find_bucket_glyph(set, key, false);
     56  return (idx != MH_TOMBSTONE) ? set->h.hash[idx] - 1 : MH_TOMBSTONE;
     57 }
     58 
     59 void mh_rehash_glyph(Set(glyph) *set)
     60 {
     61  // assume the format of set->keys, i e NUL terminated strings
     62  for (uint32_t k = 0; k < set->h.n_keys; k += (uint32_t)strlen(&set->keys[k]) + 1) {
     63    uint32_t idx = mh_find_bucket_glyph(set, cstr_as_string(&set->keys[k]), true);
     64    // there must be tombstones when we do a rehash
     65    if (!mh_is_empty((&set->h), idx)) {
     66      abort();
     67    }
     68    set->h.hash[idx] = k + 1;
     69  }
     70  set->h.n_occupied = set->h.size = set->h.n_keys;
     71 }
     72 
     73 uint32_t mh_put_glyph(Set(glyph) *set, String key, MHPutStatus *new)
     74 {
     75  MapHash *h = &set->h;
     76  // Might rehash ahead of time if "key" already existed. But it was
     77  // going to happen soon anyway.
     78  if (h->n_occupied >= h->upper_bound) {
     79    mh_realloc(h, h->n_buckets + 1);
     80    mh_rehash_glyph(set);
     81  }
     82 
     83  uint32_t idx = mh_find_bucket_glyph(set, key, true);
     84 
     85  if (mh_is_either(h, idx)) {
     86    h->size++;
     87    h->n_occupied++;
     88 
     89    uint32_t size = (uint32_t)key.size + 1;  // NUL takes space
     90    uint32_t pos = h->n_keys;
     91    h->n_keys += size;
     92    if (h->n_keys > h->keys_capacity) {
     93      h->keys_capacity = MAX(h->keys_capacity * 2, 64);
     94      set->keys = xrealloc(set->keys, h->keys_capacity * sizeof(char));
     95      *new = kMHNewKeyRealloc;
     96    } else {
     97      *new = kMHNewKeyDidFit;
     98    }
     99    memcpy(&set->keys[pos], key.data, key.size);
    100    set->keys[pos + key.size] = NUL;
    101    h->hash[idx] = pos + 1;
    102    return pos;
    103  } else {
    104    *new = kMHExisting;
    105    uint32_t pos = h->hash[idx] - 1;
    106    assert(equal_String(cstr_as_string(&set->keys[pos]), key));
    107    return pos;
    108  }
    109 }