1 /*
2 * Copyright (c) 2012 Tim Ruehsen
3 * Copyright (c) 2015-2021 Free Software Foundation, Inc.
4 *
5 * This file is part of libwget.
6 *
7 * Libwget is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU Lesser General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * Libwget is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with libwget. If not, see <https://www.gnu.org/licenses/>.
19 *
20 *
21 * stringmap routines
22 *
23 * Changelog
24 * 08.11.2012 Tim Ruehsen created
25 *
26 */
27
28 #include <config.h>
29
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <string.h>
33 #include <stdarg.h>
34 #include <ctype.h>
35
36 #include <wget.h>
37 #include "private.h"
38
39 static wget_hashmap_hash_fn hash_string, hash_string_nocase;
40
41 // Paul Larson's hash function from Microsoft Research
42 #ifdef __clang__
43 __attribute__((no_sanitize("integer")))
44 #endif
45 WGET_GCC_PURE
hash_string(const void * key)46 static unsigned int hash_string(const void *key)
47 {
48 const char *k = key;
49 unsigned int hash = 0; // use 0 as SALT if hash table attacks doesn't matter
50
51 while (*k)
52 hash = hash * 101 + (unsigned char)*k++;
53
54 return hash;
55 }
56
57 #ifdef __clang__
58 __attribute__((no_sanitize("integer")))
59 #endif
60 WGET_GCC_PURE
hash_string_nocase(const void * key)61 static unsigned int hash_string_nocase(const void *key)
62 {
63 const char *k = key;
64 unsigned int hash = 0; // use 0 as SALT if hash table attacks doesn't matter
65
66 while (*k)
67 hash = hash * 101 + (unsigned char)tolower(*k++);
68
69 return hash;
70 }
71
72 /**
73 * \file
74 * \brief Stringmap functions
75 * \defgroup libwget-stringmap Stringmap functions
76 * @{
77 *
78 * Stringmaps are key/value stores that perform at O(1) for insertion, searching and removing.
79 * The key is a C string.
80 *
81 * These functions are a wrapper around the Hashmap API.
82 */
83
84 /**
85 * \param[in] max Initial number of pre-allocated entries
86 * \return New stringmap instance
87 *
88 * Create a new stringmap instance with initial size \p max.
89 * It should be free'd after use with wget_stringmap_free().
90 *
91 * The hash function is an efficient string hash algorithm originally researched by Paul Larson.
92 *
93 * The compare function is strcmp(). The key strings are compared case-sensitive.
94 */
wget_stringmap_create(int max)95 wget_stringmap *wget_stringmap_create(int max)
96 {
97 return wget_hashmap_create(max, hash_string, (wget_hashmap_compare_fn *) wget_strcmp);
98 }
99
100 /**
101 * \param[in] max Initial number of pre-allocated entries
102 * \return New stringmap instance
103 *
104 * Create a new stringmap instance with initial size \p max.
105 * It should be free'd after use with wget_stringmap_free().
106 *
107 * The hash function is an efficient string hash algorithm originally researched by Paul Larson, using
108 * lowercase'd keys.
109 *
110 * The compare function is strcasecmp() (case-insensitive).
111 */
wget_stringmap_create_nocase(int max)112 wget_stringmap *wget_stringmap_create_nocase(int max)
113 {
114 return wget_hashmap_create(max, hash_string_nocase, (wget_hashmap_compare_fn *) wget_strcasecmp);
115 }
116
117 /**@}*/
118