source: rtems/c/src/libnetworking/rtems_webserver/sym.c @ 120b59e

4.104.114.84.95
Last change on this file since 120b59e was bfb4c547, checked in by Joel Sherrill <joel.sherrill@…>, on 03/05/04 at 18:14:27

2004-03-05 Joel Sherrill <joel@…>

  • libnetworking/rtems_webserver/ejparse.c, libnetworking/rtems_webserver/emfdb.c, libnetworking/rtems_webserver/sock.c, libnetworking/rtems_webserver/socket.c, libnetworking/rtems_webserver/sym.c, libnetworking/rtems_webserver/webs.c, libnetworking/rtems_webserver/websuemf.c: Remove warnings.
  • Property mode set to 100644
File size: 10.6 KB
Line 
1/*
2 * sym.c -- Symbol Table module
3 *
4 * Copyright (c) GoAhead Software Inc., 1995-2000. All Rights Reserved.
5 *
6 * See the file "license.txt" for usage and redistribution license requirements
7 *
8 * $Id$
9 */
10
11/******************************** Description *********************************/
12/*
13 *      This module implements a highly efficient generic symbol table with
14 *      update and access routines. Symbols are simple character strings and
15 *      the values they take can be flexible types as defined by value_t.
16 *      This modules allows multiple symbol tables to be created.
17 */
18
19/********************************* Includes ***********************************/
20
21#ifdef UEMF
22        #include        "uemf.h"
23#else
24        #include        "basic/basicInternal.h"
25#endif
26
27/********************************* Defines ************************************/
28
29typedef struct {                                                /* Symbol table descriptor */
30        int             inuse;                                          /* Is this entry in use */
31        int             hash_size;                                      /* Size of the table below */
32        sym_t   **hash_table;                           /* Allocated at run time */
33} sym_tabent_t;
34
35/********************************* Globals ************************************/
36
37static sym_tabent_t     **sym;                          /* List of symbol tables */
38static int                      symMax;                         /* One past the max symbol table */
39static int                      symOpenCount = 0;       /* Count of apps using sym */
40
41static int                      htIndex;                        /* Current location in table */
42static sym_t*           next;                           /* Next symbol in iteration */
43
44/**************************** Forward Declarations ****************************/
45
46static int              hashIndex(sym_tabent_t *tp, char_t *name);
47static sym_t    *hash(sym_tabent_t *tp, char_t *name);
48static int              calcPrime(int size);
49
50/*********************************** Code *************************************/
51/*
52 *      Open the symbol table subSystem.
53 */
54
55int symSubOpen()
56{
57        if (++symOpenCount == 1) {
58                symMax = 0;
59                sym = NULL;
60        }
61        return 0;
62}
63
64/******************************************************************************/
65/*
66 *      Close the symbol table subSystem.
67 */
68
69void symSubClose()
70{
71        if (--symOpenCount <= 0) {
72                symOpenCount = 0;
73        }
74}
75
76/******************************************************************************/
77/*
78 *      Create a symbol table.
79 */
80
81sym_fd_t symOpen(int hash_size)
82{
83        sym_fd_t                sd;
84        sym_tabent_t    *tp;
85
86        a_assert(hash_size > 2);
87
88/*
89 *      Create a new handle for this symbol table
90 */
91        if ((sd = hAlloc((void*) &sym)) < 0) {
92                return -1;
93        }
94
95/*
96 *      Create a new symbol table structure and zero
97 */
98        if ((tp = (sym_tabent_t*) balloc(B_L, sizeof(sym_tabent_t))) == NULL) {
99                symMax = hFree((void*) &sym, sd);
100                return -1;
101        }
102        memset(tp, 0, sizeof(sym_tabent_t));
103        if (sd >= symMax) {
104                symMax = sd + 1;
105        }
106        a_assert(0 <= sd && sd < symMax);
107        sym[sd] = tp;
108
109/*
110 *      Now create the hash table for fast indexing.
111 */
112        tp->hash_size = calcPrime(hash_size);
113        tp->hash_table = (sym_t**) balloc(B_L, tp->hash_size * sizeof(sym_t*));
114        a_assert(tp->hash_table);
115        memset(tp->hash_table, 0, tp->hash_size * sizeof(sym_t*));
116
117        return sd;
118}
119
120/******************************************************************************/
121/*
122 *      Close this symbol table. Call a cleanup function to allow the caller
123 *      to free resources associated with each symbol table entry.
124 */
125
126void symClose(sym_fd_t sd)
127{
128        sym_tabent_t    *tp;
129        sym_t                   *sp, *forw;
130        int                             i;
131
132        a_assert(0 <= sd && sd < symMax);
133        tp = sym[sd];
134        a_assert(tp);
135
136/*
137 *      Free all symbols in the hash table, then the hash table itself.
138 */
139        for (i = 0; i < tp->hash_size; i++) {
140                for (sp = tp->hash_table[i]; sp; sp = forw) {
141                        forw = sp->forw;
142                        valueFree(&sp->name);
143                        valueFree(&sp->content);
144                        bfree(B_L, (void*) sp);
145                        sp = forw;
146                }
147        }
148        bfree(B_L, (void*) tp->hash_table);
149
150        symMax = hFree((void*) &sym, sd);
151        bfree(B_L, (void*) tp);
152}
153
154/******************************************************************************/
155/*
156 *      Return the first symbol in the hashtable if there is one. This call is used
157 *      as the first step in traversing the table. A call to symFirst should be
158 *      followed by calls to symNext to get all the rest of the entries.
159 */
160
161sym_t* symFirst(sym_fd_t sd)
162{
163        sym_tabent_t    *tp;
164        sym_t                   *sp, *forw;
165        int                             i;
166
167        a_assert(0 <= sd && sd < symMax);
168        tp = sym[sd];
169        a_assert(tp);
170
171/*
172 *      Find the first symbol in the hashtable and return a pointer to it.
173 */
174        for (i = 0; i < tp->hash_size; i++) {
175                for (sp = tp->hash_table[i]; sp; sp = forw) {
176                        forw = sp->forw;
177
178                        if (forw == NULL) {
179                                htIndex = i + 1;
180                                next = tp->hash_table[htIndex];
181                        } else {
182                                htIndex = i;
183                                next = forw;
184                        }
185                        return sp;
186                }
187        }
188        return NULL;
189}
190
191/******************************************************************************/
192/*
193 *      Return the next symbol in the hashtable if there is one. See symFirst.
194 */
195
196sym_t* symNext(sym_fd_t sd)
197{
198        sym_tabent_t    *tp;
199        sym_t                   *sp, *forw;
200        int                             i;
201
202        a_assert(0 <= sd && sd < symMax);
203        tp = sym[sd];
204        a_assert(tp);
205
206/*
207 *      Find the first symbol in the hashtable and return a pointer to it.
208 */
209        for (i = htIndex; i < tp->hash_size; i++) {
210                for (sp = next; sp; sp = forw) {
211                        forw = sp->forw;
212
213                        if (forw == NULL) {
214                                htIndex = i + 1;
215                                next = tp->hash_table[htIndex];
216                        } else {
217                                htIndex = i;
218                                next = forw;
219                        }
220                        return sp;
221                }
222                next = tp->hash_table[i + 1];
223        }
224        return NULL;
225}
226
227/******************************************************************************/
228/*
229 *      Lookup a symbol and return a pointer to the symbol entry. If not present
230 *      then return a NULL.
231 */
232
233sym_t *symLookup(sym_fd_t sd, char_t *name)
234{
235        sym_tabent_t    *tp;
236        sym_t                   *sp;
237        char_t                  *cp;
238
239        a_assert(0 <= sd && sd < symMax);
240        if ((tp = sym[sd]) == NULL) {
241                return NULL;
242        }
243
244        if (name == NULL || *name == '\0') {
245                return NULL;
246        }
247
248/*
249 *      Do an initial hash and then follow the link chain to find the right entry
250 */
251        for (sp = hash(tp, name); sp; sp = sp->forw) {
252                cp = sp->name.value.string;
253                if (cp[0] == name[0] && gstrcmp(cp, name) == 0) {
254                        break;
255                }
256        }
257        return sp;
258}
259
260/******************************************************************************/
261/*
262 *      Enter a symbol into the table. If already there, update its value.
263 *      Always succeeds if memory available. We allocate a copy of "name" here
264 *      so it can be a volatile variable. The value "v" is just a copy of the
265 *      passed in value, so it MUST be persistent.
266 */
267
268sym_t *symEnter(sym_fd_t sd, char_t *name, value_t v, int arg)
269{
270        sym_tabent_t    *tp;
271        sym_t                   *sp, *last;
272        char_t                  *cp;
273        int                             hindex;
274
275        a_assert(name);
276        a_assert(0 <= sd && sd < symMax);
277        tp = sym[sd];
278        a_assert(tp);
279
280/*
281 *      Calculate the first daisy-chain from the hash table. If non-zero, then
282 *      we have daisy-chain, so scan it and look for the symbol.
283 */
284        last = NULL;
285        hindex = hashIndex(tp, name);
286        if ((sp = tp->hash_table[hindex]) != NULL) {
287                for (; sp; sp = sp->forw) {
288                        cp = sp->name.value.string;
289                        if (cp[0] == name[0] && gstrcmp(cp, name) == 0) {
290                                break;
291                        }
292                        last = sp;
293                }
294                if (sp) {
295/*
296 *                      Found, so update the value
297 *                      If the caller stores handles which require freeing, they
298 *                      will be lost here. It is the callers responsibility to free
299 *                      resources before overwriting existing contents. We will here
300 *                      free allocated strings which occur due to value_instring().
301 *                      We should consider providing the cleanup function on the open rather
302 *                      than the close and then we could call it here and solve the problem.
303 */
304                        if (sp->content.valid) {
305                                valueFree(&sp->content);
306                        }
307                        sp->content = v;
308                        sp->arg = arg;
309                        return sp;
310                }
311/*
312 *              Not found so allocate and append to the daisy-chain
313 */
314                sp = (sym_t*) balloc(B_L, sizeof(sym_t));
315                if (sp == NULL) {
316                        return NULL;
317                }
318                sp->name = valueString(name, VALUE_ALLOCATE);
319                sp->content = v;
320                sp->forw = (sym_t*) NULL;
321                sp->arg = arg;
322                last->forw = sp;
323
324        } else {
325/*
326 *              Daisy chain is empty so we need to start the chain
327 */
328                sp = (sym_t*) balloc(B_L, sizeof(sym_t));
329                if (sp == NULL) {
330                        return NULL;
331                }
332                tp->hash_table[hindex] = sp;
333                tp->hash_table[hashIndex(tp, name)] = sp;
334
335                sp->forw = (sym_t*) NULL;
336                sp->content = v;
337                sp->arg = arg;
338                sp->name = valueString(name, VALUE_ALLOCATE);
339        }
340        return sp;
341}
342
343/******************************************************************************/
344/*
345 *      Delete a symbol from a table
346 */
347
348int symDelete(sym_fd_t sd, char_t *name)
349{
350        sym_tabent_t    *tp;
351        sym_t                   *sp, *last;
352        char_t                  *cp;
353        int                             hindex;
354
355        a_assert(name && *name);
356        a_assert(0 <= sd && sd < symMax);
357        tp = sym[sd];
358        a_assert(tp);
359
360/*
361 *      Calculate the first daisy-chain from the hash table. If non-zero, then
362 *      we have daisy-chain, so scan it and look for the symbol.
363 */
364        last = NULL;
365        hindex = hashIndex(tp, name);
366        if ((sp = tp->hash_table[hindex]) != NULL) {
367                for ( ; sp; sp = sp->forw) {
368                        cp = sp->name.value.string;
369                        if (cp[0] == name[0] && gstrcmp(cp, name) == 0) {
370                                break;
371                        }
372                        last = sp;
373                }
374        }
375        if (sp == (sym_t*) NULL) {                              /* Not Found */
376                return -1;
377        }
378
379/*
380 *      Unlink and free the symbol. Last will be set if the element to be deleted
381 *      is not first in the chain.
382 */
383        if (last) {
384                last->forw = sp->forw;
385        } else {
386                tp->hash_table[hindex] = sp->forw;
387        }
388        valueFree(&sp->name);
389        valueFree(&sp->content);
390        bfree(B_L, (void*) sp);
391
392        return 0;
393}
394
395/******************************************************************************/
396/*
397 *      Hash a symbol and return a pointer to the hash daisy-chain list
398 *      All symbols reside on the chain (ie. none stored in the hash table itself)
399 */
400
401static sym_t *hash(sym_tabent_t *tp, char_t *name)
402{
403        a_assert(tp);
404
405        return tp->hash_table[hashIndex(tp, name)];
406}
407
408/******************************************************************************/
409/*
410 *      Compute the hash function and return an index into the hash table
411 *      We use a basic additive function that is then made modulo the size of the
412 *      table.
413 */
414
415static int hashIndex(sym_tabent_t *tp, char_t *name)
416{
417        unsigned int    sum;
418        int                             i;
419
420        a_assert(tp);
421/*
422 *      Add in each character shifted up progressively by 7 bits. The shift
423 *      amount is rounded so as to not shift too far. It thus cycles with each
424 *      new cycle placing character shifted up by one bit.
425 */
426        i = 0;
427        sum = 0;
428        while (*name) {
429                sum += (((int) *name++) << i);
430                i = (i + 7) % (BITS(int) - BITSPERBYTE);
431        }
432        return sum % tp->hash_size;
433}
434
435/******************************************************************************/
436/*
437 *      Check if this number is a prime
438 */
439
440static int isPrime(int n)
441{
442        int             i, max;
443
444        a_assert(n > 0);
445
446        max = n / 2;
447        for (i = 2; i <= max; i++) {
448                if (n % i == 0) {
449                        return 0;
450                }
451        }
452        return 1;
453}
454
455/******************************************************************************/
456/*
457 *      Calculate the largest prime smaller than size.
458 */
459
460static int calcPrime(int size)
461{
462        int count;
463
464        a_assert(size > 0);
465
466        for (count = size; count > 0; count--) {
467                if (isPrime(count)) {
468                        return count;
469                }
470        }
471        return 1;
472}
473
474/******************************************************************************/
475
Note: See TracBrowser for help on using the repository browser.