LinuxQuestions.org
Register a domain and help support LQ
Go Back   LinuxQuestions.org > Forums > LinuxQuestions.org > Linux - News
User Name
Password
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.

Notices

Reply
 
Search this Thread
Old 11-24-2013, 02:20 PM   #1
jeremy
root
 
Registered: Jun 2000
Distribution: Debian, Red Hat, Slackware, Fedora, Ubuntu
Posts: 10,609

Rep: Reputation: 2652Reputation: 2652Reputation: 2652Reputation: 2652Reputation: 2652Reputation: 2652Reputation: 2652Reputation: 2652Reputation: 2652Reputation: 2652Reputation: 2652
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
 
  


Reply


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 Off
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 12:50 PM
2nd level book, data structures, algorithms icecubeflower Linux - Newbie 6 04-03-2009 12:51 AM
from kernel data structures ? sha_neb Linux - Kernel 1 06-08-2007 04:54 PM
from kernel data structures ? sha_neb Programming 1 06-07-2007 10:53 AM
kernel data structures vishalbutte Programming 8 01-05-2006 04:19 PM


All times are GMT -5. The time now is 10:25 PM.

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