]>
Commit | Line | Data |
---|---|---|
718e3744 | 1 | /* Hash routine. |
896014f4 DL |
2 | * Copyright (C) 1998 Kunihiro Ishiguro |
3 | * | |
4 | * This file is part of GNU Zebra. | |
5 | * | |
6 | * GNU Zebra is free software; you can redistribute it and/or modify | |
7 | * it under the terms of the GNU General Public License as published | |
8 | * by the Free Software Foundation; either version 2, or (at your | |
9 | * option) any later version. | |
10 | * | |
11 | * GNU Zebra is distributed in the hope that it will be useful, but | |
12 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | * General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU General Public License along | |
17 | * with this program; see the file COPYING; if not, write to the Free Software | |
18 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
19 | */ | |
718e3744 | 20 | |
21 | #ifndef _ZEBRA_HASH_H | |
22 | #define _ZEBRA_HASH_H | |
23 | ||
4a1ab8e4 | 24 | #include "memory.h" |
6f6f0010 | 25 | #include "frratomic.h" |
4a1ab8e4 DL |
26 | |
27 | DECLARE_MTYPE(HASH) | |
28 | DECLARE_MTYPE(HASH_BACKET) | |
29 | ||
d62a17ae | 30 | /* Default hash table size. */ |
bed7ad83 QY |
31 | #define HASH_INITIAL_SIZE 256 |
32 | /* Expansion threshold */ | |
33 | #define HASH_THRESHOLD(used, size) ((used) > (size)) | |
718e3744 | 34 | |
3f9c7369 DS |
35 | #define HASHWALK_CONTINUE 0 |
36 | #define HASHWALK_ABORT -1 | |
37 | ||
d62a17ae | 38 | struct hash_backet { |
39 | /* if this backet is the head of the linked listed, len denotes the | |
40 | * number of | |
41 | * elements in the list */ | |
42 | int len; | |
6f6f0010 | 43 | |
d62a17ae | 44 | /* Linked list. */ |
45 | struct hash_backet *next; | |
718e3744 | 46 | |
d62a17ae | 47 | /* Hash key. */ |
48 | unsigned int key; | |
718e3744 | 49 | |
d62a17ae | 50 | /* Data. */ |
51 | void *data; | |
718e3744 | 52 | }; |
53 | ||
d62a17ae | 54 | struct hashstats { |
55 | /* number of empty hash buckets */ | |
56 | _Atomic uint_fast32_t empty; | |
57 | /* sum of squares of bucket length */ | |
58 | _Atomic uint_fast32_t ssq; | |
6f6f0010 QY |
59 | }; |
60 | ||
d62a17ae | 61 | struct hash { |
62 | /* Hash backet. */ | |
63 | struct hash_backet **index; | |
718e3744 | 64 | |
d62a17ae | 65 | /* Hash table size. Must be power of 2 */ |
66 | unsigned int size; | |
718e3744 | 67 | |
40520c36 DW |
68 | /* If max_size is 0 there is no limit */ |
69 | unsigned int max_size; | |
70 | ||
d62a17ae | 71 | /* Key make function. */ |
72 | unsigned int (*hash_key)(void *); | |
718e3744 | 73 | |
d62a17ae | 74 | /* Data compare function. */ |
75 | int (*hash_cmp)(const void *, const void *); | |
718e3744 | 76 | |
d62a17ae | 77 | /* Backet alloc. */ |
78 | unsigned long count; | |
4db0cff1 | 79 | |
d62a17ae | 80 | struct hashstats stats; |
6f6f0010 | 81 | |
d62a17ae | 82 | /* hash name */ |
83 | char *name; | |
718e3744 | 84 | }; |
85 | ||
8234a987 | 86 | #define hashcount(X) ((X)->count) |
87 | ||
d62a17ae | 88 | extern struct hash *hash_create(unsigned int (*)(void *), |
89 | int (*)(const void *, const void *), | |
90 | const char *); | |
91 | extern struct hash *hash_create_size(unsigned int, unsigned int (*)(void *), | |
92 | int (*)(const void *, const void *), | |
93 | const char *); | |
718e3744 | 94 | |
d62a17ae | 95 | extern void *hash_get(struct hash *, void *, void *(*)(void *)); |
96 | extern void *hash_alloc_intern(void *); | |
97 | extern void *hash_lookup(struct hash *, void *); | |
98 | extern void *hash_release(struct hash *, void *); | |
718e3744 | 99 | |
d62a17ae | 100 | extern void hash_iterate(struct hash *, void (*)(struct hash_backet *, void *), |
101 | void *); | |
718e3744 | 102 | |
d62a17ae | 103 | extern void hash_walk(struct hash *, int (*)(struct hash_backet *, void *), |
104 | void *); | |
3f9c7369 | 105 | |
d62a17ae | 106 | extern void hash_clean(struct hash *, void (*)(void *)); |
107 | extern void hash_free(struct hash *); | |
718e3744 | 108 | |
d62a17ae | 109 | extern unsigned int string_hash_make(const char *); |
6392aa83 | 110 | |
d62a17ae | 111 | extern void hash_cmd_init(void); |
4db0cff1 | 112 | |
718e3744 | 113 | #endif /* _ZEBRA_HASH_H */ |