« back to all changes in this revision
Viewing changes to keyword.c
- browse files at revision 3
- compare with another revision
- download diff
- download tarball
- view history from revision 3
- Committer: Bazaar Package Importer
- Author(s): Colin Watson
- Date: 2006-07-31 09:09:12 UTC
- mfrom: (1.1.1 upstream) (2.1.1 edgy)
- Revision ID: james.westby@ubuntu.com-20060731090912-rxe2jt8nz6g2k2zx
Tags: 1:5.6-1
* New upstream release (closes: #374097).
* Fix accidentally-unrendered line in ctags(1) (closes: #271323).
* Policy version 3.7.2: no changes required.
* Fix accidentally-unrendered line in ctags(1) (closes: #271323).
* Policy version 3.7.2: no changes required.
- files modified:
- INSTALL.oth
added
removed
keyword.c
1
1
/*
2
* $Id: keyword.c,v 1.5 2003/07/17 03:08:23 darren Exp $
2
* $Id: keyword.c,v 1.6 2006/05/30 04:37:12 darren Exp $
3
3
*
4
4
* Copyright (c) 1998-2002, Darren Hiebert
5
5
*
12
12
/*
13
13
* INCLUDE FILES
14
14
*/
15
#include "general.h" /* must always come first */
15
#include "general.h" /* must always come first */
16
16
17
17
#include <string.h>
18
18
24
24
/*
25
25
* MACROS
26
26
*/
27
#define HASH_EXPONENT 7 /* must be less than 17 */
27
#define HASH_EXPONENT 7 /* must be less than 17 */
28
28
29
29
/*
30
30
* DATA DECLARATIONS
31
31
*/
32
32
typedef struct sHashEntry {
33
struct sHashEntry *next;
34
const char *string;
35
langType language;
36
int value;
33
struct sHashEntry *next;
34
const char *string;
35
langType language;
36
int value;
37
37
} hashEntry;
38
38
39
39
/*
48
48
49
49
static hashEntry **getHashTable (void)
50
50
{
51
static boolean allocated = FALSE;
52
53
if (! allocated)
54
{
55
unsigned int i;
56
57
HashTable = xMalloc (TableSize, hashEntry*);
58
59
for (i = 0 ; i < TableSize ; ++i)
60
HashTable [i] = NULL;
61
62
allocated = TRUE;
63
}
64
return HashTable;
51
static boolean allocated = FALSE;
52
53
if (! allocated)
54
{
55
unsigned int i;
56
57
HashTable = xMalloc (TableSize, hashEntry*);
58
59
for (i = 0 ; i < TableSize ; ++i)
60
HashTable [i] = NULL;
61
62
allocated = TRUE;
63
}
64
return HashTable;
65
65
}
66
66
67
67
static hashEntry *getHashTableEntry (unsigned long hashedValue)
68
68
{
69
hashEntry **const table = getHashTable ();
70
hashEntry *entry;
71
72
Assert (hashedValue < TableSize);
73
entry = table [hashedValue];
74
75
return entry;
69
hashEntry **const table = getHashTable ();
70
hashEntry *entry;
71
72
Assert (hashedValue < TableSize);
73
entry = table [hashedValue];
74
75
return entry;
76
76
}
77
77
78
78
static unsigned long hashValue (const char *const string)
79
79
{
80
unsigned long value = 0;
81
const unsigned char *p;
82
83
Assert (string != NULL);
84
85
/* We combine the various words of the multiword key using the method
86
* described on page 512 of Vol. 3 of "The Art of Computer Programming".
87
*/
88
for (p = (const unsigned char *) string ; *p != '\0' ; ++p)
89
{
90
value <<= 1;
91
if (value & 0x00000100L)
92
value = (value & 0x000000ffL) + 1L;
93
value ^= *p;
94
}
95
/* Algorithm from page 509 of Vol. 3 of "The Art of Computer Programming"
96
* Treats "value" as a 16-bit integer plus 16-bit fraction.
97
*/
98
value *= 40503L; /* = 2^16 * 0.6180339887 ("golden ratio") */
99
value &= 0x0000ffffL; /* keep fractional part */
100
value >>= 16 - HASH_EXPONENT; /* scale up by hash size and move down */
101
102
return value;
80
unsigned long value = 0;
81
const unsigned char *p;
82
83
Assert (string != NULL);
84
85
/* We combine the various words of the multiword key using the method
86
* described on page 512 of Vol. 3 of "The Art of Computer Programming".
87
*/
88
for (p = (const unsigned char *) string ; *p != '\0' ; ++p)
89
{
90
value <<= 1;
91
if (value & 0x00000100L)
92
value = (value & 0x000000ffL) + 1L;
93
value ^= *p;
94
}
95
/* Algorithm from page 509 of Vol. 3 of "The Art of Computer Programming"
96
* Treats "value" as a 16-bit integer plus 16-bit fraction.
97
*/
98
value *= 40503L; /* = 2^16 * 0.6180339887 ("golden ratio") */
99
value &= 0x0000ffffL; /* keep fractional part */
100
value >>= 16 - HASH_EXPONENT; /* scale up by hash size and move down */
101
102
return value;
103
103
}
104
104
105
static hashEntry *newEntry (const char *const string,
106
langType language, int value)
105
static hashEntry *newEntry (
106
const char *const string, langType language, int value)
107
107
{
108
hashEntry *const entry = xMalloc (1, hashEntry);
109
110
entry->next = NULL;
111
entry->string = string;
112
entry->language = language;
113
entry->value = value;
114
115
return entry;
108
hashEntry *const entry = xMalloc (1, hashEntry);
109
110
entry->next = NULL;
111
entry->string = string;
112
entry->language = language;
113
entry->value = value;
114
115
return entry;
116
116
}
117
117
118
118
/* Note that it is assumed that a "value" of zero means an undefined keyword
122
122
*/
123
123
extern void addKeyword (const char *const string, langType language, int value)
124
124
{
125
const unsigned long hashedValue = hashValue (string);
126
hashEntry *tableEntry = getHashTableEntry (hashedValue);
127
hashEntry *entry = tableEntry;
128
129
if (entry == NULL)
130
{
131
hashEntry **const table = getHashTable ();
132
table [hashedValue] = newEntry (string, language, value);
133
}
134
else
135
{
136
hashEntry *prev = NULL;
125
const unsigned long hashedValue = hashValue (string);
126
hashEntry *tableEntry = getHashTableEntry (hashedValue);
127
hashEntry *entry = tableEntry;
128
129
if (entry == NULL)
130
{
131
hashEntry **const table = getHashTable ();
132
table [hashedValue] = newEntry (string, language, value);
133
}
134
else
135
{
136
hashEntry *prev = NULL;
137
138
while (entry != NULL)
139
{
140
if (language == entry->language &&
141
strcmp (string, entry->string) == 0)
142
{
143
Assert (("Already in table" == NULL));
144
}
145
prev = entry;
146
entry = entry->next;
147
}
148
if (entry == NULL)
149
{
150
Assert (prev != NULL);
151
prev->next = newEntry (string, language, value);
152
}
153
}
154
}
155
156
extern int lookupKeyword (const char *const string, langType language)
157
{
158
const unsigned long hashedValue = hashValue (string);
159
hashEntry *entry = getHashTableEntry (hashedValue);
160
int result = -1;
137
161
138
162
while (entry != NULL)
139
163
{
140
if (language == entry->language &&
141
strcmp (string, entry->string) == 0)
142
{
143
Assert (("Already in table" == NULL));
144
}
145
prev = entry;
146
entry = entry->next;
147
}
148
if (entry == NULL)
149
{
150
Assert (prev != NULL);
151
prev->next = newEntry (string, language, value);
152
}
153
}
154
}
155
156
extern int lookupKeyword (const char *const string, langType language)
157
{
158
const unsigned long hashedValue = hashValue (string);
159
hashEntry *entry = getHashTableEntry (hashedValue);
160
int result = -1;
161
162
while (entry != NULL)
163
{
164
if (language == entry->language && strcmp (string, entry->string) == 0)
165
{
166
result = entry->value;
167
break;
168
}
169
entry = entry->next;
170
}
171
return result;
164
if (language == entry->language && strcmp (string, entry->string) == 0)
165
{
166
result = entry->value;
167
break;
168
}
169
entry = entry->next;
170
}
171
return result;
172
172
}
173
173
174
174
extern void freeKeywordTable (void)
175
175
{
176
if (HashTable != NULL)
177
{
178
unsigned int i;
179
180
for (i = 0 ; i < TableSize ; ++i)
176
if (HashTable != NULL)
181
177
{
182
hashEntry *entry = HashTable [i];
183
184
while (entry != NULL)
185
{
186
hashEntry *next = entry->next;
187
eFree (entry);
188
entry = next;
189
}
178
unsigned int i;
179
180
for (i = 0 ; i < TableSize ; ++i)
181
{
182
hashEntry *entry = HashTable [i];
183
184
while (entry != NULL)
185
{
186
hashEntry *next = entry->next;
187
eFree (entry);
188
entry = next;
189
}
190
}
191
eFree (HashTable);
190
192
}
191
eFree (HashTable);
192
}
193
193
}
194
194
195
195
#ifdef DEBUG
196
196
197
197
static void printEntry (const hashEntry *const entry)
198
198
{
199
printf (" %-15s %-7s\n", entry->string, getLanguageName (entry->language));
199
printf (" %-15s %-7s\n", entry->string, getLanguageName (entry->language));
200
200
}
201
201
202
202
static unsigned int printBucket (const unsigned int i)
203
203
{
204
hashEntry **const table = getHashTable ();
205
hashEntry *entry = table [i];
206
unsigned int measure = 1;
207
boolean first = TRUE;
204
hashEntry **const table = getHashTable ();
205
hashEntry *entry = table [i];
206
unsigned int measure = 1;
207
boolean first = TRUE;
208
208
209
printf ("%2d:", i);
210
if (entry == NULL)
211
printf ("\n");
212
else while (entry != NULL)
213
{
214
if (! first)
215
printf (" ");
216
else
209
printf ("%2d:", i);
210
if (entry == NULL)
211
printf ("\n");
212
else while (entry != NULL)
217
213
{
218
printf (" ");
219
first = FALSE;
214
if (! first)
215
printf (" ");
216
else
217
{
218
printf (" ");
219
first = FALSE;
220
}
221
printEntry (entry);
222
entry = entry->next;
223
measure = 2 * measure;
220
224
}
221
printEntry (entry);
222
entry = entry->next;
223
measure = 2 * measure;
224
}
225
return measure - 1;
225
return measure - 1;
226
226
}
227
227
228
228
extern void printKeywordTable (void)
229
229
{
230
unsigned long emptyBucketCount = 0;
231
unsigned long measure = 0;
232
unsigned int i;
233
234
for (i = 0 ; i < TableSize ; ++i)
235
{
236
const unsigned int pass = printBucket (i);
237
238
measure += pass;
239
if (pass == 0)
240
++emptyBucketCount;
241
}
242
243
printf ("spread measure = %ld\n", measure);
244
printf ("%ld empty buckets\n", emptyBucketCount);
230
unsigned long emptyBucketCount = 0;
231
unsigned long measure = 0;
232
unsigned int i;
233
234
for (i = 0 ; i < TableSize ; ++i)
235
{
236
const unsigned int pass = printBucket (i);
237
238
measure += pass;
239
if (pass == 0)
240
++emptyBucketCount;
241
}
242
243
printf ("spread measure = %ld\n", measure);
244
printf ("%ld empty buckets\n", emptyBucketCount);
245
245
}
246
246
247
247
#endif
248
248
249
/* vi:set tabstop=8 shiftwidth=4: */
249
/* vi:set tabstop=4 shiftwidth=4: */
Loggerhead is a web-based interface for Breezy
Version: 2.0.1