145 lines
5.4 KiB
C
145 lines
5.4 KiB
C
/*
|
|
* Copyright (c) 2024 Gregory Burd <greg@burd.me>. All rights reserved.
|
|
*
|
|
* Permission is hereby granted, free of charge, to any person obtaining a copy
|
|
* of this software and associated documentation files (the "Software"), to deal
|
|
* in the Software without restriction, including without limitation the rights
|
|
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
|
* copies of the Software, and to permit persons to whom the Software is
|
|
* furnished to do so, subject to the following conditions:
|
|
*
|
|
* The above copyright notice and this permission notice shall be included in
|
|
* all copies or substantial portions of the Software.
|
|
*
|
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
|
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
|
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
|
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
|
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
|
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
|
* SOFTWARE.
|
|
*/
|
|
|
|
/*
|
|
* Sparsemap
|
|
*
|
|
* This is an implementation for a sparse, compressed bitmap. It is resizable
|
|
* and mutable, with reasonable performance for random access modifications
|
|
* and lookups.
|
|
*
|
|
* The implementation is separated into tiers.
|
|
*
|
|
* Tier 0 (lowest): bits are stored in a sm_bitvec_t (uint64_t).
|
|
*
|
|
* Tier 1 (middle): multiple sm_bitvec_t are managed in a chunk map. The chunk
|
|
* map only stores those sm_bitvec_t that have a mixed payload of bits (i.e.
|
|
* some bits are 1, some are 0). As soon as ALL bits in a sm_bitvec_t are
|
|
* identical, this sm_bitvec_t is no longer stored, it is compressed.
|
|
*
|
|
* The chunk maps store additional flags (2 bit) for each sm_bitvec_t in an
|
|
* additional word (same size as the sm_bitvec_t itself).
|
|
*
|
|
* 00 11 22 33
|
|
* ^-- descriptor for sm_bitvec_t 1
|
|
* ^-- descriptor for sm_bitvec_t 2
|
|
* ^-- descriptor for sm_bitvec_t 3
|
|
* ^-- descriptor for sm_bitvec_t 4
|
|
*
|
|
* Those flags (*) can have one of the following values:
|
|
*
|
|
* 00 The sm_bitvec_t is all zero -> sm_bitvec_t is not stored
|
|
* 11 The sm_bitvec_t is all one -> sm_bitvec_t is not stored
|
|
* 10 The sm_bitvec_t contains a bitmap -> sm_bitvec_t is stored
|
|
* 01 The sm_bitvec_t is not used (**)
|
|
*
|
|
* The serialized size of a chunk map in memory therefore is at least
|
|
* one sm_bitvec_t for the flags, and (optionally) additional sm_bitvec_ts
|
|
* if they are required.
|
|
*
|
|
* (*) The code comments often use the Erlang format for binary
|
|
* representation, i.e. 2#10 for (binary) 01.
|
|
*
|
|
* (**) This flag is set to reduce the capacity of a chunk map.
|
|
*
|
|
* Tier 2 (highest): the Sparsemap manages multiple chunk maps. Each chunk
|
|
* has its own offset (relative to the offset of the Sparsemap). In
|
|
* addition, the Sparsemap manages the memory of the chunk maps, and
|
|
* is able to grow or shrink that memory as required.
|
|
*/
|
|
#ifndef SPARSEMAP_H
|
|
#define SPARSEMAP_H
|
|
|
|
#include <sys/types.h>
|
|
|
|
#include <assert.h>
|
|
#include <limits.h>
|
|
#include <stdbool.h>
|
|
#include <stdint.h>
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
|
|
/*
|
|
* The public interface for a sparse bit-mapped index, a "sparse map".
|
|
*
|
|
* |sm_idx_t| is the user's numerical data type which is mapped to a single bit
|
|
* in the bitmap. Usually this is uint32_t or uint64_t. |sm_bitvec_t| is the
|
|
* storage type for a bit vector used by the __sm_chunk_t internal maps.
|
|
* Usually this is an uint64_t.
|
|
*/
|
|
|
|
|
|
typedef struct sparsemap sparsemap_t;
|
|
typedef uint32_t sm_idx_t;
|
|
typedef uint64_t sm_bitvec_t;
|
|
|
|
|
|
/* Allocate on a sparsemap_t on the heap and initialize it. */
|
|
sparsemap_t *sparsemap(uint8_t *data, size_t size);
|
|
|
|
/* Initialize sparsemap_t with data. */
|
|
void sparsemap_init(sparsemap_t *map, uint8_t *data, size_t size);
|
|
|
|
/* Clears the whole buffer. */
|
|
void sparsemap_clear(sparsemap_t *map);
|
|
|
|
/* Opens an existing sparsemap at the specified buffer. */
|
|
void sparsemap_open(sparsemap_t *, uint8_t *data, size_t data_size);
|
|
|
|
/* Resizes the data range. */
|
|
void sparsemap_set_data_size(sparsemap_t *map, size_t data_size);
|
|
|
|
/* Calculate remaining capacity, full when 0. */
|
|
double sparsemap_capacity_remaining(sparsemap_t *map);
|
|
|
|
/* Returns the size of the underlying byte array. */
|
|
size_t sparsemap_get_capacity(sparsemap_t *map);
|
|
|
|
/* Returns the value of a bit at index |idx|. */
|
|
bool sparsemap_is_set(sparsemap_t *map, size_t idx);
|
|
|
|
/* Sets the bit at index |idx| to true or false, depending on |value|. */
|
|
void sparsemap_set(sparsemap_t *map, size_t idx, bool value);
|
|
|
|
/* Returns the offset of the very first bit. */
|
|
sm_idx_t sparsemap_get_start_offset(sparsemap_t *map);
|
|
|
|
/* Returns the used size in the data buffer. */
|
|
size_t sparsemap_get_size(sparsemap_t *map);
|
|
|
|
/* Decompresses the whole bitmap; calls scanner for all bits. */
|
|
void sparsemap_scan(sparsemap_t *map, void (*scanner)(sm_idx_t[], size_t), size_t skip);
|
|
|
|
/* Appends all chunk maps from |map| starting at |sstart| to |other|, then
|
|
reduces the chunk map-count appropriately. */
|
|
void sparsemap_split(sparsemap_t *map, size_t sstart, sparsemap_t *other);
|
|
|
|
/* Returns the index of the n'th set bit; uses a 0-based index. */
|
|
size_t sparsemap_select(sparsemap_t *map, size_t n);
|
|
|
|
/* Counts the set bits in the range [offset, idx]. */
|
|
size_t sparsemap_rank(sparsemap_t *map, size_t offset, size_t idx);
|
|
|
|
size_t sparsemap_span(sparsemap_t *map, size_t loc, size_t len);
|
|
|
|
#endif
|