gui: Allow File|Open to select an encoding for system files.
[pspp] / src / libpspp / hmap.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
3
4    This program is free software: you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation, either version 3 of the License, or
7    (at your option) any later version.
8
9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU General Public License for more details.
13
14    You should have received a copy of the GNU General Public License
15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
16
17 #ifdef HAVE_CONFIG_H
18 #include <config.h>
19 #endif
20
21 #include "libpspp/hmap.h"
22
23 #include <assert.h>
24 #include <stdlib.h>
25
26 #include "gl/xalloc.h"
27
28 static size_t capacity_to_mask (size_t capacity);
29
30 /* Initializes MAP as a new hash map that is initially empty. */
31 void
32 hmap_init (struct hmap *map)
33 {
34   map->count = 0;
35   map->mask = 0;
36   map->buckets = &map->one;
37   map->one = NULL;
38 }
39
40 /* Exchanges the contents of hash maps A and B. */
41 void
42 hmap_swap (struct hmap *a, struct hmap *b)
43 {
44   struct hmap tmp = *a;
45   *a = *b;
46   *b = tmp;
47   if (!a->mask)
48     a->buckets = &a->one;
49   if (!b->mask)
50     b->buckets = &b->one;
51 }
52
53 /* Removes all of the elements from MAP, without destroying MAP itself and
54    without accessing the existing elements (if any). */
55 void
56 hmap_clear (struct hmap *map)
57 {
58   size_t i;
59
60   for (i = 0; i <= map->mask; i++)
61     map->buckets[i] = NULL;
62   map->count = 0;
63 }
64
65 /* Frees the memory, if any, allocated by hash map MAP.  This has
66    no effect on the actual data items in MAP, if any, because the
67    client is responsible for allocating and freeing them.  It
68    could, however, render them inaccessible if the only pointers
69    to them were from MAP itself, so in such a situation one
70    should iterate through the map and free the data items before
71    destroying it. */
72 void
73 hmap_destroy (struct hmap *map) 
74 {
75   if (map != NULL && map->buckets != &map->one) 
76     free (map->buckets);
77 }
78
79 /* Reallocates MAP's hash buckets so that NEW_MASK becomes the
80    hash value bit-mask used to choose a hash bucket, then
81    rehashes any data elements in MAP into the new hash buckets.
82
83    NEW_MASK must be a power of 2 minus 1 (including 0), that is,
84    its value in binary must be all 1-bits.  */
85 static void
86 hmap_rehash (struct hmap *map, size_t new_mask) 
87 {
88   struct hmap_node **new_buckets;
89   struct hmap_node *node, *next;
90
91   assert ((new_mask & (new_mask + 1)) == 0);
92   if (new_mask)
93     new_buckets = xcalloc (new_mask + 1, sizeof *new_buckets);
94   else 
95     {
96       new_buckets = &map->one;
97       new_buckets[0] = NULL;
98     }
99       
100   if (map->count > 0)
101     {
102       for (node = hmap_first (map); node != NULL; node = next)
103         {
104           size_t new_idx = node->hash & new_mask;
105           struct hmap_node **new_bucket = &new_buckets[new_idx];
106           next = hmap_next (map, node);
107           node->next = *new_bucket;
108           *new_bucket = node;
109         } 
110     }
111   if (map->buckets != &map->one)
112     free (map->buckets);
113   map->buckets = new_buckets;
114   map->mask = new_mask;
115 }
116
117 /* Ensures that MAP has sufficient space to store at least
118    CAPACITY data elements, allocating a new set of buckets and
119    rehashing if necessary. */
120 void
121 hmap_reserve (struct hmap *map, size_t capacity)
122 {
123   if (capacity > hmap_capacity (map))
124     hmap_rehash (map, capacity_to_mask (capacity));
125 }
126
127 /* Shrinks MAP's set of buckets to the minimum number needed to
128    store its current number of elements, allocating a new set of
129    buckets and rehashing if that would save space. */
130 void
131 hmap_shrink (struct hmap *map) 
132 {
133   size_t new_mask = capacity_to_mask (map->count);
134   if (new_mask < map->mask) 
135     hmap_rehash (map, new_mask); 
136 }
137
138 /* Moves NODE around in MAP to compensate for its hash value
139    having changed to NEW_HASH.
140
141    This function does not verify that MAP does not already
142    contain a data item that duplicates NODE's new value.  If
143    duplicates should be disallowed (which is the usual case),
144    then the client must check for duplicates before changing
145    NODE's value. */
146 void
147 hmap_changed (struct hmap *map, struct hmap_node *node, size_t new_hash)
148 {
149   if ((new_hash ^ node->hash) & map->mask) 
150     {
151       hmap_delete (map, node);
152       hmap_insert_fast (map, node, new_hash);
153     }
154   else
155     node->hash = new_hash;
156 }
157
158 /* Hash map nodes may be moved around in memory as necessary,
159    e.g. as the result of an realloc operation on a block that
160    contains a node.  Once this is done, call this function
161    passing NODE that was moved, its former location in memory
162    OLD, and its hash map MAP before attempting any other
163    operation on MAP, NODE, or any other node in MAP.
164
165    It is not safe to move more than one node, then to call this
166    function for each node.  Instead, move a single node, call
167    this function, move another node, and so on.  Alternatively,
168    remove all affected nodes from the hash map, move them, then
169    re-insert all of them.
170
171    Assuming uniform hashing and no duplicate data items in MAP,
172    this function runs in constant time. */
173 void
174 hmap_moved (struct hmap *map,
175             struct hmap_node *node, const struct hmap_node *old) 
176 {
177   struct hmap_node **p = &map->buckets[node->hash & map->mask];
178   while (*p != old)
179     p = &(*p)->next;
180   *p = node;
181 }
182 \f
183 /* Returns the minimum-value mask required to allow for a hash
184    table capacity of at least CAPACITY.  The return value will be
185    a bit-mask suitable for use as the "mask" member of struct
186    hmap, that is, a power of 2 minus 1 (including 0). */
187 static size_t
188 capacity_to_mask (size_t capacity) 
189 {
190   /* Calculate the minimum mask necesary to support the given
191      capacity. */
192   size_t mask = 0;
193   while (hmap_mask_to_capacity__ (mask) < capacity)
194     mask = (mask << 1) | 1;
195
196   /* If the mask is nonzero, make it at least 3, because there is
197      little point in allocating an array of just 2 pointers. */
198   mask |= (mask & 1) << 1;
199
200   return mask;
201 }