// SPDX-License-Identifier: GPL-2.0-only/* * Sparse bit array * * Copyright (C) 2018, Google LLC. * Copyright (C) 2018, Red Hat, Inc. (code style cleanup and fuzzing driver) * * This library provides functions to support a memory efficient bit array, * with an index size of 2^64. A sparsebit array is allocated through * the use sparsebit_alloc() and free'd via sparsebit_free(), * such as in the following: * * struct sparsebit *s; * s = sparsebit_alloc(); * sparsebit_free(&s); * * The struct sparsebit type resolves down to a struct sparsebit. * Note that, sparsebit_free() takes a pointer to the sparsebit * structure. This is so that sparsebit_free() is able to poison * the pointer (e.g. set it to NULL) to the struct sparsebit before * returning to the caller. * * Between the return of sparsebit_alloc() and the call of * sparsebit_free(), there are multiple query and modifying operations * that can be performed on the allocated sparsebit array. All of * these operations take as a parameter the value returned from * sparsebit_alloc() and most also take a bit index. Frequently * used routines include: * * ---- Query Operations * sparsebit_is_set(s, idx) * sparsebit_is_clear(s, idx) * sparsebit_any_set(s) * sparsebit_first_set(s) * sparsebit_next_set(s, prev_idx) * * ---- Modifying Operations * sparsebit_set(s, idx) * sparsebit_clear(s, idx) * sparsebit_set_num(s, idx, num); * sparsebit_clear_num(s, idx, num); * * A common operation, is to itterate over all the bits set in a test * sparsebit array. This can be done via code with the following structure: * * sparsebit_idx_t idx; * if (sparsebit_any_set(s)) { * idx = sparsebit_first_set(s); * do { * ... * idx = sparsebit_next_set(s, idx); * } while (idx != 0); * } * * The index of the first bit set needs to be obtained via * sparsebit_first_set(), because sparsebit_next_set(), needs * the index of the previously set. The sparsebit_idx_t type is * unsigned, so there is no previous index before 0 that is available. * Also, the call to sparsebit_first_set() is not made unless there * is at least 1 bit in the array set. This is because sparsebit_first_set() * aborts if sparsebit_first_set() is called with no bits set. * It is the callers responsibility to assure that the * sparsebit array has at least a single bit set before calling * sparsebit_first_set(). * * ==== Implementation Overview ==== * For the most part the internal implementation of sparsebit is * opaque to the caller. One important implementation detail that the * caller may need to be aware of is the spatial complexity of the * implementation. This implementation of a sparsebit array is not * only sparse, in that it uses memory proportional to the number of bits * set. It is also efficient in memory usage when most of the bits are * set. * * At a high-level the state of the bit settings are maintained through * the use of a binary-search tree, where each node contains at least * the following members: * * typedef u64 sparsebit_idx_t; * typedef u64 sparsebit_num_t; * * sparsebit_idx_t idx; * u32 mask; * sparsebit_num_t num_after; * * The idx member contains the bit index of the first bit described by this * node, while the mask member stores the setting of the first 32-bits. * The setting of the bit at idx + n, where 0 <= n < 32, is located in the * mask member at 1 << n. * * Nodes are sorted by idx and the bits described by two nodes will never * overlap. The idx member is always aligned to the mask size, i.e. a * multiple of 32. * * Beyond a typical implementation, the nodes in this implementation also * contains a member named num_after. The num_after member holds the * number of bits immediately after the mask bits that are contiguously set. * The use of the num_after member allows this implementation to efficiently * represent cases where most bits are set. For example, the case of all * but the last two bits set, is represented by the following two nodes: * * node 0 - idx: 0x0 mask: 0xffffffff num_after: 0xffffffffffffffc0 * node 1 - idx: 0xffffffffffffffe0 mask: 0x3fffffff num_after: 0 * * ==== Invariants ==== * This implementation usses the following invariants: * * + Node are only used to represent bits that are set. * Nodes with a mask of 0 and num_after of 0 are not allowed. * * + Sum of bits set in all the nodes is equal to the value of * the struct sparsebit_pvt num_set member. * * + The setting of at least one bit is always described in a nodes * mask (mask >= 1). * * + A node with all mask bits set only occurs when the last bit * described by the previous node is not equal to this nodes * starting index - 1. All such occurrences of this condition are * avoided by moving the setting of the nodes mask bits into * the previous nodes num_after setting. * * + Node starting index is evenly divisible by the number of bits * within a nodes mask member. * * + Nodes never represent a range of bits that wrap around the * highest supported index. * * (idx + MASK_BITS + num_after - 1) <= ((sparsebit_idx_t) 0) - 1) * * As a consequence of the above, the num_after member of a node * will always be <=: * * maximum_index - nodes_starting_index - number_of_mask_bits * * + Nodes within the binary search tree are sorted based on each * nodes starting index. * * + The range of bits described by any two nodes do not overlap. The * range of bits described by a single node is: * * start: node->idx * end (inclusive): node->idx + MASK_BITS + node->num_after - 1; * * Note, at times these invariants are temporarily violated for a * specific portion of the code. For example, when setting a mask * bit, there is a small delay between when the mask bit is set and the * value in the struct sparsebit_pvt num_set member is updated. Other * temporary violations occur when node_split() is called with a specified * index and assures that a node where its mask represents the bit * at the specified index exists. At times to do this node_split() * must split an existing node into two nodes or create a node that * has no bits set. Such temporary violations must be corrected before * returning to the caller. These corrections are typically performed * by the local function node_reduce(). */ #include "test_util.h"#include "sparsebit.h"#include <limits.h>#include <assert.h> #define DUMP_LINE_MAX 100 /* Does not include indent amount */ typedef u32 mask_t;#define MASK_BITS (sizeof(mask_t) * CHAR_BIT) struct node { struct node *parent; struct node *left; struct node *right; sparsebit_idx_t idx; /* index of least-significant bit in mask */ sparsebit_num_t num_after; /* num contiguously set after mask */ mask_t mask;}; struct sparsebit { /* * Points to root node of the binary search * tree. Equal to NULL when no bits are set in * the entire sparsebit array. */ struct node *root; /* * A redundant count of the total number of bits set. Used for * diagnostic purposes and to change the time complexity of * sparsebit_num_set() from O(n) to O(1). * Note: Due to overflow, a value of 0 means none or all set. */ sparsebit_num_t num_set;}; /* Returns the number of set bits described by the settings * of the node pointed to by nodep. */static sparsebit_num_t node_num_set(struct node *nodep){ return nodep->num_after + __builtin_popcount(nodep->mask);} /* Returns a pointer to the node that describes the * lowest bit index. */static struct node *node_first(const struct sparsebit *s){ struct node *nodep; for (nodep = s->root; nodep && nodep->left; nodep = nodep->left) ; return nodep;} /* Returns a pointer to the node that describes the * lowest bit index > the index of the node pointed to by np. * Returns NULL if no node with a higher index exists. */static struct node *node_next(const struct sparsebit *s, struct node *np){ struct node *nodep = np; /* * If current node has a right child, next node is the left-most * of the right child. */ if (nodep->right) { for (nodep = nodep->right; nodep->left; nodep = nodep->left) ; return nodep; } /* * No right child. Go up until node is left child of a parent. * That parent is then the next node. */ while (nodep->parent && nodep == nodep->parent->right) nodep = nodep->parent; return nodep->parent;} /* Searches for and returns a pointer to the node that describes the * highest index < the index of the node pointed to by np. * Returns NULL if no node with a lower index exists. */static struct node *node_prev(const struct sparsebit *s, struct node *np){ struct node *nodep = np; /* * If current node has a left child, next node is the right-most * of the left child. */ if (nodep->left) { for (nodep = nodep->left; nodep->right; nodep = nodep->right) ; return (struct node *) nodep; } /* * No left child. Go up until node is right child of a parent. * That parent is then the next node. */ while (nodep->parent && nodep == nodep->parent->left) nodep = nodep->parent; return (struct node *) nodep->parent;} /* Allocates space to hold a copy of the node sub-tree pointed to by * subtree and duplicates the bit settings to the newly allocated nodes. * Returns the newly allocated copy of subtree. */static struct node *node_copy_subtree(const struct node *subtree){ struct node *root; /* Duplicate the node at the root of the subtree */ root = calloc(1, sizeof(*root)); if (!root) { perror("calloc"); abort(); } root->idx = subtree->idx; root->mask = subtree->mask; root->num_after = subtree->num_after; /* As needed, recursively duplicate the left and right subtrees */ if (subtree->left) { root->left = node_copy_subtree(subtree->left); root->left->parent = root; } if (subtree->right) { root->right = node_copy_subtree(subtree->right); root->right->parent = root; } return root;} /* Searches for and returns a pointer to the node that describes the setting * of the bit given by idx. A node describes the setting of a bit if its * index is within the bits described by the mask bits or the number of * contiguous bits set after the mask. Returns NULL if there is no such node. */static struct node *node_find(const struct sparsebit *s, sparsebit_idx_t idx){ struct node *nodep; /* Find the node that describes the setting of the bit at idx */ for (nodep = s->root; nodep; nodep = nodep->idx > idx ? nodep->left : nodep->right) { if (idx >= nodep->idx && idx <= nodep->idx + MASK_BITS + nodep->num_after - 1) break; } return nodep;} /* Entry Requirements: * + A node that describes the setting of idx is not already present. * * Adds a new node to describe the setting of the bit at the index given * by idx. Returns a pointer to the newly added node. * * TODO(lhuemill): Degenerate cases causes the tree to get unbalanced. */static struct node *node_add(struct sparsebit *s, sparsebit_idx_t idx){ struct node *nodep, *parentp, *prev; /* Allocate and initialize the new node. */ nodep = calloc(1, sizeof(*nodep)); if (!nodep) { perror("calloc"); abort(); } nodep->idx = idx & -MASK_BITS; /* If no nodes, set it up as the root node. */ if (!s->root) { s->root = nodep; return nodep; } /* * Find the parent where the new node should be attached * and add the node there. */ parentp = s->root; while (true) { if (idx < parentp->idx) { if (!parentp->left) { parentp->left = nodep; nodep->parent = parentp; break; } parentp = parentp->left; } else { assert(idx > parentp->idx + MASK_BITS + parentp->num_after - 1); if (!parentp->right) { parentp->right = nodep; nodep->parent = parentp; break; } parentp = parentp->right; } } /* * Does num_after bits of previous node overlap with the mask * of the new node? If so set the bits in the new nodes mask * and reduce the previous nodes num_after. */ prev = node_prev(s, nodep); while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) { unsigned int n1 = (prev->idx + MASK_BITS + prev->num_after - 1) - nodep->idx; assert(prev->num_after > 0); assert(n1 < MASK_BITS); assert(!(nodep->mask & (1 << n1))); nodep->mask |= (1 << n1); prev->num_after--; } return nodep;} /* Returns whether all the bits in the sparsebit array are set. */bool sparsebit_all_set(const struct sparsebit *s){ /* * If any nodes there must be at least one bit set. Only case * where a bit is set and total num set is 0, is when all bits * are set. */ return s->root && s->num_set == 0;} /* Clears all bits described by the node pointed to by nodep, then * removes the node. */static void node_rm(struct sparsebit *s, struct node *nodep){ struct node *tmp; sparsebit_num_t num_set; num_set = node_num_set(nodep); assert(s->num_set >= num_set || sparsebit_all_set(s)); s->num_set -= node_num_set(nodep); /* Have both left and right child */ if (nodep->left && nodep->right) { /* * Move left children to the leftmost leaf node * of the right child. */ for (tmp = nodep->right; tmp->left; tmp = tmp->left) ; tmp->left = nodep->left; nodep->left = NULL; tmp->left->parent = tmp; } /* Left only child */ if (nodep->left) { if (!nodep->parent) { s->root = nodep->left; nodep->left->parent = NULL; } else { nodep->left->parent = nodep->parent; if (nodep == nodep->parent->left) nodep->parent->left = nodep->left; else { assert(nodep == nodep->parent->right); nodep->parent->right = nodep->left; } } nodep->parent = nodep->left = nodep->right = NULL; free(nodep); return; } /* Right only child */ if (nodep->right) { if (!nodep->parent) { s->root = nodep->right; nodep->right->parent = NULL; } else { nodep->right->parent = nodep->parent; if (nodep == nodep->parent->left) nodep->parent->left = nodep->right; else { assert(nodep == nodep->parent->right); nodep->parent->right = nodep->right; } } nodep->parent = nodep->left = nodep->right = NULL; free(nodep); return; } /* Leaf Node */ if (!nodep->parent) { s->root = NULL; } else { if (nodep->parent->left == nodep) nodep->parent->left = NULL; else { assert(nodep == nodep->parent->right); nodep->parent->right = NULL; } } nodep->parent = nodep->left = nodep->right = NULL; free(nodep); return;} /* Splits the node containing the bit at idx so that there is a node * that starts at the specified index. If no such node exists, a new * node at the specified index is created. Returns the new node. * * idx must start of a mask boundary. */static struct node *node_split(struct sparsebit *s, sparsebit_idx_t idx){ struct node *nodep1, *nodep2;Lines 1–500 of 2084. Load more
// SPDX-License-Identifier: GPL-2.0-only /* * Sparse bit array * * Copyright (C) 2018, Google LLC. * Copyright (C) 2018, Red Hat, Inc. (code style cleanup and fuzzing driver) * * This library provides functions to support a memory efficient bit array, * with an index size of 2^64. A sparsebit array is allocated through * the use sparsebit_alloc() and free'd via sparsebit_free(), * such as in the following: * * struct sparsebit *s; * s = sparsebit_alloc(); * sparsebit_free(&s); * * The struct sparsebit type resolves down to a struct sparsebit. * Note that, sparsebit_free() takes a pointer to the sparsebit * structure. This is so that sparsebit_free() is able to poison * the pointer (e.g. set it to NULL) to the struct sparsebit before * returning to the caller. * * Between the return of sparsebit_alloc() and the call of * sparsebit_free(), there are multiple query and modifying operations * that can be performed on the allocated sparsebit array. All of * these operations take as a parameter the value returned from * sparsebit_alloc() and most also take a bit index. Frequently * used routines include: * * ---- Query Operations * sparsebit_is_set(s, idx) * sparsebit_is_clear(s, idx) * sparsebit_any_set(s) * sparsebit_first_set(s) * sparsebit_next_set(s, prev_idx) * * ---- Modifying Operations * sparsebit_set(s, idx) * sparsebit_clear(s, idx) * sparsebit_set_num(s, idx, num); * sparsebit_clear_num(s, idx, num); * * A common operation, is to itterate over all the bits set in a test * sparsebit array. This can be done via code with the following structure: * * sparsebit_idx_t idx; * if (sparsebit_any_set(s)) { * idx = sparsebit_first_set(s); * do { * ... * idx = sparsebit_next_set(s, idx); * } while (idx != 0); * } * * The index of the first bit set needs to be obtained via * sparsebit_first_set(), because sparsebit_next_set(), needs * the index of the previously set. The sparsebit_idx_t type is * unsigned, so there is no previous index before 0 that is available. * Also, the call to sparsebit_first_set() is not made unless there * is at least 1 bit in the array set. This is because sparsebit_first_set() * aborts if sparsebit_first_set() is called with no bits set. * It is the callers responsibility to assure that the * sparsebit array has at least a single bit set before calling * sparsebit_first_set(). * * ==== Implementation Overview ==== * For the most part the internal implementation of sparsebit is * opaque to the caller. One important implementation detail that the * caller may need to be aware of is the spatial complexity of the * implementation. This implementation of a sparsebit array is not * only sparse, in that it uses memory proportional to the number of bits * set. It is also efficient in memory usage when most of the bits are * set. * * At a high-level the state of the bit settings are maintained through * the use of a binary-search tree, where each node contains at least * the following members: * * typedef u64 sparsebit_idx_t; * typedef u64 sparsebit_num_t; * * sparsebit_idx_t idx; * u32 mask; * sparsebit_num_t num_after; * * The idx member contains the bit index of the first bit described by this * node, while the mask member stores the setting of the first 32-bits. * The setting of the bit at idx + n, where 0 <= n < 32, is located in the * mask member at 1 << n. * * Nodes are sorted by idx and the bits described by two nodes will never * overlap. The idx member is always aligned to the mask size, i.e. a * multiple of 32. * * Beyond a typical implementation, the nodes in this implementation also * contains a member named num_after. The num_after member holds the * number of bits immediately after the mask bits that are contiguously set. * The use of the num_after member allows this implementation to efficiently * represent cases where most bits are set. For example, the case of all * but the last two bits set, is represented by the following two nodes: * * node 0 - idx: 0x0 mask: 0xffffffff num_after: 0xffffffffffffffc0 * node 1 - idx: 0xffffffffffffffe0 mask: 0x3fffffff num_after: 0 * * ==== Invariants ==== * This implementation usses the following invariants: * * + Node are only used to represent bits that are set. * Nodes with a mask of 0 and num_after of 0 are not allowed. * * + Sum of bits set in all the nodes is equal to the value of * the struct sparsebit_pvt num_set member. * * + The setting of at least one bit is always described in a nodes * mask (mask >= 1). * * + A node with all mask bits set only occurs when the last bit * described by the previous node is not equal to this nodes * starting index - 1. All such occurrences of this condition are * avoided by moving the setting of the nodes mask bits into * the previous nodes num_after setting. * * + Node starting index is evenly divisible by the number of bits * within a nodes mask member. * * + Nodes never represent a range of bits that wrap around the * highest supported index. * * (idx + MASK_BITS + num_after - 1) <= ((sparsebit_idx_t) 0) - 1) * * As a consequence of the above, the num_after member of a node * will always be <=: * * maximum_index - nodes_starting_index - number_of_mask_bits * * + Nodes within the binary search tree are sorted based on each * nodes starting index. * * + The range of bits described by any two nodes do not overlap. The * range of bits described by a single node is: * * start: node->idx * end (inclusive): node->idx + MASK_BITS + node->num_after - 1; * * Note, at times these invariants are temporarily violated for a * specific portion of the code. For example, when setting a mask * bit, there is a small delay between when the mask bit is set and the * value in the struct sparsebit_pvt num_set member is updated. Other * temporary violations occur when node_split() is called with a specified * index and assures that a node where its mask represents the bit * at the specified index exists. At times to do this node_split() * must split an existing node into two nodes or create a node that * has no bits set. Such temporary violations must be corrected before * returning to the caller. These corrections are typically performed * by the local function node_reduce(). */ #include "test_util.h" #include "sparsebit.h" #include <limits.h> #include <assert.h> #define DUMP_LINE_MAX 100 /* Does not include indent amount */ typedef u32 mask_t; #define MASK_BITS (sizeof(mask_t) * CHAR_BIT) struct node { struct node *parent; struct node *left; struct node *right; sparsebit_idx_t idx; /* index of least-significant bit in mask */ sparsebit_num_t num_after; /* num contiguously set after mask */ mask_t mask; }; struct sparsebit { /* * Points to root node of the binary search * tree. Equal to NULL when no bits are set in * the entire sparsebit array. */ struct node *root; /* * A redundant count of the total number of bits set. Used for * diagnostic purposes and to change the time complexity of * sparsebit_num_set() from O(n) to O(1). * Note: Due to overflow, a value of 0 means none or all set. */ sparsebit_num_t num_set; }; /* Returns the number of set bits described by the settings * of the node pointed to by nodep. */ static sparsebit_num_t node_num_set(struct node *nodep) { return nodep->num_after + __builtin_popcount(nodep->mask); } /* Returns a pointer to the node that describes the * lowest bit index. */ static struct node *node_first(const struct sparsebit *s) { struct node *nodep; for (nodep = s->root; nodep && nodep->left; nodep = nodep->left) ; return nodep; } /* Returns a pointer to the node that describes the * lowest bit index > the index of the node pointed to by np. * Returns NULL if no node with a higher index exists. */ static struct node *node_next(const struct sparsebit *s, struct node *np) { struct node *nodep = np; /* * If current node has a right child, next node is the left-most * of the right child. */ if (nodep->right) { for (nodep = nodep->right; nodep->left; nodep = nodep->left) ; return nodep; } /* * No right child. Go up until node is left child of a parent. * That parent is then the next node. */ while (nodep->parent && nodep == nodep->parent->right) nodep = nodep->parent; return nodep->parent; } /* Searches for and returns a pointer to the node that describes the * highest index < the index of the node pointed to by np. * Returns NULL if no node with a lower index exists. */ static struct node *node_prev(const struct sparsebit *s, struct node *np) { struct node *nodep = np; /* * If current node has a left child, next node is the right-most * of the left child. */ if (nodep->left) { for (nodep = nodep->left; nodep->right; nodep = nodep->right) ; return (struct node *) nodep; } /* * No left child. Go up until node is right child of a parent. * That parent is then the next node. */ while (nodep->parent && nodep == nodep->parent->left) nodep = nodep->parent; return (struct node *) nodep->parent; } /* Allocates space to hold a copy of the node sub-tree pointed to by * subtree and duplicates the bit settings to the newly allocated nodes. * Returns the newly allocated copy of subtree. */ static struct node *node_copy_subtree(const struct node *subtree) { struct node *root; /* Duplicate the node at the root of the subtree */ root = calloc(1, sizeof(*root)); if (!root) { perror("calloc"); abort(); } root->idx = subtree->idx; root->mask = subtree->mask; root->num_after = subtree->num_after; /* As needed, recursively duplicate the left and right subtrees */ if (subtree->left) { root->left = node_copy_subtree(subtree->left); root->left->parent = root; } if (subtree->right) { root->right = node_copy_subtree(subtree->right); root->right->parent = root; } return root; } /* Searches for and returns a pointer to the node that describes the setting * of the bit given by idx. A node describes the setting of a bit if its * index is within the bits described by the mask bits or the number of * contiguous bits set after the mask. Returns NULL if there is no such node. */ static struct node *node_find(const struct sparsebit *s, sparsebit_idx_t idx) { struct node *nodep; /* Find the node that describes the setting of the bit at idx */ for (nodep = s->root; nodep; nodep = nodep->idx > idx ? nodep->left : nodep->right) { if (idx >= nodep->idx && idx <= nodep->idx + MASK_BITS + nodep->num_after - 1) break; } return nodep; } /* Entry Requirements: * + A node that describes the setting of idx is not already present. * * Adds a new node to describe the setting of the bit at the index given * by idx. Returns a pointer to the newly added node. * * TODO(lhuemill): Degenerate cases causes the tree to get unbalanced. */ static struct node *node_add(struct sparsebit *s, sparsebit_idx_t idx) { struct node *nodep, *parentp, *prev; /* Allocate and initialize the new node. */ nodep = calloc(1, sizeof(*nodep)); if (!nodep) { perror("calloc"); abort(); } nodep->idx = idx & -MASK_BITS; /* If no nodes, set it up as the root node. */ if (!s->root) { s->root = nodep; return nodep; } /* * Find the parent where the new node should be attached * and add the node there. */ parentp = s->root; while (true) { if (idx < parentp->idx) { if (!parentp->left) { parentp->left = nodep; nodep->parent = parentp; break; } parentp = parentp->left; } else { assert(idx > parentp->idx + MASK_BITS + parentp->num_after - 1); if (!parentp->right) { parentp->right = nodep; nodep->parent = parentp; break; } parentp = parentp->right; } } /* * Does num_after bits of previous node overlap with the mask * of the new node? If so set the bits in the new nodes mask * and reduce the previous nodes num_after. */ prev = node_prev(s, nodep); while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) { unsigned int n1 = (prev->idx + MASK_BITS + prev->num_after - 1) - nodep->idx; assert(prev->num_after > 0); assert(n1 < MASK_BITS); assert(!(nodep->mask & (1 << n1))); nodep->mask |= (1 << n1); prev->num_after--; } return nodep; } /* Returns whether all the bits in the sparsebit array are set. */ bool sparsebit_all_set(const struct sparsebit *s) { /* * If any nodes there must be at least one bit set. Only case * where a bit is set and total num set is 0, is when all bits * are set. */ return s->root && s->num_set == 0; } /* Clears all bits described by the node pointed to by nodep, then * removes the node. */ static void node_rm(struct sparsebit *s, struct node *nodep) { struct node *tmp; sparsebit_num_t num_set; num_set = node_num_set(nodep); assert(s->num_set >= num_set || sparsebit_all_set(s)); s->num_set -= node_num_set(nodep); /* Have both left and right child */ if (nodep->left && nodep->right) { /* * Move left children to the leftmost leaf node * of the right child. */ for (tmp = nodep->right; tmp->left; tmp = tmp->left) ; tmp->left = nodep->left; nodep->left = NULL; tmp->left->parent = tmp; } /* Left only child */ if (nodep->left) { if (!nodep->parent) { s->root = nodep->left; nodep->left->parent = NULL; } else { nodep->left->parent = nodep->parent; if (nodep == nodep->parent->left) nodep->parent->left = nodep->left; else { assert(nodep == nodep->parent->right); nodep->parent->right = nodep->left; } } nodep->parent = nodep->left = nodep->right = NULL; free(nodep); return; } /* Right only child */ if (nodep->right) { if (!nodep->parent) { s->root = nodep->right; nodep->right->parent = NULL; } else { nodep->right->parent = nodep->parent; if (nodep == nodep->parent->left) nodep->parent->left = nodep->right; else { assert(nodep == nodep->parent->right); nodep->parent->right = nodep->right; } } nodep->parent = nodep->left = nodep->right = NULL; free(nodep); return; } /* Leaf Node */ if (!nodep->parent) { s->root = NULL; } else { if (nodep->parent->left == nodep) nodep->parent->left = NULL; else { assert(nodep == nodep->parent->right); nodep->parent->right = NULL; } } nodep->parent = nodep->left = nodep->right = NULL; free(nodep); return; } /* Splits the node containing the bit at idx so that there is a node * that starts at the specified index. If no such node exists, a new * node at the specified index is created. Returns the new node. * * idx must start of a mask boundary. */ static struct node *node_split(struct sparsebit *s, sparsebit_idx_t idx) { struct node *nodep1, *nodep2;