git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/htable.h

   1 /*
   2  *   Version $Id$
   3  */
   4
   5 /*
   6    Copyright (C) 2000-2003 Kern Sibbald and John Walker
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2 of
  11    the License, or (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public
  19    License along with this program; if not, write to the Free
  20    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  21    MA 02111-1307, USA.
  22
  23  */
  24
  25 /* ========================================================================
  26  *
  27  *   Hash table class -- htable
  28  *
  29  */
  30
  31 /*
  32  * Loop var through each member of table
  33  */
  34 #define foreach_htable(var, tbl) \
  35         for(((void *)(var))=(tbl)->first(); \
  36             (var); \
  37             ((void *)(var))=(tbl)->next())
  38
  39 struct hlink {
  40    void *next;                        /* next hash item */
  41    char *key;                         /* key this item */
  42    uint32_t hash;                     /* hash for this key */
  43 };
  44
  45 class htable {
  46    hlink **table;                     /* hash table */
  47    int loffset;                       /* link offset in item */
  48    uint32_t num_items;                /* current number of items */
  49    uint32_t max_items;                /* maximum items before growing */
  50    uint32_t buckets;                  /* size of hash table */
  51    uint32_t hash;                     /* temp storage */
  52    uint32_t index;                    /* temp storage */
  53    uint32_t mask;                     /* "remainder" mask */
  54    uint32_t rshift;                   /* amount to shift down */
  55    hlink *walkptr;                    /* table walk pointer */
  56    uint32_t walk_index;               /* table walk index */
  57    void hash_index(char *key);        /* produce hash key,index */
  58    void grow_table();                 /* grow the table */
  59 public:
  60    htable(void *item, void *link, int tsize = 31);
  61    void init(void *item, void *link, int tsize = 31);
  62    bool  insert(char *key, void *item);
  63    void *lookup(char *key);
  64    void *first();                     /* get first item in table */
  65    void *next();                      /* get next item in table */
  66    void destroy();
  67    void stats();                      /* print stats about the table */
  68    uint32_t size();                   /* return size of table */
  69    void * operator new(size_t);
  70    void operator delete(void *);
  71 };