Core algorithms deployed
Algorithms: Design Techniques and Analysis
The Algorithm Design Manual 2nd Edition
Computational complexity theory
Linked vs sequential
- ADT vs data structure
ADT is a data type defined by its behavior.
Any type that does not specify an implementation is an abstract data type.
Static linked list
Reprented in an array.
Internal vs external liked
Sometimes, SLUB put freelist in object
kernel doubly linked list operations
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
next->prev = prev;
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
kernel: add bl_list - 4e35e6070b1ceed89c3bba2af4216c286fb1dafd
Double linked list
Essentials: Brian Kernighan on Associative Arrays - Computerphile
vs indexed array
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.
A generic hash table
postfix and prefix and sort
Depth first sarch
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
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.
Leetcode 146 LRU cache
Order items by access times
Pseudo LRU/2 - Second chance and queue
Order items by enqueueing sequence
Second chance and 2Q
Page reclaim algorithm