File: Dkhash.h

package info (click to toggle)
virtuoso-opensource 7.2.5.1%2Bdfsg1-0.3
  • links: PTS, VCS
  • area: main
  • in suites: bookworm
  • size: 285,240 kB
  • sloc: ansic: 641,220; sql: 490,413; xml: 269,570; java: 83,893; javascript: 79,900; cpp: 36,927; sh: 31,653; cs: 25,702; php: 12,690; yacc: 10,227; lex: 7,601; makefile: 7,129; jsp: 4,523; awk: 1,697; perl: 1,013; ruby: 1,003; python: 326
file content (187 lines) | stat: -rw-r--r-- 6,198 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
/*
 *  Dkhash.h
 *
 *  $Id$
 *
 *  Hash tables
 *
 *  This file is part of the OpenLink Software Virtuoso Open-Source (VOS)
 *  project.
 *
 *  Copyright (C) 1998-2018 OpenLink Software
 *
 *  This project is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU General Public License as published by the
 *  Free Software Foundation; only version 2 of the License, dated June 1991.
 *
 *  This program is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 *
 */

#ifndef _DKHASH_H
#define _DKHASH_H

/*
 * structs hash_elt and dk_hash
 *
 * Implements a trivial hash table that will associate
 * a number with a void * and efficiently retrieve the
 * item given the number
 */


#ifdef MALLOC_DEBUG
#define dbg_ht_alloc(ht,sz) dbg_dk_alloc (file, line, sz)
#else
#define ht_alloc(ht,sz) dk_alloc (sz)
#endif

typedef void (*maphash_func) (const void *k, void *data);
typedef void (*maphash3_func) (const void *k, void *data, void *env);

typedef struct hash_elt_s hash_elt_t;

struct hash_elt_s
{
  const void *	key;
  void *	data;
  hash_elt_t *	next;
};

typedef struct
{
  hash_elt_t *	ht_elements;
  uint32 	ht_count;
  uint32 	ht_actual_size;
  short		ht_tlsf_id;
  unsigned char 	ht_rehash_threshold;
  void *	ht_mp;
#ifdef MTX_DEBUG
  dk_mutex_t *	ht_required_mtx;
#endif
#ifdef HT_STATS
  uint32 	ht_max_colls;
  uint32 	ht_stats[30];
  uint32 	ht_ngets;
  uint32 	ht_nsets;
#endif
} dk_hash_t;

#ifdef MTX_DEBUG
#define HT_REQUIRE_MTX(h, m) (h)->ht_required_mtx = m
#define HT_NO_REQUIRE_MTX(ht) (ht)->ht_required_mtx = NULL
#else
#define HT_REQUIRE_MTX(h, m)
#define HT_NO_REQUIRE_MTX(ht)
#endif

typedef struct
{
  dk_hash_t *	hit_ht;
  hash_elt_t *	hit_elt;
  uint32 	hit_inx;
} dk_hash_iterator_t;


#define HASH_EMPTY		((hash_elt_t *) -1L)
#define HASH_INX(ht,key)	(uint32)((uptrlong)key % ht->ht_actual_size)



#define GETHASH(key_value, ht, result, not_found) \
  { \
    uint32 inx = HASH_INX (ht, (key_value)); \
    hash_elt_t *elt = &ht->ht_elements[inx]; \
    hash_elt_t *next = elt->next; \
    if (next == HASH_EMPTY)\
      goto not_found;\
    if (elt->key == (key_value))	  \
      *(void**)&result = elt->data; \
    else \
      { \
	elt = next; \
	if (!elt) \
	  goto not_found; \
	for (;;) \
	  { \
	    if (elt->key == (key_value))		\
	      { \
		*(void**) &result = elt->data; \
		break; \
	      } \
	    elt = elt->next; \
	    if (!elt) \
	      goto not_found; \
	  } \
      } \
  }


