1 /*
2 * %CopyrightBegin%
3 *
4 * Copyright Ericsson AB 1998-2016. All Rights Reserved.
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 *
18 * %CopyrightEnd%
19 *
20
21 */
22 #include <stdlib.h>
23 #include <string.h>
24 #include "hash.h"
25
26 /* this function returns a bucket - from the freelist if one was found
27 * there, or from malloc(). Only "small" buckets, i.e. those whose
28 * keys are short enough to be stored in the bucket itself, are saved
29 * on the freelist.
30 */
ei_hash_bmalloc(ei_hash * tab)31 static ei_bucket *ei_hash_bmalloc(ei_hash *tab)
32 {
33 ei_bucket *new;
34
35 if (tab->freelist) {
36 new = tab->freelist;
37 tab->freelist = new->next;
38 /* fprintf(stderr,"getting bucket from freelist\n"); */
39 }
40 else {
41 new = malloc(sizeof(*new));
42 /* fprintf(stderr,"allocating new (small) bucket\n"); */
43 }
44
45 return new;
46 }
47
48 /* insert a new key-value pair. The old value (if any) is returned. If
49 * the malloc fails the function returns NULL. This is potentially a
50 * problem since the function returns the same thing when malloc fails
51 * as when a item is inserted that did not previously exist in the
52 * table. */
ei_hash_insert(ei_hash * tab,const char * key,const void * value)53 void *ei_hash_insert(ei_hash *tab, const char *key, const void *value)
54 {
55 const void *oldval=NULL;
56 ei_bucket *b=NULL;
57 int h, rh;
58
59 rh = tab->hash(key);
60 h = rh % tab->size;
61
62 b=tab->tab[h];
63 while (b) {
64 if ((rh == b->rawhash) && (!strcmp(key,b->key)))
65 break;
66 b=b->next;
67 }
68
69 if (b) {
70 /* replace existing value, return old value */
71 oldval = b->value;
72 b->value = value;
73 }
74 else {
75 int keylen = strlen(key);
76
77 /* this element is new */
78 if (keylen < EI_SMALLKEY) {
79 /* short keys stored directly in bucket */
80 /* try to get bucket from freelist */
81 if ((b = ei_hash_bmalloc(tab)) == NULL) return NULL;
82 b->key = b->keybuf;
83 }
84 else {
85 /* for longer keys we allocate space */
86 int keypos=sizeof(*b);
87
88 ei_align(keypos);
89 if ((b = malloc(keypos+keylen+1)) == NULL) return NULL;
90 b->key = (char *)b + keypos;
91 /* fprintf(stderr,"allocating new (large) bucket\n"); */
92 }
93
94 /* fill in the blanks */
95 b->rawhash = rh;
96 strcpy((char *)b->key,key);
97 b->value = value;
98
99 /* some statistiscs */
100 if (!tab->tab[h]) tab->npos++;
101 tab->nelem++;
102
103 /* link in the new element */
104 b->next = tab->tab[h];
105 tab->tab[h] = b;
106 }
107 return (void *)oldval;
108 }
109
110