Linux/lib/interval

Version: ~ [ linux-6.12-rc7 ] ~ [ linux-6.11.7 ] ~ [ linux-6.10.14 ] ~ [ linux-6.9.12 ] ~ [ linux-6.8.12 ] ~ [ linux-6.7.12 ] ~ [ linux-6.6.60 ] ~ [ linux-6.5.13 ] ~ [ linux-6.4.16 ] ~ [ linux-6.3.13 ] ~ [ linux-6.2.16 ] ~ [ linux-6.1.116 ] ~ [ linux-6.0.19 ] ~ [ linux-5.19.17 ] ~ [ linux-5.18.19 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.171 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.229 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.285 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.323 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.336 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.337 ] ~ [ linux-4.4.302 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.12 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

Diff markup

1 // SPDX-License-Identifier: GPL-2.0-only 1 // SPDX-License-Identifier: GPL-2.0-only 2 #include <linux/interval_tree.h> 2 #include <linux/interval_tree.h> 3 #include <linux/interval_tree_generic.h> 3 #include <linux/interval_tree_generic.h> 4 #include <linux/compiler.h> 4 #include <linux/compiler.h> 5 #include <linux/export.h> 5 #include <linux/export.h> 6 6 7 #define START(node) ((node)->start) 7 #define START(node) ((node)->start) 8 #define LAST(node) ((node)->last) 8 #define LAST(node) ((node)->last) 9 9 10 INTERVAL_TREE_DEFINE(struct interval_tree_node 10 INTERVAL_TREE_DEFINE(struct interval_tree_node, rb, 11 unsigned long, __subtree_ 11 unsigned long, __subtree_last, 12 START, LAST,, interval_tr 12 START, LAST,, interval_tree) 13 13 14 EXPORT_SYMBOL_GPL(interval_tree_insert); 14 EXPORT_SYMBOL_GPL(interval_tree_insert); 15 EXPORT_SYMBOL_GPL(interval_tree_remove); 15 EXPORT_SYMBOL_GPL(interval_tree_remove); 16 EXPORT_SYMBOL_GPL(interval_tree_iter_first); 16 EXPORT_SYMBOL_GPL(interval_tree_iter_first); 17 EXPORT_SYMBOL_GPL(interval_tree_iter_next); 17 EXPORT_SYMBOL_GPL(interval_tree_iter_next); 18 << 19 #ifdef CONFIG_INTERVAL_TREE_SPAN_ITER << 20 /* << 21 * Roll nodes[1] into nodes[0] by advancing no << 22 * span of nodes. This makes nodes[0]->last th << 23 * indexes that started at the original nodes[ << 24 * first node starting the next used span. A h << 25 * and nodes[1]->start. nodes[1] must be !NULL << 26 */ << 27 static void << 28 interval_tree_span_iter_next_gap(struct interv << 29 { << 30 struct interval_tree_node *cur = state << 31 << 32 state->nodes[0] = cur; << 33 do { << 34 if (cur->last > state->nodes[0 << 35 state->nodes[0] = cur; << 36 cur = interval_tree_iter_next( << 37 << 38 } while (cur && (state->nodes[0]->last << 39 state->nodes[0]->last << 40 state->nodes[1] = cur; << 41 } << 42 << 43 void interval_tree_span_iter_first(struct inte << 44 struct rb_r << 45 unsigned lo << 46 unsigned lo << 47 { << 48 iter->first_index = first_index; << 49 iter->last_index = last_index; << 50 iter->nodes[0] = NULL; << 51 iter->nodes[1] = << 52 interval_tree_iter_first(itree << 53 if (!iter->nodes[1]) { << 54 /* No nodes intersect the span << 55 iter->start_hole = first_index << 56 iter->last_hole = last_index; << 57 iter->is_hole = 1; << 58 return; << 59 } << 60 if (iter->nodes[1]->start > first_inde << 61 /* Leading hole on first itera << 62 iter->start_hole = first_index << 63 iter->last_hole = iter->nodes[ << 64 iter->is_hole = 1; << 65 interval_tree_span_iter_next_g << 66 return; << 67 } << 68 << 69 /* Starting inside a used */ << 70 iter->start_used = first_index; << 71 iter->is_hole = 0; << 72 interval_tree_span_iter_next_gap(iter) << 73 iter->last_used = iter->nodes[0]->last << 74 if (iter->last_used >= last_index) { << 75 iter->last_used = last_index; << 76 iter->nodes[0] = NULL; << 77 iter->nodes[1] = NULL; << 78 } << 79 } << 80 EXPORT_SYMBOL_GPL(interval_tree_span_iter_firs << 81 << 82 void interval_tree_span_iter_next(struct inter << 83 { << 84 if (!iter->nodes[0] && !iter->nodes[1] << 85 iter->is_hole = -1; << 86 return; << 87 } << 88 << 89 if (iter->is_hole) { << 90 iter->start_used = iter->last_ << 91 iter->last_used = iter->nodes[ << 92 if (iter->last_used >= iter->l << 93 iter->last_used = iter << 94 iter->nodes[0] = NULL; << 95 iter->nodes[1] = NULL; << 96 } << 97 iter->is_hole = 0; << 98 return; << 99 } << 100 << 101 if (!iter->nodes[1]) { << 102 /* Trailing hole */ << 103 iter->start_hole = iter->nodes << 104 iter->last_hole = iter->last_i << 105 iter->nodes[0] = NULL; << 106 iter->is_hole = 1; << 107 return; << 108 } << 109 << 110 /* must have both nodes[0] and [1], in << 111 iter->start_hole = iter->nodes[0]->las << 112 iter->last_hole = iter->nodes[1]->star << 113 iter->is_hole = 1; << 114 interval_tree_span_iter_next_gap(iter) << 115 } << 116 EXPORT_SYMBOL_GPL(interval_tree_span_iter_next << 117 << 118 /* << 119 * Advance the iterator index to a specific po << 120 * updated to start at new_index. This is fast << 121 * interval_tree_span_iter_first() as it can a << 122 * cases where the iterator is already set. << 123 */ << 124 void interval_tree_span_iter_advance(struct in << 125 struct rb << 126 unsigned << 127 { << 128 if (iter->is_hole == -1) << 129 return; << 130 << 131 iter->first_index = new_index; << 132 if (new_index > iter->last_index) { << 133 iter->is_hole = -1; << 134 return; << 135 } << 136 << 137 /* Rely on the union aliasing hole/use << 138 if (iter->start_hole <= new_index && n << 139 iter->start_hole = new_index; << 140 return; << 141 } << 142 if (new_index == iter->last_hole + 1) << 143 interval_tree_span_iter_next(i << 144 else << 145 interval_tree_span_iter_first( << 146 << 147 } << 148 EXPORT_SYMBOL_GPL(interval_tree_span_iter_adva << 149 #endif << 150 18

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

TOMOYO Linux Cross Reference
Linux/lib/interval_tree.c

Diff markup

Differences between /lib/interval_tree.c (Version linux-6.12-rc7) and /lib/interval_tree.c (Version linux-5.2.21)

TOMOYO Linux Cross Reference Linux/lib/interval_tree.c

Diff markup

Differences between /lib/interval_tree.c (Version linux-6.12-rc7) and /lib/interval_tree.c (Version linux-5.2.21)

TOMOYO Linux Cross Reference
Linux/lib/interval_tree.c