Go Job Hunting at the LQ Job Marketplace
Go Back > Forums > Linux Forums > Linux - News
User Name
Linux - News This forum is for original Linux News. If you'd like to write content for LQ, feel free to contact us.
All threads in the forum need to be approved before they will appear.


  Search this Thread
Old 11-24-2013, 01:20 PM   #1
Registered: Jun 2000
Distribution: Debian, Red Hat, Slackware, Fedora, Ubuntu
Posts: 11,265

Rep: Reputation: 2789Reputation: 2789Reputation: 2789Reputation: 2789Reputation: 2789Reputation: 2789Reputation: 2789Reputation: 2789Reputation: 2789Reputation: 2789Reputation: 2789
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...



Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
LXer: A quick GNU R tutorial to basic operations, functions and data structures LXer Syndicated Linux News 0 01-30-2013 11:50 AM
2nd level book, data structures, algorithms icecubeflower Linux - Newbie 6 04-02-2009 11:51 PM
from kernel data structures ? sha_neb Linux - Kernel 1 06-08-2007 03:54 PM
from kernel data structures ? sha_neb Programming 1 06-07-2007 09:53 AM
kernel data structures vishalbutte Programming 8 01-05-2006 03:19 PM

All times are GMT -5. The time now is 11:48 AM.

Main Menu
Write for LQ is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration