diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/nvim/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/nvim/hashtab.c | 235 | ||||
| -rw-r--r-- | src/nvim/hashtab.h | 95 | ||||
| -rw-r--r-- | src/nvim/memory.c | 4 | ||||
| -rw-r--r-- | src/nvim/memory.h | 2 | ||||
| -rw-r--r-- | src/nvim/screen.c | 2 |
6 files changed, 170 insertions, 169 deletions
diff --git a/src/nvim/CMakeLists.txt b/src/nvim/CMakeLists.txt index ad45f3ad3b..eb270eecb5 100644 --- a/src/nvim/CMakeLists.txt +++ b/src/nvim/CMakeLists.txt @@ -37,6 +37,7 @@ set(CONV_SRCS api.c arabic.c garray.c + hashtab.c memory.c map.c os/env.c diff --git a/src/nvim/hashtab.c b/src/nvim/hashtab.c index 7445a4cec1..4e4274bfa1 100644 --- a/src/nvim/hashtab.c +++ b/src/nvim/hashtab.c @@ -2,22 +2,23 @@ /// /// Handling of a hashtable with Vim-specific properties. /// -/// Each item in a hashtable has a NUL terminated string key. A key can appear +/// Each item in a hashtable has a NUL terminated string key. A key can appear /// only once in the table. /// -/// A hash number is computed from the key for quick lookup. When the hashes +/// A hash number is computed from the key for quick lookup. When the hashes /// of two different keys point to the same entry an algorithm is used to /// iterate over other entries in the table until the right one is found. /// To make the iteration work removed keys are different from entries where a /// key was never present. /// /// The mechanism has been partly based on how Python Dictionaries are -/// implemented. The algorithm is from Knuth Vol. 3, Sec. 6.4. +/// implemented. The algorithm is from Knuth Vol. 3, Sec. 6.4. /// -/// The hashtable grows to accommodate more entries when needed. At least 1/3 +/// The hashtable grows to accommodate more entries when needed. At least 1/3 /// of the entries is empty to keep the lookup efficient (at the cost of extra /// memory). +#include <stdbool.h> #include <string.h> #include "nvim/vim.h" @@ -29,12 +30,9 @@ // Magic value for algorithm that walks through the array. #define PERTURB_SHIFT 5 -static int hash_may_resize(hashtab_T *ht, int minitems); - +static int hash_may_resize(hashtab_T *ht, size_t minitems); /// Initialize an empty hash table. -/// -/// @param ht void hash_init(hashtab_T *ht) { // This zeroes all "ht_" entries and all the "hi_key" in "ht_smallarray". @@ -43,10 +41,10 @@ void hash_init(hashtab_T *ht) ht->ht_mask = HT_INIT_SIZE - 1; } -/// Free the array of a hash table. Does not free the items it contains! -/// If "ht" is not freed then you should call hash_init() next! +/// Free the array of a hash table without freeing contained values. /// -/// @param ht +/// If "ht" is not freed (after calling this) then you should call hash_init() +/// right next! void hash_clear(hashtab_T *ht) { if (ht->ht_array != ht->ht_smallarray) { @@ -54,20 +52,13 @@ void hash_clear(hashtab_T *ht) } } -/// Free the array of a hash table and all the keys it contains. The keys must -/// have been allocated. "off" is the offset from the start of the allocate -/// memory to the location of the key (it's always positive). +/// Free the array of a hash table and all contained values. /// -/// @param ht -/// @param off -void hash_clear_all(hashtab_T *ht, int off) +/// @param off the offset from start of value to start of key (@see hashitem_T). +void hash_clear_all(hashtab_T *ht, unsigned int off) { - long todo; - hashitem_T *hi; - - todo = (long)ht->ht_used; - - for (hi = ht->ht_array; todo > 0; ++hi) { + size_t todo = ht->ht_used; + for (hashitem_T *hi = ht->ht_array; todo > 0; ++hi) { if (!HASHITEM_EMPTY(hi)) { free(hi->hi_key - off); todo--; @@ -76,17 +67,15 @@ void hash_clear_all(hashtab_T *ht, int off) hash_clear(ht); } -/// Find "key" in hashtable "ht". "key" must not be NULL. -/// Always returns a pointer to a hashitem. If the item was not found then -/// HASHITEM_EMPTY() is TRUE. The pointer is then the place where the key -/// would be added. -/// WARNING: The returned pointer becomes invalid when the hashtable is changed -/// (adding, setting or removing an item)! +/// Find item for given "key" in hashtable "ht". /// -/// @param ht -/// @param key +/// @param key The key of the looked-for item. Must not be NULL. /// -/// @return Pointer to the hashitem stored with the given key. +/// @return Pointer to the hash item corresponding to the given key. +/// If not found, then return pointer to the empty item that would be +/// used for that key. +/// WARNING: Returned pointer becomes invalid as soon as the hash table +/// is changed in any way. hashitem_T* hash_find(hashtab_T *ht, char_u *key) { return hash_lookup(ht, key, hash_hash(key)); @@ -94,18 +83,16 @@ hashitem_T* hash_find(hashtab_T *ht, char_u *key) /// Like hash_find(), but caller computes "hash". /// -/// @param ht -/// @param key -/// @param hash +/// @param key The key of the looked-for item. Must not be NULL. +/// @param hash The precomputed hash for the key. /// -/// @return Pointer to the hashitem stored with the given key. +/// @return Pointer to the hashitem corresponding to the given key. +/// If not found, then return pointer to the empty item that would be +/// used for that key. +/// WARNING: Returned pointer becomes invalid as soon as the hash table +/// is changed in any way. hashitem_T* hash_lookup(hashtab_T *ht, char_u *key, hash_T hash) { - hash_T perturb; - hashitem_T *freeitem; - hashitem_T *hi; - unsigned idx; - #ifdef HT_DEBUG hash_count_lookup++; #endif // ifdef HT_DEBUG @@ -114,29 +101,28 @@ hashitem_T* hash_lookup(hashtab_T *ht, char_u *key, hash_T hash) // - return if there is no item at all // - skip over a removed item // - return if the item matches - idx = (unsigned)(hash & ht->ht_mask); - hi = &ht->ht_array[idx]; + hash_T idx = hash & ht->ht_mask; + hashitem_T *hi = &ht->ht_array[idx]; if (hi->hi_key == NULL) { return hi; } + hashitem_T *freeitem = NULL; if (hi->hi_key == HI_KEY_REMOVED) { freeitem = hi; } else if ((hi->hi_hash == hash) && (STRCMP(hi->hi_key, key) == 0)) { return hi; - } else { - freeitem = NULL; } - // Need to search through the table to find the key. The algorithm + // Need to search through the table to find the key. The algorithm // to step through the table starts with large steps, gradually becoming - // smaller down to (1/4 table size + 1). This means it goes through all + // smaller down to (1/4 table size + 1). This means it goes through all // table entries in the end. // When we run into a NULL key it's clear that the key isn't there. // Return the first available slot found (can be a slot of a removed // item). - for (perturb = hash;; perturb >>= PERTURB_SHIFT) { + for (hash_T perturb = hash;; perturb >>= PERTURB_SHIFT) { #ifdef HT_DEBUG // count a "miss" for hashtab lookup hash_count_perturb++; @@ -161,6 +147,7 @@ hashitem_T* hash_lookup(hashtab_T *ht, char_u *key, hash_T hash) } /// Print the efficiency of hashtable lookups. +/// /// Useful when trying different hash algorithms. /// Called when exiting. void hash_debug_results(void) @@ -176,12 +163,13 @@ void hash_debug_results(void) #endif // ifdef HT_DEBUG } -/// Add item with key "key" to hashtable "ht". +/// Add item for key "key" to hashtable "ht". /// -/// @param ht -/// @param key +/// @param key Pointer to the key for the new item. The key has to be contained +/// in the new item (@see hashitem_T). Must not be NULL. /// -/// @returns FAIL when out of memory or the key is already present. +/// @return OK if success. +/// FAIL if key already present, or out of memory. int hash_add(hashtab_T *ht, char_u *key) { hash_T hash = hash_hash(key); @@ -193,16 +181,16 @@ int hash_add(hashtab_T *ht, char_u *key) return hash_add_item(ht, hi, key, hash); } -/// Add item "hi" with "key" to hashtable "ht". "key" must not be NULL and -/// "hi" must have been obtained with hash_lookup() and point to an empty item. -/// "hi" is invalid after this! +/// Add item "hi" for key "key" to hashtable "ht". /// -/// @param ht -/// @param hi -/// @param key -/// @param hash +/// @param hi The hash item to be used. Must have been obtained through +/// hash_lookup() and point to an empty item. +/// @param key Pointer to the key for the new item. The key has to be contained +/// in the new item (@see hashitem_T). Must not be NULL. +/// @param hash The precomputed hash value for the key. /// -/// @returns OK or FAIL (out of memory). +/// @return OK if success. +/// FAIL if out of memory. int hash_add_item(hashtab_T *ht, hashitem_T *hi, char_u *key, hash_T hash) { // If resizing failed before and it fails again we can't add an item. @@ -221,13 +209,12 @@ int hash_add_item(hashtab_T *ht, hashitem_T *hi, char_u *key, hash_T hash) return hash_may_resize(ht, 0); } -/// Remove item "hi" from hashtable "ht". "hi" must have been obtained with -/// hash_lookup(). +/// Remove item "hi" from hashtable "ht". /// -/// The caller must take care of freeing the item itself. +/// Caller must take care of freeing the item itself. /// -/// @param ht -/// @param hi +/// @param hi The hash item to be removed. +/// It must have been obtained with hash_lookup(). void hash_remove(hashtab_T *ht, hashitem_T *hi) { ht->ht_used--; @@ -235,44 +222,37 @@ void hash_remove(hashtab_T *ht, hashitem_T *hi) hash_may_resize(ht, 0); } -/// Lock a hashtable: prevent that ht_array changes. +/// Lock hashtable (prevent changes in ht_array). +/// /// Don't use this when items are to be added! /// Must call hash_unlock() later. -/// -/// @param ht void hash_lock(hashtab_T *ht) { ht->ht_locked++; } -/// Unlock a hashtable: allow ht_array changes again. -/// Table will be resized (shrink) when necessary. +/// Unlock hashtable (allow changes in ht_array again). +/// +/// Table will be resized (shrunk) when necessary. /// This must balance a call to hash_lock(). void hash_unlock(hashtab_T *ht) { ht->ht_locked--; - (void)hash_may_resize(ht, 0); + hash_may_resize(ht, 0); } -/// Shrink a hashtable when there is too much empty space. -/// Grow a hashtable when there is not enough empty space. +/// Resize hastable (new size can be given or automatically computed). /// -/// @param ht -/// @param minitems minimal number of items +/// @param minitems Minimum number of items the new table should hold. +/// If zero, new size will depend on currently used items: +/// - Shrink when too much empty space. +/// - Grow when not enough empty space. +/// If non-zero, passed minitems will be used. /// -/// @returns OK or FAIL (out of memory). -static int hash_may_resize(hashtab_T *ht, int minitems) +/// @return OK if success. +/// FAIL if out of memory. +static int hash_may_resize(hashtab_T *ht, size_t minitems) { - hashitem_T temparray[HT_INIT_SIZE]; - hashitem_T *oldarray, *newarray; - hashitem_T *olditem, *newitem; - unsigned newi; - int todo; - long_u oldsize, newsize; - long_u minsize; - long_u newmask; - hash_T perturb; - // Don't resize a locked table. if (ht->ht_locked > 0) { return OK; @@ -288,8 +268,9 @@ static int hash_may_resize(hashtab_T *ht, int minitems) } #endif // ifdef HT_DEBUG + size_t minsize; if (minitems == 0) { - // Return quickly for small tables with at least two NULL items. NULL + // Return quickly for small tables with at least two NULL items. // items are required for the lookup to decide a key isn't there. if ((ht->ht_filled < HT_INIT_SIZE - 1) && (ht->ht_array == ht->ht_smallarray)) { @@ -298,9 +279,9 @@ static int hash_may_resize(hashtab_T *ht, int minitems) // Grow or refill the array when it's more than 2/3 full (including // removed items, so that they get cleaned up). - // Shrink the array when it's less than 1/5 full. When growing it is + // Shrink the array when it's less than 1/5 full. When growing it is // at least 1/4 full (avoids repeated grow-shrink operations) - oldsize = ht->ht_mask + 1; + size_t oldsize = ht->ht_mask + 1; if ((ht->ht_filled * 3 < oldsize * 2) && (ht->ht_used > oldsize / 5)) { return OK; } @@ -314,16 +295,15 @@ static int hash_may_resize(hashtab_T *ht, int minitems) } } else { // Use specified size. - if ((long_u)minitems < ht->ht_used) { + if (minitems < ht->ht_used) { // just in case... - minitems = (int)ht->ht_used; + minitems = ht->ht_used; } // array is up to 2/3 full minsize = minitems * 3 / 2; } - newsize = HT_INIT_SIZE; - + size_t newsize = HT_INIT_SIZE; while (newsize < minsize) { // make sure it's always a power of 2 newsize <<= 1; @@ -333,40 +313,37 @@ static int hash_may_resize(hashtab_T *ht, int minitems) } } - if (newsize == HT_INIT_SIZE) { - // Use the small array inside the hashdict structure. - newarray = ht->ht_smallarray; - if (ht->ht_array == newarray) { - // Moving from ht_smallarray to ht_smallarray! Happens when there - // are many removed items. Copy the items to be able to clean up - // removed items. - memmove(temparray, newarray, sizeof(temparray)); - oldarray = temparray; - } else { - oldarray = ht->ht_array; - } - } else { - // Allocate an array. - newarray = xmalloc(sizeof(hashitem_T) * newsize); - oldarray = ht->ht_array; - } - memset(newarray, 0, (size_t)(sizeof(hashitem_T) * newsize)); + bool newarray_is_small = newsize == HT_INIT_SIZE; + bool keep_smallarray = newarray_is_small + && ht->ht_array == ht->ht_smallarray; + + // Make sure that oldarray and newarray do not overlap, + // so that copying is possible. + hashitem_T temparray[HT_INIT_SIZE]; + hashitem_T *oldarray = keep_smallarray + ? memcpy(temparray, ht->ht_smallarray, sizeof(temparray)) + : ht->ht_array; + hashitem_T *newarray = newarray_is_small + ? ht->ht_smallarray + : xmalloc(sizeof(hashitem_T) * newsize); + + memset(newarray, 0, sizeof(hashitem_T) * newsize); // Move all the items from the old array to the new one, placing them in - // the right spot. The new array won't have any removed items, thus this + // the right spot. The new array won't have any removed items, thus this // is also a cleanup action. - newmask = newsize - 1; - todo = (int)ht->ht_used; + hash_T newmask = newsize - 1; + size_t todo = ht->ht_used; - for (olditem = oldarray; todo > 0; ++olditem) { + for (hashitem_T *olditem = oldarray; todo > 0; ++olditem) { if (!HASHITEM_EMPTY(olditem)) { // The algorithm to find the spot to add the item is identical to - // the algorithm to find an item in hash_lookup(). But we only + // the algorithm to find an item in hash_lookup(). But we only // need to search for a NULL key, thus it's simpler. - newi = (unsigned)(olditem->hi_hash & newmask); - newitem = &newarray[newi]; + hash_T newi = olditem->hi_hash & newmask; + hashitem_T *newitem = &newarray[newi]; if (newitem->hi_key != NULL) { - for (perturb = olditem->hi_hash;; perturb >>= PERTURB_SHIFT) { + for (hash_T perturb = olditem->hi_hash;; perturb >>= PERTURB_SHIFT) { newi = 5 * newi + perturb + 1; newitem = &newarray[newi & newmask]; if (newitem->hi_key == NULL) { @@ -385,33 +362,29 @@ static int hash_may_resize(hashtab_T *ht, int minitems) ht->ht_array = newarray; ht->ht_mask = newmask; ht->ht_filled = ht->ht_used; - ht->ht_error = FALSE; + ht->ht_error = false; return OK; } /// Get the hash number for a key. +/// /// If you think you know a better hash function: Compile with HT_DEBUG set and -/// run a script that uses hashtables a lot. Vim will then print statistics -/// when exiting. Try that with the current hash algorithm and yours. The +/// run a script that uses hashtables a lot. Vim will then print statistics +/// when exiting. Try that with the current hash algorithm and yours. The /// lower the percentage the better. -/// -/// @param key -/// -/// @return Hash number for the key. hash_T hash_hash(char_u *key) { - hash_T hash; - char_u *p; + hash_T hash = *key; - if ((hash = *key) == 0) { + if (hash == 0) { // Empty keys are not allowed, but we don't want to crash if we get one. return (hash_T) 0; } - p = key + 1; // A simplistic algorithm that appears to do very well. // Suggested by George Reilly. + char_u *p = key + 1; while (*p != NUL) { hash = hash * 101 + *p++; } diff --git a/src/nvim/hashtab.h b/src/nvim/hashtab.h index 118795efe6..bd64984ac8 100644 --- a/src/nvim/hashtab.h +++ b/src/nvim/hashtab.h @@ -1,56 +1,83 @@ #ifndef NVIM_HASHTAB_H #define NVIM_HASHTAB_H -/* Item for a hashtable. "hi_key" can be one of three values: - * NULL: Never been used - * HI_KEY_REMOVED: Entry was removed - * Otherwise: Used item, pointer to the actual key; this usually is - * inside the item, subtract an offset to locate the item. - * This reduces the size of hashitem by 1/3. - */ -typedef struct hashitem_S { - long_u hi_hash; /* cached hash number of hi_key */ - char_u *hi_key; -} hashitem_T; +#include <stdbool.h> +#include "nvim/vim.h" -/* The address of "hash_removed" is used as a magic number for hi_key to - * indicate a removed item. */ +/// Type for hash number (hash calculation result). +typedef size_t hash_T; + +/// The address of "hash_removed" is used as a magic number +/// for hi_key to indicate a removed item. #define HI_KEY_REMOVED &hash_removed -#define HASHITEM_EMPTY(hi) ((hi)->hi_key == NULL || (hi)->hi_key == \ - &hash_removed) +#define HASHITEM_EMPTY(hi) ((hi)->hi_key == NULL \ + || (hi)->hi_key == &hash_removed) + +/// A hastable item. +/// +/// Each item has a NUL terminated string key. +/// A key can appear only once in the table. +/// +/// A hash number is computed from the key for quick lookup. When the hashes +/// of two different keys point to the same entry an algorithm is used to +/// iterate over other entries in the table until the right one is found. +/// To make the iteration work removed keys are different from entries where a +/// key was never present. +/// +/// Note that this does not contain a pointer to the key and another pointer to +/// the value. Instead, it is assumed that the key is contained within the +/// value, so that you can get a pointer to the value subtracting an offset from +/// the pointer to the key. +/// This reduces the size of this item by 1/3. +typedef struct hashitem_S { + /// Cached hash number for hi_key. + hash_T hi_hash; + + /// Item key. + /// + /// Possible values mean the following: + /// NULL : Item was never used. + /// HI_KEY_REMOVED : Item was removed. + /// (Any other pointer value) : Item is currently being used. + char_u *hi_key; +} hashitem_T; -/* Initial size for a hashtable. Our items are relatively small and growing - * is expensive, thus use 16 as a start. Must be a power of 2. */ +/// Initial size for a hashtable. +/// Our items are relatively small and growing is expensive, thus start with 16. +/// Must be a power of 2. #define HT_INIT_SIZE 16 +/// An array-based hashtable. +/// +/// Keys are NUL terminated strings. They cannot be repeated within a table. +/// Values are of any type. +/// +/// The hashtable grows to accommodate more entries when needed. typedef struct hashtable_S { - long_u ht_mask; /* mask used for hash value (nr of items in - * array is "ht_mask" + 1) */ - long_u ht_used; /* number of items used */ - long_u ht_filled; /* number of items used + removed */ - int ht_locked; /* counter for hash_lock() */ - int ht_error; /* when set growing failed, can't add more - items before growing works */ - hashitem_T *ht_array; /* points to the array, allocated when it's - not "ht_smallarray" */ - hashitem_T ht_smallarray[HT_INIT_SIZE]; /* initial array */ + hash_T ht_mask; /// mask used for hash value + /// (nr of items in array is "ht_mask" + 1) + size_t ht_used; /// number of items used + size_t ht_filled; /// number of items used or removed + int ht_locked; /// counter for hash_lock() + bool ht_error; /// when set growing failed, can't add more + /// items before growing works + hashitem_T *ht_array; /// points to the array, allocated when it's + /// not "ht_smallarray" + hashitem_T ht_smallarray[HT_INIT_SIZE]; /// initial array } hashtab_T; -typedef long_u hash_T; /* Type for hi_hash */ - -/* hashtab.c */ +// hashtab.c void hash_init(hashtab_T *ht); void hash_clear(hashtab_T *ht); -void hash_clear_all(hashtab_T *ht, int off); +void hash_clear_all(hashtab_T *ht, unsigned int off); hashitem_T *hash_find(hashtab_T *ht, char_u *key); hashitem_T *hash_lookup(hashtab_T *ht, char_u *key, hash_T hash); void hash_debug_results(void); int hash_add(hashtab_T *ht, char_u *key); -int hash_add_item(hashtab_T *ht, hashitem_T *hi, char_u *key, - hash_T hash); +int hash_add_item(hashtab_T *ht, hashitem_T *hi, char_u *key, hash_T hash); void hash_remove(hashtab_T *ht, hashitem_T *hi); void hash_lock(hashtab_T *ht); void hash_unlock(hashtab_T *ht); hash_T hash_hash(char_u *key); -#endif /* NVIM_HASHTAB_H */ +#endif // NVIM_HASHTAB_H diff --git a/src/nvim/memory.c b/src/nvim/memory.c index 9bfb12e0ee..b6990890a6 100644 --- a/src/nvim/memory.c +++ b/src/nvim/memory.c @@ -84,7 +84,7 @@ void *verbose_try_malloc(size_t size) { void *ret = try_malloc(size); if (!ret) { - do_outofmem_msg((long_u)size); + do_outofmem_msg(size); } return ret; } @@ -214,7 +214,7 @@ void *xmemdup(const void *data, size_t len) * Avoid repeating the error message many times (they take 1 second each). * Did_outofmem_msg is reset when a character is read. */ -void do_outofmem_msg(long_u size) +void do_outofmem_msg(size_t size) { if (!did_outofmem_msg) { /* Don't hide this message */ diff --git a/src/nvim/memory.h b/src/nvim/memory.h index ac7b1ebd6a..2723a7ba80 100644 --- a/src/nvim/memory.h +++ b/src/nvim/memory.h @@ -134,7 +134,7 @@ char *xstpncpy(char *restrict dst, const char *restrict src, size_t maxlen); void *xmemdup(const void *data, size_t len) FUNC_ATTR_MALLOC FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_RET; -void do_outofmem_msg(long_u size); +void do_outofmem_msg(size_t size); void free_all_mem(void); #endif diff --git a/src/nvim/screen.c b/src/nvim/screen.c index af3f5c999f..f4616d3b8e 100644 --- a/src/nvim/screen.c +++ b/src/nvim/screen.c @@ -6288,7 +6288,7 @@ retry: || outofmem) { if (ScreenLines != NULL || !done_outofmem_msg) { /* guess the size */ - do_outofmem_msg((long_u)((Rows + 1) * Columns)); + do_outofmem_msg((Rows + 1) * Columns); /* Remember we did this to avoid getting outofmem messages over * and over again. */ |