LinuxQuestions.org - Basic Data Structures and Algorithms in the Linux Kernel

Quote:

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.

More (including links) at the phrygian cap...

--jeremy