Skip to contentSkip to conversation

Red Black Tree cleanups [2/2]

PATCH RESEND New David Woodhouse 1 participant 1 message Sep 12, 2002

Subsystems (7)
Networking Memory management Library code MM core +3 more subsystems
lore
Share & tools
lore

David Woodhouse

author
#0 lore raw

PATCH RESEND 1/1 Red Black Tree cleanups [2/2]

This is the second of two rbtree patches which can be pulled from

	master.kernel.org:/home/dwmw2/BK/rbtree-2.5

This replaces the bogus 'rb_node_t' and 'rb_root_t' typedefs with 'struct rb_node' and 'struct rb_root' respectively. It also removes a duplicate 'rb_next' function from net/sched/sch_htb.c.

# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher. # This patch includes the following deltas:

#	           ChangeSet	1.622   -> 1.623  
#	  include/linux/mm.h	1.77    -> 1.78   
#	           mm/mmap.c	1.45    -> 1.46   
#	        lib/rbtree.c	1.3     -> 1.4

# include/linux/sched.h 1.88 -> 1.89
# include/linux/rbtree.h 1.2 -> 1.3
# net/sched/sch_htb.c 1.2 -> 1.3
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 02/09/09 [email protected] 1.623
# Remove bogus rb_root_t and rb_node_t typedefs in favour of 'struct rb_node' and 'struct rb_root' # Remove duplicate implementation of rb_next() in net/sched/sch_htb.c while we're at it. # --------------------------------------------
#

include/linux/mm.h +1 -1
diff -Nru a/include/linux/mm.h b/include/linux/mm.h
@@ -54,7 +54,7 @@
 	pgprot_t vm_page_prot;		/* Access permissions of this VMA. */
 	unsigned long vm_flags;		/* Flags, listed below. */
 
-	rb_node_t vm_rb;
+	struct rb_node vm_rb;
 
 	/*
 	 * For areas with an address space and backing store,
include/linux/rbtree.h +22 -22

84 lines not on this page · raw message

include/linux/sched.h +1 -1
diff -Nru a/include/linux/sched.h b/include/linux/sched.h
@@ -173,7 +173,7 @@
 struct kioctx;
 struct mm_struct {
 	struct vm_area_struct * mmap;		/* list of VMAs */
-	rb_root_t mm_rb;
+	struct rb_root mm_rb;
 	struct vm_area_struct * mmap_cache;	/* last find_vma result */
 	pgd_t * pgd;
 	atomic_t mm_users;			/* How many users with user space? */
lib/rbtree.c +23 -22

141 lines not on this page · raw message

mm/mmap.c +18 -16
diff -Nru a/mm/mmap.c b/mm/mmap.c
@@ -245,7 +245,7 @@
 }
 
 #ifdef DEBUG_MM_RB
