2024q1 Homework2 (quiz1+2)

contributed by < YangYeh-PD >

Linked List and its Relevant APIs

Consider the structure node definition,

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

we can construct a linked list by the following APIs.

void list_add(node_t **list, node_t *node)
node_t *list_tail(node_t **left)
int list_length(node_t **left)
node_t *list_construct(node_t *list, int n)
void list_free(node_t **list)

list_add()

void list_add(node_t **list, node_t *node)
{
    node->next = *list;
    *list = node;
}

The first parameter is the indirect pointer list of the head of the linked list, and the second parameter is the pointer of the node we want to add. Since we directly change the next of the node points to *list (the head of the list), then update the *list points to the new node, the function adds the node onto the front of the linked list.

list_tail()

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &((*left)->next);
    return *left;
}

Again, we pass the indirect pointer left of the linked list as a parameter into the function.

• If the linked list is empty (or null), the while condition would be false and breaks the loop, then return the pointer (*left) directly.
• If the linked list is nonempty, the loop will keep executing until the next of the node where *left points to is empty (or null), then return the pointer *left.
  Base on these rules, the function is to find the tail of the linked list.

list_length()

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &((*left)->next);
    }
    return n;
}

The function again pass the indirect pointer left as a parameter. We ++n and reassign left to the pointer of the next node in each literation, then return n when the loop breaks.

list_construct()

node_t *list_construct(node_t *list, int n)
{
    node_t *node = malloc(sizeof(node_t));
    node->next = list;
    node->value = n;
    return node;
}

First of all, we allocate a memory with size of node_t saved by the pointer node. Then we modify the next points to the list and assign the value n, and return the pointer node.

list_free()

void list_free(node_t **list)
{
    node_t *node = (*list)->next;
    while (*list) {
        free(*list);
        *list = node;
        if (node)
            node = node->next;
    }
}

We pass the indirect pointer list as a parameter.
First, we declare the pointer node and initialize with the next which points to the next node of the head of the linked list. (Since we cannot access the memories anymore once we free them). Then we free the memory of each nodes until the last one.

Problem 1: Quicksort (Non-recursive)

How it works

We can make a non-recursive quicksort algorithm by the following functions.

Before making a list of code snip, describe the concepts and considerations!

list_is_ordered()

static bool list_is_ordered(node_t *list)
{       
    bool first = true;
    int value;
    while (list) {
        if (first) {
            value = list->value;
            first = false;
        } else {
            if (list->value < value)
                return false;
            value = list->value;
        }
        list = list->next;
    }
    return true;
}

The function that check whether the linked list is in ordered. As we can see, the literation especially skip the first node of the linked list, which is the special case. We can avoid it by checking whether the current and the next node is NULL, and compare two adjacent nodes at once.

static bool list_is_ordered(node_t *list) {
    while(list && (list->next)) {
        if (list->value > list->next->value) {
            return false;
        }
        list = list->next;
    }
    return true;
}

shuffle()

