From f449f278dd3c70e479a035f50a9bb817a9b433ba Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 17:24:08 +0200 Subject: Adding upstream version 3.2.6. Signed-off-by: Daniel Baumann --- src/libknot/rdataset.c | 371 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 371 insertions(+) create mode 100644 src/libknot/rdataset.c (limited to 'src/libknot/rdataset.c') diff --git a/src/libknot/rdataset.c b/src/libknot/rdataset.c new file mode 100644 index 0000000..03e0784 --- /dev/null +++ b/src/libknot/rdataset.c @@ -0,0 +1,371 @@ +/* Copyright (C) 2022 CZ.NIC, z.s.p.o. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . + */ + +#include +#include +#include + +#include "libknot/attribute.h" +#include "libknot/rdataset.h" +#include "contrib/mempattern.h" + +static knot_rdata_t *rr_seek(const knot_rdataset_t *rrs, uint16_t pos) +{ + assert(rrs); + assert(0 < rrs->count); + assert(pos < rrs->count); + + uint8_t *raw = (uint8_t *)(rrs->rdata); + for (uint16_t i = 0; i < pos; ++i) { + raw += knot_rdata_size(((knot_rdata_t *)raw)->len); + } + + return (knot_rdata_t *)raw; +} + +static int find_rr_pos(const knot_rdataset_t *rrs, const knot_rdata_t *rr) +{ + knot_rdata_t *search_rr = rrs->rdata; + for (uint16_t i = 0; i < rrs->count; ++i) { + if (knot_rdata_cmp(rr, search_rr) == 0) { + return i; + } + search_rr = knot_rdataset_next(search_rr); + } + + return KNOT_ENOENT; +} + +static int add_rr_at(knot_rdataset_t *rrs, const knot_rdata_t *rr, knot_rdata_t *ins_pos, + knot_mm_t *mm) +{ + assert(rrs); + assert(rr); + const size_t ins_offset = (uint8_t *)ins_pos - (uint8_t *)rrs->rdata; + assert(ins_offset <= rrs->size); + + if (rrs->count == UINT16_MAX) { + return KNOT_ESPACE; + } else if (rrs->size > UINT32_MAX - knot_rdata_size(UINT16_MAX)) { + return KNOT_ESPACE; + } + + const size_t rr_size = knot_rdata_size(rr->len); + + // Realloc RDATA. + knot_rdata_t *tmp = mm_realloc(mm, rrs->rdata, rrs->size + rr_size, + rrs->size); + if (tmp == NULL) { + return KNOT_ENOMEM; + } else { + rrs->rdata = tmp; + } + + uint8_t *ins_pos_raw = (uint8_t *)rrs->rdata + ins_offset; + // RDATA may have to be rearanged. Moving zero-length region is OK. + memmove(ins_pos_raw + rr_size, ins_pos_raw, rrs->size - ins_offset); + + // Set new RDATA. + knot_rdata_init((knot_rdata_t *)ins_pos_raw, rr->len, rr->data); + rrs->count++; + rrs->size += rr_size; + + return KNOT_EOK; +} + +static int remove_rr_at(knot_rdataset_t *rrs, uint16_t pos, knot_mm_t *mm) +{ + assert(rrs); + assert(0 < rrs->count); + assert(pos < rrs->count); + + knot_rdata_t *old_rr = rr_seek(rrs, pos); + knot_rdata_t *last_rr = rr_seek(rrs, rrs->count - 1); + + size_t old_size = knot_rdata_size(old_rr->len); + + // Move RDATA. + uint8_t *old_threshold = (uint8_t *)old_rr + old_size; + uint8_t *last_threshold = (uint8_t *)last_rr + knot_rdata_size(last_rr->len); + assert(old_threshold <= last_threshold); + memmove(old_rr, old_threshold, last_threshold - old_threshold); + + if (rrs->count > 1) { + // Realloc RDATA. + knot_rdata_t *tmp = mm_realloc(mm, rrs->rdata, rrs->size - old_size, + rrs->size); + if (tmp == NULL) { + return KNOT_ENOMEM; + } else { + rrs->rdata = tmp; + } + } else { + // Free RDATA. + mm_free(mm, rrs->rdata); + rrs->rdata = NULL; + } + rrs->count--; + rrs->size -= old_size; + + return KNOT_EOK; +} + +_public_ +void knot_rdataset_clear(knot_rdataset_t *rrs, knot_mm_t *mm) +{ + if (rrs == NULL) { + return; + } + + mm_free(mm, rrs->rdata); + knot_rdataset_init(rrs); +} + +_public_ +int knot_rdataset_copy(knot_rdataset_t *dst, const knot_rdataset_t *src, knot_mm_t *mm) +{ + if (dst == NULL || src == NULL) { + return KNOT_EINVAL; + } + + dst->count = src->count; + dst->size = src->size; + + if (src->count > 0) { + assert(src->rdata != NULL); + dst->rdata = mm_alloc(mm, src->size); + if (dst->rdata == NULL) { + return KNOT_ENOMEM; + } + memcpy(dst->rdata, src->rdata, src->size); + } else { + assert(src->size == 0); + dst->rdata = NULL; + } + + return KNOT_EOK; +} + +_public_ +knot_rdata_t *knot_rdataset_at(const knot_rdataset_t *rrs, uint16_t pos) +{ + if (rrs == NULL || rrs->count == 0 || pos >= rrs->count) { + return NULL; + } + + return rr_seek(rrs, pos); +} + +_public_ +int knot_rdataset_add(knot_rdataset_t *rrs, const knot_rdata_t *rr, knot_mm_t *mm) +{ + if (rrs == NULL || rr == NULL) { + return KNOT_EINVAL; + } + + // Optimize a little for insertion at the end, for larger RRsets. + if (rrs->count > 4) { + knot_rdata_t *last = rr_seek(rrs, rrs->count - 1); + if (knot_rdata_cmp(last, rr) < 0) { + return add_rr_at(rrs, rr, knot_rdataset_next(last), mm); + } + } + + // Look for the right place to insert. + knot_rdata_t *ins_pos = rrs->rdata; + for (int i = 0; i < rrs->count; ++i, ins_pos = knot_rdataset_next(ins_pos)) { + int cmp = knot_rdata_cmp(ins_pos, rr); + if (cmp == 0) { + // Duplicate - no need to add this RR. + return KNOT_EOK; + } else if (cmp > 0) { + // Found position to insert. + return add_rr_at(rrs, rr, ins_pos, mm); + } + } + + assert(rrs->rdata == NULL || (uint8_t *)rrs->rdata + rrs->size == (uint8_t *)ins_pos); + + // If flow gets here, it means that we should insert at the current position (append). + return add_rr_at(rrs, rr, ins_pos, mm); +} + +_public_ +bool knot_rdataset_eq(const knot_rdataset_t *rrs1, const knot_rdataset_t *rrs2) +{ + if (rrs1 == NULL || rrs2 == NULL || rrs1->count != rrs2->count) { + return false; + } + + knot_rdata_t *rr1 = rrs1->rdata; + knot_rdata_t *rr2 = rrs2->rdata; + for (uint16_t i = 0; i < rrs1->count; ++i) { + if (knot_rdata_cmp(rr1, rr2) != 0) { + return false; + } + rr1 = knot_rdataset_next(rr1); + rr2 = knot_rdataset_next(rr2); + } + + return true; +} + +_public_ +bool knot_rdataset_member(const knot_rdataset_t *rrs, const knot_rdata_t *rr) +{ + if (rrs == NULL) { + return false; + } + + knot_rdata_t *cmp_rr = rrs->rdata; + for (uint16_t i = 0; i < rrs->count; ++i) { + int cmp = knot_rdata_cmp(cmp_rr, rr); + if (cmp == 0) { + // Match. + return true; + } else if (cmp > 0) { + // 'Greater' RR present, no need to continue. + return false; + } + cmp_rr = knot_rdataset_next(cmp_rr); + } + + return false; +} + +_public_ +bool knot_rdataset_subset(const knot_rdataset_t *subset, const knot_rdataset_t *of) +{ + if (subset == NULL || (of != NULL && subset->rdata == of->rdata)) { + return true; + } + + knot_rdata_t *rd = subset->rdata; + for (uint16_t i = 0; i < subset->count; ++i) { + if (!knot_rdataset_member(of, rd)) { + return false; + } + rd = knot_rdataset_next(rd); + } + + return true; +} + +_public_ +int knot_rdataset_merge(knot_rdataset_t *rrs1, const knot_rdataset_t *rrs2, + knot_mm_t *mm) +{ + if (rrs1 == NULL || rrs2 == NULL) { + return KNOT_EINVAL; + } + + knot_rdata_t *rr2 = rrs2->rdata; + for (uint16_t i = 0; i < rrs2->count; ++i) { + int ret = knot_rdataset_add(rrs1, rr2, mm); + if (ret != KNOT_EOK) { + return ret; + } + rr2 = knot_rdataset_next(rr2); + } + + return KNOT_EOK; +} + +_public_ +int knot_rdataset_intersect(const knot_rdataset_t *rrs1, const knot_rdataset_t *rrs2, + knot_rdataset_t *out, knot_mm_t *mm) +{ + if (rrs1 == NULL || rrs2 == NULL || out == NULL) { + return KNOT_EINVAL; + } + + knot_rdataset_init(out); + knot_rdata_t *rr1 = rrs1->rdata; + for (uint16_t i = 0; i < rrs1->count; ++i) { + if (knot_rdataset_member(rrs2, rr1)) { + // Add RR into output intersection RRSet. + int ret = knot_rdataset_add(out, rr1, mm); + if (ret != KNOT_EOK) { + knot_rdataset_clear(out, mm); + return ret; + } + } + rr1 = knot_rdataset_next(rr1); + } + + return KNOT_EOK; +} + +_public_ +int knot_rdataset_intersect2(knot_rdataset_t *from, const knot_rdataset_t *what, + knot_mm_t *mm) +{ + if (from == NULL || what == NULL) { + return KNOT_EINVAL; + } + + if (from->rdata == what->rdata) { + return KNOT_EOK; + } + + knot_rdata_t *rr1 = from->rdata; + for (uint16_t i = 0; i < from->count; ) { + if (!knot_rdataset_member(what, rr1)) { + int ret = remove_rr_at(from, i, mm); + if (ret != KNOT_EOK) { + return ret; + } + if (i < from->count) { + // Just to make sure rr1 remains valid if re-allocated. + rr1 = rr_seek(from, i); + } + } else { + i++; + rr1 = knot_rdataset_next(rr1); + } + } + + return KNOT_EOK; +} + +_public_ +int knot_rdataset_subtract(knot_rdataset_t *from, const knot_rdataset_t *what, + knot_mm_t *mm) +{ + if (from == NULL || what == NULL) { + return KNOT_EINVAL; + } + + if (from->rdata == what->rdata) { + knot_rdataset_clear(from, mm); + knot_rdataset_init((knot_rdataset_t *) what); + return KNOT_EOK; + } + + knot_rdata_t *to_remove = what->rdata; + for (uint16_t i = 0; i < what->count; ++i) { + int pos_to_remove = find_rr_pos(from, to_remove); + if (pos_to_remove >= 0) { + int ret = remove_rr_at(from, pos_to_remove, mm); + if (ret != KNOT_EOK) { + return ret; + } + } + to_remove = knot_rdataset_next(to_remove); + } + + return KNOT_EOK; +} -- cgit v1.2.3