K2treeDyn

This is an implementation of the k^2 tree described in the following paper:

Arroyuelo, Diego & de Bernardo, Guillermo & Gagie, Travis & Navarro, Gonzalo. (2019). Faster Dynamic Compressed d-ary Relations. 10.1007/978-3-030-32686-9_30.

Build

• Build tested on Ubuntu 18.04, 19.10, 20.04; Debian 10.6 (buster)
• Most likely won't work on Windows, but might work with custom compilation flow, the only platform dependent code is _builtinpopcount, can be redefined in definitions.h (with POPCOUNT(u32input))
• Working on macOS Monterey

./fetch_deps.sh mkdir build cd build cmake .. make

Code usage

```c

include

include

include

int main(void) { for (int i = 0; i < 10; i++) { uint32t treedepth = 5; uint64t side = 1u << treedepth; struct block *rootblock = createblock();

struct queries_state qs;
init_queries_state(&qs, treedepth, MAX_NODES_IN_BLOCK, root_block);

int point_exists;
for (uint64_t col = 0; col < side; col++) {
  for (uint64_t row = 0; row < side; row++) {
    // printf("inserting col=%lu, row=%lu\n", col, row);
    insert_point(root_block, col, row, &qs, &point_exists);
  }
}

printf("Done inserting i=%d\n", i);

// getchar();

int err_code = free_rec_block(root_block);
if (err_code)
  printf("There was an error with free_rec_block: %d\n", err_code);
err_code = finish_queries_state(&qs);
if (err_code)
  printf("There was an error with finish_queries_state: %d\n", err_code);

if (!err_code) {
  printf("No errors while freeing data\n");
}

// getchar();

}

return 0; }

```

Also see examples.

API: Only blocks tree

(From block.h)

```c

int haspoint(struct block *inputblock, uint64t col, uint64t row, struct queries_state *qs, int *result);

int insertpoint(struct block *inputblock, uint64t col, uint64t row, struct queriesstate *qs, int *alreadyexists);

int deletepoint(struct block *inputblock, uint64t col, uint64t row, struct queriesstate *qs, int *alreadynot_exists);

int naivescanpoints(struct block *inputblock, struct queriesstate *qs, struct vectorpair2dlt *result);

int scanpointsinteractively(struct block *inputblock, struct queriesstate *qs, pointreporterfunt pointreporter, void *report_state);

int reportcolumn(struct block *inputblock, uint64t col, struct queriesstate *qs, struct vectorpair2dlt *result);

int reportrow(struct block *inputblock, uint64t row, struct queriesstate *qs, struct vectorpair2dlt *result);

int reportcolumninteractively(struct block *inputblock, uint64t col, struct queriesstate *qs, pointreporterfunt pointreporter, void *reportstate);

int reportrowinteractively(struct block *inputblock, uint64t row, struct queriesstate *qs, pointreporterfunt pointreporter, void *reportstate);

int sipjoin(struct sipjoininput input, coordreporterfunt coordreporter, void *reportstate);

struct block *create_block(void);

int freerecblock(struct block *input_block);

int freeblock(struct block *inputblock);

struct k2treemeasurement measuretreesize(struct block *inputblock);

int naivescanpointslazyinit(struct block *inputblock, struct queriesstate *qs, struct lazyhandlernaivescant *lazy_handler);

int naivescanpointslazyclean( struct lazyhandlernaivescant *lazy_handler);

int naivescanpointslazynext(struct lazyhandlernaivescant *lazyhandler, pair2dlt *result);

int naivescanpointslazyhasnext( struct lazyhandlernaivescant *lazyhandler, int *result);

int naivescanpointslazyreset( struct lazyhandlernaivescant *lazy_handler);

int reportrowlazyinit(struct lazyhandlerreportbandt *lazyhandler, struct block *inputblock, struct queriesstate *qs, uint64t coord); int reportcolumnlazyinit(struct lazyhandlerreportbandt *lazyhandler, struct block *inputblock, struct queriesstate *qs, uint64t coord);

int reportbandlazyclean(struct lazyhandlerreportbandt *lazyhandler); int reportbandnext(struct lazyhandlerreportbandt *lazyhandler, uint64t *result); int reportbandreset(struct lazyhandlerreportbandt *lazy_handler);

int reportbandhasnext(struct lazyhandlerreportbandt *lazyhandler, int *result); ```

API: Mixed Tree

This tree's upper levels are a tree of pointers, its leaves are the block's trees.

(From k2node.h)

