datapath/table.h

   1 /*
   2  * Copyright (c) 2010 Nicira Networks.
   3  * Distributed under the terms of the GNU GPL version 2.
   4  *
   5  * Significant portions of this file may be copied from parts of the Linux
   6  * kernel, by Linus Torvalds and others.
   7  */
   8
   9 #ifndef TABLE_H
  10 #define TABLE_H 1
  11
  12 struct tbl_bucket;
  13
  14 struct tbl_node {
  15         u32 hash;
  16 };
  17
  18 /**
  19  * struct tbl - hash table
  20  * @n_buckets: number of buckets (a power of 2 between %TBL_L1_SIZE and
  21  * %TBL_MAX_BUCKETS)
  22  * @buckets: pointer to @n_buckets/%TBL_L1_SIZE pointers to %TBL_L1_SIZE pointers
  23  * to buckets
  24  * @rcu: RCU callback structure
  25  * @obj_destructor: Called on each element when the table is destroyed.
  26  *
  27  * The @buckets array is logically an array of pointers to buckets.  It is
  28  * broken into two levels to avoid the need to kmalloc() any object larger than
  29  * a single page or to use vmalloc().  @buckets is always nonnull, as is each
  30  * @buckets[i], but each @buckets[i][j] is nonnull only if the specified hash
  31  * bucket is nonempty (for 0 <= i < @n_buckets/%TBL_L1_SIZE, 0 <= j <
  32  * %TBL_L1_SIZE).
  33  */
  34 struct tbl {
  35         struct rcu_head rcu;
  36         unsigned int n_buckets;
  37         struct tbl_bucket __rcu ***buckets;
  38         unsigned int count;
  39         void (*obj_destructor)(struct tbl_node *);
  40 };
  41
  42 #define TBL_L2_BITS (PAGE_SHIFT - ilog2(sizeof(struct tbl_bucket *)))
  43 #define TBL_L2_SIZE (1 << TBL_L2_BITS)
  44 #define TBL_L2_SHIFT 0
  45
  46 #define TBL_L1_BITS (PAGE_SHIFT - ilog2(sizeof(struct tbl_bucket **)))
  47 #define TBL_L1_SIZE (1 << TBL_L1_BITS)
  48 #define TBL_L1_SHIFT TBL_L2_BITS
  49
  50 /* For 4 kB pages, this is 1,024 on 32-bit or 512 on 64-bit.  */
  51 #define TBL_MIN_BUCKETS TBL_L2_SIZE
  52
  53 /* For 4 kB pages, this is 1,048,576 on 32-bit or 262,144 on 64-bit. */
  54 #define TBL_MAX_BUCKETS (TBL_L1_SIZE * TBL_L2_SIZE)
  55
  56 struct tbl *tbl_create(unsigned int n_buckets);
  57 void tbl_destroy(struct tbl *, void (*destructor)(struct tbl_node *));
  58 struct tbl_node *tbl_lookup(struct tbl *, void *target, u32 hash,
  59                             int (*cmp)(const struct tbl_node *, void *target));
  60 int tbl_insert(struct tbl *, struct tbl_node *, u32 hash);
  61 int tbl_remove(struct tbl *, struct tbl_node *);
  62 unsigned int tbl_count(struct tbl *);
  63 int tbl_foreach(struct tbl *,
  64                 int (*callback)(struct tbl_node *, void *aux), void *aux);
  65 struct tbl_node *tbl_next(struct tbl *, u32 *bucketp, u32 *objp);
  66
  67 int tbl_n_buckets(struct tbl *);
  68 struct tbl *tbl_expand(struct tbl *);
  69 void tbl_deferred_destroy(struct tbl *, void (*destructor)(struct tbl_node *));
  70
  71 #endif /* table.h */