seq-range-array.c revision 8d80659e504ffb34bb0c6a633184fece35751b18
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn/* Copyright (c) 2005 Timo Sirainen */
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser#include "lib.h"
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser#include "array.h"
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn#include "seq-range-array.h"
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallynstatic bool seq_range_lookup(ARRAY_TYPE(seq_range) *array,
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn uint32_t seq, unsigned int *idx_r)
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn{
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn struct seq_range *data;
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn unsigned int idx, left_idx, right_idx, count;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn data = array_get_modifiable(array, &count);
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn idx = 0; left_idx = 0; right_idx = count;
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn while (left_idx < right_idx) {
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn idx = (left_idx + right_idx) / 2;
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn if (data[idx].seq1 <= seq) {
acbb59f50d5196facde837ea377f70e98ce1e6f8Serge Hallyn if (data[idx].seq2 >= seq) {
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn /* it's already in the range */
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn *idx_r = idx;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn return TRUE;
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser }
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser left_idx = idx+1;
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser } else {
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber right_idx = idx;
3a5495cf2f6c1806f5a91d699448b15b510f146ePo-Hsu Lin }
ad3f14ab58ec91ff11d0dcf2cbd5f47f02935344Scott Moser }
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser *idx_r = idx;
207bf0e475f1dc6e9a2dac2cee3a209b56427855Stéphane Graber return FALSE;
207bf0e475f1dc6e9a2dac2cee3a209b56427855Stéphane Graber}
207bf0e475f1dc6e9a2dac2cee3a209b56427855Stéphane Graber
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallynvoid seq_range_array_add(ARRAY_TYPE(seq_range) *array,
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn unsigned int init_count, uint32_t seq)
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn{
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn struct seq_range *data, value;
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn unsigned int idx, count;
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn value.seq1 = value.seq2 = seq;
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn if (!array_is_created(array))
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn ARRAY_CREATE(array, default_pool, struct seq_range, init_count);
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn data = array_get_modifiable(array, &count);
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn if (count == 0) {
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn array_append(array, &value, 1);
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallyn return;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn }
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn /* quick checks */
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn if (data[count-1].seq2 == seq-1) {
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn /* grow last range */
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn data[count-1].seq2 = seq;
42ff5f0f8767114d060f5031055038a1a1c3759aSerge Hallyn return;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn }
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn if (data[count-1].seq2 < seq) {
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn array_append(array, &value, 1);
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn return;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn }
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn if (data[0].seq1 == seq+1) {
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn /* grow down first range */
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn data[0].seq1 = seq;
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn return;
daaf41b36790bdaae855048e56ed090b17a77c97Stéphane Graber }
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn if (data[0].seq1 > seq) {
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn array_insert(array, 0, &value, 1);
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber return;
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber }
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber
9313e1e628160ca64f9e7fcec6500056c9a0725fStéphane Graber /* somewhere in the middle, array is sorted so find it with
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber binary search */
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber if (seq_range_lookup(array, seq, &idx))
f02ce27d4b1a9d01b88d0ffaf626e5bafa671bf0Stéphane Graber return;
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber if (data[idx].seq2 < seq)
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber idx++;
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber /* idx == count couldn't happen because we already handle it above */
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber i_assert(idx < count && data[idx].seq1 >= seq);
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber i_assert(data[idx].seq1 > seq || data[idx].seq2 < seq);
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber if (data[idx].seq1 == seq+1) {
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber data[idx].seq1 = seq;
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber if (idx > 0 && data[idx-1].seq2 == seq-1) {
57d116ab501594c2e50ab45f1cf2fae48c5eab09Serge Hallyn /* merge */
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn data[idx-1].seq2 = data[idx].seq2;
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber array_delete(array, idx, 1);
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber }
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber } else if (data[idx].seq2 == seq-1) {
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber i_assert(idx+1 < count); /* already handled above */
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber data[idx].seq2 = seq;
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber if (data[idx+1].seq1 == seq+1) {
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber /* merge */
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber data[idx+1].seq1 = data[idx].seq1;
bf7d76cf3ae180820c0a29e0bfbaa97c20ce6a3dSerge Hallyn array_delete(array, idx, 1);
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn }
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber } else {
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber array_insert(array, idx, &value, 1);
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber }
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber}
f2a95ee1bf54c949614a68bf152ea9a8e1d3a172Stéphane Graber
1aad9e44d65e7c20dabc4c99f57bcf532db66c68Serge Hallynvoid seq_range_array_remove(ARRAY_TYPE(seq_range) *array, uint32_t seq)
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber{
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber struct seq_range *data, value;
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber unsigned int idx, left_idx, right_idx, count;
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber if (!array_is_created(array))
17abf2784de1047fb2904ff130ee5efe4ea7b598Elan Ruusamäe return;
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber data = array_get_modifiable(array, &count);
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber if (count == 0)
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber return;
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber
0a3673e80732ab83d807d406fb2fd3c3b7f54ad3Stéphane Graber /* quick checks */
542939c31bb73bab55f2fd71243b98f5559597d1Stéphane Graber if (seq > data[count-1].seq2 || seq < data[0].seq1) {
42ff5f0f8767114d060f5031055038a1a1c3759aSerge Hallyn /* outside the range */
42ff5f0f8767114d060f5031055038a1a1c3759aSerge Hallyn return;
42ff5f0f8767114d060f5031055038a1a1c3759aSerge Hallyn }
5ff337745e4a705293b056ab58f6ea7a92cabbc8Stéphane Graber if (data[count-1].seq2 == seq) {
68c36a303f402b52f94067d3da7b168e274001a7Serge Hallyn /* shrink last range */
5ff337745e4a705293b056ab58f6ea7a92cabbc8Stéphane Graber if (data[count-1].seq1 != data[count-1].seq2)
42ff5f0f8767114d060f5031055038a1a1c3759aSerge Hallyn data[count-1].seq2--;
42ff5f0f8767114d060f5031055038a1a1c3759aSerge Hallyn else
42ff5f0f8767114d060f5031055038a1a1c3759aSerge Hallyn array_delete(array, count-1, 1);
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn return;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn }
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn if (data[0].seq1 == seq) {
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn /* shrink up first range */
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn if (data[0].seq1 != data[0].seq2)
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn data[0].seq1++;
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn else
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn array_delete(array, 0, 1);
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn return;
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn }
1897e3bcd36af9f3fe6d3649910a9adb93e5e988Serge Hallyn
3f5f5d99b0ea1c204699b13d4a0caf4d9e745449Stéphane Graber /* somewhere in the middle, array is sorted so find it with
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn binary search */
52c8f624b5f9ef665f33a7aa80e0aa18b91daa4aSerge Hallyn idx = 0; left_idx = 0; right_idx = count;
ad3f14ab58ec91ff11d0dcf2cbd5f47f02935344Scott Moser while (left_idx < right_idx) {
4759162d078d86628956cae4846c6efccf548e67Serge Hallyn idx = (left_idx + right_idx) / 2;
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser if (data[idx].seq1 > seq)
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser right_idx = idx;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn else if (data[idx].seq2 < seq)
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn left_idx = idx+1;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn else {
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn /* found it */
5d066f24e65ef482cdfee241ce65e060d1652efcScott Moser if (data[idx].seq1 == seq) {
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn if (data[idx].seq1 == data[idx].seq2) {
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn /* a single sequence range.
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn remove it entirely */
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn array_delete(array, idx, 1);
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn } else {
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn /* shrink the range */
57d116ab501594c2e50ab45f1cf2fae48c5eab09Serge Hallyn data[idx].seq1++;
2133f58c66ab7627a4159fafbb75106c556b014dSerge Hallyn }
f8b2a49ce0bb7ce66d0c902b5976a48e49f754b2Stéphane Graber } else if (data[idx].seq2 == seq) {
f8b2a49ce0bb7ce66d0c902b5976a48e49f754b2Stéphane Graber /* shrink the range */
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn data[idx].seq2--;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn } else {
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser /* split the sequence range */
ad3f14ab58ec91ff11d0dcf2cbd5f47f02935344Scott Moser value.seq1 = seq + 1;
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser value.seq2 = data[idx].seq2;
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser data[idx].seq2 = seq - 1;
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn array_insert(array, idx + 1, &value, 1);
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn }
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn break;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn }
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn }
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn}
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallynbool seq_range_exists(ARRAY_TYPE(seq_range) *array, uint32_t seq)
ed4616b1cfbc84dd01caa8546d813e8c5d482921Christian Bühler{
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn unsigned int idx;
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn return seq_range_lookup(array, seq, &idx);
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn}
d1458ac8d13880f83fa2d1e08623b97c50d311d7Serge Hallyn