#define DO_HT(kt, k, dt, d, ht) \
  { \
    dk_hash_iterator_t hit; \
    kt k; dt d; \
    dk_hash_iterator (&hit, ht); \
    while (dk_hit_next (&hit, (void**)&k, (void**)&d)) { \



#define END_DO_HT }}


/* Dkhash.c */
#define ht_max_sz 1971049	/*!< The biggest value \c hash_nextprime() may return */
#define id_ht_max_sz 1045111	/*!< The biggest value valid for number of buckets of id_hash_t */
extern uint32 hash_nextprime (uint32 n);

EXE_EXPORT (dk_hash_t *,hash_table_allocate, (uint32 size));
EXE_EXPORT (void, hash_table_init, (dk_hash_t * ht, int size));
EXE_EXPORT (void, hash_table_free, (dk_hash_t * table));
EXE_EXPORT (void *,sethash, (const void *key, dk_hash_t * ht, void *data));
EXE_EXPORT (int, remhash, (const void *key, dk_hash_t * ht));
EXE_EXPORT (void, clrhash, (dk_hash_t * table));
EXE_EXPORT (void, dk_rehash, (dk_hash_t * ht, uint32 new_sz));

#ifdef MALLOC_DEBUG
extern dk_hash_t *dbg_hash_table_allocate (const char *file, int line, uint32 size);
extern void dbg_hash_table_init (const char *file, int line, dk_hash_t * ht, int size);
extern void dbg_hash_table_free (const char *file, int line, dk_hash_t * table);
extern void *dbg_sethash (const char *file, int line, const void *key, dk_hash_t * ht, void *data);
extern int dbg_remhash (const char *file, int line, const void *key, dk_hash_t * ht);
extern void dbg_clrhash (const char *file, int line, dk_hash_t * table);
extern void dbg_dk_rehash (const char *file, int line, dk_hash_t * ht, uint32 new_sz);
#define hash_table_allocate(SIZE)	dbg_hash_table_allocate (__FILE__, __LINE__, (SIZE))
#define hash_table_init(TABLE,SIZE)	dbg_hash_table_init (__FILE__, __LINE__, (TABLE), (SIZE))
#define hash_table_free(TABLE)		dbg_hash_table_free (__FILE__, __LINE__, (TABLE))
#define sethash(KEY,HT,DATA)		dbg_sethash (__FILE__, __LINE__, (KEY), (HT), (DATA))
#define remhash(KEY,HT)			dbg_remhash (__FILE__, __LINE__, (KEY), (HT))
#define clrhash(TABLE)			dbg_clrhash (__FILE__, __LINE__, (TABLE))
#define dk_rehash(HT,NEW_SZ)		dbg_dk_rehash (__FILE__, __LINE__, (HT), (NEW_SZ))
#endif
EXE_EXPORT (void, hash_table_destroy, (dk_hash_t * ht));

EXE_EXPORT (void *, gethash, (const void *key, dk_hash_t * ht));
EXE_EXPORT (void, maphash, (maphash_func func, dk_hash_t * table));
EXE_EXPORT (void, maphash3, (maphash3_func func, dk_hash_t * table, void *env));
EXE_EXPORT (void **, hash_list_keys, (dk_hash_t * table));
EXE_EXPORT (void, maphash_no_remhash, (maphash_func func, dk_hash_t * table));
EXE_EXPORT (void, dk_hash_iterator, (dk_hash_iterator_t * hit, dk_hash_t * ht));
EXE_EXPORT (int, dk_hit_next, (dk_hash_iterator_t * hit, void **key, void **data));
EXE_EXPORT (void, dk_hash_set_rehash, (dk_hash_t * ht, uint32 ov_per_bucket));

typedef int32 (*box_hash_func_t) (caddr_t);
typedef int (*box_hash_cmp_func_t) (ccaddr_t, ccaddr_t);
void dk_dtp_register_hash (dtp_t dtp, box_hash_func_t hf, box_hash_cmp_func_t cmp, box_hash_cmp_func_t strong_cmp);
void mp_map_count_print (char * buf, size_t max);
#ifdef DK_ALLOC_BOX_DEBUG						   /* These definitions are here because they need dk_hash_t, otherwise they would be placed into Dkbox.h */
extern void dk_check_tree_iter (box_t box, box_t parent, dk_hash_t ** known_ptr);
extern void dk_check_domain_of_connectivity_iter (box_t box, box_t parent, dk_hash_t ** known_ptr);
#endif
#endif /* _DKHASH_H */