seq-range-array.c revision e8ecd8f24ffc612f5d0be10f7931ac619f1eab88
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen/* Copyright (c) 2005 Timo Sirainen */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen#include "lib.h"
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen#include "array.h"
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen#include "seq-range-array.h"
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainenstatic bool seq_range_lookup(array_t *array, uint32_t seq, unsigned int *idx_r)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen{
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen ARRAY_SET_TYPE(array, struct seq_range);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen struct seq_range *data;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen unsigned int idx, left_idx, right_idx, count;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data = array_get_modifyable(array, &count);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen idx = 0; left_idx = 0; right_idx = count;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen while (left_idx < right_idx) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen idx = (left_idx + right_idx) / 2;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[idx].seq1 <= seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[idx].seq2 >= seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* it's already in the range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen *idx_r = idx;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return TRUE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen left_idx = idx+1;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen } else {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen right_idx = idx;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen *idx_r = idx;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return FALSE;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen}
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainenvoid seq_range_array_add(array_t *array, unsigned int init_count, uint32_t seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen{
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen ARRAY_SET_TYPE(array, struct seq_range);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen struct seq_range *data, value;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen unsigned int idx, count;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen value.seq1 = value.seq2 = seq;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (!array_is_created(array)) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen array_create(array, default_pool,
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen sizeof(struct seq_range), init_count);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data = array_get_modifyable(array, &count);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (count == 0) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen array_append(array, &value, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* quick checks */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[count-1].seq2 == seq-1) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* grow last range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data[count-1].seq2 = seq;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[count-1].seq2 < seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen array_append(array, &value, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[0].seq1 == seq+1) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* grow down first range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data[0].seq1 = seq;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[0].seq1 > seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen array_insert(array, 0, &value, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* somewhere in the middle, array is sorted so find it with
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen binary search */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (seq_range_lookup(array, seq, &idx))
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[idx].seq2 < seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen idx++;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* idx == count couldn't happen because we already handle it above */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen i_assert(idx < count && data[idx].seq1 >= seq);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen i_assert(data[idx].seq1 > seq || data[idx].seq2 < seq);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[idx].seq1 == seq+1) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data[idx].seq1 = seq;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (idx > 0 && data[idx-1].seq2 == seq-1) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* merge */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data[idx-1].seq2 = data[idx].seq2;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen array_delete(array, idx, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen } else if (data[idx].seq2 == seq-1) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen i_assert(idx+1 < count); /* already handled above */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data[idx].seq2 = seq;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[idx+1].seq1 == seq+1) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* merge */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data[idx+1].seq1 = data[idx].seq1;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen array_delete(array, idx, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen } else {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen array_insert(array, idx, &value, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen}
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainenvoid seq_range_array_remove(array_t *array, uint32_t seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen{
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen ARRAY_SET_TYPE(array, struct seq_range);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen struct seq_range *data, value;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen unsigned int idx, left_idx, right_idx, count;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (!array_is_created(array))
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data = array_get_modifyable(array, &count);
e8ecd8f24ffc612f5d0be10f7931ac619f1eab88Timo Sirainen if (count == 0)
e8ecd8f24ffc612f5d0be10f7931ac619f1eab88Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* quick checks */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (seq > data[count-1].seq2 || seq < data[0].seq1) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* outside the range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[count-1].seq2 == seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* shrink last range */
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen if (data[count-1].seq1 != data[count-1].seq2)
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen data[count-1].seq2--;
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen else
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen array_delete(array, count-1, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[0].seq1 == seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* shrink up first range */
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen if (data[0].seq1 != data[0].seq2)
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen data[0].seq1++;
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen else
e262f3aa3429dbc74f668bc8bd501cf08b955778Timo Sirainen array_delete(array, 0, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* somewhere in the middle, array is sorted so find it with
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen binary search */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen idx = 0; left_idx = 0; right_idx = count;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen while (left_idx < right_idx) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen idx = (left_idx + right_idx) / 2;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[idx].seq1 > seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen right_idx = idx;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen else if (data[idx].seq2 < seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen left_idx = idx+1;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen else {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* found it */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[idx].seq1 == seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen if (data[idx].seq1 == data[idx].seq2) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* a single sequence range.
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen remove it entirely */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen array_delete(array, idx, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen } else {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* shrink the range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data[idx].seq1++;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen } else if (data[idx].seq2 == seq) {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* shrink the range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data[idx].seq2--;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen } else {
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen /* split the sequence range */
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen value.seq1 = seq + 1;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen value.seq2 = data[idx].seq2;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen data[idx].seq2 = seq - 1;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen array_insert(array, idx, &value, 1);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen break;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen }
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen}
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainenbool seq_range_exists(array_t *array, uint32_t seq)
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen{
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen unsigned int idx;
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen return seq_range_lookup(array, seq, &idx);
503a863a317acba125a4e46435694e35fad769e4Timo Sirainen}