oshogbo//vx

My place in space

Introduction to nvlist part 4 - cnvlist

July 27, 2018, 10:58 p.m.

The nvlist is a very useful container but, sometimes, using the name of an element to fetch it may be less than optimal, or even impossible. Let us consider two scenarios:
- We are traversing a list which was created with an NV_FLAG_NO_UNIQUE flag.
- We are traversing very large list.

Normally, if we have created nvlist we cannot add multiple elements with same name. The NV_FLAG_NO_UNIQUE flag to the nvlist_create(9) function allows us do this. Unfortunately, this creates some issues. Let's assume we have two elements with the same name, “test”, but which have different values. When we are trying to fetch “test” using its name, we always will get the first element. The code below shows that behavior:
nvlist_t *nvl;
const char *name;
void *cookie;

nvl = nvlist_create(NV_FLAG_NO_UNIQUE);
nvlist_add_string(nvl, "test", "first");
nvlist_add_string(nvl, "test", "second");

cookie = NULL;
for ((name = nvlist_next(nvl, NULL, &cookie)) != NULL)
    printf("%s\n", nvlist_get_string(nvl, name));

This code will print "first" twice because, when we are traversing nvlist using the get function, the first occurrence of the name will always be returned.

Let's analyze the code snippet one more time, but let's assume there are 1000 elements on nvlist, and we want to fetch 500th element. What happens when we use the nvlist_get function? We again traverse from the beginning of the list over the to the 500th element. Our for loop instead of being O(n) is O(n2) complexity.

After identifying those two problems, we started looking for a solution for them. If you look very closely at our code snippet you will see we used a special cookie to track where we are as we are traversing a list. Internally this cookie contains all the information about an element. So why not use it to fetch the element? This is how the cnvlist API was created. The cnvlist functions are a similar set of functions to those of the nvlist, but instead of fetching an element using a name, it fetches it using a cookie, because the cookie contains the exact information about an element in a list. Let's look at some examples of this:
nvlist_t *nvl;
const char *name;
void *cookie;

nvl = nvlist_create(NV_FLAG_NO_UNIQUE);
nvlist_add_string(nvl, "test", "first");
nvlist_add_string(nvl, "test", "second");

cookie = NULL;
for ((name = nvlist_next(nvl, NULL, &cookie)) != NULL)
    printf("%s\n", cnvlist_get_string(cookie));

The code didn't have to change a lot but, thanks to using the cnvlist, we eliminated both of our problems. First of all, we iterate only once over a list. The cookie contains the information about an element in the list so we don't need to iterate over and over again to find a matching name. The cookie is also resistant to problems with no unique names – when we have an element, we will not stop on the first occurrence of its name. Finally, we achieved what we wanted to - the code above will print, "first", and, "second", respectively, and with O(n) complexity!