Lines Matching defs:node
76 * the use of a binary-search tree, where each node contains at least
87 * node, while the mask member stores the setting of the first 32-bits.
102 * node 0 - idx: 0x0 mask: 0xffffffff num_after: 0xffffffffffffffc0
103 * node 1 - idx: 0xffffffffffffffe0 mask: 0x3fffffff num_after: 0
117 * + A node with all mask bits set only occurs when the last bit
118 * described by the previous node is not equal to this nodes
131 * As a consequence of the above, the num_after member of a node
140 * range of bits described by a single node is:
142 * start: node->idx
143 * end (inclusive): node->idx + MASK_BITS + node->num_after - 1;
150 * index and assures that a node where its mask represents the bit
152 * must split an existing node into two nodes or create a node that
168 struct node {
169 struct node *parent;
170 struct node *left;
171 struct node *right;
179 * Points to root node of the binary search
183 struct node *root;
195 * of the node pointed to by nodep.
197 static sparsebit_num_t node_num_set(struct node *nodep)
202 /* Returns a pointer to the node that describes the
205 static struct node *node_first(struct sparsebit *s)
207 struct node *nodep;
215 /* Returns a pointer to the node that describes the
216 * lowest bit index > the index of the node pointed to by np.
217 * Returns NULL if no node with a higher index exists.
219 static struct node *node_next(struct sparsebit *s, struct node *np)
221 struct node *nodep = np;
224 * If current node has a right child, next node is the left-most
234 * No right child. Go up until node is left child of a parent.
235 * That parent is then the next node.
243 /* Searches for and returns a pointer to the node that describes the
244 * highest index < the index of the node pointed to by np.
245 * Returns NULL if no node with a lower index exists.
247 static struct node *node_prev(struct sparsebit *s, struct node *np)
249 struct node *nodep = np;
252 * If current node has a left child, next node is the right-most
258 return (struct node *) nodep;
262 * No left child. Go up until node is right child of a parent.
263 * That parent is then the next node.
268 return (struct node *) nodep->parent;
272 /* Allocates space to hold a copy of the node sub-tree pointed to by
276 static struct node *node_copy_subtree(struct node *subtree)
278 struct node *root;
280 /* Duplicate the node at the root of the subtree */
305 /* Searches for and returns a pointer to the node that describes the setting
306 * of the bit given by idx. A node describes the setting of a bit if its
308 * contiguous bits set after the mask. Returns NULL if there is no such node.
310 static struct node *node_find(struct sparsebit *s, sparsebit_idx_t idx)
312 struct node *nodep;
314 /* Find the node that describes the setting of the bit at idx */
326 * + A node that describes the setting of idx is not already present.
328 * Adds a new node to describe the setting of the bit at the index given
329 * by idx. Returns a pointer to the newly added node.
333 static struct node *node_add(struct sparsebit *s, sparsebit_idx_t idx)
335 struct node *nodep, *parentp, *prev;
337 /* Allocate and initialize the new node. */
346 /* If no nodes, set it up as the root node. */
353 * Find the parent where the new node should be attached
354 * and add the node there.
377 * Does num_after bits of previous node overlap with the mask
378 * of the new node? If so set the bits in the new nodes mask
406 /* Clears all bits described by the node pointed to by nodep, then
407 * removes the node.
409 static void node_rm(struct sparsebit *s, struct node *nodep)
411 struct node *tmp;
421 * Move left children to the leftmost leaf node
492 /* Splits the node containing the bit at idx so that there is a node
493 * that starts at the specified index. If no such node exists, a new
494 * node at the specified index is created. Returns the new node.
498 static struct node *node_split(struct sparsebit *s, sparsebit_idx_t idx)
500 struct node *nodep1, *nodep2;
507 * Is there a node that describes the setting of idx?
515 * All done if the starting index of the node is where the
534 * Add a new node to describe the bits starting at
540 /* Move bits after the split point into the new node */
553 /* Iteratively reduces the node pointed to by nodep and its adjacent
554 * nodes into a more compact form. For example, a node with a mask with
555 * all bits set adjacent to a previous node, will get combined into a
556 * single node with an increased num_after setting.
563 * responsibility of the caller to pass a nodep that is within one node
571 * of which node has the correct setting of the bit and thus such conditions
580 * node address that it set a mask bit in, and node_reduce() will notice
582 * adjacent node that the bit settings could be merged into.
593 * + A node with all mask bits set only occurs when the last bit
594 * described by the previous node is not equal to this nodes
599 static void node_reduce(struct sparsebit *s, struct node *nodep)
605 struct node *prev, *next, *tmp;
607 /* 1) Potential reductions within the current node. */
612 * About to remove the node pointed to by
615 * because the node at the starting point no longer
619 * once the node at nodep is removed, there will be
624 * node that can be reduced into a single node. As
625 * such, after removing the node at nodep, doesn't
628 * prev or next node. Either way, on the next pass
630 * prev or next node.
683 * All mask bits set and previous node has
697 * Is node adjacent to previous node and the node
756 * Is next node index adjacent to current node
781 struct node *nodep;
783 /* Find the node that describes the setting of the bit at idx */
807 struct node *nodep;
814 * Get a node where the bit at idx is described by the mask.
815 * The node_split will also create a node, if there isn't
816 * already a node that describes the setting of bit.
834 struct node *nodep;
840 /* Is there a node that describes the setting of this bit? */
846 * If a num_after bit, split the node, so that the bit is
847 * part of a node mask.
872 static void dump_nodes(FILE *stream, struct node *nodep,
877 /* Dump contents of node */
901 static inline sparsebit_idx_t node_first_set(struct node *nodep, int start)
909 static inline sparsebit_idx_t node_first_clear(struct node *nodep, int start)
1061 * Every node should have a non-zero mask. For now will
1062 * just assure that the root node has a non-zero mask,
1089 struct node *nodep;
1103 struct node *nodep1, *nodep2;
1108 /* If no nodes or first node index > 0 then lowest cleared is 0 */
1113 /* Does the mask in the first node contain any cleared bits. */
1118 * All mask bits set in first node. If there isn't a second node
1120 * described by the first node.
1125 * No second node. First cleared bit is first bit beyond
1126 * bits described by first node.
1134 * There is a second node.
1135 * If it is not adjacent to the first node, then there is a gap
1143 * Second node is adjacent to the first node.
1147 * previous node.
1160 struct node *nodep;
1170 struct node *candidate = NULL;
1176 * Find node that describes setting of bit at lowest_possible.
1177 * If such a node doesn't exist, find the node with the lowest
1198 /* Does the candidate node describe the setting of lowest_possible? */
1202 * Candidate points to the first node with a starting index
1212 * Note: although the node describes the setting of the bit
1214 * setting of all latter bits described by this node are 0.
1215 * For now, just handle the cases where this node describes
1231 * Although candidate node describes setting of bit at
1234 * this, the next bit is the first bit in the next node, if
1235 * such a node exists. If a next node doesn't exist, then
1253 struct node *nodep1, *nodep2;
1260 * Does a node describing the setting of lowest_possible exist?
1267 /* Does a mask bit in node 1 describe the next cleared bit. */
1273 * Next cleared bit is not described by node 1. If there
1274 * isn't a next node, then next cleared bit is described
1275 * by bit after the bits described by the first node.
1282 * There is a second node.
1283 * If it is not adjacent to the first node, then there is a gap
1291 * Second node is adjacent to the first node.
1295 * previous node.
1374 struct node *nodep, *next;
1390 * 1. Use node_split() to force node that describes setting
1391 * of idx to be within the mask portion of a node.
1393 * 3. Determine number of mask bits already set in the node
1395 * 4. Set the appropriate mask bits within the node.
1456 struct node *nodep, *next;
1505 * Delete the node that describes the beginning of
1592 struct node *nodep;
1600 /* For each node */
1688 struct node *nodep, *prev = NULL;
1692 /* For each node */
1698 * in this node.
1741 /* Validate node index is divisible by the mask size */
1753 * Validate bits described by node don't wrap beyond the
1757 fprintf(stderr, "Bits described by node wrap "
1770 "doesn't point to this node,\n"
1783 "doesn't point to this node,\n"
1795 fprintf(stderr, "Unexpected root node, "
1805 * Is index of previous node before index of
1806 * current node?
1809 fprintf(stderr, "Previous node index "
1810 ">= current node index,\n"
1824 fprintf(stderr, "Previous node bit range "
1825 "overlap with current node bit range,\n"
1839 * When the node has all mask bits set, it shouldn't
1841 * previous node.
1845 fprintf(stderr, "Current node has mask with "
1847 "previous node,\n"
1865 * Is sum of bits set in each node equal to the count