1/* ----------------------------------------------------------------------- *
2 *
3 * Copyright 1996-2017 The NASM Authors - All Rights Reserved
4 * See the file AUTHORS included with the NASM distribution for
5 * the specific copyright holders.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following
9 * conditions are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
19 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
20 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
21 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
26 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
29 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
30 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 *
32 * ----------------------------------------------------------------------- */
33
34/*
35 * hashtbl.h
36 *
37 * Efficient dictionary hash table class.
38 */
39
40#ifndef NASM_HASHTBL_H
41#define NASM_HASHTBL_H
42
43#include <stddef.h>
44#include "nasmlib.h"
45
46struct hash_tbl_node {
47 uint64_t hash;
48 const char *key;
49 void *data;
50};
51
52struct hash_table {
53 struct hash_tbl_node *table;
54 size_t load;
55 size_t size;
56 size_t max_load;
57};
58
59struct hash_insert {
60 uint64_t hash;
61 struct hash_table *head;
62 struct hash_tbl_node *where;
63};
64
65uint64_t crc64(uint64_t crc, const char *string);
66uint64_t crc64i(uint64_t crc, const char *string);
67#define CRC64_INIT UINT64_C(0xffffffffffffffff)
68
69/* Some reasonable initial sizes... */
70#define HASH_SMALL 4
71#define HASH_MEDIUM 16
72#define HASH_LARGE 256
73
74void hash_init(struct hash_table *head, size_t size);
75void **hash_find(struct hash_table *head, const char *string,
76 struct hash_insert *insert);
77void **hash_findi(struct hash_table *head, const char *string,
78 struct hash_insert *insert);
79void **hash_add(struct hash_insert *insert, const char *string, void *data);
80void *hash_iterate(const struct hash_table *head,
81 struct hash_tbl_node **iterator,
82 const char **key);
83void hash_free(struct hash_table *head);
84void hash_free_all(struct hash_table *head, bool free_keys);
85
86#endif /* NASM_HASHTBL_H */
87