13cb98950SDavid Howells /* Generic associative array implementation. 23cb98950SDavid Howells * 3*5fb94e9cSMauro Carvalho Chehab * See Documentation/core-api/assoc_array.rst for information. 43cb98950SDavid Howells * 53cb98950SDavid Howells * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved. 63cb98950SDavid Howells * Written by David Howells (dhowells@redhat.com) 73cb98950SDavid Howells * 83cb98950SDavid Howells * This program is free software; you can redistribute it and/or 93cb98950SDavid Howells * modify it under the terms of the GNU General Public Licence 103cb98950SDavid Howells * as published by the Free Software Foundation; either version 113cb98950SDavid Howells * 2 of the Licence, or (at your option) any later version. 123cb98950SDavid Howells */ 133cb98950SDavid Howells 143cb98950SDavid Howells #ifndef _LINUX_ASSOC_ARRAY_H 153cb98950SDavid Howells #define _LINUX_ASSOC_ARRAY_H 163cb98950SDavid Howells 173cb98950SDavid Howells #ifdef CONFIG_ASSOCIATIVE_ARRAY 183cb98950SDavid Howells 193cb98950SDavid Howells #include <linux/types.h> 203cb98950SDavid Howells 213cb98950SDavid Howells #define ASSOC_ARRAY_KEY_CHUNK_SIZE BITS_PER_LONG /* Key data retrieved in chunks of this size */ 223cb98950SDavid Howells 233cb98950SDavid Howells /* 243cb98950SDavid Howells * Generic associative array. 253cb98950SDavid Howells */ 263cb98950SDavid Howells struct assoc_array { 273cb98950SDavid Howells struct assoc_array_ptr *root; /* The node at the root of the tree */ 283cb98950SDavid Howells unsigned long nr_leaves_on_tree; 293cb98950SDavid Howells }; 303cb98950SDavid Howells 313cb98950SDavid Howells /* 323cb98950SDavid Howells * Operations on objects and index keys for use by array manipulation routines. 333cb98950SDavid Howells */ 343cb98950SDavid Howells struct assoc_array_ops { 353cb98950SDavid Howells /* Method to get a chunk of an index key from caller-supplied data */ 363cb98950SDavid Howells unsigned long (*get_key_chunk)(const void *index_key, int level); 373cb98950SDavid Howells 383cb98950SDavid Howells /* Method to get a piece of an object's index key */ 393cb98950SDavid Howells unsigned long (*get_object_key_chunk)(const void *object, int level); 403cb98950SDavid Howells 413cb98950SDavid Howells /* Is this the object we're looking for? */ 423cb98950SDavid Howells bool (*compare_object)(const void *object, const void *index_key); 433cb98950SDavid Howells 4423fd78d7SDavid Howells /* How different is an object from an index key, to a bit position in 4523fd78d7SDavid Howells * their keys? (or -1 if they're the same) 463cb98950SDavid Howells */ 4723fd78d7SDavid Howells int (*diff_objects)(const void *object, const void *index_key); 483cb98950SDavid Howells 493cb98950SDavid Howells /* Method to free an object. */ 503cb98950SDavid Howells void (*free_object)(void *object); 513cb98950SDavid Howells }; 523cb98950SDavid Howells 533cb98950SDavid Howells /* 543cb98950SDavid Howells * Access and manipulation functions. 553cb98950SDavid Howells */ 563cb98950SDavid Howells struct assoc_array_edit; 573cb98950SDavid Howells 583cb98950SDavid Howells static inline void assoc_array_init(struct assoc_array *array) 593cb98950SDavid Howells { 603cb98950SDavid Howells array->root = NULL; 613cb98950SDavid Howells array->nr_leaves_on_tree = 0; 623cb98950SDavid Howells } 633cb98950SDavid Howells 643cb98950SDavid Howells extern int assoc_array_iterate(const struct assoc_array *array, 653cb98950SDavid Howells int (*iterator)(const void *object, 663cb98950SDavid Howells void *iterator_data), 673cb98950SDavid Howells void *iterator_data); 683cb98950SDavid Howells extern void *assoc_array_find(const struct assoc_array *array, 693cb98950SDavid Howells const struct assoc_array_ops *ops, 703cb98950SDavid Howells const void *index_key); 713cb98950SDavid Howells extern void assoc_array_destroy(struct assoc_array *array, 723cb98950SDavid Howells const struct assoc_array_ops *ops); 733cb98950SDavid Howells extern struct assoc_array_edit *assoc_array_insert(struct assoc_array *array, 743cb98950SDavid Howells const struct assoc_array_ops *ops, 753cb98950SDavid Howells const void *index_key, 763cb98950SDavid Howells void *object); 773cb98950SDavid Howells extern void assoc_array_insert_set_object(struct assoc_array_edit *edit, 783cb98950SDavid Howells void *object); 793cb98950SDavid Howells extern struct assoc_array_edit *assoc_array_delete(struct assoc_array *array, 803cb98950SDavid Howells const struct assoc_array_ops *ops, 813cb98950SDavid Howells const void *index_key); 823cb98950SDavid Howells extern struct assoc_array_edit *assoc_array_clear(struct assoc_array *array, 833cb98950SDavid Howells const struct assoc_array_ops *ops); 843cb98950SDavid Howells extern void assoc_array_apply_edit(struct assoc_array_edit *edit); 853cb98950SDavid Howells extern void assoc_array_cancel_edit(struct assoc_array_edit *edit); 863cb98950SDavid Howells extern int assoc_array_gc(struct assoc_array *array, 873cb98950SDavid Howells const struct assoc_array_ops *ops, 883cb98950SDavid Howells bool (*iterator)(void *object, void *iterator_data), 893cb98950SDavid Howells void *iterator_data); 903cb98950SDavid Howells 913cb98950SDavid Howells #endif /* CONFIG_ASSOCIATIVE_ARRAY */ 923cb98950SDavid Howells #endif /* _LINUX_ASSOC_ARRAY_H */ 93