all: updated FSF address in GPL text
[sip-router] / lib / cds / hash_table.h
1 /* 
2  * Copyright (C) 2005 iptelorg GmbH
3  *
4  * This file is part of ser, a free SIP server.
5  *
6  * ser 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  * For a license to use the ser software under conditions
12  * other than those described here, or to purchase support for this
13  * software, please contact iptel.org by e-mail at the following addresses:
14  *    info@iptel.org
15  *
16  * ser is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software
23  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
24  */
25
26 #ifndef __HASH_TABLE_H
27 #define __HASH_TABLE_H
28
29 typedef struct ht_statistic {
30         int find_cnt;
31         /** count of comparations during find operations */
32         int cmp_cnt;
33         /** count of finds which started in empty slot (-> no compares) */
34         int nocmp_cnt;
35         /** count of finds returning NULL */
36         int missed_cnt;
37 } ht_statistic_t;
38
39 typedef const void* ht_key_t;
40 typedef void* ht_data_t;
41
42 typedef unsigned int (*hash_func_t)(ht_key_t k);
43 typedef int (*key_cmp_func_t)(ht_key_t a, ht_key_t b);
44
45 typedef struct ht_element {
46         ht_key_t key;
47         ht_data_t data;
48         struct ht_element *next;
49 } ht_element_t;
50
51 typedef struct ht_cslot {
52         ht_element_t *first;
53         ht_element_t *last;
54         int cnt;
55 } ht_cslot_t;
56
57 typedef struct hash_table {
58         hash_func_t hash;
59         key_cmp_func_t cmp;
60         ht_cslot_t *cslots;
61         int size;
62
63         int find_cnt;
64         int cmp_cnt;
65         int nocmp_cnt;
66         int missed_cnt;
67 } hash_table_t;
68
69 int ht_init(hash_table_t *ht, hash_func_t hash_func, key_cmp_func_t cmp_keys, int size);
70 void ht_destroy(hash_table_t *ht);
71 int ht_add(hash_table_t *ht, ht_key_t key, ht_data_t data);
72 ht_data_t ht_remove(hash_table_t *ht, ht_key_t key);
73 ht_data_t ht_find(hash_table_t *ht, ht_key_t key);
74 void ht_get_statistic(hash_table_t *ht, ht_statistic_t *s);
75 void ht_clear_statistic(hash_table_t *ht);
76
77 /* traversing through whole hash table */
78 typedef struct {
79         hash_table_t *ht;
80         int slot_pos;
81         ht_element_t *current;
82 } ht_traversal_info_t;
83
84 ht_element_t *get_first_ht_element(hash_table_t *ht, ht_traversal_info_t *info);
85 ht_element_t *get_next_ht_element(ht_traversal_info_t *info);
86
87 /* hash functions */
88 unsigned int rshash(const char* str, unsigned int len);
89
90 #endif