source: protocols/jabber/hashtable.c @ 96863f6

Last change on this file since 96863f6 was b7d3cc34, checked in by Wilmer van der Gaast <wilmer@…>, at 2005-11-06T18:23:18Z

Initial repository (0.99 release tree)

  • Property mode set to 100644
File size: 3.4 KB
Line 
1/*
2The contents of this file are subject to the Mozilla Public License
3Version 1.1 (the "License"); you may not use this file except in
4csompliance with the License. You may obtain a copy of the License at
5http://www.mozilla.org/MPL/
6
7Software distributed under the License is distributed on an "AS IS"
8basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
9License for the specific language governing rights and limitations
10under the License.
11
12The Original Code is expat.
13
14The Initial Developer of the Original Code is James Clark.
15Portions created by James Clark are Copyright (C) 1998, 1999
16James Clark. All Rights Reserved.
17
18Contributor(s):
19
20*/
21
22#include "xmldef.h"
23
24#ifdef XML_UNICODE_WCHAR_T
25#ifndef XML_UNICODE
26#define XML_UNICODE
27#endif
28#endif
29
30#include "hashtable.h"
31
32#define INIT_SIZE 64
33
34static
35int keyeq(KEY s1, KEY s2)
36{
37    for (; *s1 == *s2; s1++, s2++)
38        if (*s1 == 0)
39            return 1;
40    return 0;
41}
42
43static
44unsigned long hash(KEY s)
45{
46    unsigned long h = 0;
47    while (*s)
48        h = (h << 5) + h + (unsigned char)*s++;
49    return h;
50}
51
52NAMED *lookup(HASH_TABLE *table, KEY name, size_t createSize)
53{
54    size_t i;
55    if (table->size == 0) {
56        if (!createSize)
57            return 0;
58        table->v = calloc(INIT_SIZE, sizeof(NAMED *));
59        if (!table->v)
60            return 0;
61        table->size = INIT_SIZE;
62        table->usedLim = INIT_SIZE / 2;
63        i = hash(name) & (table->size - 1);
64    }
65    else {
66        unsigned long h = hash(name);
67        for (i = h & (table->size - 1);
68                table->v[i];
69                i == 0 ? i = table->size - 1 : --i) {
70            if (keyeq(name, table->v[i]->name))
71                return table->v[i];
72        }
73        if (!createSize)
74            return 0;
75        if (table->used == table->usedLim) {
76            /* check for overflow */
77            size_t newSize = table->size * 2;
78            NAMED **newV = calloc(newSize, sizeof(NAMED *));
79            if (!newV)
80                return 0;
81            for (i = 0; i < table->size; i++)
82                if (table->v[i]) {
83                    size_t j;
84                    for (j = hash(table->v[i]->name) & (newSize - 1);
85                            newV[j];
86                            j == 0 ? j = newSize - 1 : --j)
87                        ;
88                    newV[j] = table->v[i];
89                }
90            g_free(table->v);
91            table->v = newV;
92            table->size = newSize;
93            table->usedLim = newSize/2;
94            for (i = h & (table->size - 1);
95                    table->v[i];
96                    i == 0 ? i = table->size - 1 : --i)
97                ;
98        }
99    }
100    table->v[i] = calloc(1, createSize);
101    if (!table->v[i])
102        return 0;
103    table->v[i]->name = name;
104    (table->used)++;
105    return table->v[i];
106}
107
108void hashTableDestroy(HASH_TABLE *table)
109{
110    size_t i;
111    for (i = 0; i < table->size; i++) {
112        NAMED *p = table->v[i];
113        if (p)
114            g_free(p);
115    }
116    g_free(table->v);
117}
118
119void hashTableInit(HASH_TABLE *p)
120{
121    p->size = 0;
122    p->usedLim = 0;
123    p->used = 0;
124    p->v = 0;
125}
126
127void hashTableIterInit(HASH_TABLE_ITER *iter, const HASH_TABLE *table)
128{
129    iter->p = table->v;
130    iter->end = iter->p + table->size;
131}
132
133NAMED *hashTableIterNext(HASH_TABLE_ITER *iter)
134{
135    while (iter->p != iter->end) {
136        NAMED *tem = *(iter->p)++;
137        if (tem)
138            return tem;
139    }
140    return 0;
141}
142
Note: See TracBrowser for help on using the repository browser.