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;
  13 struct tbl_bucket;
  14
  15 struct tbl_node {
  16         u32 hash;
  17 };
  18
  19 #define TBL_L2_BITS (PAGE_SHIFT - ilog2(sizeof(struct tbl_bucket *)))
  20 #define TBL_L2_SIZE (1 << TBL_L2_BITS)
  21 #define TBL_L2_SHIFT 0
  22
  23 #define TBL_L1_BITS (PAGE_SHIFT - ilog2(sizeof(struct tbl_bucket **)))
  24 #define TBL_L1_SIZE (1 << TBL_L1_BITS)
  25 #define TBL_L1_SHIFT TBL_L2_BITS
  26
  27 /* For 4 kB pages, this is 1,048,576 on 32-bit or 262,144 on 64-bit. */
  28 #define TBL_MAX_BUCKETS (TBL_L1_SIZE * TBL_L2_SIZE)
  29
  30 struct tbl *tbl_create(unsigned int n_buckets);
  31 void tbl_destroy(struct tbl *, void (*destructor)(struct tbl_node *));
  32 struct tbl_node *tbl_lookup(struct tbl *, void *target, u32 hash,
  33                             int (*cmp)(const struct tbl_node *, void *target));
  34 int tbl_insert(struct tbl *, struct tbl_node *, u32 hash);
  35 int tbl_remove(struct tbl *, struct tbl_node *);
  36 unsigned int tbl_count(struct tbl *);
  37 int tbl_foreach(struct tbl *,
  38                 int (*callback)(struct tbl_node *, void *aux), void *aux);
  39
  40 int tbl_n_buckets(struct tbl *);
  41 struct tbl *tbl_expand(struct tbl *);
  42 void tbl_deferred_destroy(struct tbl *, void (*destructor)(struct tbl_node *));
  43
  44 #endif /* table.h */