Page MenuHomeFreeBSD
Files F145934058

D35516.id107152.diff
No OneTemporary
Actions

D35516.id107152.diff
View Options

Index: share/man/man3/tree.3
===================================================================
--- share/man/man3/tree.3
+++ share/man/man3/tree.3
@@ -97,6 +97,7 @@
.Nm RB_FOREACH_REVERSE_SAFE ,
.Nm RB_INIT ,
.Nm RB_INSERT ,
+.Nm RB_INSERT_AT ,
.Nm RB_REMOVE ,
.Nm RB_REINSERT
.Nd "implementations of splay and rank-balanced (wavl) trees"
@@ -189,6 +190,8 @@
.Fn RB_INIT "RB_HEAD *head"
.Ft "struct TYPE *"
.Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
+.Ft "void"
+.Fn RB_INSERT NAME_AT "RB_HEAD *head" "struct TYPE *parent" "int comp" "struct TYPE *elm"
.Ft "struct TYPE *"
.Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *"
@@ -506,6 +509,12 @@
into the tree.
.Pp
The
+.Fn RB_INSERT_AT
+macro inserts the new element
+.Fa elm
+into the tree as a child of a specified parent.
+.Pp
+The
.Fn RB_REMOVE
macro removes the element
.Fa elm
Index: sys/dev/iommu/iommu_gas.c
===================================================================
--- sys/dev/iommu/iommu_gas.c
+++ sys/dev/iommu/iommu_gas.c
@@ -352,9 +352,9 @@
}
static void
-iommu_gas_match_insert(struct iommu_gas_match_args *a)
+iommu_gas_match_insert(struct iommu_gas_match_args *a,
+ struct iommu_map_entry *parent, int comp)
{
- bool found __diagused;
/*
* The prev->end is always aligned on the page size, which
@@ -367,9 +367,15 @@
a->entry->end = a->entry->start +
roundup2(a->size + a->offset, IOMMU_PAGE_SIZE);
- found = iommu_gas_rb_insert(a->domain, a->entry);
- KASSERT(found, ("found dup %p start %jx size %jx",
- a->domain, (uintmax_t)a->entry->start, (uintmax_t)a->size));
+ if (comp < 0) {
+ while (RB_LEFT(first, rb_entry) != NULL)
+ first = RB_LEFT(first, rb_entry);
+ } else {
+ while (RB_RIGHT(first, rb_entry) != NULL)
+ first = RB_RIGHT(first, rb_entry);
+ }
+ RB_INSERT_AT(iommu_gas_entries_tree,
+ &a->domain->rb_root, parent, comp, a->entry);
a->entry->flags = IOMMU_MAP_ENTRY_MAP;
}
@@ -406,7 +412,7 @@
}
if (iommu_gas_match_one(a, first->last, entry->start,
a->common->lowaddr)) {
- iommu_gas_match_insert(a);
+ iommu_gas_match_insert(a, first, RB_INF);
return (0);
}
}
@@ -417,7 +423,7 @@
if ((first = RB_RIGHT(entry, rb_entry)) != NULL &&
iommu_gas_match_one(a, entry->end, first->first,
a->common->lowaddr)) {
- iommu_gas_match_insert(a);
+ iommu_gas_match_insert(a, first, RB_NEGINF);
return (0);
}
/* Find the next entry that might abut a big-enough range. */
@@ -458,14 +464,14 @@
if (child != NULL && child->last >= a->common->highaddr &&
iommu_gas_match_one(a, child->last, entry->start,
a->domain->end)) {
- iommu_gas_match_insert(a);
+ iommu_gas_match_insert(a, child, RB_INF);
return (0);
}
child = RB_RIGHT(entry, rb_entry);
if (child != NULL && entry->end >= a->common->highaddr &&
iommu_gas_match_one(a, entry->end, child->first,
a->domain->end)) {
- iommu_gas_match_insert(a);
+ iommu_gas_match_insert(a, child, RB_NEGINF);
return (0);
}
if (child != NULL && 0 == iommu_gas_uppermatch(a, child))
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -411,6 +411,7 @@
#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
+ RB_PROTOTYPE_INSERT_AT(name, type, attr); \
RB_PROTOTYPE_INSERT(name, type, attr); \
RB_PROTOTYPE_REMOVE(name, type, attr); \
RB_PROTOTYPE_FIND(name, type, attr); \
@@ -426,6 +427,9 @@
struct type *, struct type *)
#define RB_PROTOTYPE_REMOVE(name, type, attr) \
attr struct type *name##_RB_REMOVE(struct name *, struct type *)
+#define RB_PROTOTYPE_INSERT_AT(name, type, attr) \
+ attr void name##_RB_INSERT_AT(struct name *, struct type *, \
+ int, struct type *)
#define RB_PROTOTYPE_INSERT(name, type, attr) \
attr struct type *name##_RB_INSERT(struct name *, struct type *)
#define RB_PROTOTYPE_FIND(name, type, attr) \
@@ -451,6 +455,7 @@
#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
+ RB_GENERATE_INSERT_AT(name, type, field, cmp, attr) \
RB_GENERATE_INSERT(name, type, field, cmp, attr) \
RB_GENERATE_REMOVE(name, type, field, attr) \
RB_GENERATE_FIND(name, type, field, cmp, attr) \
@@ -634,6 +639,26 @@
return (old); \
}
+#define RB_GENERATE_INSERT_AT(name, type, field, cmp, attr) \
+/* Inserts a node into the RB tree */ \
+attr void \
+name##_RB_INSERT_AT(struct name *head, struct type *parent, \
+ int comp, struct type *elm) \
+{ \
+ RB_SET(elm, parent, field); \
+ if (parent == NULL) \
+ RB_ROOT(head) = elm; \
+ else if (comp < 0) \
+ RB_LEFT(parent, field) = elm; \
+ else \
+ RB_RIGHT(parent, field) = elm; \
+ name##_RB_INSERT_COLOR(head, elm); \
+ while (elm != NULL) { \
+ RB_AUGMENT(elm); \
+ elm = RB_PARENT(elm, field); \
+ } \
+}
+
#define RB_GENERATE_INSERT(name, type, field, cmp, attr) \
/* Inserts a node into the RB tree */ \
attr struct type * \
@@ -653,18 +678,7 @@
else \
return (tmp); \
} \
- RB_SET(elm, parent, field); \
- if (parent == NULL) \
- RB_ROOT(head) = elm; \
- else if (comp < 0) \
- RB_LEFT(parent, field) = elm; \
- else \
- RB_RIGHT(parent, field) = elm; \
- name##_RB_INSERT_COLOR(head, elm); \
- while (elm != NULL) { \
- RB_AUGMENT(elm); \
- elm = RB_PARENT(elm, field); \
- } \
+ name##_RB_INSERT_AT(head, parent, comp, elm); \
return (NULL); \
}
@@ -781,6 +795,7 @@
#define RB_INF 1
#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
+#define RB_INSERT_AT(name, x, y, z, w)name##_RB_INSERT_AT(x, y, z, w)
#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)

File Metadata

Mime Type
text/plain
Expires
Fri, Feb 27, 7:41 AM (12 h, 9 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
29021223
Default Alt Text
D35516.id107152.diff (5 KB)

Event Timeline