void shuffle(int *array, size_t n)
{
    if (n <= 0)
        return;

    for (size_t i = 0; i < n - 1; i++) {
        size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
        int t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

This function shuffle the array into random order.

TODO: Make it computationally better.

quick_sort()

The following non-recursive quicksort is not same as in Optimized QuickSort - C Implementation (Non-recursive), since such the implementation needs doubly linked list, which is contradict to our current node_t conrfiguration.

1. We first pick the first entry of the list as the pivot, and assignment the first and the last entry to begin[0] and end[0] respectively.

node_t *L = begin[i], *R = end[i];
if (L != R) {
    node_t *pivot = L;
    value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;
}

2. Then we traverse each entry, and add the entries with smaller number to the left and larger ones to the right.

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

3. begin[] stores all of the entries for the following iteration, and end[] records the tail of each begin element.

    begin[i] = left;
+   end[i] = list_tail(&begin[i]);
    begin[i + 1] = pivot;
    end[i + 1] = pivot;
    begin[i + 2] = right;
+   end[i + 2] = list_tail(&begin[i + 2]);    

4. The next iteration begin and continue to begin[2] splice the list, until begin[i] == end[i].

At this point, since begin[1] ~ begin[4] cannot be divided anymore, we add them to result

list_add(&result, L);

For begin[0], we continue the iteration and it will add them to result in ascending order.

But left and right in node_t seem useless…
ChenYang YehThu, Mar 7, 2024 14:43 PM

Further Improvements

left and right in node_t seem to be useless, maybe we can make the best used of it.

Using Linux Kernel List API

How to Avoid Worst Cases in Quicksort?

Linux Kernel Style Linked List

In the figure below, in linux/list.h, the linked list is actually implemented by using doubly circular linked list list_head.

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

Both prev and next are pointers of the list_head type, pointing to the type itself. In this, we can easily observe that from the beginning, the Linux kernel does not specify the data type to be stored, significantly increasing the flexibility of linked lists in the design of the Linux kernel.

If we want to store integer data in the linked list, we only need to include the definition of list_head in list.h and then implement an additional struct.

struct item {                         
    int value;
    struct list_head list;
};

To make manipulating this linked list more convenient, the Linux kernel provides corresponding APIs for our use.

#define list_first_entry(ptr, type, field)
#define list_last_entry(ptr, type, field)
#define list_for_each(p, head)
#define list_for_each_safe(p, n, head
void INIT_LIST_HEAD(struct list_head *list)
void __list_add(struct list_head *new,
                struct list_head *prev,
                struct list_head *next)
void list_add(struct list_head *_new, struct list_head *head)
void __list_del(struct list_head *entry)
void list_del(struct list_head *entry)
void list_move(struct list_head *entry, struct list_head *head)

list_first_entry() / list_last_entry()

Return the first and the last entry of the linked list.
Since the linked list is circular and doubly, we can simply define the macro as

#define list_first_entry(ptr, type, field) list_entry((ptr)->next, type, field)
#define list_last_entry(ptr, type, field) list_entry((ptr)->prev, type, field)

list_for_each()

It use for loop traverses all entries of hlist, but cannot remove nodes.
It would end once pos == head.

#define list_for_each(p, head) for (p = (head)->next; p != head; p = p->next)

list_for_each_safe()

There have two variables in the for loop.

• pos : points to the current entry.
• n : points to the next entry.

Thus, it allows us to remove the node during traversal.

#define list_for_each_safe(p, n, head) \
    for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next)

INIT_LIST_HEAD()

Initialized the head of the list.

void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

__list_add() / list_add()

Add the node new between the previous node prev and the next node next.

void __list_add(struct list_head *new,
                struct list_head *prev,
                struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

Thus, the function of list_add is adding the node new to the head of the list head.

void list_add(struct list_head *_new, struct list_head *head)
{
    __list_add(_new, head, head->next);
}

__list_del() / list_del()

Remove the node entry from the list.

void __list_del(struct list_head *entry)
{
    entry->next->prev = entry->prev;
    entry->prev->next = entry->next;
}

And list_del() initializes entry after it is removed from the list.

void list_del(struct list_head *entry)
{
    __list_del(entry);
    entry->next = entry->prev = NULL;
}

list_move()

Move the node entry to the new linked list head.

void list_move(struct list_head *entry, struct list_head *head)
{
    __list_del(entry);
    list_add(entry, head);
}

So it just divided into 2 steps.

• Remove entry from the old list.
• Add it to the new list head.

Problem 2: Timsort

Linked List for Hash Table

Consider a following definition of structure

struct hlist_node {
    struct hlist_node *next, **pprev;
};

struct hlist_head {
    struct hlist_node *first;
};

where hlist_head points to the first element of the hlist.
Since pprev is an indirect pointer to itself, we may illustrate the graph like this.

and again, there are several relevant APIs we can use

#define container_of(ptr, type, member)
#define list_entry(ptr, type, member)
#define hlist_for_each(pos, head)
#define hlist_for_each_safe(pos, n, head)
static inline void INIT_HLIST_HEAD(struct hlist_head *h)
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
static inline void hlist_del(struct hlist_node *n)

container_of() / list_entry()

Given a member pointer, structure name and the member name, it would return the pointer to the beginning of the structure.

#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) - (size_t) & (((type *) 0)->member)))

#define list_entry(ptr, type, member) container_of(ptr, type, member)

In ISO/IEC 9899 §7.17 3, C standard library provides a macro offsetof() which returns the offset of the member.

offsetof(type, member-designator) which expands to an integer constant expression that has type size_t, the value of which is the offset in bytes, to the structure member, from the beginning of its structure (designated by type).

offsetof() is defined as

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE*)0)->MEMBER)

Thus,

((type *) ((char *) (ptr) - (size_t) & (((type *) 0)->member)))

means the address to the head of the type.

What is the meaning of ((TYPE*)0)->MEMBER? I still cannot understand in stackoverflow.ChenYang YehSat, Mar 9, 2024 19:03 PM

hlist_for_each()

It use for loop traverses all entries of hlist, but cannot remove nodes.
It would end once pos == NULL.

