# 2022q1 Homework1 (quiz1)
contributed by < [cantfindagoodname](https://github.com/cantfindagoodname) >
> [題目](https://hackmd.io/@sysprog/linux2022-quiz1)

## 實驗環境

$ cat /proc/version
Linux version 5.13.0-30-generic (buildd@lcy02-amd64-003) (gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0, GNU ld (GNU Binutils for Ubuntu) 2.34) #33~20.04.1-Ubuntu SMP Mon Feb 7 14:25:10 UTC 2022

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

## 測驗1
### 解題
The question is a multiple choice fill-in question. We are required to choose the correct answer for `AAA` and `BBB`.
:::spoiler Function where `AAA` and `BBB` reside.

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    struct hlist_node *n = &kn->node, *first = h->first;
    AAA;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    BBB;
}

:::
Assuming the code is functioning, and the name `map_add()` is correctly representing the function, we can solve this question by focusing only on `line 12-16`.

AAA;
if (first)
	first->pprev = &n->next;
h->first = n
BBB;

Note that all graphs below is just a visual representation of connection between the nodes, actual implementation may differ.

`n` is node to be added, `first` is the original first element `hlist_head` points to after hashing.

The function would try to move `n` into the bucket `hlist_head.first`, without `AAA` and `BBB`, the process is incomplete.

It should be clear that `AAA` and `BBB` would assign value to `n->pprev` and `n->next`.

As `AAA` is executed before `h->first` update its value, it should be responsible of `n->next`.
`BBB` is executed after `h->first` update its value, `BBB` would be responsible for `n->pprev`.

And so, we got the solution.
`AAA` : `n->next = first`
`BBB` : `n->pprev = &h->first`
### 分析
After writing a very simple `main()` function for the program, the solution correctness is proven.
:::spoiler

int main(int argc, char *argv[]) {
  int len = 0, target = 9, *sol = NULL, arr[4] = {2, 1, 7, 5}; 

  sol = twoSum(arr, sizeof arr, target, &len);
  printf("target %d = [", target);
  for (int i = 0; i < len; ++i)
    printf(" %d ", arr[sol[i]]);
  printf("]\n");
  return 0;
}

$ gcc main.c && ./a.out
target 9 = [ 7 2 ]

:::
---
We can know how the program works by tracing the program.

The very first step `twoSum()` did is to initialize `map`, which would initialize the hash table. Every entry of the hash table is `NULL` after initialization.

map_t *map = map_init(10);

The program would then iterate through the list of numbers one by one.
To demonstrate how the algorithm works, I first assume that the hash table is infinitely large. So that it could be seen as an array.
Let `number` $+$ `value` $=$ `target`, when the loop reaches `number`, and table[`number`] is empty, the program would fill in table[`value`], so that when it reaches `value` the program recognize that the solution is found as `number` $+$ `value` $=$ `target`.

for (int i = 0; i < numsSize; i++) {
        int *p = map_get(map, target - nums[i]);
        if (p) {
            ret[0] = i, ret[1] = *p;
            *returnSize = 2;
            break;
        }
        // ...
    }

So what if the size of the table is limited. Thats when hash table comes into play. When table[`number`] is not empty, and the solution is not present yet, we could say that hash collision has occured, the program would iterate through the chain to check for solution, then append to end of list if solution does not exist.

static struct hash_key *find_key(map_t *map, int key) {
    struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
    for (struct hlist_node *p = head->first; p; p = p->next) {
        struct hash_key *kn = container_of(p, struct hash_key, node);
        if (kn->key == key)
            return kn;
    }
    return NULL;
}

The program would use `goto` statement to move to `bail` when a part of program fails. Which i assume is to skip other procedure to the end and still free resource allocated.
### 延伸
#### `hash table`
Hash table is implemented using some macros. The table each has element of `hlist_head` and would first initialized using macros in [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h).

`hlist_head` would chain `hlist_nodes` into the same `hlist` by operations on `hlist` similar to the doubly-linked list.
`hlist_head` only uses `first` to points to `hlist_nodes` with will chain together as a circular doubly-linked list. Presumably to save space as hash table typically will not take too long to tranverse from head to tail of list when hash is well designed.

Take `has_add()` as example, the operation on hash table would take the hash value as index then do operations on the `hlist_head` at said index as the head of `hlist`.

#define hash_add(hashtable, node, key)						\
	hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])

#### `GOLDEN_RATIO`
From what I've red, the program uses golden ratio merely as a multiplicand for a [pseudo-random number generator](https://man7.org/linux/man-pages/man3/srand.3.html) for very large number. Which the result is used as hash value.

