LIRC libraries
LinuxInfraredRemoteControl
 All Data Structures Files Functions Variables Typedefs Enumerations Macros Modules Pages
dictionary.c
Go to the documentation of this file.
1 /* Copyright (c) 2000-2007 by Nicolas Devillard.
2  * Copyright (x) 2009 by Tim Post <tinkertim@gmail.com>
3  * MIT License
4  *
5  * Permission is hereby granted, free of charge, to any person obtaining a
6  * copy of this software and associated documentation files (the "Software"),
7  * to deal in the Software without restriction, including without limitation
8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9  * and/or sell copies of the Software, and to permit persons to whom the
10  * Software is furnished to do so, subject to the following conditions:
11  *
12  * The above copyright notice and this permission notice shall be included in
13  * all copies or substantial portions of the Software.
14  *
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21  * DEALINGS IN THE SOFTWARE.
22  */
23 
39 #include "dictionary.h"
40 
41 #include <stdio.h>
42 #include <stdlib.h>
43 #include <string.h>
44 #include <unistd.h>
45 
47 #define MAXVALSZ 1024
48 
50 #define DICTMINSZ 128
51 
53 #define DICT_INVALID_KEY ((char*)-1)
54 
60 static void *mem_double(void *ptr, int size)
61 {
62  void *newptr;
63 
64  newptr = calloc(2 * size, 1);
65  if (newptr == NULL) {
66  return NULL;
67  }
68  memcpy(newptr, ptr, size);
69  free(ptr);
70  return newptr;
71 }
72 
73 /* The remaining exposed functions are documented in dictionary.h */
74 
75 unsigned dictionary_hash(const char *key)
76 {
77  int len;
78  unsigned hash;
79  int i;
80 
81  len = strlen(key);
82  for (hash = 0, i = 0; i < len; i++) {
83  hash += (unsigned) key[i];
84  hash += (hash << 10);
85  hash ^= (hash >> 6);
86  }
87  hash += (hash << 3);
88  hash ^= (hash >> 11);
89  hash += (hash << 15);
90  return hash;
91 }
92 
94 {
95  dictionary *d;
96 
97  /* If no size was specified, allocate space for DICTMINSZ */
98  if (size<DICTMINSZ) size=DICTMINSZ;
99 
100  if (!(d = (dictionary *) calloc(1, sizeof(dictionary)))) {
101  return NULL;
102  }
103  d->size = size;
104  d->val = (char **) calloc(size, sizeof(char *));
105  d->key = (char **) calloc(size, sizeof(char *));
106  d->hash = (unsigned int *) calloc(size, sizeof(unsigned));
107  return d;
108 }
109 
111 {
112  int i;
113 
114  if (d == NULL)
115  return;
116  for (i = 0; i < d->size; i++) {
117  if (d->key[i] != NULL)
118  free(d->key[i]);
119  if (d->val[i] != NULL)
120  free(d->val[i]);
121  }
122  free(d->val);
123  free(d->key);
124  free(d->hash);
125  free(d);
126  return;
127 }
128 
129 const char *dictionary_get(dictionary *d, const char *key, const char *def)
130 {
131  unsigned hash;
132  int i;
133 
134  hash = dictionary_hash(key);
135  for (i=0; i < d->size; i++) {
136  if (d->key[i] == NULL)
137  continue;
138  /* Compare hash */
139  if (hash == d->hash[i]) {
140  /* Compare string, to avoid hash collisions */
141  if (!strcmp(key, d->key[i])) {
142  return d->val[i];
143  }
144  }
145  }
146  return def;
147 }
148 
149 int dictionary_set(dictionary *d, const char *key, const char *val)
150 {
151  int i;
152  unsigned hash;
153 
154  if (d==NULL || key==NULL)
155  return -1;
156 
157  /* Compute hash for this key */
158  hash = dictionary_hash(key);
159  /* Find if value is already in dictionary */
160  if (d->n > 0) {
161  for (i = 0; i < d->size; i++) {
162  if (d->key[i] == NULL)
163  continue;
164  /* Same hash value */
165  if (hash == d->hash[i]) {
166  /* Same key */
167  if (!strcmp(key, d->key[i])) {
168  /* Found a value: modify and return */
169  if (d->val[i] != NULL)
170  free(d->val[i]);
171  d->val[i] = val ? strdup(val) : NULL;
172  /* Value has been modified: return */
173  return 0;
174  }
175  }
176  }
177  }
178 
179  /* Add a new value
180  * See if dictionary needs to grow */
181  if (d->n == d->size) {
182  /* Reached maximum size: reallocate dictionary */
183  d->val = (char **) mem_double(d->val, d->size * sizeof(char *));
184  d->key = (char **) mem_double(d->key, d->size * sizeof(char *));
185  d->hash = (unsigned int *)
186  mem_double(d->hash, d->size * sizeof(unsigned));
187  if ((d->val == NULL) || (d->key == NULL) || (d->hash == NULL))
188  /* Cannot grow dictionary */
189  return -1;
190  /* Double size */
191  d->size *= 2;
192  }
193 
194  /* Insert key in the first empty slot */
195  for (i = 0; i < d->size; i++) {
196  if (d->key[i] == NULL) {
197  /* Add key here */
198  break;
199  }
200  }
201  /* Copy key */
202  d->key[i] = strdup(key);
203  d->val[i] = val ? strdup(val) : NULL;
204  d->hash[i] = hash;
205  d->n ++;
206  return 0;
207 }
208 
209 void dictionary_unset(dictionary *d, const char *key)
210 {
211  unsigned hash;
212  int i;
213 
214  if (key == NULL)
215  return;
216 
217  hash = dictionary_hash(key);
218  for (i = 0; i < d->size; i++) {
219  if (d->key[i] == NULL)
220  continue;
221  /* Compare hash */
222  if (hash == d->hash[i]) {
223  /* Compare string, to avoid hash collisions */
224  if (!strcmp(key, d->key[i])) {
225  /* Found key */
226  break;
227  }
228  }
229  }
230  if (i >= d->size)
231  /* Key not found */
232  return;
233 
234  free(d->key[i]);
235  d->key[i] = NULL;
236  if (d->val[i]!=NULL) {
237  free(d->val[i]);
238  d->val[i] = NULL;
239  }
240  d->hash[i] = 0;
241  d->n --;
242  return;
243 }
244 
245 void dictionary_dump(dictionary *d, FILE *out)
246 {
247  int i;
248 
249  if (d == NULL || out == NULL)
250  return;
251  if (d->n < 1) {
252  fprintf(out, "empty dictionary\n");
253  return;
254  }
255  for (i = 0; i < d->size; i++) {
256  if (d->key[i]) {
257  fprintf(out, "%20s\t[%s]\n",
258  d->key[i],
259  d->val[i] ? d->val[i] : "UNDEF");
260  }
261  }
262  return;
263 }
264 
int dictionary_set(dictionary *d, const char *key, const char *val)
Set a value in a dictionary.
Definition: dictionary.c:149
#define DICTMINSZ
Definition: dictionary.c:50
const char * dictionary_get(dictionary *d, const char *key, const char *def)
Get a value from a dictionary.
Definition: dictionary.c:129
dictionary * dictionary_new(int size)
Create a new dictionary object.
Definition: dictionary.c:93
void dictionary_del(dictionary *d)
Delete a dictionary object.
Definition: dictionary.c:110
void dictionary_unset(dictionary *d, const char *key)
Delete a key in a dictionary.
Definition: dictionary.c:209
void dictionary_dump(dictionary *d, FILE *out)
Dump a dictionary to an opened file pointer.
Definition: dictionary.c:245
Dictionary object.
Definition: dictionary.h:67
unsigned dictionary_hash(const char *key)
Compute the hash key for a string.
Definition: dictionary.c:75
Implements a dictionary for string variables.This module implements a simple dictionary object...