1*b4d0d230SThomas Gleixner /* SPDX-License-Identifier: GPL-2.0-or-later */
23cb98950SDavid Howells /* Generic associative array implementation.
33cb98950SDavid Howells *
45fb94e9cSMauro Carvalho Chehab * See Documentation/core-api/assoc_array.rst for information.
53cb98950SDavid Howells *
63cb98950SDavid Howells * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
73cb98950SDavid Howells * Written by David Howells (dhowells@redhat.com)
83cb98950SDavid Howells */
93cb98950SDavid Howells
103cb98950SDavid Howells #ifndef _LINUX_ASSOC_ARRAY_H
113cb98950SDavid Howells #define _LINUX_ASSOC_ARRAY_H
123cb98950SDavid Howells
133cb98950SDavid Howells #ifdef CONFIG_ASSOCIATIVE_ARRAY
143cb98950SDavid Howells
153cb98950SDavid Howells #include <linux/types.h>
163cb98950SDavid Howells
173cb98950SDavid Howells #define ASSOC_ARRAY_KEY_CHUNK_SIZE BITS_PER_LONG /* Key data retrieved in chunks of this size */
183cb98950SDavid Howells
193cb98950SDavid Howells /*
203cb98950SDavid Howells * Generic associative array.
213cb98950SDavid Howells */
223cb98950SDavid Howells struct assoc_array {
233cb98950SDavid Howells struct assoc_array_ptr *root; /* The node at the root of the tree */
243cb98950SDavid Howells unsigned long nr_leaves_on_tree;
253cb98950SDavid Howells };
263cb98950SDavid Howells
273cb98950SDavid Howells /*
283cb98950SDavid Howells * Operations on objects and index keys for use by array manipulation routines.
293cb98950SDavid Howells */
303cb98950SDavid Howells struct assoc_array_ops {
313cb98950SDavid Howells /* Method to get a chunk of an index key from caller-supplied data */
323cb98950SDavid Howells unsigned long (*get_key_chunk)(const void *index_key, int level);
333cb98950SDavid Howells
343cb98950SDavid Howells /* Method to get a piece of an object's index key */
353cb98950SDavid Howells unsigned long (*get_object_key_chunk)(const void *object, int level);
363cb98950SDavid Howells
373cb98950SDavid Howells /* Is this the object we're looking for? */
383cb98950SDavid Howells bool (*compare_object)(const void *object, const void *index_key);
393cb98950SDavid Howells
4023fd78d7SDavid Howells /* How different is an object from an index key, to a bit position in
4123fd78d7SDavid Howells * their keys? (or -1 if they're the same)
423cb98950SDavid Howells */
4323fd78d7SDavid Howells int (*diff_objects)(const void *object, const void *index_key);
443cb98950SDavid Howells
453cb98950SDavid Howells /* Method to free an object. */
463cb98950SDavid Howells void (*free_object)(void *object);
473cb98950SDavid Howells };
483cb98950SDavid Howells
493cb98950SDavid Howells /*
503cb98950SDavid Howells * Access and manipulation functions.
513cb98950SDavid Howells */
523cb98950SDavid Howells struct assoc_array_edit;
533cb98950SDavid Howells
assoc_array_init(struct assoc_array * array)543cb98950SDavid Howells static inline void assoc_array_init(struct assoc_array *array)
553cb98950SDavid Howells {
563cb98950SDavid Howells array->root = NULL;
573cb98950SDavid Howells array->nr_leaves_on_tree = 0;
583cb98950SDavid Howells }
593cb98950SDavid Howells
603cb98950SDavid Howells extern int assoc_array_iterate(const struct assoc_array *array,
613cb98950SDavid Howells int (*iterator)(const void *object,
623cb98950SDavid Howells void *iterator_data),
633cb98950SDavid Howells void *iterator_data);
643cb98950SDavid Howells extern void *assoc_array_find(const struct assoc_array *array,
653cb98950SDavid Howells const struct assoc_array_ops *ops,
663cb98950SDavid Howells const void *index_key);
673cb98950SDavid Howells extern void assoc_array_destroy(struct assoc_array *array,
683cb98950SDavid Howells const struct assoc_array_ops *ops);
693cb98950SDavid Howells extern struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
703cb98950SDavid Howells const struct assoc_array_ops *ops,
713cb98950SDavid Howells const void *index_key,
723cb98950SDavid Howells void *object);
733cb98950SDavid Howells extern void assoc_array_insert_set_object(struct assoc_array_edit *edit,
743cb98950SDavid Howells void *object);
753cb98950SDavid Howells extern struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
763cb98950SDavid Howells const struct assoc_array_ops *ops,
773cb98950SDavid Howells const void *index_key);
783cb98950SDavid Howells extern struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
793cb98950SDavid Howells const struct assoc_array_ops *ops);
803cb98950SDavid Howells extern void assoc_array_apply_edit(struct assoc_array_edit *edit);
813cb98950SDavid Howells extern void assoc_array_cancel_edit(struct assoc_array_edit *edit);
823cb98950SDavid Howells extern int assoc_array_gc(struct assoc_array *array,
833cb98950SDavid Howells const struct assoc_array_ops *ops,
843cb98950SDavid Howells bool (*iterator)(void *object, void *iterator_data),
853cb98950SDavid Howells void *iterator_data);
863cb98950SDavid Howells
873cb98950SDavid Howells #endif /* CONFIG_ASSOCIATIVE_ARRAY */
883cb98950SDavid Howells #endif /* _LINUX_ASSOC_ARRAY_H */
89