)]}' { "log": [ { "commit": "b945d6b2554d550fe95caadc61e521c0ad71fb9c", "tree": "0b76cdb978bead82188de40cae6d24bd88d71b7d", "parents": [ "d596043d71ff0d7b3d0bead19b1d68c55f003093" ], "author": { "name": "Peter Zijlstra", "email": "peterz@infradead.org", "time": "Sat May 29 15:31:43 2010 +0200" }, "committer": { "name": "Ingo Molnar", "email": "mingo@elte.hu", "time": "Mon Jul 05 14:43:50 2010 +0200" }, "message": "rbtree: Undo augmented trees performance damage and regression\n\nReimplement augmented RB-trees without sprinkling extra branches\nall over the RB-tree code (which lives in the scheduler hot path).\n\nThis approach is \u0027borrowed\u0027 from Fabio\u0027s BFQ implementation and\nrelies on traversing the rebalance path after the RB-tree-op to\ncorrect the heap property for insertion/removal and make up for\nthe damage done by the tree rotations.\n\nFor insertion the rebalance path is trivially that from the new\nnode upwards to the root, for removal it is that from the deepest\nnode in the path from the to be removed node that will still\nbe around after the removal.\n\n[ This patch also fixes a video driver regression reported by\n Ali Gholami Rudi - the memtype-\u003esubtree_max_end was updated\n incorrectly. ]\n\nAcked-by: Suresh Siddha \u003csuresh.b.siddha@intel.com\u003e\nAcked-by: Venkatesh Pallipadi \u003cvenki@google.com\u003e\nSigned-off-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nTested-by: Ali Gholami Rudi \u003cali@rudi.ir\u003e\nCc: Fabio Checconi \u003cfabio@gandalf.sssup.it\u003e\nCc: \"H. Peter Anvin\" \u003chpa@zytor.com\u003e\nCc: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nCc: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\nLKML-Reference: \u003c1275414172.27810.27961.camel@twins\u003e\nSigned-off-by: Ingo Molnar \u003cmingo@elte.hu\u003e\n" }, { "commit": "17d9ddc72fb8bba0d4f67868c9c612e472a594a9", "tree": "51c5e50f91eb060e346c129aa7403624934966d8", "parents": [ "724e6d3fe8003c3f60bf404bf22e4e331327c596" ], "author": { "name": "Pallipadi, Venkatesh", "email": "venkatesh.pallipadi@intel.com", "time": "Wed Feb 10 15:23:44 2010 -0800" }, "committer": { "name": "H. Peter Anvin", "email": "hpa@zytor.com", "time": "Thu Feb 18 15:40:56 2010 -0800" }, "message": "rbtree: Add support for augmented rbtrees\n\nAdd support for augmented rbtrees in core rbtree code.\n\nThis will be used in subsequent patches, in x86 PAT code, which needs\ninterval trees to efficiently keep track of PAT ranges.\n\nSigned-off-by: Venkatesh Pallipadi \u003cvenkatesh.pallipadi@intel.com\u003e\nLKML-Reference: \u003c20100210232343.GA11465@linux-os.sc.intel.com\u003e\nSigned-off-by: Suresh Siddha \u003csuresh.b.siddha@intel.com\u003e\nSigned-off-by: H. Peter Anvin \u003chpa@zytor.com\u003e\n" }, { "commit": "4b324126e0c6c3a5080ca3ec0981e8766ed6f1ee", "tree": "f49edd4acf4963eb3377fd3a700982081970ba14", "parents": [ "4c60117811171d867d4f27f17ea07d7419d45dae" ], "author": { "name": "Wolfram Strepp", "email": "wstrepp@gmx.de", "time": "Tue Jun 16 15:34:13 2009 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Tue Jun 16 19:47:56 2009 -0700" }, "message": "rb_tree: remove redundant if()-condition in rb_erase()\n\nFurthermore, notice that the initial checks:\n\n\tif (!node-\u003erb_left)\n\t\tchild \u003d node-\u003erb_right;\n\telse if (!node-\u003erb_right)\n\t\tchild \u003d node-\u003erb_left;\n\telse\n\t{\n\t\t...\n\t}\nguarantee that old-\u003erb_right is set in the final else branch, therefore\nwe can omit checking that again.\n\nSigned-off-by: Wolfram Strepp \u003cwstrepp@gmx.de\u003e\nSigned-off-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "4c60117811171d867d4f27f17ea07d7419d45dae", "tree": "9148532285b9276573f000b3125aee885afce411", "parents": [ "16c047add3ceaf0ab882e3e094d1ec904d02312d" ], "author": { "name": "Wolfram Strepp", "email": "wstrepp@gmx.de", "time": "Tue Jun 16 15:34:12 2009 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Tue Jun 16 19:47:56 2009 -0700" }, "message": "rb_tree: make clear distinction between two different cases in rb_erase()\n\nThere are two cases when a node, having 2 childs, is erased:\n\u0027normal case\u0027: the successor is not the right-hand-child of the node to be erased\n\u0027special case\u0027: the successor is the right-hand child of the node to be erased\n\nHere some ascii-art, with following symbols (referring to the code):\nO: node to be deleted\nN: the successor of O\nP: parent of N\nC: child of N\nL: some other node\n\nnormal case:\n\n O N\n / \\ / \\\n / \\ / \\\n L \\ L \\\n / \\ P ----\u003e / \\ P\n / \\ / \\\n / /\n N C\n \\ / \\\n \\\n C\n / \\\n\nspecial case:\n O|P N\n / \\ / \\\n / \\ / \\\n L \\ L \\\n / \\ N ----\u003e / C\n \\ / \\\n \\\n C\n / \\\n\nNotice that for the special case we don\u0027t have to reconnect C to N.\n\nSigned-off-by: Wolfram Strepp \u003cwstrepp@gmx.de\u003e\nSigned-off-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "16c047add3ceaf0ab882e3e094d1ec904d02312d", "tree": "80702a25fc558bec68e3214048fd6f8301e7d17d", "parents": [ "130b76cf5295d74a2174d0843bb563bbf0a19dbb" ], "author": { "name": "Wolfram Strepp", "email": "wstrepp@gmx.de", "time": "Tue Jun 16 15:34:11 2009 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Tue Jun 16 19:47:56 2009 -0700" }, "message": "rb_tree: reorganize code in rb_erase() for additional changes\n\nFirst, move some code around in order to make the next change more obvious.\n\n[akpm@linux-foundation.org: coding-style fixes]\nSigned-off-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nSigned-off-by: Wolfram Strepp \u003cwstrepp@gmx.de\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "55a63998b8967615a15e2211ba0ff3a84a565824", "tree": "a83905577b60496a3ea9174bf29596f927354746", "parents": [ "53d6660836f233df66490707365ab177e5fb2bb4" ], "author": { "name": "Wolfram Strepp", "email": "wstrepp@gmx.de", "time": "Tue Mar 31 15:23:45 2009 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Wed Apr 01 08:59:17 2009 -0700" }, "message": "lib/rbtree.c: optimize rb_erase()\n\nTfour 4 redundant if-conditions in function __rb_erase_color() in\nlib/rbtree.c are removed.\n\nIn pseudo-source-code, the structure of the code is as follows:\n\nif ((!A || B) \u0026\u0026 (!C || D)) {\n\t.\n\t.\n\t.\n} else {\n\tif (!C || D) {//if this is true, it implies: (A \u003d\u003d true) \u0026\u0026 (B \u003d\u003d false)\n\t\tif (A) {//hence this always evaluates to \u0027true\u0027...\n\t\t\t.\n\t\t}\n\t\t.\n\t\t//at this point, C always becomes true, because of:\n\t\t__rb_rotate_right/left();\n\t\t//and:\n\t\tother \u003d parent-\u003erb_right/left;\n\t}\n\t.\n\t.\n\tif (C) {//...and this too !\n\t\t.\n\t}\n}\n\nSigned-off-by: Wolfram Strepp \u003cwstrepp@gmx.de\u003e\nAcked-by: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Andrea Arcangeli \u003candrea@qumranet.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "f4b477c47332367d35686bd2b808c2156b96d7c7", "tree": "ab8a2cf098b69be9ed7a44426106a7af596241d9", "parents": [ "cfce41a6d643c001d416ead960caf04fae2d609a" ], "author": { "name": "Artem Bityutskiy", "email": "Artem.Bityutskiy@nokia.com", "time": "Sat Jan 10 11:12:09 2009 +0000" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@linux-foundation.org", "time": "Sat Jan 10 06:04:33 2009 -0800" }, "message": "rbtree: add const qualifier to some functions\n\nThe \u0027rb_first()\u0027, \u0027rb_last()\u0027, \u0027rb_next()\u0027 and \u0027rb_prev()\u0027 calls\ntake a pointer to an RB node or RB root. They do not change the\npointed objects, so add a \u0027const\u0027 qualifier in order to make life\nof the users of these functions easier.\n\nIndeed, if I have my own constant pointer \u0026const struct my_type *p,\nand I call \u0027rb_next(\u0026p-\u003erb)\u0027, I get a GCC warning:\n\nwarning: passing argument 1 of ‘rb_next’ discards qualifiers from pointer target type\n\nSigned-off-by: Artem Bityutskiy \u003cArtem.Bityutskiy@nokia.com\u003e\nSigned-off-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n" }, { "commit": "10fd48f2376db52f08bf0420d2c4f580e39269e1", "tree": "89de18dcda9c8a09937187a0e8d138cfe3cb4089", "parents": [ "9817064b68fef7e4580c6df1ea597e106b9ff88b" ], "author": { "name": "Jens Axboe", "email": "axboe@suse.de", "time": "Tue Jul 11 21:15:52 2006 +0200" }, "committer": { "name": "Jens Axboe", "email": "axboe@nelson.home.kernel.dk", "time": "Sat Sep 30 20:26:56 2006 +0200" }, "message": "[PATCH] rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev\n\nThe conditions got reserved. Also make rb_next() and rb_prev() check\nfor the empty condition.\n\nSigned-off-by: Jens Axboe \u003caxboe@suse.de\u003e\n" }, { "commit": "2f3243aebd8df4d9eecaeca04bbff6c7dbfb2142", "tree": "a5b5e3ec2be7f9497dc991b7c7914df6fde27b98", "parents": [ "aa783a8f31c79f493bd49ba926b171b79b9839fb" ], "author": { "name": "David Woodhouse", "email": "dwmw2@infradead.org", "time": "Mon Jun 05 20:19:05 2006 +0100" }, "committer": { "name": "David Woodhouse", "email": "dwmw2@infradead.org", "time": "Mon Jun 05 20:19:05 2006 +0100" }, "message": "[RBTREE] Switch rb_colour() et al to en_US spelling of \u0027color\u0027 for consistency\n\nSince rb_insert_color() is part of the _public_ API, while the others are\npurely internal, switch to be consistent with that.\n\nSigned-off-by: David Woodhouse \u003cdwmw2@infradead.org\u003e\n" }, { "commit": "55a981027fc393c86de2c4e7836c9515088a9a58", "tree": "dd950b79d9f57ce48b2b2a91262b88eecb5296da", "parents": [ "1975e59375756da4ff4e6e7d12f67485e813ace0" ], "author": { "name": "David Woodhouse", "email": "dwmw2@infradead.org", "time": "Fri Apr 21 13:35:51 2006 +0100" }, "committer": { "name": "David Woodhouse", "email": "dwmw2@infradead.org", "time": "Fri Apr 21 13:35:51 2006 +0100" }, "message": "[RBTREE] Merge colour and parent fields of struct rb_node.\n\nWe only used a single bit for colour information, so having a whole\nmachine word of space allocated for it was a bit wasteful. Instead,\nstore it in the lowest bit of the \u0027parent\u0027 pointer, since that was\nalways going to be aligned anyway.\n\nSigned-off-by: David Woodhouse \u003cdwmw2@infradead.org\u003e\n" }, { "commit": "1975e59375756da4ff4e6e7d12f67485e813ace0", "tree": "2370244862fa47b4ad8d4156d1a4ed32c326d628", "parents": [ "21f1d5fc592e145574dede8debe9603334d08fde" ], "author": { "name": "David Woodhouse", "email": "dwmw2@infradead.org", "time": "Fri Apr 21 13:30:36 2006 +0100" }, "committer": { "name": "David Woodhouse", "email": "dwmw2@infradead.org", "time": "Fri Apr 21 13:30:36 2006 +0100" }, "message": "[RBTREE] Remove dead code in rb_erase()\n\nObserve rb_erase(), when the victim node \u0027old\u0027 has two children so\nneither of the simple cases at the beginning are taken.\n\nObserve that it effectively does an \u0027rb_next()\u0027 operation to find the\nnext (by value) node in the tree. That is; we go to the victim\u0027s\nright-hand child and then follow left-hand pointers all the way\ndown the tree as far as we can until we find the next node \u0027node\u0027. We\nend up with \u0027node\u0027 being either the same immediate right-hand child of\n\u0027old\u0027, or one of its descendants on the far left-hand side.\n\nFor a start, we _know_ that \u0027node\u0027 has a parent. We can drop that check.\n\nWe also know that if \u0027node\u0027s parent is \u0027old\u0027, then \u0027node\u0027 is the\nright-hand child of its parent. And that if \u0027node\u0027s parent is _not_\n\u0027old\u0027, then \u0027node\u0027 is the left-hand child of its parent.\n\nSo instead of checking for \u0027node-\u003erb_parent \u003d\u003d old\u0027 in one place and\nalso checking \u0027node\u0027s heritage separately when we\u0027re trying to change\nits link from its parent, we can shuffle things around a bit and do\nit like this...\n\nSigned-off-by: David Woodhouse \u003cdwmw2@infradead.org\u003e\n" }, { "commit": "1da177e4c3f41524e886b7f1b8a0c1fc7321cac2", "tree": "0bba044c4ce775e45a88a51686b5d9f90697ea9d", "parents": [], "author": { "name": "Linus Torvalds", "email": "torvalds@ppc970.osdl.org", "time": "Sat Apr 16 15:20:36 2005 -0700" }, "committer": { "name": "Linus Torvalds", "email": "torvalds@ppc970.osdl.org", "time": "Sat Apr 16 15:20:36 2005 -0700" }, "message": "Linux-2.6.12-rc2\n\nInitial git repository build. I\u0027m not bothering with the full history,\neven though we have it. We can create a separate \"historical\" git\narchive of that later if we want to, and in the meantime it\u0027s about\n3.2GB when imported into git - space that would just make the early\ngit days unnecessarily complicated, when we don\u0027t have a lot of good\ninfrastructure for it.\n\nLet it rip!\n" } ] }