Algorithms and data structues


Core algorithms deployed
Algorithms: Design Techniques and Analysis
The Algorithm Design Manual 2nd Edition

Computational complexity theory

Core conceptions

Linked list

Static linked list

Reprented in an array.

Internal vs external liked

Sometimes, SLUB put freelist in object

kernel doubly linked list operations


  • kernel version
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;


  • kernel version
    next->prev = prev;
    WRITE_ONCE(prev->next, next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;

    BL list

    kernel: add bl_list - 4e35e6070b1ceed89c3bba2af4216c286fb1dafd

Double linked list

Associative array

Essentials: Brian Kernighan on Associative Arrays - Computerphile
vs indexed array


  • trade-off
    a) Checking more places takes more power and chip area,
    b) and potentially more time. On the other hand, caches with more associativity suffer fewer misses
    fully associative - the best miss rates, but practical only for a small number of entries
    N-way set associative cache: 8 is a common choice for later implementations
    direct-mapped cache - if two locations map to the same entry, they may continually knock each other out. anti-fragmantion worsens this case.

Judy array


A generic hash table
hash function


In-order traversal
postfix and prefix and sort


Depth first sarch


Redblack tree

Interval tree in kernel

anonymous page: anon_vma_interval_tree_insert


Trie is prefix tree.
Trees only store keys.
Trie Data Structure
Trie with numeric key
* terms very confused
Radix tree vs Trie, check radix meaning
Patricia is compact trie or Patricia is radix = 2 trie?

Radix tree in kernel not wikipedia

page cache: page_cache_tree_insert
Wikipedia: Radix tree looks like a compact trie.
Kernel: Radix tree was more like a Multi-level index associative arrya or judy array.
Trees I: Radix trees
Enhancing the Linux Radix Tree
The design and implementation of the XArray
A multi-order radix tree
radix_tree_init_maxnodes(): height is 11 in kernel?
radix_tree_create() add one page
radix_tree_lookup_slot: find one page


Data property: unique key, indexed
Search data structure
Sequencial array: binary search
Associative array

Which algorithm?

Advantages of BST over Hash Table
1. Can get all keys in sorted order by just doing in-order traversal of BST
2. Doing order statistics, finding closest lower and greater elements, doing range queries are easy to do with BSTs.
3. BSTs are easy to implement compared to hashing.
4. With Self Balancing BSTs, all operations are guarnateed to work in O(logN) time.

Replacement polices



Leetcode 146 LRU cache
Order items by access times

Pseudo LRU/2 - Second chance and queue

type: Reclaim
Order items by enqueueing sequence

Second chance and 2Q

Page reclaim algorithm
type: Reclaim


MCS lock