oshogbo//vx

My place in space

Introduction to nvlist part 3 - simple traversing

Oct. 31, 2017, 11:17 p.m.

Nvlist allows us to keep pairs (name, value). The question for today is what if the name of an element is unknown? Or what if there is a need to traverse over all elements on a list? First of all there is the nvlist_next() function. This function allows to iterate over one single list. The return value is the name of the next element on the list or NULL if the list is ends. The additional information which is returned by this function is the type of the element. Thanks to these two values (the name of the element and it’s type) we can decide which function to use. The last element is secret cookie which refers to the position where we are on the list. At the beginning the cookie needs to be initialized by NULL otherwise the program will behave abnormally.

Going back to the simple traverse, let’s examine the code below:
void *cookie;
const char *name;
int type;

cookie = NULL;
while ((name = nvlist_next(nvl, &type, &cookie)) != NULL) {
    printf("%s = ", name);
    switch (type) {
    case NV_TYPE_STRING:
        printf("%s\n", nvlist_get_string(nvl, name));
        break;
    case NV_TYPE_BOOL:
        printf("%d\n", nvlist_get_bool(nvl, name));
        break;
    default:
        err(1, "Unexpected type");
    }
}
The code above which traverses the whole list supports two types: STRING and BOOL. The nvlist_next function returns a type of an element which has been checked. In case of STRING the nvlist_get_string function is used to fetch the element, if it’s BOOL the nvlist_get_bool function is used. If another type of element will be used the default statement will be executed.

So what if there is a need to remove an element during traversing? The cookie points to the current element so if we will remove it from nvlist our cookie will be out-of-date. If we would like to do so we should fetch the next element before removing the current one.
void *cookie;
const char *name, *nextname;
char *value, *tmpname;
int type, nexttype;

cookie = NULL;
name = nvlist_next(nvl, &type, &cookie);

do {
    nextname = nvlist_next(nvl, &nexttype, &cookie);

    switch (type) {
    case NV_TYPE_STRING:
        printf("%s = ", name);
        value = nvlist_take_string(nvl, name);
        printf("%s\n", value);
        free(value);
        break;
    case NV_TYPE_BOOL:
        nvlist_free_bool(nvl, name);
        break;
    default:
        err(1, "Unexpected type");
    }

    name = nextname;
    type = nexttype;
} while (name != NULL);
The example above is very similar to the previous one. The difference is that in case of STRING we use the take function to remove the element from the list. In this code the name is printed before removing the element, that is an intentional operation. When the element will be removed  from the list the name of it will be released so there will not be any information about it’s name. In the case of BOOL the element is not printed but just freed up using the nvlist_free_bool function.

By default names in nvlist are unique. This means that it is not possible to have different elements (the type doesn't matter) with the same name. However there is a possibility to create nvlist with non-unique names using the NV_FLAG_NO_UNIQ flag. The problem with this is if there will be 3  elements on nvlist with the same name, the fetch functions use the name to distinguish which element is needed. Due the fact that all elements have the same name there will be an attempt to only fetch the first element three times. There are a couple of hacks to accomplish this such as cloning the entire nvlist and remove elements from the list instead of fetching them. Fortunately there is an extension called cnv. This extension is used to fetch elements using cookie instead of a name. This also optimizes the code. Standard fetch operations need to go over the entire list to find the element because the name is used as a filter. If a cookie is used then access to the element is instantaneous. Let’s examine the code below which uses the cnv extension:
void *cookie;
const char *name;
int type;

nvl = nvlist_create(NV_FLAG_NO_UNIQUE);
nvlist_add_string(nvl, "test", "cat");
nvlist_add_string(nvl, "test", "dog");

cookie = NULL;
while ((name = nvlist_next(nvl, &type, &cookie)) != NULL) {
    printf("%s = ", name);
    switch (type) {
    case NV_TYPE_STRING:
        printf("%s\n", cnvlist_get_string(cookie));
        break;
    default:
        err(1, "Unexpected type");
    }
}
First nvlist is created. The NV_FLAG_NO_UNIQ is used which means that it can contain multiple elements with the same name. Secondly two elements with name “test” are added. While iterating over the list there is an expectation that only elements with STRING types appear on the list. In the code above the fetch functions which use cookies are used.

Dnv and cnv are two very useful extensions which can optimize access to elements on a list. If the list is very short, using these extensions are like micro optimizations but the assumption of nvlist is that it’s a general purpose container so we don’t know how many elements there will be on the list. So to simplify and optimize the code these two extensions should be used. Also it is recommended to use cnvlist while traversing a list with NO_UNIQUE flag otherwise we can create a bug and fetch the same element multiple times.