hashtab.h File Reference

#include <stddef.h>
#include "nvim/types.h"

Go to the source code of this file.

Data Structures
struct	hashitem_S
struct	hashtable_S

Macros
#define	HI_KEY_REMOVED   ((char_u *)&hash_removed)
#define	HASHITEM_EMPTY(hi)
#define	HT_INIT_SIZE   16
#define	HASHTAB_ITER(ht, hi, code)

Typedefs
typedef size_t	hash_T
	Type for hash number (hash calculation result). More...
typedef struct hashitem_S	hashitem_T
typedef struct hashtable_S	hashtab_T

Variables
char	hash_removed

Macro Definition Documentation

HASHITEM_EMPTY

#define HASHITEM_EMPTY

(

hi

)

Value:

                            ((hi)->hi_key == NULL \
                            || (hi)->hi_key == (char_u *)&hash_removed)

HASHTAB_ITER

#define HASHTAB_ITER	(		ht,
			hi,
			code
	)

Value:

  do { \
    hashtab_T *const hi##ht_ = (ht); \
    size_t hi##todo_ = hi##ht_->ht_used; \
    for (hashitem_T *hi = hi##ht_->ht_array; hi##todo_; hi++) { \
      if (!HASHITEM_EMPTY(hi)) { \
        hi##todo_--; \
        { \
          code \
        } \
      } \
    } \
  } while (0)

Iterate over a hashtab

Parameters

[in]	ht	Hashtab to iterate over.
	hi	Name of the variable with current hashtab entry.
	code	Cycle body.

HI_KEY_REMOVED

#define HI_KEY_REMOVED   ((char_u *)&hash_removed)

The address of "hash_removed" is used as a magic number for hi_key to indicate a removed item.

HT_INIT_SIZE

#define HT_INIT_SIZE   16

Initial size for a hashtable. Our items are relatively small and growing is expensive, thus start with 16. Must be a power of 2. This allows for storing 10 items (2/3 of 16) before a resize is needed.

Typedef Documentation

hash_T

typedef size_t hash_T

Type for hash number (hash calculation result).

hashitem_T

typedef struct hashitem_S hashitem_T

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

hashtab_T

typedef struct hashtable_S hashtab_T

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.

Variable Documentation

hash_removed

char hash_removed

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

Only the address is used.