Branch data Line data Source code
1 : : /* SPDX-License-Identifier: GPL-2.0-or-later */ 2 : : /* Generic associative array implementation. 3 : : * 4 : : * See Documentation/core-api/assoc_array.rst for information. 5 : : * 6 : : * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved. 7 : : * Written by David Howells (dhowells@redhat.com) 8 : : */ 9 : : 10 : : #ifndef _LINUX_ASSOC_ARRAY_H 11 : : #define _LINUX_ASSOC_ARRAY_H 12 : : 13 : : #ifdef CONFIG_ASSOCIATIVE_ARRAY 14 : : 15 : : #include <linux/types.h> 16 : : 17 : : #define ASSOC_ARRAY_KEY_CHUNK_SIZE BITS_PER_LONG /* Key data retrieved in chunks of this size */ 18 : : 19 : : /* 20 : : * Generic associative array. 21 : : */ 22 : : struct assoc_array { 23 : : struct assoc_array_ptr *root; /* The node at the root of the tree */ 24 : : unsigned long nr_leaves_on_tree; 25 : : }; 26 : : 27 : : /* 28 : : * Operations on objects and index keys for use by array manipulation routines. 29 : : */ 30 : : struct assoc_array_ops { 31 : : /* Method to get a chunk of an index key from caller-supplied data */ 32 : : unsigned long (*get_key_chunk)(const void *index_key, int level); 33 : : 34 : : /* Method to get a piece of an object's index key */ 35 : : unsigned long (*get_object_key_chunk)(const void *object, int level); 36 : : 37 : : /* Is this the object we're looking for? */ 38 : : bool (*compare_object)(const void *object, const void *index_key); 39 : : 40 : : /* How different is an object from an index key, to a bit position in 41 : : * their keys? (or -1 if they're the same) 42 : : */ 43 : : int (*diff_objects)(const void *object, const void *index_key); 44 : : 45 : : /* Method to free an object. */ 46 : : void (*free_object)(void *object); 47 : : }; 48 : : 49 : : /* 50 : : * Access and manipulation functions. 51 : : */ 52 : : struct assoc_array_edit; 53 : : 54 : 105 : static inline void assoc_array_init(struct assoc_array *array) 55 : : { 56 : 105 : array->root = NULL; 57 : 105 : array->nr_leaves_on_tree = 0; 58 : : } 59 : : 60 : : extern int assoc_array_iterate(const struct assoc_array *array, 61 : : int (*iterator)(const void *object, 62 : : void *iterator_data), 63 : : void *iterator_data); 64 : : extern void *assoc_array_find(const struct assoc_array *array, 65 : : const struct assoc_array_ops *ops, 66 : : const void *index_key); 67 : : extern void assoc_array_destroy(struct assoc_array *array, 68 : : const struct assoc_array_ops *ops); 69 : : extern struct assoc_array_edit *assoc_array_insert(struct assoc_array *array, 70 : : const struct assoc_array_ops *ops, 71 : : const void *index_key, 72 : : void *object); 73 : : extern void assoc_array_insert_set_object(struct assoc_array_edit *edit, 74 : : void *object); 75 : : extern struct assoc_array_edit *assoc_array_delete(struct assoc_array *array, 76 : : const struct assoc_array_ops *ops, 77 : : const void *index_key); 78 : : extern struct assoc_array_edit *assoc_array_clear(struct assoc_array *array, 79 : : const struct assoc_array_ops *ops); 80 : : extern void assoc_array_apply_edit(struct assoc_array_edit *edit); 81 : : extern void assoc_array_cancel_edit(struct assoc_array_edit *edit); 82 : : extern int assoc_array_gc(struct assoc_array *array, 83 : : const struct assoc_array_ops *ops, 84 : : bool (*iterator)(void *object, void *iterator_data), 85 : : void *iterator_data); 86 : : 87 : : #endif /* CONFIG_ASSOCIATIVE_ARRAY */ 88 : : #endif /* _LINUX_ASSOC_ARRAY_H */