summaryrefslogtreecommitdiffstats
path: root/libnetdata/dictionary/README.md
diff options
context:
space:
mode:
Diffstat (limited to 'libnetdata/dictionary/README.md')
-rw-r--r--libnetdata/dictionary/README.md74
1 files changed, 56 insertions, 18 deletions
diff --git a/libnetdata/dictionary/README.md b/libnetdata/dictionary/README.md
index 28d0cfbbd..879c1bcc1 100644
--- a/libnetdata/dictionary/README.md
+++ b/libnetdata/dictionary/README.md
@@ -22,7 +22,7 @@ Dictionaries are **ordered**, meaning that the order they have been added is pre
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.
+Dictionaries are extremely fast in all operations. They are indexing the keys with `JudyHS` (or `AVL` when `libJudy` is not available) and they utilize a double-linked-list for the traversal operations. Deletion is the most expensive operation, usually somewhat slower than insertion.
## Memory management
@@ -31,13 +31,13 @@ Dictionaries come with 2 memory management options:
- **Clone** (copy) the name and/or the value to memory allocated by the dictionary.
- **Link** the name and/or the value, 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 needs to have user allocated memory, the following callback functions can be registered:
+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:
1.`dictionary_register_insert_callback()` that will be called just after the insertion of an item to the dictionary, or after the replacement of the value of a dictionary item (but while the dictionary is write-locked - if locking is enabled).
2. `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 (but while the dictionary is write-locked - if locking is enabled).
3. `dictionary_register_conflict_callback()` that will be called when `DICTIONARY_FLAG_DONT_OVERWRITE_VALUE` is set and another value is attempted to be inserted for the same key.
-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 used after an item is deleted from the dictionary.
+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.
@@ -63,7 +63,7 @@ The dictionary supports the following operations supported by the hash table:
Use `dictionary_create()` to create a dictionary.
-Use `dictionary_destroy()` to destroy a dictionary. When destroyed, a dictionary frees all the memory it has allocated on its own. The exception is the registration of a deletion callback function that can be called on deletion of an item, which may free additional resources.
+Use `dictionary_destroy()` to destroy a dictionary. When destroyed, a dictionary frees all the memory it has allocated on its own. This can be complemented by the registration of a deletion callback function that can be called upon deletion of each item in the dictionary, which may free additional resources.
### dictionary_set()
@@ -72,7 +72,7 @@ This call is used to:
- **add** an item to the dictionary.
- **reset** the value of an existing item in the dictionary.
-If **resetting** is not desired, add `DICTIONARY_FLAG_DONT_OVERWRITE_VALUE` to the flags when creating the dictionary. In this case, `dictionary_set()` will return the value of the original item found in the dictionary instead of resetting it and the value passed to the call will be ignored.
+If **resetting** is not desired, add `DICTIONARY_FLAG_DONT_OVERWRITE_VALUE` to the flags when creating the dictionary. In this case, `dictionary_set()` will return the value of the original item found in the dictionary instead of resetting it and the value passed to the call will be ignored. Optionally a conflict callback function can be registered, to manipulate (probably merge or extend) the original value, based on the new value attempted to be added to the dictionary.
For **multi-threaded** operation, the `dictionary_set()` calls get an exclusive write lock on the dictionary.
@@ -89,14 +89,16 @@ Where:
* `value` is a pointer to the value associated with this item. In **clone** mode, if `value` is `NULL`, a new memory allocation will be made of `value_len` size and will be initialized to zero.
* `value_len` is the size of the `value` data. If `value_len` is zero, no allocation will be done and the dictionary item will permanently have the `NULL` value.
-> **IMPORTANT**<br/>There is also an **unsafe** version (without locks) of this call. This is to be used when traversing the dictionary. It should never be called without an active lock on the dictionary, which can only be acquired while traversing.
+> **IMPORTANT**<br/>There is also an **unsafe** version (without locks) of this call. This is to be used when traversing the dictionary in write mode. It should never be called without an active lock on the dictionary, which can only be acquired while traversing.
### dictionary_get()
-This call is used to get the value of an item, given its name. It utilizes the JudyHS hash table for making the lookup.
+This call is used to get the value of an item, given its name. It utilizes the `JudyHS` hash table for making the lookup.
For **multi-threaded** operation, the `dictionary_get()` call gets a shared read lock on the dictionary.
+In clone mode, the value returned is not guaranteed to be valid, as any other thread may delete the item from the dictionary at any time. To ensure the value will be available, use `dictionary_get_and_acquire_item()`, which uses a reference counter to defer deletes until the item is released.
+
The format is:
```c
@@ -114,7 +116,7 @@ Where:
This call is used to delete an item from the dictionary, given its name.
-If there is a delete callback registered to the dictionary (`dictionary_register_delete_callback()`), it is called prior to the actual deletion of the item.
+If there is a deletion callback registered to the dictionary (`dictionary_register_delete_callback()`), it is called prior to the actual deletion of the item.
For **multi-threaded** operation, the `dictionary_del()` calls get an exclusive write lock on the dictionary.
@@ -131,29 +133,65 @@ Where:
> **IMPORTANT**<br/>There is also an **unsafe** version (without locks) of this call. This is to be used when traversing the dictionary, to delete the current item. It should never be called without an active lock on the dictionary, which can only be acquired while traversing.
+### dictionary_get_and_acquire_item()
+
+This call can be used the search and get a dictionary item, while ensuring that it will be available for use, until `dictionary_acquired_item_release()` is called.
+
+This call **does not return the value** of the dictionary item. It returns an internal pointer to a structure that maintains the reference counter used to protect the actual value. To get the value of the item (the same value as returned by `dictionary_get()`), the function `dictionary_acquired_item_value()` has to be called.
+
+Example:
+
+```c
+// create the dictionary
+DICTIONARY *dict = dictionary_create(DICTIONARY_FLAGS_NONE);
+
+// add an item to it
+dictionary_set(dict, "name", "value", 6);
+
+// find the item we added and acquire it
+void *item = dictionary_get_and_acquire_item(dict, "name");
+
+// extract its value
+char *value = (char *)dictionary_acquired_item_value(dict, item);
+
+// now value points to the string "value"
+printf("I got value = '%s'\n", value);
+
+// release the item, so that it can deleted
+dictionary_acquired_item_release(dict, item);
+
+// destroy the dictionary
+dictionary_destroy(dict);
+```
+
+When items are acquired, a reference counter is maintained to keep track of how many users exist for it. If an item with a non-zero number of users is deleted, it is removed from the index, it can be added again to the index (without conflict), and although it exists in the linked-list, it is not offered during traversal. Garbage collection to actually delete the item happens every time a write-locked dictionary is unlocked (just before the unlock) and items are deleted only if no users are using them.
+
+If any item is still acquired when the dictionary is destroyed, the destruction of the dictionary is also deferred until all the acquired items are released. When the dictionary is destroyed like that, all operations on the dictionary fail (traversals do not traverse, insertions do not insert, deletions do not delete, searches do not find any items, etc). Once the last item in the dictionary is released, the dictionary is automatically destroyed too.
+
## Traversal
-Dictionaries offer 2 ways to traverse the entire dictionary:
+Dictionaries offer 3 ways to traverse the entire dictionary:
- **walkthrough**, implemented by setting a callback function to be called for every item.
+- **sorted walkthrough**, which first sorts the dictionary and then call a callback function for every item.
- **foreach**, a way to traverse the dictionary with a for-next loop.
-Both of these methods are available in **read** or **write** mode. In **read** mode only lookups are allowed to the dictionary. In **write** both lookups but also deletion of the currently working item is also allowed.
+All these methods are available in **read** or **write** mode. In **read** mode only lookups are allowed to the dictionary. In **write** lookups but also insertions and deletions are allowed.
-While traversing the dictionary with any of these methods, all calls to the dictionary have to use the `_unsafe` versions of the function calls, otherwise deadlock may arise.
+While traversing the dictionary with any of these methods, all calls to the dictionary have to use the `_unsafe` versions of the function calls, otherwise deadlocks may arise.
> **IMPORTANT**<br/>The dictionary itself does not check to ensure that a user is actually using the right lock mode (read or write) while traversing the dictionary for each of the unsafe calls.
### walkthrough (callback)
-There are 2 calls:
+There are 4 calls:
-- `dictionary_walkthrough_read()` that acquires a shared read lock, and it calls a callback function for every item of the dictionary. The callback function may use the unsafe versions of the `dictionary_get()` calls to lookup other items in the dictionary, but it should not add or remove item from the dictionary.
-- `dictionary_walkthrough_write()` that acquires an exclusive write lock, and it calls a callback function for every item of the dictionary. This is to be used when items need to be added to the dictionary, or when the current item may need to be deleted. If the callback function deletes any other items, the behavior may be undefined (actually, the item next to the one currently working should not be deleted - a pointer to it is held by the traversal function to move on traversing the dictionary).
+- `dictionary_walkthrough_read()` and `dictionary_sorted_walkthrough_read()` that acquire a shared read lock, and they call a callback function for every item of the dictionary. The callback function may use the unsafe versions of the `dictionary_get()` calls to lookup other items in the dictionary, but it should not attempt to add or remove items to/from the dictionary.
+- `dictionary_walkthrough_write()` and `dictionary_sorted_walkthrough_write()` that acquire an exclusive write lock, and they call a callback function for every item of the dictionary. This is to be used when items need to be added to or removed from the dictionary. The `write` versions can be used to delete any or all the items from the dictionary, including the currently working one. For the `sorted` version, all items in the dictionary maintain a reference counter, so all deletions are deferred until the sorted walkthrough finishes.**
-The items are traversed in the same order they have been added to the dictionary (or the reverse order if the flag `DICTIONARY_FLAG_ADD_IN_FRONT` is set during dictionary creation).
+The non sorted versions traverse the items in the same order they have been added to the dictionary (or the reverse order if the flag `DICTIONARY_FLAG_ADD_IN_FRONT` is set during dictionary creation). The sorted versions sort alphabetically the items based on their name, and then they traverse them in the sorted order.
-The callback function returns an `int`. If this value is negative, traversal of the dictionary is stopped immediately and the negative value is returned to the caller. If the returned value of all callbacks is zero or positive, the walkthrough functions return the sum of the return values of all callbacks. So, if you are just interested to know how many items fall into some condition, write a callback function that returns 1 when the item satisfies that condition and 0 when it does not and the walkthrough function will return how many tested positive.
+The callback function returns an `int`. If this value is negative, traversal of the dictionary is stopped immediately and the negative value is returned to the caller. If the returned value of all callback calls is zero or positive, the walkthrough functions return the sum of the return values of all callbacks. So, if you are just interested to know how many items fall into some condition, write a callback function that returns 1 when the item satisfies that condition and 0 when it does not and the walkthrough function will return how many tested positive.
### foreach (for-next loop)
@@ -186,14 +224,14 @@ else
something else;
```
-In the above, the `if(x)` condition will work as expected. It will do the foreach loop when x is 1, otherwise it will run `something else`.
+In the above, the `if(x == 1)` condition will work as expected. It will do the foreach loop when x is 1, otherwise it will run `something else`.
There are 2 versions of `dfe_start`:
- `dfe_start_read()` that acquires a shared read lock to the dictionary.
- `dfe_start_write()` that acquires an exclusive write lock to the dictionary.
-While in the loop, depending on the read or write versions of `dfe_start`, the caller may lookup or manipulate the dictionary. The rules are the same with the walkthrough callback functions.
+While in the loop, depending on the read or write versions of `dfe_start`, the caller may lookup or manipulate the dictionary using the unsafe functions. The rules are the same with the unsorted walkthrough callback functions.
PS: DFE is Dictionary For Each.