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 RIGHT_GRAVITY   (((uint64_t)1) << 63)
 
#define ANTIGRAVITY(id)   ((id)&(RIGHT_GRAVITY-1))
 
#define IS_RIGHT(id)   ((id)&RIGHT_GRAVITY)
 
#define PAIRED   MARKTREE_PAIRED_FLAG
 
#define END_FLAG   MARKTREE_END_FLAG
 
#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

uint64_t marktree_put (MarkTree *b, int row, int col, bool right_gravity, uint8_t decor_level)
 
uint64_t marktree_put_pair (MarkTree *b, int start_row, int start_col, bool start_right, int end_row, int end_col, bool end_right, uint8_t decor_level)
 
void marktree_put_key (MarkTree *b, int row, int col, uint64_t id)
 
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)
 
uint64_t marktree_revise (MarkTree *b, MarkTreeIter *itr, uint8_t decor_level)
 NB: caller must check not pair! More...
 
void marktree_move (MarkTree *b, MarkTreeIter *itr, int row, int col)
 
bool marktree_itr_get (MarkTree *b, int 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)
 
mtmark_t marktree_itr_current (MarkTreeIter *itr)
 
bool marktree_splice (MarkTree *b, int 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)
 
mtpos_t marktree_lookup (MarkTree *b, uint64_t id, MarkTreeIter *itr)
 
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

◆ ANTIGRAVITY

#define ANTIGRAVITY (   id)    ((id)&(RIGHT_GRAVITY-1))

◆ END_FLAG

#define END_FLAG   MARKTREE_END_FLAG

◆ ID_INCR

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

◆ ILEN

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

◆ IS_RIGHT

#define IS_RIGHT (   id)    ((id)&RIGHT_GRAVITY)

◆ mt_generic_cmp

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

◆ PAIRED

#define PAIRED   MARKTREE_PAIRED_FLAG

◆ rawkey

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

◆ RIGHT_GRAVITY

#define RIGHT_GRAVITY   (((uint64_t)1) << 63)

◆ 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_itr_current()

mtmark_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,
int  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()

mtpos_t marktree_lookup ( MarkTree b,
uint64_t  id,
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()

uint64_t marktree_put ( MarkTree b,
int  row,
int  col,
bool  right_gravity,
uint8_t  decor_level 
)

◆ marktree_put_key()

void marktree_put_key ( MarkTree b,
int  row,
int  col,
uint64_t  id 
)

◆ marktree_put_pair()

uint64_t marktree_put_pair ( MarkTree b,
int  start_row,
int  start_col,
bool  start_right,
int  end_row,
int  end_col,
bool  end_right,
uint8_t  decor_level 
)

◆ marktree_revise()

uint64_t marktree_revise ( MarkTree b,
MarkTreeIter itr,
uint8_t  decor_level 
)

NB: caller must check not pair!

◆ marktree_splice()

bool marktree_splice ( MarkTree b,
int  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)