#define hlist_for_each(pos, head) \
    for (pos = (head)->first; pos; pos = pos->next)

hlist_for_each_safe()

There have two variables in the for loop.

• pos : points to the current entry.
• n : points to the next entry.

Thus, it allows us to remove the node during traversal.

#define hlist_for_each_safe(pos, n, head)        \
    for (pos = (head)->first; pos && ({          \
                                  n = pos->next; \
                                  true           \
                              });                \
         pos = n)

Note that {n = pos->next; true} is a compound statement, which always return the value of last expression. So it assign pos->next to n, then return true.

INIT_HLIST_HEAD()

Initializing hlist_head to NULL.

static inline void INIT_HLIST_HEAD(struct hlist_head *h)
{
    h->first = NULL;
}

hlist_add_head()

It adds node n at the beginning of the hlist h.

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = h->first;
    n->pprev = &h->first;
    h->first = n;
}

It first modifies the indirect pointer pprev of the first node points to the address of n->next, and modify next and pprev of n point to the h->first and &h->first respectively, then make h->first point to n.

hlist_del()

Remove the node n from the list.

void hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;
    if (next)
        next->pprev = pprev;
}

First define next as a pointer to the next entry of n and pprev as an indirect pointer to n itself.
To remove the node n, just simply change the pointer pprev to next and the pprev of the next node to pprev.

Problem 3: Building Tree

How it works

We first define the node of the tree TreeNode and the node order node.

struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};

struct order_node {
    struct hlist_node node;
    int val;
    int idx;
};

All of order_node would be added into hash table by the following node_add().

node_add()

This function add the node on into the hash table heads.
The idx is the index of the inorder array, and hash is the result of hash function.

$$h(x)=|x|\mathrm{mod}\text{size}.$$
After

$h(x)$ is calculated, on would be added into the corresponding bucket.

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, DDDD);
}

find()

Find the node in hash table, then return its index in inorder array. Return -1 if it doesn't find the node.

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, &heads{hash}) {
        struct order_node *on = list_entry(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

dfs()

dfs() constructs a tree in recursive manner.
Both preorder and inorder are array of integers, which are used to store the preorder and inorder array given by user.
pre_low, pre_high, in_low and in_high are used to record the range of preorder and inorder array in each level of recursion, which is quite important in this implementaiton.

static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)

Once it is called, it first check whether both arrays are out of range, if so, directly return NULL.

{
    if (in_low > in_high || pre_low > pre_high)
            return NULL;

Then allocates sizeof(TreeNode) memories to tn, use preorder[pre_low] as the root (or parent) node.

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];

Finally, use find() to find the idx of the node in inorder array, then recursively add left and right childs based on arrays range and idx.

    int idx = find(preorder[pre_low], size, in_heads);
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}

The rule of preorder traversal in binary tree visits the current (or parent) node first, then traverse left and right childs.

struct NodeTree *preOrder(struct NodeTree* root) 
{
    if(!root) {
        return;
    }
    printf("%d ", root->val);
    preOrder(root->left);
    preOrder(root->right);
}

Maybe it can be done iteratively.ChenYang YehSat, Mar 9, 2024 18:23 PM

And in inorder traversal, it visits the left child first, then the parent node and right child.

struct NodeTree *inOrder(struct NodeTree* root) 
{
    if(!root) {
        return;
    }
    preOrder(root->left);
    printf("%d ", root->val);
    preOrder(root->right);
}

So, the first few element in preorder should be the root or parent nodes in the tree. Once we determine the parent node, we can partition inorder array base on idx of the parent node. Those who has smaller index in inorder array should be assigned to left subtree, and vice versa.

$$\text{inorder range}=\begin{array}{rl}\text{in\_low ~ idx - 1},& \text{ left}\\ \text{idx + 1 ~ in\_high},& \text{ right}\end{array}$$

We can verify the result by post ordered tree traversal.

I still not figure out why the range of preorder array should be

$$\text{preorder range}=\begin{array}{rl}\text{pre\_low + 1 ~ pre\_low + (idx - in\_low)},& \text{ left}\\ \text{pre\_high - (in\_high - idx - 1) ~ pre\_high},& \text{ right}\end{array}$$
ChenYang YehSat, Mar 9, 2024 19:04 PM

Further Improvements

Linux Kernel cgroups

preorder walk.

Problem 4: LRU Cache

Least Recently Used (LRU) cache is a type of caching mechanism used in computer systems, particularly in the context of managing memory or storage.
The goal of an LRU cache is to keep track of the usage patterns of various items and prioritize the retention of the most recently used items while evicting the least recently used items when the cache reaches its capacity.
LRU cache can also help lower the rate of cache misses in certain scenarios and remain good temporal locality.

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output 
[null, null, null, 1, null, -1, null, -1, 3, 4]

