kvm/lib/sparsebit.c

129  *      (idx + MASK_BITS + num_after - 1) <= ((sparsebit_idx_t) 0) - 1)
143  *       end (inclusive): node->idx + MASK_BITS + node->num_after - 1;
166 #define MASK_BITS (sizeof(mask_t) * CHAR_BIT)
318 		    idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
344 	nodep->idx = idx & -MASK_BITS;
366 			assert(idx > parentp->idx + MASK_BITS + parentp->num_after - 1);
382 	while (prev && prev->idx + MASK_BITS + prev->num_after - 1 >= nodep->idx) {
383 		unsigned int n1 = (prev->idx + MASK_BITS + prev->num_after - 1)
386 		assert(n1 < MASK_BITS);
504 	assert(!(idx % MASK_BITS));
530 	offset = idx - (nodep1->idx + MASK_BITS);
542 	if (nodep2->num_after >= MASK_BITS) {
544 		nodep2->num_after -= MASK_BITS;
649 			assert(nodep->idx + MASK_BITS > nodep->idx);
651 			nodep->idx += MASK_BITS;
653 			if (nodep->num_after >= MASK_BITS) {
655 				nodep->num_after -= MASK_BITS;
686 			    prev->idx + MASK_BITS == nodep->idx) {
687 				prev->num_after += MASK_BITS + nodep->num_after;
700 			prev_highest_bit = prev->idx + MASK_BITS - 1 + prev->num_after;
731 				if (num_contiguous == MASK_BITS) {
758 			if (next->idx == nodep->idx + MASK_BITS + nodep->num_after &&
760 				nodep->num_after += MASK_BITS;
786 		    idx <= nodep->idx + MASK_BITS + nodep->num_after - 1)
793 	if (nodep->num_after && idx >= nodep->idx + MASK_BITS)
797 	assert(idx >= nodep->idx && idx - nodep->idx < MASK_BITS);
817 	nodep = node_split(s, idx & -MASK_BITS);
820 	assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
848 	if (idx >= nodep->idx + MASK_BITS)
849 		nodep = node_split(s, idx & -MASK_BITS);
855 	assert(idx >= nodep->idx && idx <= nodep->idx + MASK_BITS - 1);
1066 	       (s->root->num_after == ((sparsebit_num_t) 0) - MASK_BITS &&
1128 		assert(nodep1->idx + MASK_BITS + nodep1->num_after != (sparsebit_idx_t) 0);
1129 		return nodep1->idx + MASK_BITS + nodep1->num_after;
1138 	if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1139 		return nodep1->idx + MASK_BITS + nodep1->num_after;
1180 		if ((nodep->idx + MASK_BITS + nodep->num_after - 1)
1219 	if (start < MASK_BITS && candidate->mask >= (1 << start))
1223 		sparsebit_idx_t first_num_after_idx = candidate->idx + MASK_BITS;
1267 	for (idx = lowest_possible - nodep1->idx; idx < MASK_BITS; idx++)
1278 		return nodep1->idx + MASK_BITS + nodep1->num_after;
1286 	if (nodep1->idx + MASK_BITS + nodep1->num_after != nodep2->idx)
1287 		return nodep1->idx + MASK_BITS + nodep1->num_after;
1402 	for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1407 	middle_end = middle_start + (n & -MASK_BITS) - 1;
1408 	if (n >= MASK_BITS) {
1423 			assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1429 		for (n1 = 0; n1 < MASK_BITS; n1++) {
1437 		nodep->num_after = middle_end - middle_start + 1 - MASK_BITS;
1446 	assert(n < MASK_BITS);
1465 	for (idx = start, n = num; n > 0 && idx % MASK_BITS != 0; idx++, n--)
1470 	middle_end = middle_start + (n & -MASK_BITS) - 1;
1471 	if (n >= MASK_BITS) {
1486 			assert(next->idx + MASK_BITS + next->num_after - 1 <= middle_end);
1492 		for (n1 = 0; n1 < MASK_BITS; n1++) {
1515 	assert(n < MASK_BITS);
1605 		for (n1 = 0; n1 < MASK_BITS; n1++) {
1609 				for (; n1 < MASK_BITS; n1++) {
1616 				if ((n1 == MASK_BITS) && nodep->num_after)
1649 		if (!(nodep->mask & (1 << (MASK_BITS - 1))) && nodep->num_after) {
1650 			low = nodep->idx + MASK_BITS;
1651 			high = nodep->idx + MASK_BITS + nodep->num_after - 1;
1699 		for (n1 = 0; n1 < MASK_BITS; n1++)
1726 		 * MASK_BITS worth of bits are described by the mask,
1729 		 *    (~(sparsebit_num_t) 0) - MASK_BITS + 1
1732 			> (~(sparsebit_num_t) 0) - MASK_BITS + 1) {
1741 		if (nodep->idx % MASK_BITS) {
1745 				"MASK_BITS: %lu\n",
1746 				nodep, nodep->idx, MASK_BITS);
1755 		if ((nodep->idx + MASK_BITS + nodep->num_after - 1) < nodep->idx) {
1759 				"  MASK_BITS: %lu nodep->num_after: 0x%lx",
1760 				nodep, nodep->idx, MASK_BITS, nodep->num_after);
1821 			if ((prev->idx + MASK_BITS + prev->num_after - 1)
1829 					"  MASK_BITS: %lu",
1832 					MASK_BITS);
1843 			    prev->idx + MASK_BITS + prev->num_after == nodep->idx) {
1851 					"  MASK_BITS: %lu",
1854 					MASK_BITS);