Search for the position of "value". Return 1 when the value was found and * sets "pos" to the position of the value within the intset. Return 0 when * the value is not present in the intset and sets "pos" to the position * where "value" can be inserted. */
| 115 | * the value is not present in the intset and sets "pos" to the position |
| 116 | * where "value" can be inserted. */ |
| 117 | static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) { |
| 118 | int min = 0, max = intrev32ifbe(is->length)-1, mid = -1; |
| 119 | int64_t cur = -1; |
| 120 | |
| 121 | /* The value can never be found when the set is empty */ |
| 122 | if (intrev32ifbe(is->length) == 0) { |
| 123 | if (pos) *pos = 0; |
| 124 | return 0; |
| 125 | } else { |
| 126 | /* Check for the case where we know we cannot find the value, |
| 127 | * but do know the insert position. */ |
| 128 | if (value > _intsetGet(is,max)) { |
| 129 | if (pos) *pos = intrev32ifbe(is->length); |
| 130 | return 0; |
| 131 | } else if (value < _intsetGet(is,0)) { |
| 132 | if (pos) *pos = 0; |
| 133 | return 0; |
| 134 | } |
| 135 | } |
| 136 | |
| 137 | while(max >= min) { |
| 138 | mid = ((unsigned int)min + (unsigned int)max) >> 1; |
| 139 | cur = _intsetGet(is,mid); |
| 140 | if (value > cur) { |
| 141 | min = mid+1; |
| 142 | } else if (value < cur) { |
| 143 | max = mid-1; |
| 144 | } else { |
| 145 | break; |
| 146 | } |
| 147 | } |
| 148 | |
| 149 | if (value == cur) { |
| 150 | if (pos) *pos = mid; |
| 151 | return 1; |
| 152 | } else { |
| 153 | if (pos) *pos = min; |
| 154 | return 0; |
| 155 | } |
| 156 | } |
| 157 | |
| 158 | /* Upgrades the intset to a larger encoding and inserts the given integer. */ |
| 159 | static intset *intsetUpgradeAndAdd(intset *is, int64_t value) { |
no test coverage detected