LXR linux/include/linux/assoc

   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 */
  26struct 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 */
  34struct 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
  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)
  46         */
  47        int (*diff_objects)(const void *object, const void *index_key);
  48
  49        /* Method to free an object. */
  50        void (*free_object)(void *object);
  51};
  52
  53/*
  54 * Access and manipulation functions.
  55 */
  56struct assoc_array_edit;
  57
  58static inline void assoc_array_init(struct assoc_array *array)
  59{
  60        array->root = NULL;
  61        array->nr_leaves_on_tree = 0;
  62}
  63
  64extern int assoc_array_iterate(const struct assoc_array *array,
  65                               int (*iterator)(const void *object,
  66                                               void *iterator_data),
  67                               void *iterator_data);
  68extern void *assoc_array_find(const struct assoc_array *array,
  69                              const struct assoc_array_ops *ops,
  70                              const void *index_key);
  71extern void assoc_array_destroy(struct assoc_array *array,
  72                                const struct assoc_array_ops *ops);
  73extern 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);
  77extern void assoc_array_insert_set_object(struct assoc_array_edit *edit,
  78                                          void *object);
  79extern struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
  80                                                   const struct assoc_array_ops *ops,
  81                                                   const void *index_key);
  82extern struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
  83                                                  const struct assoc_array_ops *ops);
  84extern void assoc_array_apply_edit(struct assoc_array_edit *edit);
  85extern void assoc_array_cancel_edit(struct assoc_array_edit *edit);
  86extern 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 */
  93