aboutsummaryrefslogtreecommitdiffstats
path: root/include
Commit message (Expand)AuthorAge
* [PATCH] Add driver_for_each_device().mochel@digitalimplant.org2005-06-20
* [PATCH] Add a semaphore to struct device to synchronize calls to its driver.mochel@digitalimplant.org2005-06-20
* [PATCH] class: remove class_simple code, as no one in the tree is using it an...gregkh@suse.de2005-06-20
* [PATCH] USB: move the usb hcd code to use the new class code.gregkh@suse.de2005-06-20
* [PATCH] INPUT: move to use the new class code, instead of class_simplegregkh@suse.de2005-06-20
* [PATCH] CLASS: move a "simple" class logic into the class core.gregkh@suse.de2005-06-20
* [PATCH] Make attributes names const char *Dmitry Torokhov2005-06-20
* [PATCH] make driver's name be const char *Dmitry Torokhov2005-06-20
* [PATCH] kset_hotplug_ops->name shoudl return const char *Dmitry Torokhov2005-06-20
* [PATCH] Make kobject's name be const char *Dmitry Torokhov2005-06-20
* [PATCH] sysfs_{create|remove}_link should take const char *Dmitry Torokhov2005-06-20
* Merge master.kernel.org:/home/rmk/linux-2.6-armLinus Torvalds2005-06-19
|\
| * Merge with ../linux-2.6-smpRussell King2005-06-19
| |\
| | * [PATCH] ARM SMP: Add missed files from Integrator/CP platformRussell King2005-06-19
| | * [PATCH] ARM SMP: Add support for startup of secondary processorsRussell King2005-06-18
| * | [PATCH] ARM SMP: Fix PXA/SA11x0 suspend resume crashRussell King2005-06-19
* | | [PKT_SCHED]: Generic queue management interface for qdiscs using internal skb...Thomas Graf2005-06-19
* | | [IPSEC]: Add XFRMA_SA/XFRMA_POLICY for delete notificationHerbert Xu2005-06-19
* | | [NETLINK]: Introduce NLMSG_NEW macro to better handle netlink flagsThomas Graf2005-06-19
* | | [RTNETLINK]: Add RTA_(PUT|GET) shortcuts for u8, u16, and flagThomas Graf2005-06-19
* | | [NETLINK]: Fix RTA_NEST_CANCEL().Thomas Graf2005-06-19
* | | [NEIGHBOUR]: Remove unused fields in struct neigh_parms and neigh_tableThomas Graf2005-06-19
* | | [NETLINK]: Neighbour table configuration and statistics via rtnetlinkThomas Graf2005-06-19
* | | [NETLINK] Routing attribute related shortcutsThomas Graf2005-06-19
* | | [NETLINK]: New message building macrosThomas Graf2005-06-19
* | | [NET]: Move sysctl_max_syn_backlog into request_sock.cDavid S. Miller2005-06-19
* | | [NET] rename struct tcp_listen_opt to struct listen_sockArnaldo Carvalho de Melo2005-06-19
* | | [NET] Generalise tcp_listen_optArnaldo Carvalho de Melo2005-06-19
* | | [NET] Rename open_request to request_sockArnaldo Carvalho de Melo2005-06-19
* | | [NET] Generalise TCP's struct open_request minisock infrastructureArnaldo Carvalho de Melo2005-06-19
* | | [SLAB] Introduce kmem_cache_nameArnaldo Carvalho de Melo2005-06-19
* | | [IPSEC] Use XFRM_MSG_* instead of XFRM_SAP_*Herbert Xu2005-06-19
* | | [IPSEC] Turn km_event.data into a unionHerbert Xu2005-06-19
* | | [IPSEC] Kill spurious hard expire messagesHerbert Xu2005-06-19
* | | [IPSEC] Add complete xfrm event notificationJamal Hadi Salim2005-06-19
|/ /
* | Merge master.kernel.org:/pub/scm/linux/kernel/git/dwmw2/audit-2.6Linus Torvalds2005-06-18
|\ \
| * | Merge with master.kernel.org:/pub/scm/linux/kernel/git/torvalds/linux-2.6.gitDavid Woodhouse2005-06-18
| |\|
| * | Merge with master.kernel.org:/pub/scm/linux/kernel/git/torvalds/linux-2.6.gitDavid Woodhouse2005-06-02
| |\ \
| * | | AUDIT: Record working directory when syscall arguments are pathnamesDavid Woodhouse2005-05-27
| * | | AUDIT: Assign serial number to non-syscall messagesDavid Woodhouse2005-05-21
| * | | AUDIT: Avoid sleeping function in SElinux AVC audit.Stephen Smalley2005-05-20
| * | | Merge with master.kernel.org:/pub/scm/linux/kernel/git/torvalds/linux-2.6.gitDavid Woodhouse2005-05-19
| |\ \ \
| * | | | AUDIT: Treat all user messages identically.David Woodhouse2005-05-18
| * | | | AUDIT: Capture sys_socketcall arguments and sockaddrs David Woodhouse2005-05-17
| * | | | Merge with master.kernel.org:/pub/scm/linux/kernel/git/torvalds/linux-2.6.gitDavid Woodhouse2005-05-17
| |\ \ \ \
| * | | | | AUDIT: Fix some spelling errorsSteve Grubb2005-05-13
| * | | | | AUDIT: Add message types to audit recordsSteve Grubb2005-05-13
| * | | | | Add missing asm-ppc/seccomp.h. Must learn to use git properly.David Woodhouse2005-05-11
| * | | | | Add audit_log_typeChris Wright2005-05-11
| * | | | | Move ifdef CONFIG_AUDITSYSCALL to headerChris Wright2005-05-11
generated by cgit v1.2.2 (git 2.25.0) at 2025-09-16 19:28:54 -0400
an> continue; } } if (parent->rb_right == node) { register struct rb_node *tmp; __rb_rotate_left(parent, root); tmp = parent; parent = node; node = tmp; } rb_set_black(parent); rb_set_red(gparent); __rb_rotate_right(gparent, root); } else { { register struct rb_node *uncle = gparent->rb_left; if (uncle && rb_is_red(uncle)) { rb_set_black(uncle); rb_set_black(parent); rb_set_red(gparent); node = gparent; continue; } } if (parent->rb_left == node) { register struct rb_node *tmp; __rb_rotate_right(parent, root); tmp = parent; parent = node; node = tmp; } rb_set_black(parent); rb_set_red(gparent); __rb_rotate_left(gparent, root); } } rb_set_black(root->rb_node); } EXPORT_SYMBOL(rb_insert_color); static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root) { struct rb_node *other; while ((!node || rb_is_black(node)) && node != root->rb_node) { if (parent->rb_left == node) { other = parent->rb_right; if (rb_is_red(other)) { rb_set_black(other); rb_set_red(parent); __rb_rotate_left(parent, root); other = parent->rb_right; } if ((!other->rb_left || rb_is_black(other->rb_left)) && (!other->rb_right || rb_is_black(other->rb_right))) { rb_set_red(other); node = parent; parent = rb_parent(node); } else { if (!other->rb_right || rb_is_black(other->rb_right)) { struct rb_node *o_left; if ((o_left = other->rb_left)) rb_set_black(o_left); rb_set_red(other); __rb_rotate_right(other, root); other = parent->rb_right; } rb_set_color(other, rb_color(parent)); rb_set_black(parent); if (other->rb_right) rb_set_black(other->rb_right); __rb_rotate_left(parent, root); node = root->rb_node; break; } } else { other = parent->rb_left; if (rb_is_red(other)) { rb_set_black(other); rb_set_red(parent); __rb_rotate_right(parent, root); other = parent->rb_left; } if ((!other->rb_left || rb_is_black(other->rb_left)) && (!other->rb_right || rb_is_black(other->rb_right))) { rb_set_red(other); node = parent; parent = rb_parent(node); } else { if (!other->rb_left || rb_is_black(other->rb_left)) { register struct rb_node *o_right; if ((o_right = other->rb_right)) rb_set_black(o_right); rb_set_red(other); __rb_rotate_left(other, root); other = parent->rb_left; } rb_set_color(other, rb_color(parent)); rb_set_black(parent); if (other->rb_left) rb_set_black(other->rb_left); __rb_rotate_right(parent, root); node = root->rb_node; break; } } } if (node) rb_set_black(node); } void rb_erase(struct rb_node *node, struct rb_root *root) { struct rb_node *child, *parent; int color; if (!node->rb_left) child = node->rb_right; else if (!node->rb_right) child = node->rb_left; else { struct rb_node *old = node, *left; node = node->rb_right; while ((left = node->rb_left) != NULL) node = left; child = node->rb_right; parent = rb_parent(node); color = rb_color(node); if (child) rb_set_parent(child, parent); if (parent == old) { parent->rb_right = child; parent = node; } else parent->rb_left = child; node->rb_parent_color = old->rb_parent_color; node->rb_right = old->rb_right; node->rb_left = old->rb_left; if (rb_parent(old)) { if (rb_parent(old)->rb_left == old) rb_parent(old)->rb_left = node; else rb_parent(old)->rb_right = node; } else root->rb_node = node; rb_set_parent(old->rb_left, node); if (old->rb_right) rb_set_parent(old->rb_right, node); goto color; } parent = rb_parent(node); color = rb_color(node); if (child) rb_set_parent(child, parent); if (parent) { if (parent->rb_left == node) parent->rb_left = child; else parent->rb_right = child; } else root->rb_node = child; color: if (color == RB_BLACK) __rb_erase_color(child, parent, root); } EXPORT_SYMBOL(rb_erase); /* * This function returns the first node (in sort order) of the tree. */ struct rb_node *rb_first(struct rb_root *root) { struct rb_node *n; n = root->rb_node; if (!n) return NULL; while (n->rb_left) n = n->rb_left; return n; } EXPORT_SYMBOL(rb_first); struct rb_node *rb_last(struct rb_root *root) { struct rb_node *n; n = root->rb_node; if (!n) return NULL; while (n->rb_right) n = n->rb_right; return n; } EXPORT_SYMBOL(rb_last); struct rb_node *rb_next(struct rb_node *node) { struct rb_node *parent; if (rb_parent(node) == node) return NULL; /* If we have a right-hand child, go down and then left as far as we can. */ if (node->rb_right) { node = node->rb_right; while (node->rb_left) node=node->rb_left; return node; } /* No right-hand children. Everything down and left is smaller than us, so any 'next' node must be in the general direction of our parent. Go up the tree; any time the ancestor is a right-hand child of its parent, keep going up. First time it's a left-hand child of its parent, said parent is our 'next' node. */ while ((parent = rb_parent(node)) && node == parent->rb_right) node = parent; return parent; } EXPORT_SYMBOL(rb_next); struct rb_node *rb_prev(struct rb_node *node) { struct rb_node *parent; if (rb_parent(node) == node) return NULL; /* If we have a left-hand child, go down and then right as far as we can. */ if (node->rb_left) { node = node->rb_left; while (node->rb_right) node=node->rb_right; return node; } /* No left-hand children. Go up till we find an ancestor which is a right-hand child of its parent */ while ((parent = rb_parent(node)) && node == parent->rb_left) node = parent; return parent; } EXPORT_SYMBOL(rb_prev); void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { struct rb_node *parent = rb_parent(victim); /* Set the surrounding nodes to point to the replacement */ if (parent) { if (victim == parent->rb_left) parent->rb_left = new; else parent->rb_right = new; } else { root->rb_node = new; } if (victim->rb_left) rb_set_parent(victim->rb_left, new); if (victim->rb_right) rb_set_parent(victim->rb_right, new); /* Copy the pointers/colour from the victim to the replacement */ *new = *victim; } EXPORT_SYMBOL(rb_replace_node);
generated by cgit v1.2.2 (git 2.25.0) at 2025-09-16 19:28:54 -0400