Page MenuHomeFreeBSD
Files F146613648

D47680.id146737.diff
No OneTemporary
Actions

D47680.id146737.diff
View Options

Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -539,14 +539,27 @@
enum pctrie_access access)
{
struct pctrie_node *node;
- int slot;
+ int slot, top;
+
+ top = it->top;
+ if (top != 0) {
+ node = it->path[top - 1];
+ KASSERT(!powerof2(node->pn_popmap),
+ ("%s: freed node in iter path", __func__));
+ if (!pctrie_keybarr(node, index, &slot)) {
+ node = pctrie_node_load(
+ &node->pn_child[slot], smr, access);
+ if (pctrie_isleaf(node))
+ return (node);
+ }
+ }
/*
* Climb the search path to find the lowest node from which to start the
* search for a value matching 'index'.
*/
- while (it->top != 0) {
- node = it->path[it->top - 1];
+ while (top != 0) {
+ node = it->path[top - 1];
KASSERT(!powerof2(node->pn_popmap),
("%s: freed node in iter path", __func__));
if (!pctrie_keybarr(node, index, &slot)) {
@@ -554,18 +567,19 @@
&node->pn_child[slot], smr, access);
break;
}
- --it->top;
+ --top;
}
- if (it->top == 0)
+ if (top == 0)
node = pctrie_root_load(it->ptree, smr, access);
/* Seek a node that matches index. */
while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot)) {
- KASSERT(it->top < nitems(it->path),
+ KASSERT(top < nitems(it->path),
("%s: path overflow in trie %p", __func__, it->ptree));
- it->path[it->top++] = node;
+ it->path[top++] = node;
node = pctrie_node_load(&node->pn_child[slot], smr, access);
}
+ it->top = top;
return (node);
}
@@ -781,6 +795,43 @@
return (pctrie_lookup_ge_node(node, index + 1));
}
+static struct pctrie_node *
+_pctrie_iter_lookup_gt_node(struct pctrie_iter *it, uint64_t index)
+{
+ struct pctrie_node *node;
+ int slot, top;
+
+ top = it->top;
+ if (top != 0) {
+ node = it->path[top - 1];
+ slot = pctrie_slot(node, index);
+ if ((node->pn_popmap & (-2 << slot)) != 0) {
+ /* Return least child with a descendant > index. */
+ slot = ffs(node->pn_popmap & (-2 << slot)) - 1;
+ node = pctrie_node_load(&node->pn_child[slot], NULL,
+ PCTRIE_LOCKED);
+ return (node);
+ }
+ --top;
+ }
+ while (top != 0) {
+ node = it->path[top - 1];
+ slot = pctrie_slot(node, index);
+ if ((node->pn_popmap & (-2 << slot)) != 0) {
+ /* Return least child with a descendant > index. */
+ slot = ffs(node->pn_popmap & (-2 << slot)) - 1;
+ node = pctrie_node_load(&node->pn_child[slot], NULL,
+ PCTRIE_LOCKED);
+ it->top = top;
+ return (node);
+ }
+ --top;
+ }
+ it->top = 0;
+ return (NULL);
+
+}
+
/*
* Find first leaf >= index, and fill iter with the path to the parent of that
* leaf. Return NULL if there is no such leaf less than limit.
@@ -801,21 +852,11 @@
*/
if (node == PCTRIE_NULL || *pctrie_toval(node) < index) {
/* Climb the path to find a node with a descendant > index. */
- while (it->top != 0) {
- node = it->path[it->top - 1];
- slot = pctrie_slot(node, index) + 1;
- if ((node->pn_popmap >> slot) != 0)
- break;
- --it->top;
- }
- if (it->top == 0)
+ node = _pctrie_iter_lookup_gt_node(it, index);
+ if (node == NULL)
return (NULL);
-
- /* Step to the least child with a descendant > index. */
- slot += ffs(node->pn_popmap >> slot) - 1;
- node = pctrie_node_load(&node->pn_child[slot], NULL,
- PCTRIE_LOCKED);
}
+
/* Descend to the least leaf of the subtrie. */
while (!pctrie_isleaf(node)) {
if (it->limit != 0 && node->pn_owner >= it->limit)
@@ -938,6 +979,44 @@
return (pctrie_lookup_le_node(node, index - 1));
}
+static struct pctrie_node *
+_pctrie_iter_lookup_lt_node(struct pctrie_iter *it, uint64_t index)
+{
+ struct pctrie_node *node;
+ int slot, top;
+
+ top = it->top;
+ if (top != 0) {
+ node = it->path[top - 1];
+ slot = pctrie_slot(node, index);
+ if ((node->pn_popmap & ((1 << slot) - 1)) != 0) {
+ /* Return greatest child with a descendant < index. */
+ slot = ilog2(node->pn_popmap & ((1 << slot) - 1));
+ node = pctrie_node_load(&node->pn_child[slot], NULL,
+ PCTRIE_LOCKED);
+ return (node);
+ }
+ --top;
+ }
+
+ while (top != 0) {
+ node = it->path[top - 1];
+ slot = pctrie_slot(node, index);
+ if ((node->pn_popmap & ((1 << slot) - 1)) != 0) {
+ /* Return greatest child with a descendant < index. */
+ slot = ilog2(node->pn_popmap & ((1 << slot) - 1));
+ node = pctrie_node_load(&node->pn_child[slot], NULL,
+ PCTRIE_LOCKED);
+ it->top = top;
+ return (node);
+ }
+ --top;
+ }
+ it->top = 0;
+ return (NULL);
+
+}
+
/*
* Find first leaf <= index, and fill iter with the path to the parent of that
* leaf. Return NULL if there is no such leaf greater than limit.
@@ -958,21 +1037,11 @@
*/
if (node == PCTRIE_NULL || *pctrie_toval(node) > index) {
/* Climb the path to find a node with a descendant < index. */
- while (it->top != 0) {
- node = it->path[it->top - 1];
- slot = pctrie_slot(node, index);
- if ((node->pn_popmap & ((1 << slot) - 1)) != 0)
- break;
- --it->top;
- }
- if (it->top == 0)
+ node = _pctrie_iter_lookup_lt_node(it, index);
+ if (node == NULL)
return (NULL);
-
- /* Step to the greatest child with a descendant < index. */
- slot = ilog2(node->pn_popmap & ((1 << slot) - 1));
- node = pctrie_node_load(&node->pn_child[slot], NULL,
- PCTRIE_LOCKED);
}
+
/* Descend to the greatest leaf of the subtrie. */
while (!pctrie_isleaf(node)) {
if (it->limit != 0 && it->limit >=

File Metadata

Mime Type
text/plain
Expires
Thu, Mar 5, 2:55 AM (26 m, 13 s)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
29268061
Default Alt Text
D47680.id146737.diff (5 KB)

Event Timeline