* means LRU Cache.

How it works

We first define the structure of LRUCache and LRUNode.

typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;

lRUCacheCreate()

Create a LRUCache node, and initializes all of dhead and all of hlist_head in the array.

LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
                             capacity * sizeof(struct list_head));
    cache->capacity = capacity;
    cache->count = 0;
    INIT_LIST_HEAD(&cache->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_HLIST_HEAD(&cache->hhead[i]);
    return cache;
}

Note that since the definition of LRUCache is imcompleted type, we cannot use malloc(sizeof(LRUCache)) directly.

Perhaps malloc(2 * sizeof(int) + sizeof(struct list_head) + capacity * sizeof(struct hlist_head)) is more reasonable. ChenYang YehSat, Mar 9, 2024 23:52 PM

lRUCacheFree()

Free LRUCache and its relevant LRUNode.

void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, FFFF);
        list_del(GGGG);
        free(cache);
    }
    free(obj);
}

lRUCacheGet()

move the LRUNode in the hash table with key to dhead of LRUCache, then return its value.

int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *cache = list_entry(pos, LRUNode, node);
        if (cache->key == key) {
            list_move(&cache->link, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}

It would first search LRUNode with key in certain bucket in hash table, if the object is successfully found, move it to the beginning of dhead and return value, if not, return -1.
The hash function is

$$h(\text{key})=\text{key }\mathrm{\%}\text{ capacity}.$$
So at this point, we know that the hash table in LRUCache is used to store the LRUNode for

$O(1)$ finding complexity.

Of course the hash function can be redesigned, or it may not meet SUHA condition when capacity is large.
ChenYang YehSun, Mar 10, 2024 01:01 AM

lRUCachePut()

There are two circumstances in lRUCachePut().

• If CacheNode we want can be found in the hash table of obj, then move it to the beginning of dhead and change its value to value.

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *cache = NULL;
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *c = list_entry(pos, LRUNode, node);
        if (c->key == key) {
            list_move(&c->link, &obj->dhead);
            cache = c;
        }
    }

• If the CacheNode we want cannot be found in hash table,
  • If the cache is full (count == capacity), then we directly remove the last LRUNode in dhead, then add it into the beginning of dhead again and change its value.
  • If the cache isn't full, then allocated the memory for LRUNode, and add it to the dhead and hash table.

    if (!cache) {
        if (obj->count == obj->capacity) {
            cache = list_last_entry(&obj->dhead, LRUNode, link);
            list_move(&cache->link, &obj->dhead);
            hlist_del(&cache->node);
            hlist_add_head(&cache->node, &obj->hhead[hash]);
        } else {
            cache = malloc(sizeof(LRUNode));
            hlist_add_head(&cache->node, &obj->hhead[hash]);
            list_add(&cache->link, &obj->dhead);
            obj->count++;
        }
        cache->key = key;
    }
    cache->value = value;
}

Improvements

LRU in Linux Kernel

Problem 5: Find nth Bit

You shall explain why such routine exists in the Linux kernel and other applications.

How it works

We need to figure out the following macro first.

#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
#define __const_hweight8(w) 

BITMAP_LAST_WORK_MASK()

The purpose of this macro is to generate a bitmask for a bitmap with a specified number of bits nbits. Note that since in most Unix and Unix-like systems using LP64 data model, we cannot directly use 0UL in 32-bit architecture, or it will lead to an error.

$ ./bitmap
Bitmask for setting the last 5 bits to 1: 0b11111111111111111111111111111111

We need to declare 32-bit unsigned integer by our own.

#include <stdio.h>
#include <stdint.h>

uint32_t zero = 0;

#define BITS_PER_LONG 32  // Assume 64 bits for this example
#define BITMAP_LAST_WORD_MASK(nbits) (~(zero) >> (-(nbits) & (BITS_PER_LONG - 1)))

$ ./bitmap
Bitmask for setting the last 5 bits to 1: 0b00000000000000000000000000011111

__const_hweight8(w)

This macro calculates the number of set bits (bits set to 1) in an 8-bit binary number, which means the count of bits that are 1 in the given number.

#define __const_hweight8(w)                                              \
    ((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
                     (!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
                     (!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
                     (!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))

The !! operator ensures that the resulting calculation yields only 0 or 1, without any other numbers.

!!(00000010) will return 1 instead of 2.

Find nth Bit in Linux Kernel