← Back to branch summary

~zulcss/samba/server-dailies-3.4

« back to all changes in this revision

Viewing changes to source4/heimdal/lib/asn1/hash.c

  • Committer: Chuck Short
  • Date: 2010-09-28 20:38:39 UTC
  • Revision ID: zulcss@ubuntu.com-20100928203839-pgjulytsi9ue63x1
Initial version

Show diffs side-by-side

added added

removed removed

Lines of Context:
source4/heimdal/lib/asn1/hash.c
 
1
/*
 
2
 * Copyright (c) 1997 Kungliga Tekniska Högskolan
 
3
 * (Royal Institute of Technology, Stockholm, Sweden).
 
4
 * All rights reserved.
 
5
 *
 
6
 * Redistribution and use in source and binary forms, with or without
 
7
 * modification, are permitted provided that the following conditions
 
8
 * are met:
 
9
 *
 
10
 * 1. Redistributions of source code must retain the above copyright
 
11
 *    notice, this list of conditions and the following disclaimer.
 
12
 *
 
13
 * 2. Redistributions in binary form must reproduce the above copyright
 
14
 *    notice, this list of conditions and the following disclaimer in the
 
15
 *    documentation and/or other materials provided with the distribution.
 
16
 *
 
17
 * 3. Neither the name of the Institute nor the names of its contributors
 
18
 *    may be used to endorse or promote products derived from this software
 
19
 *    without specific prior written permission.
 
20
 *
 
21
 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
 
22
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
23
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
24
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
 
25
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 
26
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 
27
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
28
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 
29
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 
30
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 
31
 * SUCH DAMAGE.
 
32
 */
 
33
 
 
34
/*
 
35
 * Hash table functions
 
36
 */
 
37
 
 
38
#include "gen_locl.h"
 
39
 
 
40
RCSID("$Id$");
 
41
 
 
42
static Hashentry *_search(Hashtab * htab,       /* The hash table */
 
43
                          void *ptr);   /* And key */
 
44
 
 
45
Hashtab *
 
46
hashtabnew(int sz,
 
47
           int (*cmp) (void *, void *),
 
48
           unsigned (*hash) (void *))
 
49
{
 
50
    Hashtab *htab;
 
51
    int i;
 
52
 
 
53
    assert(sz > 0);
 
54
 
 
55
    htab = (Hashtab *) malloc(sizeof(Hashtab) + (sz - 1) * sizeof(Hashentry *));
 
56
    if (htab == NULL)
 
57
        return NULL;
 
58
 
 
59
    for (i = 0; i < sz; ++i)
 
60
        htab->tab[i] = NULL;
 
61
 
 
62
    htab->cmp = cmp;
 
63
    htab->hash = hash;
 
64
    htab->sz = sz;
 
65
    return htab;
 
66
}
 
67
 
 
68
/* Intern search function */
 
69
 
 
70
static Hashentry *
 
71
_search(Hashtab * htab, void *ptr)
 
72
{
 
73
    Hashentry *hptr;
 
74
 
 
75
    assert(htab && ptr);
 
76
 
 
77
    for (hptr = htab->tab[(*htab->hash) (ptr) % htab->sz];
 
78
         hptr;
 
79
         hptr = hptr->next)
 
80
        if ((*htab->cmp) (ptr, hptr->ptr) == 0)
 
81
            break;
 
82
    return hptr;
 
83
}
 
84
 
 
85
/* Search for element in hash table */
 
86
 
 
87
void *
 
88
hashtabsearch(Hashtab * htab, void *ptr)
 
89
{
 
90
    Hashentry *tmp;
 
91
 
 
92
    tmp = _search(htab, ptr);
 
93
    return tmp ? tmp->ptr : tmp;
 
94
}
 
95
 
 
96
/* add element to hash table */
 
97
/* if already there, set new value */
 
98
/* !NULL if succesful */
 
99
 
 
100
void *
 
101
hashtabadd(Hashtab * htab, void *ptr)
 
102
{
 
103
    Hashentry *h = _search(htab, ptr);
 
104
    Hashentry **tabptr;
 
105
 
 
106
    assert(htab && ptr);
 
107
 
 
108
    if (h)
 
109
        free((void *) h->ptr);
 
110
    else {
 
111
        h = (Hashentry *) malloc(sizeof(Hashentry));
 
112
        if (h == NULL) {
 
113
            return NULL;
 
114
        }
 
115
        tabptr = &htab->tab[(*htab->hash) (ptr) % htab->sz];
 
116
        h->next = *tabptr;
 
117
        *tabptr = h;
 
118
        h->prev = tabptr;
 
119
        if (h->next)
 
120
            h->next->prev = &h->next;
 
121
    }
 
122
    h->ptr = ptr;
 
123
    return h;
 
124
}
 
125
 
 
126
/* delete element with key key. Iff freep, free Hashentry->ptr */
 
127
 
 
128
int
 
129
_hashtabdel(Hashtab * htab, void *ptr, int freep)
 
130
{
 
131
    Hashentry *h;
 
132
 
 
133
    assert(htab && ptr);
 
134
 
 
135
    h = _search(htab, ptr);
 
136
    if (h) {
 
137
        if (freep)
 
138
            free(h->ptr);
 
139
        if ((*(h->prev) = h->next))
 
140
            h->next->prev = h->prev;
 
141
        free(h);
 
142
        return 0;
 
143
    } else
 
144
        return -1;
 
145
}
 
146
 
 
147
/* Do something for each element */
 
148
 
 
149
void
 
150
hashtabforeach(Hashtab * htab, int (*func) (void *ptr, void *arg),
 
151
               void *arg)
 
152
{
 
153
    Hashentry **h, *g;
 
154
 
 
155
    assert(htab);
 
156
 
 
157
    for (h = htab->tab; h < &htab->tab[htab->sz]; ++h)
 
158
        for (g = *h; g; g = g->next)
 
159
            if ((*func) (g->ptr, arg))
 
160
                return;
 
161
}
 
162
 
 
163
/* standard hash-functions for strings */
 
164
 
 
165
unsigned
 
166
hashadd(const char *s)
 
167
{                               /* Standard hash function */
 
168
    unsigned i;
 
169
 
 
170
    assert(s);
 
171
 
 
172
    for (i = 0; *s; ++s)
 
173
        i += *s;
 
174
    return i;
 
175
}
 
176
 
 
177
unsigned
 
178
hashcaseadd(const char *s)
 
179
{                               /* Standard hash function */
 
180
    unsigned i;
 
181
 
 
182
    assert(s);
 
183
 
 
184
    for (i = 0; *s; ++s)
 
185
        i += toupper((unsigned char)*s);
 
186
    return i;
 
187
}
 
188
 
 
189
#define TWELVE (sizeof(unsigned))
 
190
#define SEVENTYFIVE (6*sizeof(unsigned))
 
191
#define HIGH_BITS (~((unsigned)(~0) >> TWELVE))
 
192
 
 
193
unsigned
 
194
hashjpw(const char *ss)
 
195
{                               /* another hash function */
 
196
    unsigned h = 0;
 
197
    unsigned g;
 
198
    const unsigned char *s = (const unsigned char *)ss;
 
199
 
 
200
    for (; *s; ++s) {
 
201
        h = (h << TWELVE) + *s;
 
202
        if ((g = h & HIGH_BITS))
 
203
            h = (h ^ (g >> SEVENTYFIVE)) & ~HIGH_BITS;
 
204
    }
 
205
    return h;
 
206
}