1/*
2 * run.h
3 *
4 */
5
6#ifndef INCLUDE_CONTAINERS_RUN_H_
7#define INCLUDE_CONTAINERS_RUN_H_
8
9#include <assert.h>
10#include <stdbool.h>
11#include <stdint.h>
12#include <string.h>
13
14#include <roaring/containers/perfparameters.h>
15#include <roaring/portability.h>
16#include <roaring/roaring_types.h>
17#include <roaring/array_util.h>
18
19/* struct rle16_s - run length pair
20 *
21 * @value: start position of the run
22 * @length: length of the run is `length + 1`
23 *
24 * An RLE pair {v, l} would represent the integers between the interval
25 * [v, v+l+1], e.g. {3, 2} = [3, 4, 5].
26 */
27struct rle16_s {
28 uint16_t value;
29 uint16_t length;
30};
31
32typedef struct rle16_s rle16_t;
33
34/* struct run_container_s - run container bitmap
35 *
36 * @n_runs: number of rle_t pairs in `runs`.
37 * @capacity: capacity in rle_t pairs `runs` can hold.
38 * @runs: pairs of rle_t.
39 *
40 */
41struct run_container_s {
42 int32_t n_runs;
43 int32_t capacity;
44 rle16_t *runs;
45};
46
47typedef struct run_container_s run_container_t;
48
49/* Create a new run container. Return NULL in case of failure. */
50run_container_t *run_container_create(void);
51
52/* Create a new run container with given capacity. Return NULL in case of
53 * failure. */
54run_container_t *run_container_create_given_capacity(int32_t size);
55
56/*
57 * Shrink the capacity to the actual size, return the number of bytes saved.
58 */
59int run_container_shrink_to_fit(run_container_t *src);
60
61/* Free memory owned by `run'. */
62void run_container_free(run_container_t *run);
63
64/* Duplicate container */
65run_container_t *run_container_clone(const run_container_t *src);
66
67int32_t run_container_serialize(const run_container_t *container,
68 char *buf) WARN_UNUSED;
69
70uint32_t run_container_serialization_len(const run_container_t *container);
71
72void *run_container_deserialize(const char *buf, size_t buf_len);
73
74/*
75 * Effectively deletes the value at index index, repacking data.
76 */
77static inline void recoverRoomAtIndex(run_container_t *run, uint16_t index) {
78 memmove(run->runs + index, run->runs + (1 + index),
79 (run->n_runs - index - 1) * sizeof(rle16_t));
80 run->n_runs--;
81}
82
83/**
84 * Good old binary search through rle data
85 */
86inline int32_t interleavedBinarySearch(const rle16_t *array, int32_t lenarray,
87 uint16_t ikey) {
88 int32_t low = 0;
89 int32_t high = lenarray - 1;
90 while (low <= high) {
91 int32_t middleIndex = (low + high) >> 1;
92 uint16_t middleValue = array[middleIndex].value;
93 if (middleValue < ikey) {
94 low = middleIndex + 1;
95 } else if (middleValue > ikey) {
96 high = middleIndex - 1;
97 } else {
98 return middleIndex;
99 }
100 }
101 return -(low + 1);
102}
103
104/*
105 * Returns index of the run which contains $ikey
106 */
107static inline int32_t rle16_find_run(const rle16_t *array, int32_t lenarray,
108 uint16_t ikey) {
109 int32_t low = 0;
110 int32_t high = lenarray - 1;
111 while (low <= high) {
112 int32_t middleIndex = (low + high) >> 1;
113 uint16_t min = array[middleIndex].value;
114 uint16_t max = array[middleIndex].value + array[middleIndex].length;
115 if (ikey > max) {
116 low = middleIndex + 1;
117 } else if (ikey < min) {
118 high = middleIndex - 1;
119 } else {
120 return middleIndex;
121 }
122 }
123 return -(low + 1);
124}
125
126
127/**
128 * Returns number of runs which can'be be merged with the key because they
129 * are less than the key.
130 * Note that [5,6,7,8] can be merged with the key 9 and won't be counted.
131 */
132static inline int32_t rle16_count_less(const rle16_t* array, int32_t lenarray,
133 uint16_t key) {
134 if (lenarray == 0) return 0;
135 int32_t low = 0;
136 int32_t high = lenarray - 1;
137 while (low <= high) {
138 int32_t middleIndex = (low + high) >> 1;
139 uint16_t min_value = array[middleIndex].value;
140 uint16_t max_value = array[middleIndex].value + array[middleIndex].length;
141 if (max_value + UINT32_C(1) < key) { // uint32 arithmetic
142 low = middleIndex + 1;
143 } else if (key < min_value) {
144 high = middleIndex - 1;
145 } else {
146 return middleIndex;
147 }
148 }
149 return low;
150}
151
152static inline int32_t rle16_count_greater(const rle16_t* array, int32_t lenarray,
153 uint16_t key) {
154 if (lenarray == 0) return 0;
155 int32_t low = 0;
156 int32_t high = lenarray - 1;
157 while (low <= high) {
158 int32_t middleIndex = (low + high) >> 1;
159 uint16_t min_value = array[middleIndex].value;
160 uint16_t max_value = array[middleIndex].value + array[middleIndex].length;
161 if (max_value < key) {
162 low = middleIndex + 1;
163 } else if (key + UINT32_C(1) < min_value) { // uint32 arithmetic
164 high = middleIndex - 1;
165 } else {
166 return lenarray - (middleIndex + 1);
167 }
168 }
169 return lenarray - low;
170}
171
172/**
173 * increase capacity to at least min. Whether the
174 * existing data needs to be copied over depends on copy. If "copy" is false,
175 * then the new content will be uninitialized, otherwise a copy is made.
176 */
177void run_container_grow(run_container_t *run, int32_t min, bool copy);
178
179/**
180 * Moves the data so that we can write data at index
181 */
182static inline void makeRoomAtIndex(run_container_t *run, uint16_t index) {
183 /* This function calls realloc + memmove sequentially to move by one index.
184 * Potentially copying twice the array.
185 */
186 if (run->n_runs + 1 > run->capacity)
187 run_container_grow(run, run->n_runs + 1, true);
188 memmove(run->runs + 1 + index, run->runs + index,
189 (run->n_runs - index) * sizeof(rle16_t));
190 run->n_runs++;
191}
192
193/* Add `pos' to `run'. Returns true if `pos' was not present. */
194bool run_container_add(run_container_t *run, uint16_t pos);
195
196/* Remove `pos' from `run'. Returns true if `pos' was present. */
197static inline bool run_container_remove(run_container_t *run, uint16_t pos) {
198 int32_t index = interleavedBinarySearch(run->runs, run->n_runs, pos);
199 if (index >= 0) {
200 int32_t le = run->runs[index].length;
201 if (le == 0) {
202 recoverRoomAtIndex(run, (uint16_t)index);
203 } else {
204 run->runs[index].value++;
205 run->runs[index].length--;
206 }
207 return true;
208 }
209 index = -index - 2; // points to preceding value, possibly -1
210 if (index >= 0) { // possible match
211 int32_t offset = pos - run->runs[index].value;
212 int32_t le = run->runs[index].length;
213 if (offset < le) {
214 // need to break in two
215 run->runs[index].length = (uint16_t)(offset - 1);
216 // need to insert
217 uint16_t newvalue = pos + 1;
218 int32_t newlength = le - offset - 1;
219 makeRoomAtIndex(run, (uint16_t)(index + 1));
220 run->runs[index + 1].value = newvalue;
221 run->runs[index + 1].length = (uint16_t)newlength;
222 return true;
223
224 } else if (offset == le) {
225 run->runs[index].length--;
226 return true;
227 }
228 }
229 // no match
230 return false;
231}
232
233/* Check whether `pos' is present in `run'. */
234inline bool run_container_contains(const run_container_t *run, uint16_t pos) {
235 int32_t index = interleavedBinarySearch(run->runs, run->n_runs, pos);
236 if (index >= 0) return true;
237 index = -index - 2; // points to preceding value, possibly -1
238 if (index != -1) { // possible match
239 int32_t offset = pos - run->runs[index].value;
240 int32_t le = run->runs[index].length;
241 if (offset <= le) return true;
242 }
243 return false;
244}
245
246/*
247* Check whether all positions in a range of positions from pos_start (included)
248* to pos_end (excluded) is present in `run'.
249*/
250static inline bool run_container_contains_range(const run_container_t *run,
251 uint32_t pos_start, uint32_t pos_end) {
252 uint32_t count = 0;
253 int32_t index = interleavedBinarySearch(run->runs, run->n_runs, pos_start);
254 if (index < 0) {
255 index = -index - 2;
256 if ((index == -1) || ((pos_start - run->runs[index].value) > run->runs[index].length)){
257 return false;
258 }
259 }
260 for (int32_t i = index; i < run->n_runs; ++i) {
261 const uint32_t stop = run->runs[i].value + run->runs[i].length;
262 if (run->runs[i].value >= pos_end) break;
263 if (stop >= pos_end) {
264 count += (((pos_end - run->runs[i].value) > 0) ? (pos_end - run->runs[i].value) : 0);
265 break;
266 }
267 const uint32_t min = (stop - pos_start) > 0 ? (stop - pos_start) : 0;
268 count += (min < run->runs[i].length) ? min : run->runs[i].length;
269 }
270 return count >= (pos_end - pos_start - 1);
271}
272
273#ifdef USEAVX
274
275/* Get the cardinality of `run'. Requires an actual computation. */
276static inline int run_container_cardinality(const run_container_t *run) {
277 const int32_t n_runs = run->n_runs;
278 const rle16_t *runs = run->runs;
279
280 /* by initializing with n_runs, we omit counting the +1 for each pair. */
281 int sum = n_runs;
282 int32_t k = 0;
283 const int32_t step = sizeof(__m256i) / sizeof(rle16_t);
284 if (n_runs > step) {
285 __m256i total = _mm256_setzero_si256();
286 for (; k + step <= n_runs; k += step) {
287 __m256i ymm1 = _mm256_lddqu_si256((const __m256i *)(runs + k));
288 __m256i justlengths = _mm256_srli_epi32(ymm1, 16);
289 total = _mm256_add_epi32(total, justlengths);
290 }
291 // a store might be faster than extract?
292 uint32_t buffer[sizeof(__m256i) / sizeof(rle16_t)];
293 _mm256_storeu_si256((__m256i *)buffer, total);
294 sum += (buffer[0] + buffer[1]) + (buffer[2] + buffer[3]) +
295 (buffer[4] + buffer[5]) + (buffer[6] + buffer[7]);
296 }
297 for (; k < n_runs; ++k) {
298 sum += runs[k].length;
299 }
300
301 return sum;
302}
303
304#else
305
306/* Get the cardinality of `run'. Requires an actual computation. */
307static inline int run_container_cardinality(const run_container_t *run) {
308 const int32_t n_runs = run->n_runs;
309 const rle16_t *runs = run->runs;
310
311 /* by initializing with n_runs, we omit counting the +1 for each pair. */
312 int sum = n_runs;
313 for (int k = 0; k < n_runs; ++k) {
314 sum += runs[k].length;
315 }
316
317 return sum;
318}
319#endif
320
321/* Card > 0?, see run_container_empty for the reverse */
322static inline bool run_container_nonzero_cardinality(
323 const run_container_t *run) {
324 return run->n_runs > 0; // runs never empty
325}
326
327/* Card == 0?, see run_container_nonzero_cardinality for the reverse */
328static inline bool run_container_empty(
329 const run_container_t *run) {
330 return run->n_runs == 0; // runs never empty
331}
332
333
334
335/* Copy one container into another. We assume that they are distinct. */
336void run_container_copy(const run_container_t *src, run_container_t *dst);
337
338/* Set the cardinality to zero (does not release memory). */
339static inline void run_container_clear(run_container_t *run) {
340 run->n_runs = 0;
341}
342
343/**
344 * Append run described by vl to the run container, possibly merging.
345 * It is assumed that the run would be inserted at the end of the container, no
346 * check is made.
347 * It is assumed that the run container has the necessary capacity: caller is
348 * responsible for checking memory capacity.
349 *
350 *
351 * This is not a safe function, it is meant for performance: use with care.
352 */
353static inline void run_container_append(run_container_t *run, rle16_t vl,
354 rle16_t *previousrl) {
355 const uint32_t previousend = previousrl->value + previousrl->length;
356 if (vl.value > previousend + 1) { // we add a new one
357 run->runs[run->n_runs] = vl;
358 run->n_runs++;
359 *previousrl = vl;
360 } else {
361 uint32_t newend = vl.value + vl.length + UINT32_C(1);
362 if (newend > previousend) { // we merge
363 previousrl->length = (uint16_t)(newend - 1 - previousrl->value);
364 run->runs[run->n_runs - 1] = *previousrl;
365 }
366 }
367}
368
369/**
370 * Like run_container_append but it is assumed that the content of run is empty.
371 */
372static inline rle16_t run_container_append_first(run_container_t *run,
373 rle16_t vl) {
374 run->runs[run->n_runs] = vl;
375 run->n_runs++;
376 return vl;
377}
378
379/**
380 * append a single value given by val to the run container, possibly merging.
381 * It is assumed that the value would be inserted at the end of the container,
382 * no check is made.
383 * It is assumed that the run container has the necessary capacity: caller is
384 * responsible for checking memory capacity.
385 *
386 * This is not a safe function, it is meant for performance: use with care.
387 */
388static inline void run_container_append_value(run_container_t *run,
389 uint16_t val,
390 rle16_t *previousrl) {
391 const uint32_t previousend = previousrl->value + previousrl->length;
392 if (val > previousend + 1) { // we add a new one
393 //*previousrl = (rle16_t){.value = val, .length = 0};// requires C99
394 previousrl->value = val;
395 previousrl->length = 0;
396
397 run->runs[run->n_runs] = *previousrl;
398 run->n_runs++;
399 } else if (val == previousend + 1) { // we merge
400 previousrl->length++;
401 run->runs[run->n_runs - 1] = *previousrl;
402 }
403}
404
405/**
406 * Like run_container_append_value but it is assumed that the content of run is
407 * empty.
408 */
409static inline rle16_t run_container_append_value_first(run_container_t *run,
410 uint16_t val) {
411 // rle16_t newrle = (rle16_t){.value = val, .length = 0};// requires C99
412 rle16_t newrle;
413 newrle.value = val;
414 newrle.length = 0;
415
416 run->runs[run->n_runs] = newrle;
417 run->n_runs++;
418 return newrle;
419}
420
421/* Check whether the container spans the whole chunk (cardinality = 1<<16).
422 * This check can be done in constant time (inexpensive). */
423static inline bool run_container_is_full(const run_container_t *run) {
424 rle16_t vl = run->runs[0];
425 return (run->n_runs == 1) && (vl.value == 0) && (vl.length == 0xFFFF);
426}
427
428/* Compute the union of `src_1' and `src_2' and write the result to `dst'
429 * It is assumed that `dst' is distinct from both `src_1' and `src_2'. */
430void run_container_union(const run_container_t *src_1,
431 const run_container_t *src_2, run_container_t *dst);
432
433/* Compute the union of `src_1' and `src_2' and write the result to `src_1' */
434void run_container_union_inplace(run_container_t *src_1,
435 const run_container_t *src_2);
436
437/* Compute the intersection of src_1 and src_2 and write the result to
438 * dst. It is assumed that dst is distinct from both src_1 and src_2. */
439void run_container_intersection(const run_container_t *src_1,
440 const run_container_t *src_2,
441 run_container_t *dst);
442
443/* Compute the size of the intersection of src_1 and src_2 . */
444int run_container_intersection_cardinality(const run_container_t *src_1,
445 const run_container_t *src_2);
446
447/* Check whether src_1 and src_2 intersect. */
448bool run_container_intersect(const run_container_t *src_1,
449 const run_container_t *src_2);
450
451/* Compute the symmetric difference of `src_1' and `src_2' and write the result
452 * to `dst'
453 * It is assumed that `dst' is distinct from both `src_1' and `src_2'. */
454void run_container_xor(const run_container_t *src_1,
455 const run_container_t *src_2, run_container_t *dst);
456
457/*
458 * Write out the 16-bit integers contained in this container as a list of 32-bit
459 * integers using base
460 * as the starting value (it might be expected that base has zeros in its 16
461 * least significant bits).
462 * The function returns the number of values written.
463 * The caller is responsible for allocating enough memory in out.
464 */
465int run_container_to_uint32_array(void *vout, const run_container_t *cont,
466 uint32_t base);
467
468/*
469 * Print this container using printf (useful for debugging).
470 */
471void run_container_printf(const run_container_t *v);
472
473/*
474 * Print this container using printf as a comma-separated list of 32-bit
475 * integers starting at base.
476 */
477void run_container_printf_as_uint32_array(const run_container_t *v,
478 uint32_t base);
479
480/**
481 * Return the serialized size in bytes of a container having "num_runs" runs.
482 */
483static inline int32_t run_container_serialized_size_in_bytes(int32_t num_runs) {
484 return sizeof(uint16_t) +
485 sizeof(rle16_t) * num_runs; // each run requires 2 2-byte entries.
486}
487
488bool run_container_iterate(const run_container_t *cont, uint32_t base,
489 roaring_iterator iterator, void *ptr);
490bool run_container_iterate64(const run_container_t *cont, uint32_t base,
491 roaring_iterator64 iterator, uint64_t high_bits,
492 void *ptr);
493
494/**
495 * Writes the underlying array to buf, outputs how many bytes were written.
496 * This is meant to be byte-by-byte compatible with the Java and Go versions of
497 * Roaring.
498 * The number of bytes written should be run_container_size_in_bytes(container).
499 */
500int32_t run_container_write(const run_container_t *container, char *buf);
501
502/**
503 * Reads the instance from buf, outputs how many bytes were read.
504 * This is meant to be byte-by-byte compatible with the Java and Go versions of
505 * Roaring.
506 * The number of bytes read should be bitset_container_size_in_bytes(container).
507 * The cardinality parameter is provided for consistency with other containers,
508 * but
509 * it might be effectively ignored..
510 */
511int32_t run_container_read(int32_t cardinality, run_container_t *container,
512 const char *buf);
513
514/**
515 * Return the serialized size in bytes of a container (see run_container_write).
516 * This is meant to be compatible with the Java and Go versions of Roaring.
517 */
518static inline int32_t run_container_size_in_bytes(
519 const run_container_t *container) {
520 return run_container_serialized_size_in_bytes(container->n_runs);
521}
522
523/**
524 * Return true if the two containers have the same content.
525 */
526static inline bool run_container_equals(const run_container_t *container1,
527 const run_container_t *container2) {
528 if (container1->n_runs != container2->n_runs) {
529 return false;
530 }
531 return memequals(container1->runs, container2->runs,
532 container1->n_runs * sizeof(rle16_t));
533}
534
535/**
536* Return true if container1 is a subset of container2.
537*/
538bool run_container_is_subset(const run_container_t *container1,
539 const run_container_t *container2);
540
541/**
542 * Used in a start-finish scan that appends segments, for XOR and NOT
543 */
544
545void run_container_smart_append_exclusive(run_container_t *src,
546 const uint16_t start,
547 const uint16_t length);
548
549/**
550* The new container consists of a single run [start,stop).
551* It is required that stop>start, the caller is responsability for this check.
552* It is required that stop <= (1<<16), the caller is responsability for this check.
553* The cardinality of the created container is stop - start.
554* Returns NULL on failure
555*/
556static inline run_container_t *run_container_create_range(uint32_t start,
557 uint32_t stop) {
558 run_container_t *rc = run_container_create_given_capacity(1);
559 if (rc) {
560 rle16_t r;
561 r.value = (uint16_t)start;
562 r.length = (uint16_t)(stop - start - 1);
563 run_container_append_first(rc, r);
564 }
565 return rc;
566}
567
568/**
569 * If the element of given rank is in this container, supposing that the first
570 * element has rank start_rank, then the function returns true and sets element
571 * accordingly.
572 * Otherwise, it returns false and update start_rank.
573 */
574bool run_container_select(const run_container_t *container,
575 uint32_t *start_rank, uint32_t rank,
576 uint32_t *element);
577
578/* Compute the difference of src_1 and src_2 and write the result to
579 * dst. It is assumed that dst is distinct from both src_1 and src_2. */
580
581void run_container_andnot(const run_container_t *src_1,
582 const run_container_t *src_2, run_container_t *dst);
583
584/* Returns the smallest value (assumes not empty) */
585inline uint16_t run_container_minimum(const run_container_t *run) {
586 if (run->n_runs == 0) return 0;
587 return run->runs[0].value;
588}
589
590/* Returns the largest value (assumes not empty) */
591inline uint16_t run_container_maximum(const run_container_t *run) {
592 if (run->n_runs == 0) return 0;
593 return run->runs[run->n_runs - 1].value + run->runs[run->n_runs - 1].length;
594}
595
596/* Returns the number of values equal or smaller than x */
597int run_container_rank(const run_container_t *arr, uint16_t x);
598
599/* Returns the index of the first run containing a value at least as large as x, or -1 */
600inline int run_container_index_equalorlarger(const run_container_t *arr, uint16_t x) {
601 int32_t index = interleavedBinarySearch(arr->runs, arr->n_runs, x);
602 if (index >= 0) return index;
603 index = -index - 2; // points to preceding run, possibly -1
604 if (index != -1) { // possible match
605 int32_t offset = x - arr->runs[index].value;
606 int32_t le = arr->runs[index].length;
607 if (offset <= le) return index;
608 }
609 index += 1;
610 if(index < arr->n_runs) {
611 return index;
612 }
613 return -1;
614}
615
616/*
617 * Add all values in range [min, max] using hint.
618 */
619static inline void run_container_add_range_nruns(run_container_t* run,
620 uint32_t min, uint32_t max,
621 int32_t nruns_less,
622 int32_t nruns_greater) {
623 int32_t nruns_common = run->n_runs - nruns_less - nruns_greater;
624 if (nruns_common == 0) {
625 makeRoomAtIndex(run, nruns_less);
626 run->runs[nruns_less].value = min;
627 run->runs[nruns_less].length = max - min;
628 } else {
629 uint32_t common_min = run->runs[nruns_less].value;
630 uint32_t common_max = run->runs[nruns_less + nruns_common - 1].value +
631 run->runs[nruns_less + nruns_common - 1].length;
632 uint32_t result_min = (common_min < min) ? common_min : min;
633 uint32_t result_max = (common_max > max) ? common_max : max;
634
635 run->runs[nruns_less].value = result_min;
636 run->runs[nruns_less].length = result_max - result_min;
637
638 memmove(&(run->runs[nruns_less + 1]),
639 &(run->runs[run->n_runs - nruns_greater]),
640 nruns_greater*sizeof(rle16_t));
641 run->n_runs = nruns_less + 1 + nruns_greater;
642 }
643}
644
645/**
646 * Add all values in range [min, max]
647 */
648static inline void run_container_add_range(run_container_t* run,
649 uint32_t min, uint32_t max) {
650 int32_t nruns_greater = rle16_count_greater(run->runs, run->n_runs, max);
651 int32_t nruns_less = rle16_count_less(run->runs, run->n_runs - nruns_greater, min);
652 run_container_add_range_nruns(run, min, max, nruns_less, nruns_greater);
653}
654
655/**
656 * Shifts last $count elements either left (distance < 0) or right (distance > 0)
657 */
658static inline void run_container_shift_tail(run_container_t* run,
659 int32_t count, int32_t distance) {
660 if (distance > 0) {
661 if (run->capacity < count+distance) {
662 run_container_grow(run, count+distance, true);
663 }
664 }
665 int32_t srcpos = run->n_runs - count;
666 int32_t dstpos = srcpos + distance;
667 memmove(&(run->runs[dstpos]), &(run->runs[srcpos]), sizeof(rle16_t) * count);
668 run->n_runs += distance;
669}
670
671/**
672 * Remove all elements in range [min, max]
673 */
674static inline void run_container_remove_range(run_container_t *run, uint32_t min, uint32_t max) {
675 int32_t first = rle16_find_run(run->runs, run->n_runs, min);
676 int32_t last = rle16_find_run(run->runs, run->n_runs, max);
677
678 if (first >= 0 && min > run->runs[first].value &&
679 max < ((uint32_t)run->runs[first].value + (uint32_t)run->runs[first].length)) {
680 // split this run into two adjacent runs
681
682 // right subinterval
683 makeRoomAtIndex(run, first+1);
684 run->runs[first+1].value = max + 1;
685 run->runs[first+1].length = (run->runs[first].value + run->runs[first].length) - (max + 1);
686
687 // left subinterval
688 run->runs[first].length = (min - 1) - run->runs[first].value;
689
690 return;
691 }
692
693 // update left-most partial run
694 if (first >= 0) {
695 if (min > run->runs[first].value) {
696 run->runs[first].length = (min - 1) - run->runs[first].value;
697 first++;
698 }
699 } else {
700 first = -first-1;
701 }
702
703 // update right-most run
704 if (last >= 0) {
705 uint16_t run_max = run->runs[last].value + run->runs[last].length;
706 if (run_max > max) {
707 run->runs[last].value = max + 1;
708 run->runs[last].length = run_max - (max + 1);
709 last--;
710 }
711 } else {
712 last = (-last-1) - 1;
713 }
714
715 // remove intermediate runs
716 if (first <= last) {
717 run_container_shift_tail(run, run->n_runs - (last+1), -(last-first+1));
718 }
719}
720
721
722#endif /* INCLUDE_CONTAINERS_RUN_H_ */
723