static unsigned long next = 1;

/* RAND_MAX assumed to be 32767 */
int myrand(void) {
	next = next * 1103515245 + 12345;
	return((unsigned)(next/65536) % 32768);
}

void mysrand(unsigned int seed) {
	next = seed;
}

Above is example given by POSIX.1-2001 of implementation of `rand()` and `srand()`.
Which is random number is actually just a value multiply by a very large number. Which [hash.h](https://github.com/torvalds/linux/blob/master/include/linux/hash.h#L26) chose golden ratio as the number.

static inline u32 __hash_32_generic(u32 val)
{
	return val * GOLDEN_RATIO_32;
}

Different to `myrand()` however, the hash value should be consistent given an input, so no assignment is needed after the multiplication.

When I follow the comments in the source code, they do state why they chose golden ratio as the multiplicand. However, the reason are stated from followed.
> Our multiplicative hash functions were derived from [Knuth], p. 513ff.

What I assume [Knuth] is [TAOCP](https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming), which I currently unfortunately don't have acces to.

## 測驗2
### 解題
We are required to fill in the correct answer for `COND1` and `COND2`.
:::spoiler Function where `COND1` and `COND2` reside.

#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (COND1) {
        /* Remove all duplicate numbers */
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

:::

The function is a recursive function, where the function is called recursively twice. Once inside `if (COND1)` and once right after the branch.

It is obvious what both `COND1` and `COND2` is doing.

if (COND1) {
	/* Remove all duplicate numbers */
	while (COND2)
		head = head->next;
	return deleteDuplicates(head->next);
}

As the comment in `line 14` states, it remove all duplicate numbers, `COND1` must be an expression checking if the value are duplicates.

We know that `head` is currently the duplicate number indicated by `line 13`, and `line 15-16` only tranverse through the list, `COND2` must be a expression to let `line 16` statement tranverse through the duplicates.

head->next = deleteDuplicates(head->next)

After `line 18` is a assigment to `head->next`, which means `head` itself will not be removed from the list. In `line 17` the function returns the recursive call with `head->next` as the argument. Which means that any nodes before `head->next` would never be return together with the list.

And so, we got the solution. ( check for end of list included )
`COND1` : `head->next && head->val == head->next->val`
`COND2` : `head->next && head->val == head->next->val`

### 分析
After writing a very simple `main()` function for the program, the solution correctness is proven.
:::spoiler

int main()
{
	/* assign value */
	// ...
	struct ListNode *head = deleteDuplicates(head);
	/* print value */
	// ...
}

Before  : 0 1 1 1 4 5 6 6 
After   : 0 4 5 

:::
### 延伸
#### 迭代

#include <stddef.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    struct ListNode *htemp = head, **pnext;
    while(head->next && head->val == head->next->val){
        head = head->next;
        htemp = head->next;
    }   
    while(head){
        if(head->next && head->val != head->next->val)
            pnext = &head->next;
        while(head->next && head->val == head->next->val){
            head = head->next;
            *pnext = head->next;
        }
        head = head->next;  
    }
    return htemp;
} 

The function above is not practical as the memory of removed node is lost and cannot be released anymore. But the original version also did not release memory so I just leave it be.

## 測驗3
We are required to fill in the correct answer for `MMM1`, `MMM2`, `MMM3`, and `MMM4`.
:::spoiler

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

