source/include/hash.h

   1 /*
   2    Unix SMB/CIFS implementation.
   3
   4    Copyright (C) Ying Chen 2000.
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software
  18    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19 */
  20
  21 #ifndef _HASH_H_
  22 #define _HASH_H_
  23
  24 #define MAX_HASH_TABLE_SIZE    16384
  25 #define HASH_TABLE_INCREMENT  2
  26
  27 typedef int (*compare_function)(char *, char *);
  28 typedef int (*hash_function)(int, char *);
  29
  30 /*
  31  * lru_link: links the node to the LRU list.
  32  * hash_elem: the pointer to the element that is tied onto the link.
  33  */
  34 typedef struct lru_node {
  35         ubi_dlNode lru_link;
  36         void *hash_elem;
  37 } lru_node;
  38
  39 /*
  40  * bucket_link: link the hash element to the bucket chain that it belongs to.
  41  * lru_link: this element ties the hash element to the lru list.
  42  * bucket: a pointer to the hash bucket that this element belongs to.
  43  * value: a pointer to the hash element content. It can be anything.
  44  * key: stores the string key. The hash_element is always allocated with
  45  * more memory space than the structure shown below to accomodate the space
  46  * used for the whole string. But the memory is always appended at the
  47  * end of the structure, so keep "key" at the end of the structure.
  48  * Don't move it.
  49  */
  50 typedef struct hash_element {
  51         ubi_dlNode      bucket_link;
  52         lru_node    lru_link;
  53         ubi_dlList      *bucket;
  54         void    *value;
  55         char key[1];
  56 } hash_element;
  57
  58 /*
  59  * buckets: a list of buckets, implemented as a dLinkList.
  60  * lru_chain: the lru list of all the hash elements.
  61  * num_elements: the # of elements in the hash table.
  62  * size: the hash table size.
  63  * comp_func: the compare function used during hash key comparisons.
  64  */
  65
  66 typedef struct hash_table {
  67         ubi_dlList      *buckets;
  68         ubi_dlList      lru_chain;
  69         int     num_elements;
  70         int     size;
  71         compare_function        comp_func;
  72 } hash_table;
  73
  74 #endif /* _HASH_H_ */