-static int browse_rb(rb_node_t * rb_node) {
+static int browse_rb(struct rb_node * rb_node) {
 	int i = 0;
 	if (rb_node) {
 		i++;

@@ -277,10 +277,11 @@
 
 static struct vm_area_struct * find_vma_prepare(struct mm_struct * mm, unsigned long addr,
 						struct vm_area_struct ** pprev,
-						rb_node_t *** rb_link, rb_node_t ** rb_parent)
+						struct rb_node *** rb_link,
+						struct rb_node ** rb_parent)
 {
 	struct vm_area_struct * vma;
-	rb_node_t ** __rb_link, * __rb_parent, * rb_prev;
+	struct rb_node ** __rb_link, * __rb_parent, * rb_prev;
 
 	__rb_link = &mm->mm_rb.rb_node;
 	rb_prev = __rb_parent = NULL;

@@ -311,8 +312,8 @@
 	return vma;
 }
 
-static inline void __vma_link_list(struct mm_struct * mm, struct vm_area_struct * vma, struct vm_area_struct * prev,
-				   rb_node_t * rb_parent)
+static inline void __vma_link_list(struct mm_struct * mm, struct vm_area_struct * vma,
+				   struct vm_area_struct * prev, struct rb_node * rb_parent)
 {
 	if (prev) {
 		vma->vm_next = prev->vm_next;

@@ -327,7 +328,7 @@
 }
 
 static inline void __vma_link_rb(struct mm_struct * mm, struct vm_area_struct * vma,
-				 rb_node_t ** rb_link, rb_node_t * rb_parent)
+				 struct rb_node ** rb_link, struct rb_node * rb_parent)
 {
 	rb_link_node(&vma->vm_rb, rb_parent, rb_link);
 	rb_insert_color(&vma->vm_rb, &mm->mm_rb);

@@ -353,7 +354,7 @@
 }
 
 static void __vma_link(struct mm_struct * mm, struct vm_area_struct * vma,  struct vm_area_struct * prev,
-		       rb_node_t ** rb_link, rb_node_t * rb_parent)
+		       struct rb_node ** rb_link, struct rb_node * rb_parent)
 {
 	__vma_link_list(mm, vma, prev, rb_parent);
 	__vma_link_rb(mm, vma, rb_link, rb_parent);

@@ -361,7 +362,7 @@
 }
 
 static inline void vma_link(struct mm_struct * mm, struct vm_area_struct * vma, struct vm_area_struct * prev,
-			    rb_node_t ** rb_link, rb_node_t * rb_parent)
+			    struct rb_node ** rb_link, struct rb_node * rb_parent)
 {
 	spin_lock(&mm->page_table_lock);
 	lock_vma_mappings(vma);

@@ -374,7 +375,8 @@
 }
 
 static int vma_merge(struct mm_struct * mm, struct vm_area_struct * prev,
-		     rb_node_t * rb_parent, unsigned long addr, unsigned long end, unsigned long vm_flags)
+		     struct rb_node * rb_parent, unsigned long addr, 
+		     unsigned long end, unsigned long vm_flags)
 {
 	spinlock_t * lock = &mm->page_table_lock;
 	if (!prev) {

@@ -426,7 +428,7 @@
 	unsigned int vm_flags;
 	int correct_wcount = 0;
 	int error;
-	rb_node_t ** rb_link, * rb_parent;
+	struct rb_node ** rb_link, * rb_parent;
 	unsigned long charged = 0;
 
 	if (file && (!file->f_op || !file->f_op->mmap))

@@ -698,7 +700,7 @@
 		/* (Cache hit rate is typically around 35%.) */
 		vma = mm->mmap_cache;
 		if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
-			rb_node_t * rb_node;
+			struct rb_node * rb_node;
 
 			rb_node = mm->mm_rb.rb_node;
 			vma = NULL;

@@ -728,7 +730,7 @@
 				      struct vm_area_struct **pprev)
 {
 	struct vm_area_struct *vma = NULL, *prev = NULL;
-	rb_node_t * rb_node;
+	struct rb_node * rb_node;
 	if (!mm)
 		goto out;
 

@@ -1158,7 +1160,7 @@
 	struct mm_struct * mm = current->mm;
 	struct vm_area_struct * vma, * prev;
 	unsigned long flags;
-	rb_node_t ** rb_link, * rb_parent;
+	struct rb_node ** rb_link, * rb_parent;
 
 	len = PAGE_ALIGN(len);
 	if (!len)

@@ -1236,7 +1238,7 @@
 void build_mmap_rb(struct mm_struct * mm)
 {
 	struct vm_area_struct * vma;
-	rb_node_t ** rb_link, * rb_parent;
+	struct rb_node ** rb_link, * rb_parent;
 
 	mm->mm_rb = RB_ROOT;
 	rb_link = &mm->mm_rb.rb_node;

@@ -1319,7 +1321,7 @@
 void __insert_vm_struct(struct mm_struct * mm, struct vm_area_struct * vma)
 {
 	struct vm_area_struct * __vma, * prev;
-	rb_node_t ** rb_link, * rb_parent;
+	struct rb_node ** rb_link, * rb_parent;
 
 	__vma = find_vma_prepare(mm, vma->vm_start, &prev, &rb_link, &rb_parent);
 	if (__vma && __vma->vm_start < vma->vm_end)

@@ -1332,7 +1334,7 @@
 void insert_vm_struct(struct mm_struct * mm, struct vm_area_struct * vma)
 {
 	struct vm_area_struct * __vma, * prev;
-	rb_node_t ** rb_link, * rb_parent;
+	struct rb_node ** rb_link, * rb_parent;
 
 	__vma = find_vma_prepare(mm, vma->vm_start, &prev, &rb_link, &rb_parent);
 	if (__vma && __vma->vm_start < vma->vm_end)
net/sched/sch_htb.c +18 -29

107 lines not on this page · raw message

--
dwmw2