neovim

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

map_key_impl.c.h (4572B)

      1 #include "nvim/map_defs.h"
      2 #include "nvim/memory.h"
      3 
      4 #ifndef KEY_NAME
      5 // Don't error out. it is nice to type-check the file in isolation, in clangd or otherwise
      6 # define KEY_NAME(x) x##int
      7 # define hash_int(x) ((uint32_t)x)
      8 # define equal_int(x, y) ((x) == (y))
      9 #endif
     10 
     11 #define SET_TYPE KEY_NAME(Set_)
     12 #define KEY_TYPE KEY_NAME()
     13 
     14 /// find bucket to get or put "key"
     15 ///
     16 /// set->h.hash assumed already allocated!
     17 ///
     18 /// @return bucket index, or MH_TOMBSTONE if not found and `put` was false
     19 ///         mh_is_either(hash[rv]) : not found, but this is the place to put
     20 ///         otherwise: hash[rv]-1 is index into key/value arrays
     21 uint32_t KEY_NAME(mh_find_bucket_)(SET_TYPE *set, KEY_TYPE 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 = KEY_NAME(hash_)(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 (KEY_NAME(equal_)(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 KEY_NAME(mh_get_)(SET_TYPE *set, KEY_TYPE key)
     51 {
     52  if (set->h.n_buckets == 0) {
     53    return MH_TOMBSTONE;
     54  }
     55  uint32_t idx = KEY_NAME(mh_find_bucket_)(set, key, false);
     56  return (idx != MH_TOMBSTONE) ? set->h.hash[idx] - 1 : MH_TOMBSTONE;
     57 }
     58 
     59 /// Rebuild hash from keys[] array
     60 ///
     61 /// set->h.hash must be allocated and empty before&alling!
     62 void KEY_NAME(mh_rehash_)(SET_TYPE *set)
     63 {
     64  for (uint32_t k = 0; k < set->h.n_keys; k++) {
     65    uint32_t idx = KEY_NAME(mh_find_bucket_)(set, set->keys[k], true);
     66    // there must be tombstones when we do a rehash
     67    if (!mh_is_empty((&set->h), idx)) {
     68      abort();
     69    }
     70    set->h.hash[idx] = k + 1;
     71  }
     72  set->h.n_occupied = set->h.size = set->h.n_keys;
     73 }
     74 
     75 /// Put a key. Return the existing item if found
     76 ///
     77 /// Allocates/resizes the hash table and/or keys[] table if needed.
     78 ///
     79 /// @param[out] new mandatory. Reveals if an existing key was found. In addition,
     80 ///                 if new item, indicates if keys[] was resized.
     81 ///
     82 /// @return keys index
     83 uint32_t KEY_NAME(mh_put_)(SET_TYPE *set, KEY_TYPE key, MHPutStatus *new)
     84 {
     85  MapHash *h = &set->h;
     86  // Might rehash ahead of time if "key" already existed. But it was
     87  // going to happen soon anyway.
     88  if (h->n_occupied >= h->upper_bound) {
     89    // If we likely were to resize soon, do it now to avoid extra rehash
     90    // TODO(bfredl): we never shrink. but maybe that's fine
     91    if (h->size >= h->upper_bound * 0.9) {
     92      mh_realloc(h, h->n_buckets + 1);
     93    } else {
     94      // Just a lot of tombstones from deleted items, start all over again
     95      memset(h->hash, 0, h->n_buckets * sizeof(*h->hash));
     96      h->size = h->n_occupied = 0;
     97    }
     98    KEY_NAME(mh_rehash_)(set);
     99  }
    100 
    101  uint32_t idx = KEY_NAME(mh_find_bucket_)(set, key, true);
    102 
    103  if (mh_is_either(h, idx)) {
    104    h->size++;
    105    if (mh_is_empty(h, idx)) {
    106      h->n_occupied++;
    107    }
    108 
    109    uint32_t pos = h->n_keys++;
    110    if (pos >= h->keys_capacity) {
    111      h->keys_capacity = MAX(h->keys_capacity * 2, 8);
    112      set->keys = xrealloc(set->keys, h->keys_capacity * sizeof(KEY_TYPE));
    113      *new = kMHNewKeyRealloc;
    114    } else {
    115      *new = kMHNewKeyDidFit;
    116    }
    117    set->keys[pos] = key;
    118    h->hash[idx] = pos + 1;
    119    return pos;
    120  } else {
    121    *new = kMHExisting;
    122    uint32_t pos = h->hash[idx] - 1;
    123    if (!KEY_NAME(equal_)(set->keys[pos], key)) {
    124      abort();
    125    }
    126    return pos;
    127  }
    128 }
    129 
    130 /// Deletes `*key` if found, do nothing otherwise
    131 ///
    132 /// @param[in, out] key modified to the value contained in the set
    133 /// @return the index the item used to have in keys[]
    134 ///         MH_TOMBSTONE if key was not found
    135 uint32_t KEY_NAME(mh_delete_)(SET_TYPE *set, KEY_TYPE *key)
    136 {
    137  if (set->h.size == 0) {
    138    return MH_TOMBSTONE;
    139  }
    140  uint32_t idx = KEY_NAME(mh_find_bucket_)(set, *key, false);
    141  if (idx != MH_TOMBSTONE) {
    142    uint32_t k = set->h.hash[idx] - 1;
    143    set->h.hash[idx] = MH_TOMBSTONE;
    144 
    145    uint32_t last = --set->h.n_keys;
    146    *key = set->keys[k];
    147    set->h.size--;
    148    if (last != k) {
    149      uint32_t idx2 = KEY_NAME(mh_find_bucket_)(set, set->keys[last], false);
    150      if (set->h.hash[idx2] != last + 1) {
    151        abort();
    152      }
    153      set->h.hash[idx2] = k + 1;
    154      set->keys[k] = set->keys[last];
    155    }
    156    return k;
    157  }
    158  return MH_TOMBSTONE;
    159 }