{"action":"created","issue":{"url":"https://api.github.com/repos/radare/radare2/issues/8381","repository_url":"https://api.github.com/repos/radare/radare2","labels_url":"https://api.github.com/repos/radare/radare2/issues/8381/labels{/name}","comments_url":"https://api.github.com/repos/radare/radare2/issues/8381/comments","events_url":"https://api.github.com/repos/radare/radare2/issues/8381/events","html_url":"https://github.com/radare/radare2/pull/8381","id":253894090,"number":8381,"title":"Intrusive augmented top-down red-black tree","user":{"login":"MaskRay","id":416322,"avatar_url":"https://avatars3.githubusercontent.com/u/416322?v=4","gravatar_id":"","url":"https://api.github.com/users/MaskRay","html_url":"https://github.com/MaskRay","followers_url":"https://api.github.com/users/MaskRay/followers","following_url":"https://api.github.com/users/MaskRay/following{/other_user}","gists_url":"https://api.github.com/users/MaskRay/gists{/gist_id}","starred_url":"https://api.github.com/users/MaskRay/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MaskRay/subscriptions","organizations_url":"https://api.github.com/users/MaskRay/orgs","repos_url":"https://api.github.com/users/MaskRay/repos","events_url":"https://api.github.com/users/MaskRay/events{/privacy}","received_events_url":"https://api.github.com/users/MaskRay/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2017-08-30T06:43:14Z","updated_at":"2017-08-30T14:16:56Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/radare/radare2/pulls/8381","html_url":"https://github.com/radare/radare2/pull/8381","diff_url":"https://github.com/radare/radare2/pull/8381.diff","patch_url":"https://github.com/radare/radare2/pull/8381.patch"},"body":"Fix a rotation bug in `r_rbtree_delete` \r\n\r\n```c\r\n      if (! red (s->child[0]) || ! red (s->child[1])) {\r\n==>\r\n      if (! red (s->child[0]) && ! red (s->child[1])) {\r\n```\r\n\r\nand changed to an intrusive and augmented tree. That is, user can define custom aggregation callback (monoid sum) and the insertion/deletion routines will calculate the aggregate value for each subtree.\r\n\r\nFor example, if you define\r\n\r\n```c\r\nvoid size(RBNode *a_) {\r\n\tstruct Node *a = container_of(a_, struct Node, rb);\r\n\ta->size = 1;\r\n\tfor (int i = 0; i < 2; i++)\r\n\t\tif (a_->child[i])\r\n\t\t\ta->size += container_of(a_->child[i], struct Node, rb)->size;\r\n}\r\nstatic int cmp(const void *a, const RBNode *b) {\r\n\treturn ((const struct Node *)a)->key - container_of(b, const struct Node, rb)->key;\r\n}\r\n```\r\nand use `r_rbtree_aug_insert(&tree, x, &x->rb, cmp, sum);` for insertion. Each node will be attacked a `size` field which represents the number of nodes in the tree. This can be used to define random access (get nth element) operations.\r\n\r\nSee https://github.com/radare/radare2-regressions/pull/988 for more usage."},"comment":{"url":"https://api.github.com/repos/radare/radare2/issues/comments/326004381","html_url":"https://github.com/radare/radare2/pull/8381#issuecomment-326004381","issue_url":"https://api.github.com/repos/radare/radare2/issues/8381","id":326004381,"user":{"login":"condret","id":5904302,"avatar_url":"https://avatars0.githubusercontent.com/u/5904302?v=4","gravatar_id":"","url":"https://api.github.com/users/condret","html_url":"https://github.com/condret","followers_url":"https://api.github.com/users/condret/followers","following_url":"https://api.github.com/users/condret/following{/other_user}","gists_url":"https://api.github.com/users/condret/gists{/gist_id}","starred_url":"https://api.github.com/users/condret/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/condret/subscriptions","organizations_url":"https://api.github.com/users/condret/orgs","repos_url":"https://api.github.com/users/condret/repos","events_url":"https://api.github.com/users/condret/events{/privacy}","received_events_url":"https://api.github.com/users/condret/received_events","type":"User","site_admin":false},"created_at":"2017-08-30T14:16:56Z","updated_at":"2017-08-30T14:16:56Z","author_association":"COLLABORATOR","body":"is the old api still available?"}}
{"actor":{"display_login":"condret"}}