Macros | Functions
marktree.c File Reference
#include <assert.h>
#include "nvim/garray.h"
#include "nvim/lib/kvec.h"
#include "nvim/marktree.h"

Macros

#define T   MT_BRANCH_FACTOR
 
#define ILEN   (sizeof(mtnode_t) + (2 * T) * sizeof(void *))
 
#define ID_INCR   (((uint64_t)1) << 2)
 
#define rawkey(itr)   (itr->node->key[itr->i])
 
#define mt_generic_cmp(a, b)   (((b) < (a)) - ((a) < (b)))
 

Functions

void marktree_put (MarkTree *b, mtkey_t key, int end_row, int end_col, bool end_right)
 
void marktree_put_key (MarkTree *b, mtkey_t k)
 
void marktree_del_itr (MarkTree *b, MarkTreeIter *itr, bool rev)
 
void marktree_clear (MarkTree *b)
 frees all mem, resets tree to valid empty state More...
 
void marktree_free_node (mtnode_t *x)
 
void marktree_revise (MarkTree *b, MarkTreeIter *itr, uint8_t decor_level, mtkey_t key)
 NB: caller must check not pair! More...
 
void marktree_move (MarkTree *b, MarkTreeIter *itr, int row, int col)
 
bool marktree_itr_get (MarkTree *b, int32_t row, int col, MarkTreeIter *itr)
 
bool marktree_itr_get_ext (MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last, bool gravity, mtpos_t *oldbase)
 
bool marktree_itr_first (MarkTree *b, MarkTreeIter *itr)
 
int marktree_itr_last (MarkTree *b, MarkTreeIter *itr)
 
bool marktree_itr_next (MarkTree *b, MarkTreeIter *itr)
 
bool marktree_itr_prev (MarkTree *b, MarkTreeIter *itr)
 
void marktree_itr_rewind (MarkTree *b, MarkTreeIter *itr)
 
bool marktree_itr_node_done (MarkTreeIter *itr)
 
mtpos_t marktree_itr_pos (MarkTreeIter *itr)
 
mtkey_t marktree_itr_current (MarkTreeIter *itr)
 
bool marktree_splice (MarkTree *b, int32_t start_line, int start_col, int old_extent_line, int old_extent_col, int new_extent_line, int new_extent_col)
 
void marktree_move_region (MarkTree *b, int start_row, colnr_T start_col, int extent_row, colnr_T extent_col, int new_row, colnr_T new_col)
 
mtkey_t marktree_lookup_ns (MarkTree *b, uint32_t ns, uint32_t id, bool end, MarkTreeIter *itr)
 
mtkey_t marktree_lookup (MarkTree *b, uint64_t id, MarkTreeIter *itr)
 
mtpos_t marktree_get_altpos (MarkTree *b, mtkey_t mark, MarkTreeIter *itr)
 
mtkey_t marktree_get_alt (MarkTree *b, mtkey_t mark, MarkTreeIter *itr)
 
void marktree_put_test (MarkTree *b, uint32_t id, int row, int col, bool right_gravity)
 
bool mt_right_test (mtkey_t key)
 
void marktree_check (MarkTree *b)
 
char * mt_inspect_rec (MarkTree *b)
 
void mt_inspect_node (MarkTree *b, garray_T *ga, mtnode_t *n, mtpos_t off)
 

Macro Definition Documentation

◆ ID_INCR

#define ID_INCR   (((uint64_t)1) << 2)

◆ ILEN

#define ILEN   (sizeof(mtnode_t) + (2 * T) * sizeof(void *))

◆ mt_generic_cmp

#define mt_generic_cmp (   a,
 
)    (((b) < (a)) - ((a) < (b)))

◆ rawkey

#define rawkey (   itr)    (itr->node->key[itr->i])

◆ T

#define T   MT_BRANCH_FACTOR

Function Documentation

◆ marktree_check()

void marktree_check ( MarkTree b)

◆ marktree_clear()

void marktree_clear ( MarkTree b)

frees all mem, resets tree to valid empty state

◆ marktree_del_itr()

void marktree_del_itr ( MarkTree b,
MarkTreeIter itr,
bool  rev 
)

