lib/datastruct/radix-tree.h - main - githubmirror/lvm2

lib/datastruct/radix-tree.h
103 строки3 KB
Zdenek Kabelac
cppcheck: fix funcArgNamesDifferent in lib headers and tools
11 май 2026, 11:18
11 май 2026, 11:1897c21ac
/*
 * Copyright (C) 2018-2026 Red Hat, Inc. All rights reserved.
 *
 * This file is part of LVM2.
 *
 * This copyrighted material is made available to anyone wishing to use,
 * modify, copy, or redistribute it subject to the terms and conditions
 * of the GNU Lesser General Public License v.2.1.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef BASE_DATA_STRUCT_RADIX_TREE_H
#define BASE_DATA_STRUCT_RADIX_TREE_H

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

/*----------------------------------------------------------------*/

struct radix_tree;

union radix_value {
	void *ptr;
	uint64_t n;
};

typedef void (*radix_value_dtr)(void *context, union radix_value v);

/* dtr will be called on any deleted entries.  dtr may be NULL. */
struct radix_tree *radix_tree_create(radix_value_dtr dtr, void *dtr_context);
void radix_tree_destroy(struct radix_tree *rt);

unsigned radix_tree_size(const struct radix_tree *rt);
bool radix_tree_insert(struct radix_tree *rt, const void *key, size_t keylen, union radix_value rv);
bool radix_tree_remove(struct radix_tree *rt, const void *key, size_t keylen);
/*
 * Returns: 1 success
 *	    0 failure during insert
 *	   -1 key had already existing value (that was updated)
 */
int radix_tree_uniq_insert(struct radix_tree *rt, const void *key, size_t keylen, union radix_value rv);

/* Returns the number of values removed */
unsigned radix_tree_remove_prefix(struct radix_tree *rt, const void *prefix, size_t prefix_len);

bool radix_tree_lookup(const struct radix_tree *rt, const void *key, size_t keylen,
		       union radix_value *result);

/*
 * The radix tree stores entries in lexicographical order.  Which means
 * we can iterate entries, in order.  Or iterate entries with a particular
 * prefix.
 */
struct radix_tree_iterator {
	/* Returns false if the iteration should end. */
	bool (*visit)(struct radix_tree_iterator *it,
		      const void *key, size_t keylen, union radix_value v);
};

void radix_tree_iterate(const struct radix_tree *rt, const void *key, size_t keylen,
			struct radix_tree_iterator *it);

/*
 * Alternative traversing radix_tree.
 * Builds set of all matching radix_tree values into nr_values.
 * After use, free(values).
 */
bool radix_tree_values(const struct radix_tree *rt, const void *key, size_t keylen,
		       union radix_value **values, unsigned *nr_values);

/*
 * Checks that some constraints on the shape of the tree are
 * being held.  For debug only.
 */
bool radix_tree_is_well_formed(const struct radix_tree *rt);
void radix_tree_dump(const struct radix_tree *rt, FILE *out);

/* Shortcut for ptr value return */
/* WARNING: NULL ptr stored as a value is indistinguishable from "not found". */
static inline void *radix_tree_lookup_ptr(const struct radix_tree *rt, const void *key, size_t keylen)
{
	union radix_value v;
	return radix_tree_lookup(rt, key, keylen, &v) ? v.ptr : NULL;
}

static inline bool radix_tree_insert_ptr(struct radix_tree *rt, const void *key, size_t keylen, void *ptr)
{
	union radix_value v = { .ptr = ptr };
	return radix_tree_insert(rt, key, keylen, v);
}

static inline int radix_tree_uniq_insert_ptr(struct radix_tree *rt, const void *key, size_t keylen, void *ptr)
{
	union radix_value v = { .ptr = ptr };
	return radix_tree_uniq_insert(rt, key, keylen, v);
}
/*----------------------------------------------------------------*/

#endif