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 | static inline void assoc_array_init(struct assoc_array *array) |
55 | { |
56 | array->root = NULL; |
57 | 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 */ |
89 | |