Dictionaries
Netdata dictionaries associate a name
with a value
:
- A
name
can be any string. - A
value
can be anything.
Such a pair of a name
and a value
consists of an item
or an entry
in the dictionary.
Dictionaries provide an interface to:
- Add an item to the dictionary
- Get an item from the dictionary (provided its
name
) - Delete an item from the dictionary (provided its
name
) - Traverse the list of items in the dictionary
Dictionaries are ordered, meaning that the order they have been added, is preserved while traversing them. The caller may reverse this order by passing the flag DICT_OPTION_ADD_IN_FRONT
when creating the dictionary.
Dictionaries guarantee uniqueness of all items added to them, meaning that only one item with a given name
can exist in the dictionary at any given time.
Dictionaries are extremely fast in all operations. They are indexing the keys with JudyHS
and they utilize a double-linked-list for the traversal operations. Deletion is the most expensive operation, usually somewhat slower than insertion.
Memory management
Dictionaries come with 2 memory management options:
- Clone (copy) the
name
and/or thevalue
to memory allocated by the dictionary. - Link the
name
and/or thevalue
, without allocating any memory about them.
In clone mode, the dictionary guarantees that all operations on the dictionary items, will automatically take care of the memory used by the name
and/or the value
. In case the value
is an object that needs to have user allocated memory, the following callback functions can be registered:
dictionary_register_insert_callback()
that can be called just after the insertion of an item to the dictionary, or after the replacement of the value of a dictionary item.dictionary_register_delete_callback()
that will be called just prior to the deletion of an item from the dictionary, or prior to the replacement of the value of a dictionary item.dictionary_register_conflict_callback()
that will be called whenDICT_OPTION_DONT_OVERWRITE_VALUE
is set, and anothervalue
is attempted to be inserted for the same key.dictionary_register_react_callback()
that will be called after the theinsert
and theconflict
callbacks. Theconflict
callback is called while the dictionary hash table is available for other threads.
In link mode, the name
and/or the value
are just linked to the dictionary item, and it is the user's responsibility to free the memory they use after an item is deleted from the dictionary or when the dictionary is destroyed.
By default, clone mode is used for both the name and the value.
To use link mode for names, add DICT_OPTION_NAME_LINK_DONT_CLONE
to the flags when creating the dictionary.
To use link mode for values, add DICT_OPTION_VALUE_LINK_DONT_CLONE
to the flags when creating the dictionary.
Locks
The dictionary allows both single-threaded operation (no locks - faster) and multi-threaded operation utilizing a read-write lock.
The default is multi-threaded. To enable single-threaded add DICT_OPTION_SINGLE_THREADED
to the flags when creating the dictionary.
When in multi-threaded mode, the dictionaries have 2 independent R/W locks. One for the linked list and one for the hash table (index). An insertion and a deletion will acquire both independently (one after another) for as long as they are needed, but a traversal may hold the the linked list for longer durations. The hash table (index) lock may be acquired while the linked list is acquired, but not the other way around (and the way the code is structured, it is not technically possible to hold and index lock and then lock the linked list one).
These locks are R/W locks. They allow multiple readers, but only one writer.
Unlike POSIX standards, the linked-list lock, allows one writer to lock it multiple times. This has been implemented in such a way, so that a traversal to the items of the dictionary in write-lock mode, allows the writing thread to call dictionary_set()
or dictionary_del()
, which alter the dictionary index and the linked list. Especially for the deletion of the currently working item, the dictionary support delayed removal, so it will remove it from the index immediately and mark it as deleted, so that it can be added to the dictionary again with a different value and the traversal will still proceed from the point it was.