C28 Hash Lists

The kernel also provides an adapted version of doubly linked lists that is especially suitable to implement overflow lists in hash tables. In this case, the list elements are also embedded into other data structures, but there is an asymmetry between the list head and the list elements:

struct hlist_head {

struct hlist_node *first;

struct hlist_node {

struct hlist_node *next, **pprev;

The list elements themselves are still doubly linked, but the list head is connected with the list by a single pointer. The end of the list cannot be accessed in constant time any more, but this is usually never required for hash lists anyway. Instead, the containing data structure becomes slightly smaller because only one pointer instead of two is required. To manipulate hash lists, essentially the same API can be used as for regular lists. The only difference is that list must be replaced by hlist — so list_add_head will become hlist_add_head; list_del will become hlist_del. It's all quite logical.

As for lists, it is possible to use the RCU mechanism to provide protection against concurrent access. If this is desired, the hash list operations must be postfixed with _rcu — for instance, hlist_del_rcu to delete a list element. See Chapter 5 for a description of the protection that the RCU mechanism offers.

Continue reading here: C29 Red Black Trees

Was this article helpful?

0 0