Commit | Line | Data |
---|---|---|
b4d0d230 | 1 | /* SPDX-License-Identifier: GPL-2.0-or-later */ |
3cb98950 DH |
2 | /* Generic associative array implementation. |
3 | * | |
5fb94e9c | 4 | * See Documentation/core-api/assoc_array.rst for information. |
3cb98950 DH |
5 | * |
6 | * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved. | |
7 | * Written by David Howells (dhowells@redhat.com) | |
3cb98950 DH |
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 | ||
23fd78d7 DH |
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) | |
3cb98950 | 42 | */ |
23fd78d7 | 43 | int (*diff_objects)(const void *object, const void *index_key); |
3cb98950 DH |
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 */ |