)]}'
{
  "log": [
    {
      "commit": "3cb7a56344ca45ee56d71c5f8fe9f922306bff1f",
      "tree": "da6fd5aa462e9e7c117063740c15fd95241c72d3",
      "parents": [
        "a8906b0b673a8a64ae1446a7847def62388f6e46"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Fri Jan 11 14:32:20 2013 -0800"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Fri Jan 11 14:54:56 2013 -0800"
      },
      "message": "lib/rbtree.c: avoid the use of non-static __always_inline\n\nlib/rbtree.c declared __rb_erase_color() as __always_inline void, and\nthen exported it with EXPORT_SYMBOL.\n\nThis was because __rb_erase_color() must be exported for augmented\nrbtree users, but it must also be inlined into rb_erase() so that the\ndummy callback can get optimized out of that call site.\n\n(Actually with a modern compiler, none of the dummy callback functions\nshould even be generated as separate text functions).\n\nThe above usage is legal C, but it was unusual enough for some compilers\nto warn about it.  This change makes things more explicit, with a static\n__always_inline ____rb_erase_color function for use in rb_erase(), and a\nseparate non-inline __rb_erase_color function for use in\nrb_erase_augmented call sites.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nReported-by: Wu Fengguang \u003cfengguang.wu@intel.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "9c079add0d0f45220f4bb37febf0621137ec2d38",
      "tree": "ce6ba6d7e2d517a2004de856c882f2a08af12be2",
      "parents": [
        "147e615f83c2c36caf89e7a3bf78090ade6f266c"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:33 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:40 2012 +0900"
      },
      "message": "rbtree: move augmented rbtree functionality to rbtree_augmented.h\n\nProvide rb_insert_augmented() and rb_erase_augmented() through a new\nrbtree_augmented.h include file.  rb_erase_augmented() is defined there as\nan __always_inline function, in order to allow inlining of augmented\nrbtree callbacks into it.  Since this generates a relatively large\nfunction, each augmented rbtree user should make sure to have a single\ncall site.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Hillf Danton \u003cdhillf@gmail.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Catalin Marinas \u003ccatalin.marinas@arm.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: David Woodhouse \u003cdwmw2@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "9d9e6f9703bbd642f3f2f807e6aaa642a4cbcec9",
      "tree": "6d0061d6c1369bb006da753cc2cea55df60efe0f",
      "parents": [
        "14b94af0b251a2c80885b60538166fb7d04a642e"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:20 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:38 2012 +0900"
      },
      "message": "rbtree: remove prior augmented rbtree implementation\n\nconvert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api\nand remove the old augmented rbtree implementation.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nAcked-by: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: David Woodhouse \u003cdwmw2@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "14b94af0b251a2c80885b60538166fb7d04a642e",
      "tree": "ef447d340435c441f8c3e54eb8f26f747aa73108",
      "parents": [
        "dadf93534f125b9eda486b471446a8456a603d27"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:17 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:37 2012 +0900"
      },
      "message": "rbtree: faster augmented rbtree manipulation\n\nIntroduce new augmented rbtree APIs that allow minimal recalculation of\naugmented node information.\n\nA new callback is added to the rbtree insertion and erase rebalancing\nfunctions, to be called on each tree rotations. Such rotations preserve\nthe subtree\u0027s root augmented value, but require recalculation of the one\nchild that was previously located at the subtree root.\n\nIn the insertion case, the handcoded search phase must be updated to\nmaintain the augmented information on insertion, and then the rbtree\ncoloring/rebalancing algorithms keep it up to date.\n\nIn the erase case, things are more complicated since it is library\ncode that manipulates the rbtree in order to remove internal nodes.\nThis requires a couple additional callbacks to copy a subtree\u0027s\naugmented value when a new root is stitched in, and to recompute\naugmented values down the ancestry path when a node is removed from\nthe tree.\n\nIn order to preserve maximum speed for the non-augmented case,\nwe provide two versions of each tree manipulation function.\nrb_insert_augmented() is the augmented equivalent of rb_insert_color(),\nand rb_erase_augmented() is the augmented equivalent of rb_erase().\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nAcked-by: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: David Woodhouse \u003cdwmw2@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "4f035ad67f4633c233cb3642711d49b4efc9c82d",
      "tree": "151fd5ff00a07da479805a01cb8b1d370db72d8f",
      "parents": [
        "46b6135a7402ac23c5b25f2bd79b03bab8f98278"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:13 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:37 2012 +0900"
      },
      "message": "rbtree: low level optimizations in rb_erase()\n\nVarious minor optimizations in rb_erase():\n- Avoid multiple loading of node-\u003e__rb_parent_color when computing parent\n  and color information (possibly not in close sequence, as there might\n  be further branches in the algorithm)\n- In the 1-child subcase of case 1, copy the __rb_parent_color field from\n  the erased node to the child instead of recomputing it from the desired\n  parent and color\n- When searching for the erased node\u0027s successor, differentiate between\n  cases 2 and 3 based on whether any left links were followed. This avoids\n  a condition later down.\n- In case 3, keep a pointer to the erased node\u0027s right child so we don\u0027t\n  have to refetch it later to adjust its parent.\n- In the no-childs subcase of cases 2 and 3, place the rebalance assigment\n  last so that the compiler can remove the following if(rebalance) test.\n\nAlso, added some comments to illustrate cases 2 and 3.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nAcked-by: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: David Woodhouse \u003cdwmw2@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "46b6135a7402ac23c5b25f2bd79b03bab8f98278",
      "tree": "8430c191a455b1ff48c62229731ded4cbc71a9a1",
      "parents": [
        "60670b8034d6e2ba860af79c9379b7788d09db73"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:11 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:37 2012 +0900"
      },
      "message": "rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()\n\nAn interesting observation for rb_erase() is that when a node has\nexactly one child, the node must be black and the child must be red.\nAn interesting consequence is that removing such a node can be done by\nsimply replacing it with its child and making the child black,\nwhich we can do efficiently in rb_erase(). __rb_erase_color() then\nonly needs to handle the no-childs case and can be modified accordingly.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nAcked-by: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: David Woodhouse \u003cdwmw2@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "60670b8034d6e2ba860af79c9379b7788d09db73",
      "tree": "5fed30a98d29a03c078f756275ba34c830fee36c",
      "parents": [
        "7abc704ae399fcb9c51ca200b0456f8a975a8011"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:10 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:36 2012 +0900"
      },
      "message": "rbtree: place easiest case first in rb_erase()\n\nIn rb_erase, move the easy case (node to erase has no more than\n1 child) first. I feel the code reads easier that way.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nReviewed-by: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: David Woodhouse \u003cdwmw2@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "7abc704ae399fcb9c51ca200b0456f8a975a8011",
      "tree": "3180bbf50ef3d25f0647362ecc7e7925f884d738",
      "parents": [
        "28d7530928d01638678f63c3c70113540b0e6abe"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:07 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:36 2012 +0900"
      },
      "message": "rbtree: add __rb_change_child() helper function\n\nAdd __rb_change_child() as an inline helper function to replace code that\nwould otherwise be duplicated 4 times in the source.\n\nNo changes to binary size or speed.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nReviewed-by: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: David Woodhouse \u003cdwmw2@infradead.org\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "59633abf34e2f44b8e772a2c12a92132aa7c2220",
      "tree": "3a260a6100ae2c3e2dbade989c3692234081f1c7",
      "parents": [
        "7ce6ff9e5de99e7b72019c7de82fb438fe1dc5a0"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:02 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:35 2012 +0900"
      },
      "message": "rbtree: optimize fetching of sibling node\n\nWhen looking to fetch a node\u0027s sibling, we went through a sequence of:\n- check if node is the parent\u0027s left child\n- if it is, then fetch the parent\u0027s right child\n\nThis can be replaced with:\n- fetch the parent\u0027s right child as an assumed sibling\n- check that node is NOT the fetched child\n\nThis avoids fetching the parent\u0027s left child when node is actually\nthat child. Saves a bit on code size, though it doesn\u0027t seem to make\na large difference in speed.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nCc: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nAcked-by: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nCc: \"Eric W. Biederman\" \u003cebiederm@xmission.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "7ce6ff9e5de99e7b72019c7de82fb438fe1dc5a0",
      "tree": "8caa4509f6421f5e923a1dc361013db629f80f54",
      "parents": [
        "6280d2356fd8ad0936a63c10dc1e6accf48d0c61"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:31:01 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:35 2012 +0900"
      },
      "message": "rbtree: coding style adjustments\n\nSet comment and indentation style to be consistent with linux coding style\nand the rest of the file, as suggested by Peter Zijlstra\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nAcked-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nCc: \"Eric W. Biederman\" \u003cebiederm@xmission.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "6280d2356fd8ad0936a63c10dc1e6accf48d0c61",
      "tree": "867b959cc5441f5af443965acc60d2e78dc7fec0",
      "parents": [
        "e125d1471a4f8f1bf7ea9a83deb8d23cb40bd712"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:30:57 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:35 2012 +0900"
      },
      "message": "rbtree: low level optimizations in __rb_erase_color()\n\nIn __rb_erase_color(), we often already have pointers to the nodes being\nrotated and/or know what their colors must be, so we can generate more\nefficient code than the generic __rb_rotate_left() and __rb_rotate_right()\nfunctions.\n\nAlso when the current node is red or when flipping the sibling\u0027s color,\nthe parent is already known so we can use the more efficient\nrb_set_parent_color() function to set the desired color.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nAcked-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nCc: \"Eric W. Biederman\" \u003cebiederm@xmission.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "e125d1471a4f8f1bf7ea9a83deb8d23cb40bd712",
      "tree": "00c6bb561cdb8d0cb455563aa233bffe73b7e6db",
      "parents": [
        "d6ff1273928ebf15466a85b7e1810cd00e72998b"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:30:54 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:34 2012 +0900"
      },
      "message": "rbtree: optimize case selection logic in __rb_erase_color()\n\nIn __rb_erase_color(), we have to select one of 3 cases depending on the\ncolor on the \u0027other\u0027 node children.  If both children are black, we flip a\nfew node colors and iterate.  Otherwise, we do either one or two tree\nrotations, depending on the color of the \u0027other\u0027 child opposite to \u0027node\u0027,\nand then we are done.\n\nThe corresponding logic had duplicate checks for the color of the \u0027other\u0027\nchild opposite to \u0027node\u0027.  It was checking it first to determine if both\nchildren are black, and then to determine how many tree rotations are\nrequired.  Rearrange the logic to avoid that extra check.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nAcked-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nCc: \"Eric W. Biederman\" \u003cebiederm@xmission.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "d6ff1273928ebf15466a85b7e1810cd00e72998b",
      "tree": "709cd0702c1ae1366994382bcd170c37ea857149",
      "parents": [
        "5bc9188aa207dafd47eab57df7c4fe5b3d3f636a"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:30:50 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:34 2012 +0900"
      },
      "message": "rbtree: adjust node color in __rb_erase_color() only when necessary\n\nIn __rb_erase_color(), we were always setting a node to black after\nexiting the main loop.  And in one case, after fixing up the tree to\nsatisfy all rbtree invariants, we were setting the current node to root\njust to guarantee a loop exit, at which point the root would be set to\nblack.  However this is not necessary, as the root of an rbtree is already\nknown to be black.  The only case where the color flip is required is when\nwe exit the loop due to the current node being red, and it\u0027s easiest to\njust do the flip at that point instead of doing it after the loop.\n\n[adrian.hunter@intel.com: perf tools: fix build for another rbtree.c change]\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nAcked-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nCc: \"Eric W. Biederman\" \u003cebiederm@xmission.com\u003e\nSigned-off-by: Adrian Hunter \u003cadrian.hunter@intel.com\u003e\nCc: Alexander Shishkin \u003calexander.shishkin@intel.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "5bc9188aa207dafd47eab57df7c4fe5b3d3f636a",
      "tree": "09bce40b0253f38250dd180315d7b3fa22999988",
      "parents": [
        "6d58452dc066db61acdff7b84671db1b11a3de1c"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:30:47 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:34 2012 +0900"
      },
      "message": "rbtree: low level optimizations in rb_insert_color()\n\n- Use the newly introduced rb_set_parent_color() function to flip the color\n  of nodes whose parent is already known.\n- Optimize rb_parent() when the node is known to be red - there is no need\n  to mask out the color in that case.\n- Flipping gparent\u0027s color to red requires us to fetch its rb_parent_color\n  field, so we can reuse it as the parent value for the next loop iteration.\n- Do not use __rb_rotate_left() and __rb_rotate_right() to handle tree\n  rotations: we already have pointers to all relevant nodes, and know their\n  colors (either because we want to adjust it, or because we\u0027ve tested it,\n  or we can deduce it as black due to the node proximity to a known red node).\n  So we can generate more efficient code by making use of the node pointers\n  we already have, and setting both the parent and color attributes for\n  nodes all at once. Also in Case 2, some node attributes don\u0027t have to\n  be set because we know another tree rotation (Case 3) will always follow\n  and override them.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nAcked-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nCc: \"Eric W. Biederman\" \u003cebiederm@xmission.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "6d58452dc066db61acdff7b84671db1b11a3de1c",
      "tree": "36df08157d975398c5416d068f83cd31b79ae2c7",
      "parents": [
        "1f0528653e41ec230c60f5738820e8a544731399"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:30:44 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:33 2012 +0900"
      },
      "message": "rbtree: adjust root color in rb_insert_color() only when necessary\n\nThe root node of an rbtree must always be black.  However,\nrb_insert_color() only needs to maintain this invariant when it has been\nbroken - that is, when it exits the loop due to the current (red) node\nbeing the root.  In all other cases (exiting after tree rotations, or\nexiting due to an existing black parent) the invariant is already\nsatisfied, so there is no need to adjust the root node color.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nAcked-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nCc: \"Eric W. Biederman\" \u003cebiederm@xmission.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "1f0528653e41ec230c60f5738820e8a544731399",
      "tree": "f07f4eb1ed58122b810b586839833e0c015b681c",
      "parents": [
        "910a742d4ba863848c7283d69c21bfa779d3b9a8"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:30:42 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:33 2012 +0900"
      },
      "message": "rbtree: break out of rb_insert_color loop after tree rotation\n\nIt is a well known property of rbtrees that insertion never requires more\nthan two tree rotations.  In our implementation, after one loop iteration\nidentified one or two necessary tree rotations, we would iterate and look\nfor more.  However at that point the node\u0027s parent would always be black,\nwhich would cause us to exit the loop.\n\nWe can make the code flow more obvious by just adding a break statement\nafter the tree rotations, where we know we are done.  Additionally, in the\ncases where two tree rotations are necessary, we don\u0027t have to update the\n\u0027node\u0027 pointer as it wouldn\u0027t be used until the next loop iteration, which\nwe now avoid due to this break statement.\n\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nAcked-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nCc: \"Eric W. Biederman\" \u003cebiederm@xmission.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "bf7ad8eeab995710c766df49c9c69a8592ca0216",
      "tree": "737988d677b8ea408a44a58a949cc0e8eda02440",
      "parents": [
        "ea5272f5c94fb2ee62f4f15a5b88eef6184cd506"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:30:37 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:32 2012 +0900"
      },
      "message": "rbtree: move some implementation details from rbtree.h to rbtree.c\n\nrbtree users must use the documented APIs to manipulate the tree\nstructure.  Low-level helpers to manipulate node colors and parenthood are\nnot part of that API, so move them to lib/rbtree.c\n\n[dwmw2@infradead.org: fix jffs2 build issue due to renamed __rb_parent_color field]\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nAcked-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nCc: \"Eric W. Biederman\" \u003cebiederm@xmission.com\u003e\nSigned-off-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "4c199a93a2d36b277a9fd209a0f2793f8460a215",
      "tree": "b7d6af9220ef445eb4a9f5f0966a3bc5306fe513",
      "parents": [
        "1457d2877864d918c546735bd89c29d5e2a542f1"
      ],
      "author": {
        "name": "Michel Lespinasse",
        "email": "walken@google.com",
        "time": "Mon Oct 08 16:30:32 2012 -0700"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Tue Oct 09 16:22:32 2012 +0900"
      },
      "message": "rbtree: empty nodes have no color\n\nEmpty nodes have no color.  We can make use of this property to simplify\nthe code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE macros.  Also,\nwe can get rid of the rb_init_node function which had been introduced by\ncommit 88d19cf37952 (\"timers: Add rb_init_node() to allow for stack\nallocated rb nodes\") to avoid some issue with the empty node\u0027s color not\nbeing initialized.\n\nI\u0027m not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next() are\ndoing there, though.  axboe introduced them in commit 10fd48f2376d\n(\"rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev\").  The way I\nsee it, the \u0027empty node\u0027 abstraction is only used by rbtree users to\nflag nodes that they haven\u0027t inserted in any rbtree, so asking the\npredecessor or successor of such nodes doesn\u0027t make any sense.\n\nOne final rb_init_node() caller was recently added in sysctl code to\nimplement faster sysctl name lookups.  This code doesn\u0027t make use of\nRB_EMPTY_NODE at all, and from what I could see it only called\nrb_init_node() under the mistaken assumption that such initialization was\nrequired before node insertion.\n\n[sfr@canb.auug.org.au: fix net/ceph/osd_client.c build]\nSigned-off-by: Michel Lespinasse \u003cwalken@google.com\u003e\nCc: Andrea Arcangeli \u003caarcange@redhat.com\u003e\nAcked-by: David Woodhouse \u003cDavid.Woodhouse@intel.com\u003e\nCc: Rik van Riel \u003criel@redhat.com\u003e\nCc: Peter Zijlstra \u003ca.p.zijlstra@chello.nl\u003e\nCc: Daniel Santos \u003cdaniel.santos@pobox.com\u003e\nCc: Jens Axboe \u003caxboe@kernel.dk\u003e\nCc: \"Eric W. Biederman\" \u003cebiederm@xmission.com\u003e\nCc: John Stultz \u003cjohn.stultz@linaro.org\u003e\nSigned-off-by: Stephen Rothwell \u003csfr@canb.auug.org.au\u003e\nSigned-off-by: Andrew Morton \u003cakpm@linux-foundation.org\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "commit": "8bc3bcc93a2b4e47d5d410146f6546bca6171663",
      "tree": "101f55a96f751749041c90c32ef1ba89f94dc4d1",
      "parents": [
        "630d9c47274aa89bfa77fe6556d7818bdcb12992"
      ],
      "author": {
        "name": "Paul Gortmaker",
        "email": "paul.gortmaker@windriver.com",
        "time": "Wed Nov 16 21:29:17 2011 -0500"
      },
      "committer": {
        "name": "Paul Gortmaker",
        "email": "paul.gortmaker@windriver.com",
        "time": "Wed Mar 07 15:04:04 2012 -0500"
      },
      "message": "lib: reduce the use of module.h wherever possible\n\nFor files only using THIS_MODULE and/or EXPORT_SYMBOL, map\nthem onto including export.h -- or if the file isn\u0027t even\nusing those, then just delete the include.  Fix up any implicit\ninclude dependencies that were being masked by module.h along\nthe way.\n\nSigned-off-by: Paul Gortmaker \u003cpaul.gortmaker@windriver.com\u003e\n"
    },
    {
      "commit": "0b6bb66d1247601e4a2560bb048d64c606bd7b73",
      "tree": "74319fede412aab03d19034a30eaf164d3dc2498",
      "parents": [
        "b12ece7d852efbc8db45371c068900fcc62002d4"
      ],
      "author": {
        "name": "Andreas Gruenbacher",
        "email": "agruen@linbit.com",
        "time": "Wed Jan 26 15:55:36 2011 +0100"
      },
      "committer": {
        "name": "Linus Torvalds",
        "email": "torvalds@linux-foundation.org",
        "time": "Fri Jan 28 12:16:59 2011 +1000"
      },
      "message": "Export the augmented rbtree helper functions\n\nThe augmented rbtree helper functions are not exported to modules right\nnow.\n\n(We have started using augmented rbtrees in the upcoming version of\ndrbd.)\n\nSigned-off-by: Andreas Gruenbacher \u003cagruen@linbit.com\u003e\nSigned-off-by: Linus Torvalds \u003ctorvalds@linux-foundation.org\u003e\n"
    },
    {
      "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"
    }
  ]
}