LRUCache *lRUCacheCreate(int capacity)
{   
    LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
    obj->count = 0;
    obj->capacity = capacity;
    INIT_LIST_HEAD(&obj->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_LIST_HEAD(&obj->hheads[i]);
    return obj;
}
    
void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    MMM1 (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}   

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM2 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM3 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }

    if (obj->count == obj->capacity) {
        lru = MMM4(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}

:::
### 解題
Look at [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h), then the solution should be clear.
There are two main types of statement included in [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h), the expression statement, and the iteration statement.

Expression statement normally ends with a semicolon `;` and iteration statement ends with blocks `{}`, and occasionally null statement or another expression statement.
> Types of statement from [ \[ 6.8 \] ISO/IEC 9899](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)

In [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h), only the `for_each` macro is iteration statement.

MMM1 (lru, n, &obj->dhead, dlink) {
	list_del(&lru->dlink);
	free(lru);
}

Only `list_for_each_safe` and `list_for_each_entry_safe` have 4 arguments, `lru` is not type `list_head`, so `MMM1` must be `list_for_each_entry_safe`.

MMM2 (lru, &obj->hheads[hash], hlink) {
	if (lru->key == key) {
		list_move(&lru->dlink, &obj->dhead);
		return lru->value;
	}
}

MMM3 (lru, &obj->hheads[hash], hlink) {
	if (lru->key == key) {
		list_move(&lru->dlink, &obj->dhead);
		lru->value = value;
		return;
	}
}

`MMM2` and `MMM3` are both iteration statements. They take `lru` as argument which its type is not `list_head` and there is no `safe` argument. Both `MM2` and `MM3` are `list_for_each_entry`.

lru = MMM4(&obj->dhead, LRUNode, dlink);

`MMM4` returns a value and is a expression statement. And lru would be evicted later on. As the name suggested, the *least recently used* node should be evicted. When `lRUCachePut()` is called, from the block after `MMM3` we can see the most recently used node would be placed in front of list, hence the least recently used node should be the end of list. Hence `MMM4` should be `list_last_entry`.

### 分析
[Leetcode](https://leetcode.com/problems/lru-cache/) describes the functions pretty well.
Basically, 4 basic operations of CRUD is implemented.

`lRUCacheCreate()` allocates memory for the cache, then it initialize each `list_head` structure so that both `next` and `prev` points to the `list_head` structure. Indicating the list is empty.

`lRUCacheFree()` frees all memory allocated by the cache, which is each element in the cache as well as the `list_head` structure of the list.

`lRUCachePut()` puts the key value pair into the cache, and there could be few cases.
If the key already exist, it replace the value of the key with the new value.

If the key does not exist, it checks if the cache is full.
If the cache is at max capacity, it evicts the last entry of the list.
If there is still capacity for the cache, it keep track of the `count` of elements.
Then it place the key into the head of cache list.

`lRUCacheGet()` iterates through the list and match the key, if the key exists, the cache moves the element to the head of list, indicating it is recently used.

---
> The graph is just a simplified graphical representation, the implementation might differ.

The cache would be maintaining some data.
`count` indicates current node count.
`capacity` checks if `count` is at maximum.
`dhead` maintains the list with `dink` to show recency of access.
`hhead` maintains the list where to data should be place, the index is based on the hash function.

The hash function is the `key` number wrap around by the `capacity`.

### 延伸
#### 可改進之處
1. When freeing the cache, as the entirety of cache would be free, there is no need to do list_del.

#### Linux 核心找出 LRU 相關程式碼
:::spoiler Linux `cache get`

static struct lc_element *__lc_find(struct lru_cache *lc, unsigned int enr,
		bool include_changing)
{
	struct lc_element *e;

	BUG_ON(!lc);
	BUG_ON(!lc->nr_elements);
	hlist_for_each_entry(e, lc_hash_slot(lc, enr), colision) {
		/* "about to be changed" elements, pending transaction commit,
		 * are hashed by their "new number". "Normal" elements have
		 * lc_number == lc_new_number. */
		if (e->lc_new_number != enr)
			continue;
		if (e->lc_new_number == e->lc_number || include_changing)
			return e;
		break;
	}
	return NULL;
}

static struct lc_element *__lc_get(struct lru_cache *lc, unsigned int enr, unsigned int flags)
{
	struct lc_element *e;

	PARANOIA_ENTRY();
	if (lc->flags & LC_STARVING) {
		++lc->starving;
		RETURN(NULL);
	}

	e = __lc_find(lc, enr, 1);
	/* if lc_new_number != lc_number,
	 * this enr is currently being pulled in already,
	 * and will be available once the pending transaction
	 * has been committed. */
	if (e) {
		if (e->lc_new_number != e->lc_number) {
			/* It has been found above, but on the "to_be_changed"
			 * list, not yet committed.  Don't pull it in twice,
			 * wait for the transaction, then try again...
			 */
			if (!(flags & LC_GET_MAY_USE_UNCOMMITTED))
				RETURN(NULL);
			/* ... unless the caller is aware of the implications,
			 * probably preparing a cumulative transaction. */
			++e->refcnt;
			++lc->hits;
			RETURN(e);
		}
		/* else: lc_new_number == lc_number; a real hit. */
		++lc->hits;
		if (e->refcnt++ == 0)
			lc->used++;
		list_move(&e->list, &lc->in_use); /* Not evictable... */
		RETURN(e);
	}
	/* e == NULL */

	++lc->misses;
	if (!(flags & LC_GET_MAY_CHANGE))
		RETURN(NULL);

	/* To avoid races with lc_try_lock(), first, mark us dirty
	 * (using test_and_set_bit, as it implies memory barriers), ... */
	test_and_set_bit(__LC_DIRTY, &lc->flags);

	/* ... only then check if it is locked anyways. If lc_unlock clears
	 * the dirty bit again, that's not a problem, we will come here again.
	 */
	if (test_bit(__LC_LOCKED, &lc->flags)) {
		++lc->locked;
		RETURN(NULL);
	}

	/* In case there is nothing available and we can not kick out
	 * the LRU element, we have to wait ...
	 */
	if (!lc_unused_element_available(lc)) {
		__set_bit(__LC_STARVING, &lc->flags);
		RETURN(NULL);
	}

	/* It was not present in the active set.  We are going to recycle an
	 * unused (or even "free") element, but we won't accumulate more than
	 * max_pending_changes changes.  */
	if (lc->pending_changes >= lc->max_pending_changes)
		RETURN(NULL);

	e = lc_prepare_for_change(lc, enr);
	BUG_ON(!e);

	clear_bit(__LC_STARVING, &lc->flags);
	BUG_ON(++e->refcnt != 1);
	lc->used++;
	lc->pending_changes++;

	RETURN(e);
}

:::
There are some other topics that linux lru cache would consider to make the more comprehensive.

e = __lc_find(lc, enr, 1);
if (e) {
	if (e->lc_new_number != e->lc_number) {
		if (!(flags & LC_GET_MAY_USE_UNCOMMITTED))
			RETURN(NULL);
		++e->refcnt;
		++lc->hits;
		RETURN(e);
	}
	++lc->hits;
	if (e->refcnt++ == 0)
		lc->used++;
	list_move(&e->list, &lc->in_use);
	RETURN(e);
}

These are the segment of codes that are essentialy what `lRUCacheGet()` does.
Just a glimpse of the code shows what they did consider when doing `lRUCacheGet()`. For example,

`__lc_find()` would triggers a `hlist_for_each_entry`, instead of matching the value directly, the program would do a check for elements that are "about to be used", which means elements that are yet to get into the pending set.
After the first check, there would be another check in the `line 3`. Which is elements that are about to change but not changed yet.
Then the program can do what `lRUCacheGet()` does, indicate a cache hit and add its `refcnt`, and mark recently use with `used`.

if (lc->flags & LC_STARVING) {
	++lc->starving;
	RETURN(NULL);
}
/* ... */
if (!lc_unused_element_available(lc)) {
		__set_bit(__LC_STARVING, &lc->flags);
		RETURN(NULL);
	}

There are also codes that manage `lc->starving`, which it will track if there are free / unused element available. So that the machine have to wait before an element is available again to evict an element.

test_and_set_bit(__LC_DIRTY, &lc->flags);
if (test_bit(__LC_LOCKED, &lc->flags)) {
	++lc->locked;
	RETURN(NULL);
}

I also found `test_and_set()` instruction in the code, whether this is for race condition or just a memory barrier to synchronize all threads / process, this implies the linux code did take parllelism into consideration for a certain degree.

## 測驗4
We are required to fill in the correct answer for `LLL` and `RRR`.
:::spoiler

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

struct seq_node {
    int num;
    struct list_head link;
};
            
static struct seq_node *find(int num, int size, struct list_head *heads)
{ 
    struct seq_node *node;
    int hash = num < 0 ? -num % size : num % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (node->num == num)
            return node;
    }
    return NULL;
}

int longestConsecutive(int *nums, int n_size)
{
    int hash, length = 0;
    struct seq_node *node;
    struct list_head *heads = malloc(n_size * sizeof(*heads));

    for (int i = 0; i < n_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; i < n_size; i++) {
        if (!find(nums[i], n_size, heads)) {
            hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
            node = malloc(sizeof(*node));
            node->num = nums[i];
            list_add(&node->link, &heads[hash]);
        }
    }

    for (int i = 0; i < n_size; i++) {
        int len = 0;
        int num;
        node = find(nums[i], n_size, heads);
        while (node) {
            len++;
            num = node->num;
            list_del(&node->link);

            int left = num, right = num;
            while ((node = find(LLL, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(RRR, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }

    return length;
}

:::
### 解題

int left = num, right = num;
while ((node = find(LLL, n_size, heads))) {
	len++;
	list_del(&node->link);
}

while ((node = find(RRR, n_size, heads))) {
	len++;
	list_del(&node->link);
}

`find()` would do a foreach loop that find the node with `num` in bucket[hash(`num`)].

Before `find()`, the program would assign value `num` to `left` and `right`. The program should do `find()` starting from left of `num` and right of `num` judging by the variable name.

int hash = num < 0 ? -num % size : num % size;

From the hash, we know that the numbers should be in ascending order of the buckets, and wrap around when it reach index `size`. Hence, LLL and RRR would be `len -= 1` or `len += 1`.

len++;
num = node->num;
list_del(&node->link);

The remain problem is should we put `++` and `--` as the prefix or suffix. Take the first case as example, the first case `num` already contributed to `len`. Hence, the first case should be `num - 1` and `num + 1`.
The `+1` or `-1` would be before `find()`, so they should be the prefix of `left` and `right`

i.e.
`LLL` : `--left`
`RRR` : `++right`

### 分析
Given an array of `n` integers, the program would allocate space of hash table for `n` elements.

An array has the ability to do random access, it can easily track if a number is stored as input before. However, without sorting, the size of array would be equal to the largest value of number, which could be the limitation of the program.

A linked list could in theory allocate as much space for this specific program. However, when doing the main algorithm, the program would need to either sort the list or would tranverse through the entire list several time, which is very time consuming.

Hash table is used as it has advantages of both linked list and array. As the only information needed is if any two number is consecutive, it could use an array to keep track of relative position between two numbers. Whlist using a list to track the number with difference of multiple of `nsize` including 1 at neighbour element of hash table.
When input is $892,10000,1,20,-3000,-40,52,70,1400,90$, we could get a structure similar as the visual representation.

The size of hash table would be $10$ as there are $10$ numbers. We could see that every numbers that are put before and after the index of $1$ is multiple of $10\pm1$, which contains $1-1$ and $1+1$.

A point to note is that no two number would present themself in two unique list of consecutive number. Hence a number could be removed from the hash table after it is accessed.
### 延伸
:::spoiler test `main`
#include "lc.h"

int main()
{
int arr[] = {1,892,10000,20,-3000,-40,52,70,1400,90};
printf("sol = %d\n", longestConsecutive(arr, (sizeof arr) / (sizeof *arr)));
return 0;
}
:::

#### Linux 核心風格 hash table
Essentially, all i did is replacing `list` with `hlist`
:::spoiler
#include <stdio.h>
#include <stdlib.h>

#include "list.h"

struct seq_node {
int num;
struct hlist_node link;
};

static void p(int num, int size, struct hlist_head *heads)
{
struct seq_node *node;
int hash = num < 0 ? -num % size : num % size;
hlist_for_each_entry (node, &heads[hash], link) {
printf("%d ", node->num);
}
printf("\n");
}

static struct seq_node *find(int num, int size, struct hlist_head *heads)
{
struct seq_node *node;
int hash = num < 0 ? -num % size : num % size;
hlist_for_each_entry (node, &heads[hash], link) {
if (node->num == num)
return node;
}
return NULL;
}

int longestConsecutive(int *nums, int n_size)
{
int hash, length = 0;
struct seq_node *node;
struct hlist_head *heads = malloc(n_size * sizeof(*heads));

for (int i = 0; i < n_size; i++)
INIT_HLIST_HEAD(&heads[i]);

for (int i = 0; i < n_size; i++) {
if (!find(nums[i], n_size, heads)) {
hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
node = malloc(sizeof(*node));
node->num = nums[i];
hlist_add_head(&node->link, &heads[hash]);
}
}

/*
for(int i = 0;i < n_size;++i)
p(i, n_size, heads);
*/

for (int i = 0; i < n_size; i++) {
int len = 0;
int num;
node = find(nums[i], n_size, heads);
while (node) {
len++;
num = node->num;
hlist_del(&node->link);

int left = num, right = num;
while ((node = find(--left, n_size, heads))) {
len++;
hlist_del(&node->link);
}

while ((node = find(++right, n_size, heads))) {
len++;
hlist_del(&node->link);
}

length = len > length ? len : length;
}
}

return length;
}
:::

After including `hashtable.h`, we can also use the macros.

-- struct seq_node *node;
-- struct hlist_head *heads = malloc(n_size * sizeof(*heads));

-- for (int i = 0; i < n_size; i++)
--     INIT_HLIST_HEAD(&heads[i]);
++ DECLARE_HASHTABLE(heads, ilog2(n_size));
++ __hash_init(heads, n_size);

`hash.h` is not used as all it did is give a random enough hash function, which this problem don't need as the table has to maintain relative position between elements of table.