||11-24-2013 02:20 PM
Basic Data Structures and Algorithms in the Linux Kernel
More (including links) at the phrygian cap...
Thanks to Vijay D'Silva's brilliant answer at cstheory SE I have been reading some of the famous data structures and algorithms used in the Linux Kernel. And so can you.
Links based on linux 2.6:
- Linked lists, doubly linked lists, lock-free linked lists.
- B+ Trees with comments telling you what you can't find in the textbooks.
- Priority sorted lists used for mutexes, drivers, etc.
- Red-Black trees are used are used for scheduling, virtual memory management, to track file descriptors and directory entries, etc.
- Interval trees.
- Radix trees, are used for memory management, NFS related lookups and networking related functionality.
- Priority heap, which is literally, a textbook implementation, used in the control group system.
- Hash functions, with a reference to Knuth and to a paper.
Some parts of the code, such as this driver, implement their own hash function.
- Hash tables used to implement inodes, file system integrity checks, etc.
- Bit arrays, which are used for dealing with flags, interrupts, etc. and are featured in Knuth Vol. 4.
- Semaphores and spin locks.
- Binary search is used for interrupt handling, register cache lookup, etc.
- Binary search with B-trees.
- Depth first search and variant used in directory configuration.
- Breadth first search is used to check correctness of locking at runtime.
- Merge sort on linked lists is used for garbage collection, file system management, etc.
- Bubble sort is amazingly implemented too, in a driver library.
- Knuth-Morris-Pratt string matching.
- Boyer-Moore pattern matching with references and recommendations for when to prefer the alternative.