htable.c
Go to the documentation of this file.
1 /*
2  * Copyright 2004, Regents of the University of Minnesota
3  *
4  * This file contains routines for manipulating a direct-access hash table
5  *
6  * Started 3/22/04
7  * George
8  *
9  */
10 
11 #include <GKlib.h>
12 
13 /******************************************************************************
14 * This function creates the hash-table
15 *******************************************************************************/
16 gk_HTable_t *HTable_Create(int nelements)
17 {
18  gk_HTable_t *htable;
19 
20  htable = gk_malloc(sizeof(gk_HTable_t), "HTable_Create: htable");
21  htable->harray = gk_ikvmalloc(nelements, "HTable_Create: harray");
22  htable->nelements = nelements;
23 
24  HTable_Reset(htable);
25 
26  return htable;
27 }
28 
29 
30 /******************************************************************************
31 * This function resets the data-structures associated with the hash-table
32 *******************************************************************************/
34 {
35  int i;
36 
37  for (i=0; i<htable->nelements; i++)
38  htable->harray[i].key = HTABLE_EMPTY;
39  htable->htsize = 0;
40 
41 }
42 
43 /******************************************************************************
44 * This function resizes the hash-table
45 *******************************************************************************/
46 void HTable_Resize(gk_HTable_t *htable, int nelements)
47 {
48  int i, old_nelements;
49  gk_ikv_t *old_harray;
50 
51  old_nelements = htable->nelements;
52  old_harray = htable->harray;
53 
54  /* prepare larger hash */
55  htable->nelements = nelements;
56  htable->htsize = 0;
57  htable->harray = gk_ikvmalloc(nelements, "HTable_Resize: harray");
58  for (i=0; i<nelements; i++)
59  htable->harray[i].key = HTABLE_EMPTY;
60 
61  /* reassign the values */
62  for (i=0; i<old_nelements; i++)
63  if (old_harray[i].key != HTABLE_EMPTY)
64  HTable_Insert(htable, old_harray[i].key, old_harray[i].val);
65 
66  /* remove old harray */
67  gk_free((void **)&old_harray, LTERM);
68 }
69 
70 
71 /******************************************************************************
72 * This function inserts a key-value pair in the array
73 *******************************************************************************/
74 void HTable_Insert(gk_HTable_t *htable, int key, int val)
75 {
76  int i, first;
77 
78  if (htable->htsize > htable->nelements/2)
79  HTable_Resize(htable, 2*htable->nelements);
80 
81  first = HTable_HFunction(htable->nelements, key);
82 
83  for (i=first; i<htable->nelements; i++) {
84  if (htable->harray[i].key == HTABLE_EMPTY || htable->harray[i].key == HTABLE_DELETED) {
85  htable->harray[i].key = key;
86  htable->harray[i].val = val;
87  htable->htsize++;
88  return;
89  }
90  }
91 
92  for (i=0; i<first; i++) {
93  if (htable->harray[i].key == HTABLE_EMPTY || htable->harray[i].key == HTABLE_DELETED) {
94  htable->harray[i].key = key;
95  htable->harray[i].val = val;
96  htable->htsize++;
97  return;
98  }
99  }
100 
101 }
102 
103 
104 /******************************************************************************
105 * This function deletes key from the htable
106 *******************************************************************************/
107 void HTable_Delete(gk_HTable_t *htable, int key)
108 {
109  int i, first;
110 
111  first = HTable_HFunction(htable->nelements, key);
112 
113  for (i=first; i<htable->nelements; i++) {
114  if (htable->harray[i].key == key) {
115  htable->harray[i].key = HTABLE_DELETED;
116  htable->htsize--;
117  return;
118  }
119  }
120 
121  for (i=0; i<first; i++) {
122  if (htable->harray[i].key == key) {
123  htable->harray[i].key = HTABLE_DELETED;
124  htable->htsize--;
125  return;
126  }
127  }
128 
129 }
130 
131 
132 /******************************************************************************
133 * This function returns the data associated with the key in the hastable
134 *******************************************************************************/
135 int HTable_Search(gk_HTable_t *htable, int key)
136 {
137  int i, first;
138 
139  first = HTable_HFunction(htable->nelements, key);
140 
141  for (i=first; i<htable->nelements; i++) {
142  if (htable->harray[i].key == key)
143  return htable->harray[i].val;
144  else if (htable->harray[i].key == HTABLE_EMPTY)
145  return -1;
146  }
147 
148  for (i=0; i<first; i++) {
149  if (htable->harray[i].key == key)
150  return htable->harray[i].val;
151  else if (htable->harray[i].key == HTABLE_EMPTY)
152  return -1;
153  }
154 
155  return -1;
156 }
157 
158 
159 /******************************************************************************
160 * This function returns the next key/val
161 *******************************************************************************/
162 int HTable_GetNext(gk_HTable_t *htable, int key, int *r_val, int type)
163 {
164  int i;
165  static int first, last;
166 
167  if (type == HTABLE_FIRST)
168  first = last = HTable_HFunction(htable->nelements, key);
169 
170  if (first > last) {
171  for (i=first; i<htable->nelements; i++) {
172  if (htable->harray[i].key == key) {
173  *r_val = htable->harray[i].val;
174  first = i+1;
175  return 1;
176  }
177  else if (htable->harray[i].key == HTABLE_EMPTY)
178  return -1;
179  }
180  first = 0;
181  }
182 
183  for (i=first; i<last; i++) {
184  if (htable->harray[i].key == key) {
185  *r_val = htable->harray[i].val;
186  first = i+1;
187  return 1;
188  }
189  else if (htable->harray[i].key == HTABLE_EMPTY)
190  return -1;
191  }
192 
193  return -1;
194 }
195 
196 
197 /******************************************************************************
198 * This function returns the data associated with the key in the hastable
199 *******************************************************************************/
201 {
202  int i, first;
203 
204  first = HTable_HFunction(htable->nelements, key);
205 
206  for (i=first; i<htable->nelements; i++) {
207  if (htable->harray[i].key == key) {
208  htable->harray[i].key = HTABLE_DELETED;
209  htable->htsize--;
210  return htable->harray[i].val;
211  }
212  else if (htable->harray[i].key == HTABLE_EMPTY)
213  gk_errexit(SIGERR, "HTable_SearchAndDelete: Failed to find the key!\n");
214  }
215 
216  for (i=0; i<first; i++) {
217  if (htable->harray[i].key == key) {
218  htable->harray[i].key = HTABLE_DELETED;
219  htable->htsize--;
220  return htable->harray[i].val;
221  }
222  else if (htable->harray[i].key == HTABLE_EMPTY)
223  gk_errexit(SIGERR, "HTable_SearchAndDelete: Failed to find the key!\n");
224  }
225 
226  return -1;
227 
228 }
229 
230 
231 
232 /******************************************************************************
233 * This function destroys the data structures associated with the hash-table
234 *******************************************************************************/
236 {
237  gk_free((void **)&htable->harray, &htable, LTERM);
238 }
239 
240 
241 /******************************************************************************
242 * This is the hash-function. Based on multiplication
243 *******************************************************************************/
244 int HTable_HFunction(int nelements, int key)
245 {
246  return (int)(key%nelements);
247 }
const gtsam::Symbol key('X', 0)
gk_ikv_t * harray
Definition: gk_struct.h:131
int HTable_GetNext(gk_HTable_t *htable, int key, int *r_val, int type)
Definition: htable.c:162
for(size_t i=1;i< poses.size();++i)
void HTable_Resize(gk_HTable_t *htable, int nelements)
Definition: htable.c:46
#define HTABLE_EMPTY
Definition: gk_defs.h:21
gk_HTable_t * HTable_Create(int nelements)
Definition: htable.c:16
void gk_errexit(int signum, char *f_str,...)
Definition: error.c:77
EIGEN_CONSTEXPR Index first(const T &x) EIGEN_NOEXCEPT
int nelements
Definition: gk_struct.h:129
static const symbolic::SymbolExpr< internal::symbolic_last_tag > last
void HTable_Delete(gk_HTable_t *htable, int key)
Definition: htable.c:107
void HTable_Insert(gk_HTable_t *htable, int key, int val)
Definition: htable.c:74
#define SIGERR
Definition: gk_defs.h:38
int HTable_SearchAndDelete(gk_HTable_t *htable, int key)
Definition: htable.c:200
void HTable_Reset(gk_HTable_t *htable)
Definition: htable.c:33
#define HTABLE_DELETED
Definition: gk_defs.h:22
void * gk_malloc(size_t nbytes, char *msg)
Definition: memory.c:140
void gk_free(void **ptr1,...)
Definition: memory.c:202
int HTable_Search(gk_HTable_t *htable, int key)
Definition: htable.c:135
#define HTABLE_FIRST
Definition: gk_defs.h:23
void HTable_Destroy(gk_HTable_t *htable)
Definition: htable.c:235
int HTable_HFunction(int nelements, int key)
Definition: htable.c:244
Definition: pytypes.h:1370
#define LTERM
Definition: gk_defs.h:14


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:20