include/linux/assoc_array.h

0001 /* SPDX-License-Identifier: GPL-2.0-or-later */
0002 /* Generic associative array implementation.
0003  *
0004  * See Documentation/core-api/assoc_array.rst for information.
0005  *
0006  * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved.
0007  * Written by David Howells (dhowells@redhat.com)
0008  */
0009
0010 #ifndef _LINUX_ASSOC_ARRAY_H
0011 #define _LINUX_ASSOC_ARRAY_H
0012
0013 #ifdef CONFIG_ASSOCIATIVE_ARRAY
0014
0015 #include <linux/types.h>
0016
0017 #define ASSOC_ARRAY_KEY_CHUNK_SIZE BITS_PER_LONG /* Key data retrieved in chunks of this size */
0018
0019 /*
0020  * Generic associative array.
0021  */
0022 struct assoc_array {
0023     struct assoc_array_ptr  *root;      /* The node at the root of the tree */
0024     unsigned long       nr_leaves_on_tree;
0025 };
0026
0027 /*
0028  * Operations on objects and index keys for use by array manipulation routines.
0029  */
0030 struct assoc_array_ops {
0031     /* Method to get a chunk of an index key from caller-supplied data */
0032     unsigned long (*get_key_chunk)(const void *index_key, int level);
0033
0034     /* Method to get a piece of an object's index key */
0035     unsigned long (*get_object_key_chunk)(const void *object, int level);
0036
0037     /* Is this the object we're looking for? */
0038     bool (*compare_object)(const void *object, const void *index_key);
0039
0040     /* How different is an object from an index key, to a bit position in
0041      * their keys? (or -1 if they're the same)
0042      */
0043     int (*diff_objects)(const void *object, const void *index_key);
0044
0045     /* Method to free an object. */
0046     void (*free_object)(void *object);
0047 };
0048
0049 /*
0050  * Access and manipulation functions.
0051  */
0052 struct assoc_array_edit;
0053
0054 static inline void assoc_array_init(struct assoc_array *array)
0055 {
0056     array->root = NULL;
0057     array->nr_leaves_on_tree = 0;
0058 }
0059
0060 extern int assoc_array_iterate(const struct assoc_array *array,
0061                    int (*iterator)(const void *object,
0062                            void *iterator_data),
0063                    void *iterator_data);
0064 extern void *assoc_array_find(const struct assoc_array *array,
0065                   const struct assoc_array_ops *ops,
0066                   const void *index_key);
0067 extern void assoc_array_destroy(struct assoc_array *array,
0068                 const struct assoc_array_ops *ops);
0069 extern struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
0070                            const struct assoc_array_ops *ops,
0071                            const void *index_key,
0072                            void *object);
0073 extern void assoc_array_insert_set_object(struct assoc_array_edit *edit,
0074                       void *object);
0075 extern struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
0076                            const struct assoc_array_ops *ops,
0077                            const void *index_key);
0078 extern struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
0079                           const struct assoc_array_ops *ops);
0080 extern void assoc_array_apply_edit(struct assoc_array_edit *edit);
0081 extern void assoc_array_cancel_edit(struct assoc_array_edit *edit);
0082 extern int assoc_array_gc(struct assoc_array *array,
0083               const struct assoc_array_ops *ops,
0084               bool (*iterator)(void *object, void *iterator_data),
0085               void *iterator_data);
0086
0087 #endif /* CONFIG_ASSOCIATIVE_ARRAY */
0088 #endif /* _LINUX_ASSOC_ARRAY_H */