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