INITIATING DELETION PROTOCOL:

  1. Construct a valid iterator to the node to delete (argument)
  2. If an "internal" key. Iterate one step to the left or right, which gives an internal key "auxiliary key".
  3. Now delete this internal key (intended or auxiliary). The leaf node X might become undersized.
  4. If step two was done: now replace the key that should be deleted with the auxiliary key. Adjust relative
  5. Now "repair" the tree as needed. We always start at a leaf node X.
    • if the node is big enough, terminate
    • if we can steal from the left, steal
    • if we can steal from the right, steal
    • otherwise merge this node with a neighbour. This might make our parent undersized. So repeat 5 for the parent.
  6. If 4 went all the way to the root node. The root node might have ended up with size 0. Delete it then.

NB: ideally keeps the iterator valid. Like point to the key after this if present.

Parameters
revshould be true if we plan to iterate backwards and delete stuff before this key. Most of the time this is false (the recommended strategy is to always iterate forward)

◆ marktree_free_node()

void marktree_free_node ( mtnode_t x)

◆ marktree_get_alt()

mtkey_t marktree_get_alt ( MarkTree b,
mtkey_t  mark,
MarkTreeIter itr 
)

◆ marktree_get_altpos()

mtpos_t marktree_get_altpos ( MarkTree b,
mtkey_t  mark,
MarkTreeIter itr 
)

◆ marktree_itr_current()

mtkey_t marktree_itr_current ( MarkTreeIter itr)

◆ marktree_itr_first()

bool marktree_itr_first ( MarkTree b,
MarkTreeIter itr 
)

◆ marktree_itr_get()

bool marktree_itr_get ( MarkTree b,
int32_t  row,
int  col,
MarkTreeIter itr 
)

◆ marktree_itr_get_ext()

bool marktree_itr_get_ext ( MarkTree b,
mtpos_t  p,
MarkTreeIter itr,
bool  last,
bool  gravity,
mtpos_t oldbase 
)

◆ marktree_itr_last()

int marktree_itr_last ( MarkTree b,
MarkTreeIter itr 
)

◆ marktree_itr_next()

bool marktree_itr_next ( MarkTree b,
MarkTreeIter itr 
)

◆ marktree_itr_node_done()

bool marktree_itr_node_done ( MarkTreeIter itr)

◆ marktree_itr_pos()

mtpos_t marktree_itr_pos ( MarkTreeIter itr)

◆ marktree_itr_prev()

bool marktree_itr_prev ( MarkTree b,
MarkTreeIter itr 
)

◆ marktree_itr_rewind()

void marktree_itr_rewind ( MarkTree b,
MarkTreeIter itr 
)

◆ marktree_lookup()

mtkey_t marktree_lookup ( MarkTree b,
uint64_t  id,
MarkTreeIter itr 
)
Parameters
itrOPTIONAL. set itr to pos.

◆ marktree_lookup_ns()

mtkey_t marktree_lookup_ns ( MarkTree b,
uint32_t  ns,
uint32_t  id,
bool  end,
MarkTreeIter itr 
)
Parameters
itrOPTIONAL. set itr to pos.

◆ marktree_move()

void marktree_move ( MarkTree b,
MarkTreeIter itr,
int  row,
int  col 
)

◆ marktree_move_region()

void marktree_move_region ( MarkTree b,
int  start_row,
colnr_T  start_col,
int  extent_row,
colnr_T  extent_col,
int  new_row,
colnr_T  new_col 
)

◆ marktree_put()

void marktree_put ( MarkTree b,
mtkey_t  key,
int  end_row,
int  end_col,
bool  end_right 
)

◆ marktree_put_key()

void marktree_put_key ( MarkTree b,
mtkey_t  k 
)

◆ marktree_put_test()

void marktree_put_test ( MarkTree b,
uint32_t  id,
int  row,
int  col,
bool  right_gravity 
)

◆ marktree_revise()

void marktree_revise ( MarkTree b,
MarkTreeIter itr,
uint8_t  decor_level,
mtkey_t  key 
)

NB: caller must check not pair!

◆ marktree_splice()

bool marktree_splice ( MarkTree b,
int32_t  start_line,
int  start_col,
int  old_extent_line,
int  old_extent_col,
int  new_extent_line,
int  new_extent_col 
)

◆ mt_inspect_node()

void mt_inspect_node ( MarkTree b,
garray_T ga,
mtnode_t n,
mtpos_t  off 
)

◆ mt_inspect_rec()

char* mt_inspect_rec ( MarkTree b)

◆ mt_right_test()

bool mt_right_test ( mtkey_t  key)