neovim

Neovim text editor
git clone https://git.dasho.dev/neovim.git
Log | Files | Refs | README

marktree_defs.h (2248B)

      1 #pragma once
      2 
      3 #include <stdbool.h>
      4 #include <stddef.h>
      5 #include <stdint.h>
      6 
      7 #include "nvim/decoration_defs.h"
      8 #include "nvim/map_defs.h"
      9 
     10 enum {
     11  MT_MAX_DEPTH     = 20,
     12  MT_BRANCH_FACTOR = 10,
     13  // note max branch is actually 2*MT_BRANCH_FACTOR
     14  // and strictly this is ceil(log2(2*MT_BRANCH_FACTOR + 1))
     15  // as we need a pseudo-index for "right before this node"
     16  MT_LOG2_BRANCH   = 5,
     17 };
     18 
     19 typedef struct {
     20  int32_t row;
     21  int32_t col;
     22 } MTPos;
     23 #define MTPos(r, c) ((MTPos){ .row = (r), .col = (c) })
     24 
     25 typedef enum {
     26  kMTMetaInline,
     27  kMTMetaLines,
     28  kMTMetaSignHL,
     29  kMTMetaSignText,
     30  kMTMetaConcealLines,
     31  kMTMetaCount,  // sentinel, must be last
     32 } MetaIndex;
     33 
     34 #define kMTFilterSelect ((uint32_t)-1)
     35 
     36 // a filter should be set to kMTFilterSelect for the selected kinds, zero otherwise
     37 typedef const uint32_t *MetaFilter;
     38 
     39 typedef struct mtnode_s MTNode;
     40 
     41 typedef struct {
     42  MTPos pos;
     43  int lvl;
     44  MTNode *x;
     45  int i;
     46  struct {
     47    int oldcol;
     48    int i;
     49  } s[MT_MAX_DEPTH];
     50 
     51  size_t intersect_idx;
     52  MTPos intersect_pos;
     53  MTPos intersect_pos_x;
     54 } MarkTreeIter;
     55 
     56 #define marktree_itr_valid(itr) ((itr)->x != NULL)
     57 // access raw key: flags in MT_FLAG_EXTERNAL_MASK and decor_data are safe to modify.
     58 #define mt_itr_rawkey(itr) ((itr)->x->key[(itr)->i])
     59 
     60 // Internal storage
     61 //
     62 // NB: actual marks have flags > 0, so we can use (row,col,0) pseudo-key for
     63 // "space before (row,col)"
     64 typedef struct {
     65  MTPos pos;
     66  uint32_t ns;
     67  uint32_t id;
     68  uint16_t flags;
     69  DecorInlineData decor_data;  // "ext" tag in flags
     70 } MTKey;
     71 
     72 typedef struct {
     73  MTKey start;
     74  MTPos end_pos;
     75  bool end_right_gravity;
     76 } MTPair;
     77 
     78 typedef kvec_withinit_t(uint64_t, 4) Intersection;
     79 
     80 // part of mtnode_s which is only allocated for inner nodes:
     81 // pointer to children as well as their meta counts
     82 struct mtnode_inner_s {
     83  MTNode *i_ptr[2 * MT_BRANCH_FACTOR];
     84  uint32_t i_meta[2 * MT_BRANCH_FACTOR][kMTMetaCount];
     85 };
     86 
     87 struct mtnode_s {
     88  int32_t n;
     89  int16_t level;
     90  int16_t p_idx;  // index in parent
     91  Intersection intersect;
     92  MTNode *parent;
     93  MTKey key[2 * MT_BRANCH_FACTOR - 1];
     94  struct mtnode_inner_s s[];
     95 };
     96 
     97 typedef struct {
     98  MTNode *root;
     99  uint32_t meta_root[kMTMetaCount];
    100  size_t n_keys, n_nodes;
    101  PMap(uint64_t) id2node[1];
    102 } MarkTree;