-   Linux - News (
-   -   Basic Data Structures and Algorithms in the Linux Kernel (

jeremy 11-24-2013 02:20 PM

Basic Data Structures and Algorithms in the Linux Kernel

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...


All times are GMT -5. The time now is 11:57 PM.