Macros | Functions | Variables
hashtab.c File Reference
#include <assert.h>
#include <stdbool.h>
#include <string.h>
#include <inttypes.h>
#include "nvim/vim.h"
#include "nvim/ascii.h"
#include "nvim/hashtab.h"
#include "nvim/message.h"
#include "nvim/memory.h"

Macros

#define PERTURB_SHIFT   5
 
#define HASH_CYCLE_BODY(hash, p)   hash = hash * 101 + *p++
 

Functions

void hash_init (hashtab_T *ht)
 Initialize an empty hash table. More...
 
void hash_clear (hashtab_T *ht)
 
void hash_clear_all (hashtab_T *ht, unsigned int off)
 
hashitem_Thash_find (const hashtab_T *const ht, const char_u *const key)
 
hashitem_Thash_find_len (const hashtab_T *const ht, const char *const key, const size_t len)
 
hashitem_Thash_lookup (const hashtab_T *const ht, const char *const key, const size_t key_len, const hash_T hash)
 
void hash_debug_results (void)
 
int hash_add (hashtab_T *ht, char_u *key)
 
void 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 (const char_u *key)
 
hash_T hash_hash_len (const char *key, const size_t len) FUNC_ATTR_PURE FUNC_ATTR_WARN_UNUSED_RESULT
 
const char_u_hash_key_removed (void)
 

Variables

char hash_removed
 

Detailed Description

Handling of a hashtable with Vim-specific properties.

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 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.

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).

Macro Definition Documentation

#define HASH_CYCLE_BODY (   hash,
  p 
)    hash = hash * 101 + *p++
#define PERTURB_SHIFT   5

Function Documentation

const char_u* _hash_key_removed ( void  )

Function to get HI_KEY_REMOVED value

Used for testing because luajit ffi does not allow getting addresses of globals.

int hash_add ( hashtab_T ht,
char_u key 
)

Add item for key "key" to hashtable "ht".

Parameters
keyPointer to the key for the new item. The key has to be contained in the new item (
See also
hashitem_T). Must not be NULL.
Returns
OK if success. FAIL if key already present
void hash_add_item ( hashtab_T ht,
hashitem_T hi,
char_u key,
hash_T  hash 
)

Add item "hi" for key "key" to hashtable "ht".

Parameters
hiThe hash item to be used. Must have been obtained through hash_lookup() and point to an empty item.
keyPointer to the key for the new item. The key has to be contained in the new item (
See also
hashitem_T). Must not be NULL.
Parameters
hashThe precomputed hash value for the key.
void hash_clear ( hashtab_T ht)

Free the array of a hash table without freeing contained values.

If "ht" is not freed (after calling this) then you should call hash_init() right next!

void hash_clear_all ( hashtab_T ht,
unsigned int  off 
)

Free the array of a hash table and all contained values.

Parameters
offthe offset from start of value to start of key (
See also
hashitem_T).
void hash_debug_results ( void  )

Print the efficiency of hashtable lookups.

Useful when trying different hash algorithms. Called when exiting.

hashitem_T* hash_find ( const hashtab_T *const  ht,
const char_u *const  key 
)

Find item for given "key" in hashtable "ht".

Parameters
keyThe key of the looked-for item. Must not be NULL.
Returns
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_len ( const hashtab_T *const  ht,
const char *const  key,
const size_t  len 
)

Like hash_find, but key is not NUL-terminated

Parameters
[in]htHashtab to look in.
[in]keyKey of the looked-for item. Must not be NULL.
[in]lenKey length.
Returns
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.
hash_T hash_hash ( const char_u key)

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 lower the percentage the better.

hash_T hash_hash_len ( const char *  key,
const size_t  len 
)

Get the hash number for a key that is not a NUL-terminated string

Warning
Function does not check whether key contains NUL. But you will not be able to get hash entry in this case.
Parameters
[in]keyKey.
[in]lenKey length.
Returns
Key hash.
void hash_init ( hashtab_T ht)

Initialize an empty hash table.

void hash_lock ( hashtab_T ht)

Lock hashtable (prevent changes in ht_array).

Don't use this when items are to be added! Must call hash_unlock() later.

hashitem_T* hash_lookup ( const hashtab_T *const  ht,
const char *const  key,
const size_t  key_len,
const hash_T  hash 
)

Like hash_find(), but caller computes "hash".

Parameters
[in]keyThe key of the looked-for item. Must not be NULL.
[in]key_lenKey length.
[in]hashThe precomputed hash for the key.
Returns
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.
void hash_remove ( hashtab_T ht,
hashitem_T hi 
)

Remove item "hi" from hashtable "ht".

Caller must take care of freeing the item itself.

Parameters
hiThe hash item to be removed. It must have been obtained with hash_lookup().
void hash_unlock ( hashtab_T ht)

Unlock hashtable (allow changes in ht_array again).

Table will be resized (shrunk) when necessary. This must balance a call to hash_lock().

Variable Documentation

char hash_removed

Magic number used for hashitem "hi_key" value indicating a deleted item

Only the address is used.