From b04286a187d57c50f01cd36cd4668b7a69026579 Mon Sep 17 00:00:00 2001 From: bfredl Date: Sun, 22 Nov 2020 10:10:37 +0100 Subject: feat(extmark): support proper multiline ranges The removes the previous restriction that nvim_buf_set_extmark() could not be used to highlight arbitrary multi-line regions The problem can be summarized as follows: let's assume an extmark with a hl_group is placed covering the region (5,0) to (50,0) Now, consider what happens if nvim needs to redraw a window covering the lines 20-30. It needs to be able to ask the marktree what extmarks cover this region, even if they don't begin or end here. Therefore the marktree needs to be augmented with the information covers a point, not just what marks begin or end there. To do this, we augment each node with a field "intersect" which is a set the ids of the marks which overlap this node, but only if it is not part of the set of any parent. This ensures the number of nodes that need to be explicitly marked grows only logarithmically with the total number of explicitly nodes (and thus the number of of overlapping marks). Thus we can quickly iterate all marks which overlaps any query position by looking up what leaf node contains that position. Then we only need to consider all "start" marks within that leaf node, and the "intersect" set of that node and all its parents. Now, and the major source of complexity is that the tree restructuring operations (to ensure that each node has T-1 <= size <= 2*T-1) also need to update these sets. If a full inner node is split in two, one of the new parents might start to completely overlap some ranges and its ids will need to be moved from its children's sets to its own set. Similarly, if two undersized nodes gets joined into one, it might no longer completely overlap some ranges, and now the children which do needs to have the have the ids in its set instead. And then there are the pivots! Yes the pivot operations when a child gets moved from one parent to another. --- src/klib/kvec.h | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) (limited to 'src/klib/kvec.h') diff --git a/src/klib/kvec.h b/src/klib/kvec.h index f6674a0adf..fd9096e1ad 100644 --- a/src/klib/kvec.h +++ b/src/klib/kvec.h @@ -207,6 +207,16 @@ static inline void *_memcpy_free(void *const restrict dest, void *const restrict /* 2^x initial array size. */ \ kvi_resize(v, (v).capacity << 1) +/// fit at least "len" more items +#define kvi_ensure_more_space(v, len) \ + do { \ + if ((v).capacity < (v).size + len) { \ + (v).capacity = (v).size + len; \ + kv_roundup32((v).capacity); \ + kvi_resize((v), (v).capacity); \ + } \ + } while (0) + /// Get location where to store new element to a vector with preallocated array /// /// @param[in,out] v Vector to push to. @@ -223,6 +233,19 @@ static inline void *_memcpy_free(void *const restrict dest, void *const restrict #define kvi_push(v, x) \ (*kvi_pushp(v) = (x)) +/// Copy a vector to a preallocated vector +/// +/// @param[out] v1 destination +/// @param[in] v0 source (can be either vector or preallocated vector) +#define kvi_copy(v1, v0) \ + do { \ + if ((v1).capacity < (v0).size) { \ + kvi_resize(v1, (v0).size); \ + } \ + (v1).size = (v0).size; \ + memcpy((v1).items, (v0).items, sizeof((v1).items[0]) * (v0).size); \ + } while (0) + /// Free array of elements of a vector with preallocated array if needed /// /// @param[out] v Vector to free. -- cgit From 353a4be7e84fdc101318215bdcc8a7e780d737fe Mon Sep 17 00:00:00 2001 From: dundargoc Date: Sun, 12 Nov 2023 13:13:58 +0100 Subject: build: remove PVS We already have an extensive suite of static analysis tools we use, which causes a fair bit of redundancy as we get duplicate warnings. PVS is also prone to give false warnings which creates a lot of work to identify and disable. --- src/klib/kvec.h | 2 -- 1 file changed, 2 deletions(-) (limited to 'src/klib/kvec.h') diff --git a/src/klib/kvec.h b/src/klib/kvec.h index fd9096e1ad..5677a93b1b 100644 --- a/src/klib/kvec.h +++ b/src/klib/kvec.h @@ -170,8 +170,6 @@ static inline void *_memcpy_free(void *const restrict dest, void *const restrict return dest; } -// -V:kvi_push:512 - /// Resize vector with preallocated array /// /// @note May not resize to an array smaller then init_array: if requested, -- cgit