```c int k2nodehaspoint(struct k2node *k2node, uint64t col, uint64t row, struct k2qstate *st, int *result); int k2nodeinsertpoint(struct k2node *inputnode, uint64t col, uint64t row, struct k2qstate *st, int *alreadyexists); int k2nodedeletepoint(struct k2node *inputnode, uint64t col, uint64t row, struct k2qstate *st, int *alreadynot_exists);

int k2nodenaivescanpoints(struct k2node *inputnode, struct k2qstate *st, struct vectorpair2dlt *result);

int k2nodescanpointsinteractively(struct k2node *inputnode, struct k2qstate *st, pointreporterfunt pointreporter, void *report_state);

int k2nodereportcolumn(struct k2node *inputnode, uint64t col, struct k2qstate *st, struct vectorpair2dlt *result); int k2nodereportrow(struct k2node *inputnode, uint64t row, struct k2qstate *st, struct vectorpair2dlt *result);

int k2nodereportcolumninteractively(struct k2node *inputnode, uint64t col, struct k2qstate *st, pointreporterfunt pointreporter, void *reportstate); int k2nodereportrowinteractively(struct k2node *inputnode, uint64t row, struct k2qstate *st, pointreporterfunt pointreporter, void *reportstate);

struct k2node *createk2node(void); int freereck2node(struct k2node *inputnode, uint64t currentdepth, uint64t cutdepth);

int initk2qstate(struct k2qstate *st, TREEDEPTHT treedepth, MAXNODECOUNTT maxnodescount, TREEDEPTHT cutdepth); int cleank2qstate(struct k2qstate *st); struct k2treemeasurement k2nodemeasuretreesize(struct k2node *inputnode, uint64t cut_depth);

int k2nodenaivescanpointslazyinit( struct k2node *inputnode, struct k2qstate *st, struct k2nodelazyhandlernaivescant *lazyhandler);

int k2nodenaivescanpointslazyclean( struct k2nodelazyhandlernaivescant *lazy_handler);

int k2nodenaivescanpointslazynext( struct k2nodelazyhandlernaivescant *lazyhandler, pair2dlt *result);

int k2nodenaivescanpointslazyhasnext( struct k2nodelazyhandlernaivescant *lazyhandler, int *result);

int k2nodenaivescanpointslazyreset( struct k2nodelazyhandlernaivescant *lazy_handler);

int k2nodereportrowlazyinit( struct k2nodelazyhandlerreportbandt *lazyhandler, struct k2node *inputnode, struct k2qstate *st, uint64t coord); int k2nodereportcolumnlazyinit( struct k2nodelazyhandlerreportbandt *lazyhandler, struct k2node *inputnode, struct k2qstate *st, uint64t coord);

int k2nodereportbandlazyclean( struct k2nodelazyhandlerreportbandt *lazyhandler); int k2nodereportbandnext( struct k2nodelazyhandlerreportbandt *lazyhandler, uint64t *result);

int k2nodereportbandhasnext( struct k2nodelazyhandlerreportbandt *lazyhandler, int *result);

int k2nodereportbandreset( struct k2nodelazyhandlerreportbandt *lazy_handler); ```

Some explanations

has_point

Receives an input_block which must be the root block, also the coordinates of the matrix to be checked within the range [0, 2^treedepth - 1] both col and row.

• queries_state is a state structure to avoid doing too much memory allocation. The same can be used for all queries among insert, lookup, reporting and scanning.

• result is the address to store the result (boolean) of the query

naive_scan_points

Naive means that this is not the most optimized version of a scan of all the points, but nonetheless works good enough.

Stores all the points stored in the k2tree into a vector of struct pair2dl:

c struct pair2dl { long col; long row; };

A struct vector is a self increasing array, see: https://github.com/CristobalM/c-vector/blob/master/include/vector.h).

• *input_block the root block of the tree
• *queries_state struct holding state info
• *result Holds the resulting points, must receive an address to an initialized struct vector

report_column

• *input_block the root block of the tree
• col column to report
• *qs struct holding state info
• *result output of points in the column

report_row

Analogous to report_column

create_block

Initializes a block, for the user only use this with the root block, all other inner blocks will be initialized with inserts.

• tree_depth: Depth of the tree, this is fixed so that coordinates of points can only be in the range [0, 2^treedepth-1]. If a bigger range is needed, a new tree must be created. Attempting to insert coordinates into a bigger range will throw an error code in the corresponding calling function.
• TREEDEPTHT is of type uint8_t, a 8 bits unsigned int which allows depth of at most 255.

freerecblock

Will recursively deallocate a block and its children blocks starting at input_block

free_block

Will deallocate a single specified block

More to be documented on k2node...