Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/hashmap.h @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
27 #ifndef LEPTONICA_HASHMAP_H
28 #define LEPTONICA_HASHMAP_H
29
30 /*
31 * \file hashmap.h
32 *
33 * <pre>
34 * Contains the following structs:
35 * struct L_Hashmap
36 * struct L_Hashitem
37 *
38 * Goal:
39 * You have a set of objects (integers, strings, pts, whatever),
40 * and you want to store them in a data structure (L_Hashmap) that allows
41 * O(1) to find, insert and count the occurrences of such an object.
42 * The tool is a hash map. This is not ordered, unlike the O(log n)
43 * ordered map (L_Amap), which is implemented by an rbtree.
44 *
45 * In slightly more detail:
46 * Store the set of objects in an array, which in general can be
47 * held in a pointer array (L_Ptra). You need a hash function that
48 * will generate a unique uint64 key from each object. For our simple
49 * built-in arrays, such as float, double and Pta (points), these hash
50 * functions are in utils1.c. Then for each object in the array,
51 * you store the key and the index to the array of objects (the val)
52 * in a list of hashitems in the hash table, where the specific
53 * list is determined by the key (specifically, the mod of the key
54 * with the size of the hashtable).
55 *
56 * In yet more detail:
57 * (1) The design loosely follows the design of a hashmap in "The Practice
58 * of Programming by Brian Kernighan and Rob Pike, Addison Wesley, 1999.
59 * (2) The L_Hashmap contains a hashtable with a prime number of pointers
60 * to lists of hashitems. The lookup function takes a key and a value,
61 * which are both 64-bit unsigned integers. The key has been generated
62 * by hashing the input object in a way that avoids collisions between
63 * different objects. The value is an integer that identifies the
64 * object; typically it is the index into an array of objects.
65 * The hashtable size is a prime number, and an index into the table
66 * is made from the key by taking its mod with the hashtable size.
67 * The index points to a list of hashitems, which have all been hashed
68 * by the mod function into the same index in the table.
69 * Because the key is expected to be randomly distributed in uint64,
70 * the table indices should be uniformly distributed, resulting in
71 * approximately the same number of items being placed in each of
72 * these lists. The list of hashitems is traversed, comparing the
73 * input uint64 key in the lookup() function with the key stored in
74 * each hashitem. If a hashitem is found with a matching key,
75 * return a pointer to that hashitem. If not found and the op is
76 * L_HASH_CREATE, make a new hash item, add it to the list, and
77 * return a pointer to it.
78 * (3) The count field in the hashitem gives the number of times the
79 * key has been seen when storing key/value pairs.
80 * (4) The val field is the index into an array of the objects. When
81 * the hashmap is initially made, it is the index of the first item
82 * seen with its key.
83 * (5) For the hashmap to work efficiently, the lists must not become too
84 * long. Because in general you do not know the number of objects
85 * in advance, it is important to be able to dynamically resize
86 * the hashtable as it grows. The hashmap is initialized with
87 * room for some number of hashitems and the maximum average list
88 * size. These two numbers determine the size of the hashtable,
89 * which is constrained to be a prime number. As the hashtable grows,
90 * if the average occupancy exceeds the input %maxocc, the hashtable
91 * size is approximately doubled and the existing items are re-hashed
92 * into it, mod the new (prime number) table size.
93 * </pre>
94 */
95
96 /*------------------------------------------------------------------------*
97 * Hash map structs *
98 *------------------------------------------------------------------------*/
99 /*! General hash map */
100 struct L_Hashmap
101 {
102 l_int32 nitems; /*!< number of stored items */
103 l_int32 ntogo; /*!< number of items to be stored */
104 /*!< before resizing the hashmap */
105 l_int32 maxocc; /*!< max average occupancy allowed */
106 struct L_Hashitem **hashtab; /*!< array of hash item ptrs */
107 l_int32 tabsize; /*!< size of array of hash item ptrs */
108 };
109 typedef struct L_Hashmap L_HASHMAP;
110
111 /*! Hash item, containing storage for the key, value and count. The key
112 is a l_uint64, which is hashed by the mod function to find the index
113 into the hashtab. */
114 struct L_Hashitem
115 {
116 l_uint64 key; /*!< key is hashed into index into hashtab */
117 l_uint64 val; /*!< number stored associated with the key */
118 l_int32 count; /*!< number of elements seen with this key */
119 struct L_Hashitem *next; /*!< ptr to the next in the list */
120 };
121 typedef struct L_Hashitem L_HASHITEM;
122
123
124 /*------------------------------------------------------------------------*
125 * Hashmap flags *
126 *------------------------------------------------------------------------*/
127 /*! Hashmap Lookup */
128 enum {
129 L_UNDEFINED = 0, /*!< invalid operation */
130 L_HMAP_CHECK = 1, /*!< check if this key/val has been stored */
131 L_HMAP_CREATE = 2 /*!< create and store a hashitem if not found */
132 };
133
134 #endif /* LEPTONICA_HASHMAP_H */