1 | /* |
1 | /* |
2 | * static char *rcsid_shstr_c = |
2 | * static char *rcsid_shstr_c = |
3 | * "$Id: shstr.C,v 1.1 2006/08/13 17:16:01 elmex Exp $"; |
3 | * "$Id: shstr.C,v 1.2 2006/08/29 08:01:36 root Exp $"; |
4 | * |
4 | * |
5 | * shstr.c |
5 | * shstr.c |
6 | * |
6 | * |
7 | * This is a simple shared strings package with a simple interface. |
7 | * This is a simple shared strings package with a simple interface. |
8 | * |
8 | * |
… | |
… | |
63 | const char *p; |
63 | const char *p; |
64 | |
64 | |
65 | GATHER(hash_stats.calls); |
65 | GATHER(hash_stats.calls); |
66 | |
66 | |
67 | for (p = str; i < MAXSTRING && *p; p++, i++) { |
67 | for (p = str; i < MAXSTRING && *p; p++, i++) { |
68 | hash ^= (unsigned long) *p << rot; |
68 | hash ^= (unsigned long) *p << rot; |
69 | rot += 2; |
69 | rot += 2; |
70 | if (rot >= (sizeof(long) - sizeof(char)) * CHAR_BIT) |
70 | if (rot >= (sizeof(long) - sizeof(char)) * CHAR_BIT) |
71 | rot = 0; |
71 | rot = 0; |
72 | } |
72 | } |
73 | return (hash % TABLESIZE); |
73 | return (hash % TABLESIZE); |
74 | } |
74 | } |
75 | |
75 | |
76 | /* |
76 | /* |
… | |
… | |
85 | /* Allocate room for a struct which can hold str. Note |
85 | /* Allocate room for a struct which can hold str. Note |
86 | * that some bytes for the string are already allocated in the |
86 | * that some bytes for the string are already allocated in the |
87 | * shared_string struct. |
87 | * shared_string struct. |
88 | */ |
88 | */ |
89 | ss = (shared_string *) malloc(sizeof(shared_string) - PADDING + |
89 | ss = (shared_string *) malloc(sizeof(shared_string) - PADDING + |
90 | strlen(str) + 1); |
90 | strlen(str) + 1); |
91 | ss->u.previous = NULL; |
91 | ss->u.previous = NULL; |
92 | ss->next = NULL; |
92 | ss->next = NULL; |
93 | ss->refcount = 1; |
93 | ss->refcount = 1; |
94 | strcpy(ss->string, str); |
94 | strcpy(ss->string, str); |
95 | |
95 | |
… | |
… | |
115 | * add_string with a null parameter. But this will prevent a few |
115 | * add_string with a null parameter. But this will prevent a few |
116 | * core dumps. |
116 | * core dumps. |
117 | */ |
117 | */ |
118 | if (str==NULL) { |
118 | if (str==NULL) { |
119 | #ifdef MANY_CORES |
119 | #ifdef MANY_CORES |
120 | abort(); |
120 | abort(); |
121 | #else |
121 | #else |
122 | return NULL; |
122 | return NULL; |
123 | #endif |
123 | #endif |
124 | } |
124 | } |
125 | |
125 | |
126 | ind = hashstr(str); |
126 | ind = hashstr(str); |
127 | ss = hash_table[ind]; |
127 | ss = hash_table[ind]; |
128 | |
128 | |
129 | /* Is there an entry for that hash? |
129 | /* Is there an entry for that hash? |
130 | */ |
130 | */ |
131 | if (ss) { |
131 | if (ss) { |
132 | /* Simple case first: See if the first pointer matches. |
132 | /* Simple case first: See if the first pointer matches. |
133 | */ |
133 | */ |
134 | if (str != ss->string) { |
134 | if (str != ss->string) { |
135 | GATHER(add_stats.strcmps); |
135 | GATHER(add_stats.strcmps); |
136 | if (strcmp(ss->string, str)) { |
136 | if (strcmp(ss->string, str)) { |
137 | /* Apparantly, a string with the same hash value has this |
137 | /* Apparantly, a string with the same hash value has this |
138 | * slot. We must see in the list if "str" has been |
138 | * slot. We must see in the list if "str" has been |
139 | * registered earlier. |
139 | * registered earlier. |
140 | */ |
140 | */ |
141 | while (ss->next) { |
141 | while (ss->next) { |
142 | GATHER(add_stats.search); |
142 | GATHER(add_stats.search); |
143 | ss = ss->next; |
143 | ss = ss->next; |
144 | if (ss->string != str) { |
144 | if (ss->string != str) { |
145 | GATHER(add_stats.strcmps); |
145 | GATHER(add_stats.strcmps); |
146 | if (strcmp(ss->string, str)) { |
146 | if (strcmp(ss->string, str)) { |
147 | /* This wasn't the right string... |
147 | /* This wasn't the right string... |
148 | */ |
148 | */ |
149 | continue; |
149 | continue; |
150 | } |
150 | } |
151 | } |
151 | } |
152 | /* We found an entry for this string. Fix the |
152 | /* We found an entry for this string. Fix the |
153 | * refcount and exit. |
153 | * refcount and exit. |
154 | */ |
154 | */ |
|
|
155 | GATHER(add_stats.linked); |
|
|
156 | ++(ss->refcount); |
|
|
157 | |
|
|
158 | return ss->string; |
|
|
159 | } |
|
|
160 | /* There are no occurences of this string in the hash table. |
|
|
161 | */ |
|
|
162 | { |
|
|
163 | shared_string *new_ss; |
|
|
164 | |
|
|
165 | GATHER(add_stats.linked); |
|
|
166 | new_ss = new_shared_string(str); |
|
|
167 | ss->next = new_ss; |
|
|
168 | new_ss->u.previous = ss; |
|
|
169 | return new_ss->string; |
|
|
170 | } |
|
|
171 | } |
|
|
172 | /* Fall through. |
|
|
173 | */ |
|
|
174 | } |
155 | GATHER(add_stats.linked); |
175 | GATHER(add_stats.hashed); |
156 | ++(ss->refcount); |
176 | ++(ss->refcount); |
157 | |
|
|
158 | return ss->string; |
177 | return ss->string; |
159 | } |
|
|
160 | /* There are no occurences of this string in the hash table. |
|
|
161 | */ |
|
|
162 | { |
|
|
163 | shared_string *new_ss; |
|
|
164 | |
|
|
165 | GATHER(add_stats.linked); |
|
|
166 | new_ss = new_shared_string(str); |
|
|
167 | ss->next = new_ss; |
|
|
168 | new_ss->u.previous = ss; |
|
|
169 | return new_ss->string; |
|
|
170 | } |
|
|
171 | } |
|
|
172 | /* Fall through. |
|
|
173 | */ |
|
|
174 | } |
|
|
175 | GATHER(add_stats.hashed); |
|
|
176 | ++(ss->refcount); |
|
|
177 | return ss->string; |
|
|
178 | } else { |
178 | } else { |
179 | /* The string isn't registered, and the slot is empty. |
179 | /* The string isn't registered, and the slot is empty. |
180 | */ |
180 | */ |
181 | GATHER(add_stats.hashed); |
181 | GATHER(add_stats.hashed); |
182 | hash_table[ind] = new_shared_string(str); |
182 | hash_table[ind] = new_shared_string(str); |
183 | |
183 | |
184 | /* One bit in refcount is used to keep track of the union. |
184 | /* One bit in refcount is used to keep track of the union. |
185 | */ |
185 | */ |
186 | hash_table[ind]->refcount |= TOPBIT; |
186 | hash_table[ind]->refcount |= TOPBIT; |
187 | hash_table[ind]->u.array = &(hash_table[ind]); |
187 | hash_table[ind]->u.array = &(hash_table[ind]); |
188 | |
188 | |
189 | return hash_table[ind]->string; |
189 | return hash_table[ind]->string; |
190 | } |
190 | } |
191 | } |
191 | } |
192 | |
192 | |
193 | /* |
193 | /* |
194 | * Description: |
194 | * Description: |
… | |
… | |
244 | ss = hash_table[ind]; |
244 | ss = hash_table[ind]; |
245 | |
245 | |
246 | /* Is there an entry for that hash? |
246 | /* Is there an entry for that hash? |
247 | */ |
247 | */ |
248 | if (ss) { |
248 | if (ss) { |
249 | /* Simple case first: Is the first string the right one? |
249 | /* Simple case first: Is the first string the right one? |
250 | */ |
250 | */ |
251 | GATHER(find_stats.strcmps); |
251 | GATHER(find_stats.strcmps); |
252 | if (!strcmp(ss->string, str)) { |
252 | if (!strcmp(ss->string, str)) { |
253 | GATHER(find_stats.hashed); |
253 | GATHER(find_stats.hashed); |
254 | return ss->string; |
254 | return ss->string; |
255 | } else { |
255 | } else { |
256 | /* Recurse through the linked list, if there's one. |
256 | /* Recurse through the linked list, if there's one. |
257 | */ |
257 | */ |
258 | while (ss->next) { |
258 | while (ss->next) { |
259 | GATHER(find_stats.search); |
259 | GATHER(find_stats.search); |
260 | GATHER(find_stats.strcmps); |
260 | GATHER(find_stats.strcmps); |
261 | ss = ss->next; |
261 | ss = ss->next; |
262 | if (!strcmp(ss->string, str)) { |
262 | if (!strcmp(ss->string, str)) { |
263 | GATHER(find_stats.linked); |
263 | GATHER(find_stats.linked); |
264 | return ss->string; |
264 | return ss->string; |
265 | } |
265 | } |
266 | } |
266 | } |
267 | /* No match. Fall through. |
267 | /* No match. Fall through. |
268 | */ |
268 | */ |
269 | } |
269 | } |
270 | } |
270 | } |
271 | return NULL; |
271 | return NULL; |
272 | } |
272 | } |
273 | |
273 | |
274 | /* |
274 | /* |
… | |
… | |
286 | GATHER(free_stats.calls); |
286 | GATHER(free_stats.calls); |
287 | |
287 | |
288 | ss = SS(str); |
288 | ss = SS(str); |
289 | |
289 | |
290 | if ((--ss->refcount & ~TOPBIT) == 0) { |
290 | if ((--ss->refcount & ~TOPBIT) == 0) { |
291 | /* Remove this entry. |
291 | /* Remove this entry. |
292 | */ |
292 | */ |
293 | if (ss->refcount & TOPBIT) { |
293 | if (ss->refcount & TOPBIT) { |
294 | /* We must put a new value into the hash_table[]. |
294 | /* We must put a new value into the hash_table[]. |
295 | */ |
295 | */ |
296 | if (ss->next) { |
296 | if (ss->next) { |
297 | *(ss->u.array) = ss->next; |
297 | *(ss->u.array) = ss->next; |
298 | ss->next->u.array = ss->u.array; |
298 | ss->next->u.array = ss->u.array; |
299 | ss->next->refcount |= TOPBIT; |
299 | ss->next->refcount |= TOPBIT; |
|
|
300 | } else { |
|
|
301 | *(ss->u.array) = NULL; |
|
|
302 | } |
|
|
303 | free(ss); |
300 | } else { |
304 | } else { |
301 | *(ss->u.array) = NULL; |
|
|
302 | } |
|
|
303 | free(ss); |
|
|
304 | } else { |
|
|
305 | /* Relink and free this struct. |
305 | /* Relink and free this struct. |
306 | */ |
306 | */ |
307 | if (ss->next) |
307 | if (ss->next) |
308 | ss->next->u.previous = ss->u.previous; |
308 | ss->next->u.previous = ss->u.previous; |
309 | ss->u.previous->next = ss->next; |
309 | ss->u.previous->next = ss->next; |
310 | free(ss); |
310 | free(ss); |
311 | } |
311 | } |
312 | } |
312 | } |
313 | } |
313 | } |
314 | |
314 | |
315 | #ifdef SS_STATISTICS |
315 | #ifdef SS_STATISTICS |
316 | |
316 | |
… | |
… | |
328 | void |
328 | void |
329 | ss_dump_statistics(void) { |
329 | ss_dump_statistics(void) { |
330 | static char line[80]; |
330 | static char line[80]; |
331 | |
331 | |
332 | sprintf(errmsg, "%-13s %6s %6s %6s %6s %6s\n", |
332 | sprintf(errmsg, "%-13s %6s %6s %6s %6s %6s\n", |
333 | "", "calls", "hashed", "strcmp", "search", "linked"); |
333 | "", "calls", "hashed", "strcmp", "search", "linked"); |
334 | sprintf(line, "%-13s %6d %6d %6d %6d %6d\n", |
334 | sprintf(line, "%-13s %6d %6d %6d %6d %6d\n", |
335 | "add_string:", add_stats.calls, add_stats.hashed, |
335 | "add_string:", add_stats.calls, add_stats.hashed, |
336 | add_stats.strcmps, add_stats.search, add_stats.linked); |
336 | add_stats.strcmps, add_stats.search, add_stats.linked); |
337 | strcat(errmsg, line); |
337 | strcat(errmsg, line); |
338 | sprintf(line, "%-13s %6d\n", |
338 | sprintf(line, "%-13s %6d\n", |
339 | "add_refcount:", add_ref_stats.calls); |
339 | "add_refcount:", add_ref_stats.calls); |
340 | strcat(errmsg, line); |
340 | strcat(errmsg, line); |
341 | sprintf(line, "%-13s %6d\n", |
341 | sprintf(line, "%-13s %6d\n", |
342 | "free_string:", free_stats.calls); |
342 | "free_string:", free_stats.calls); |
343 | strcat(errmsg, line); |
343 | strcat(errmsg, line); |
344 | sprintf(line, "%-13s %6d %6d %6d %6d %6d\n", |
344 | sprintf(line, "%-13s %6d %6d %6d %6d %6d\n", |
345 | "find_string:", find_stats.calls, find_stats.hashed, |
345 | "find_string:", find_stats.calls, find_stats.hashed, |
346 | find_stats.strcmps, find_stats.search, find_stats.linked); |
346 | find_stats.strcmps, find_stats.search, find_stats.linked); |
347 | strcat(errmsg, line); |
347 | strcat(errmsg, line); |
348 | sprintf(line, "%-13s %6d\n", |
348 | sprintf(line, "%-13s %6d\n", |
349 | "hashstr:", hash_stats.calls); |
349 | "hashstr:", hash_stats.calls); |
350 | strcat(errmsg, line); |
350 | strcat(errmsg, line); |
351 | } |
351 | } |
352 | #endif /* SS_STATISTICS */ |
352 | #endif /* SS_STATISTICS */ |
353 | |
353 | |
354 | /* |
354 | /* |
… | |
… | |
365 | static char totals[80]; |
365 | static char totals[80]; |
366 | int entries = 0, refs = 0, links = 0; |
366 | int entries = 0, refs = 0, links = 0; |
367 | int i; |
367 | int i; |
368 | |
368 | |
369 | for (i = 0; i < TABLESIZE; i++) { |
369 | for (i = 0; i < TABLESIZE; i++) { |
370 | shared_string *ss; |
370 | shared_string *ss; |
371 | |
371 | |
372 | if ((ss = hash_table[i])!=NULL) { |
372 | if ((ss = hash_table[i])!=NULL) { |
373 | ++entries; |
373 | ++entries; |
374 | refs += (ss->refcount & ~TOPBIT); |
374 | refs += (ss->refcount & ~TOPBIT); |
375 | #if 1 /* Can't use stderr any longer, need to include global.h and |
375 | #if 1 /* Can't use stderr any longer, need to include global.h and |
376 | if (what & SS_DUMP_TABLE) |
376 | if (what & SS_DUMP_TABLE) |
377 | * use logfile. */ |
377 | * use logfile. */ |
378 | fprintf(stderr, "%4d -- %4d refs '%s' %c\n", |
378 | fprintf(stderr, "%4d -- %4d refs '%s' %c\n", |
379 | i, (ss->refcount & ~TOPBIT), ss->string, |
379 | i, (ss->refcount & ~TOPBIT), ss->string, |
380 | (ss->refcount & TOPBIT ? ' ' : '#')); |
380 | (ss->refcount & TOPBIT ? ' ' : '#')); |
381 | #endif |
381 | #endif |
382 | while (ss->next) { |
382 | while (ss->next) { |
383 | ss = ss->next; |
383 | ss = ss->next; |
384 | ++links; |
384 | ++links; |
385 | refs += (ss->refcount & ~TOPBIT); |
385 | refs += (ss->refcount & ~TOPBIT); |
386 | #if 1 |
386 | #if 1 |
387 | if (what & SS_DUMP_TABLE) |
387 | if (what & SS_DUMP_TABLE) |
388 | fprintf(stderr, " -- %4d refs '%s' %c\n", |
388 | fprintf(stderr, " -- %4d refs '%s' %c\n", |
389 | (ss->refcount & ~TOPBIT), ss->string, |
389 | (ss->refcount & ~TOPBIT), ss->string, |
390 | (ss->refcount & TOPBIT ? '*' : ' ')); |
390 | (ss->refcount & TOPBIT ? '*' : ' ')); |
391 | #endif |
391 | #endif |
392 | } |
392 | } |
393 | } |
393 | } |
394 | } |
394 | } |
395 | |
395 | |
396 | if (what & SS_DUMP_TOTALS) { |
396 | if (what & SS_DUMP_TOTALS) { |
397 | sprintf(totals, "\n%d entries, %d refs, %d links.", |
397 | sprintf(totals, "\n%d entries, %d refs, %d links.", |
398 | entries, refs, links); |
398 | entries, refs, links); |
399 | return totals; |
399 | return totals; |
400 | } |
400 | } |
401 | return NULL; |
401 | return NULL; |
402 | } |
402 | } |
403 | |
403 | |
… | |
… | |
409 | buf_overflow (const char *buf1, const char *buf2, int bufsize) |
409 | buf_overflow (const char *buf1, const char *buf2, int bufsize) |
410 | { |
410 | { |
411 | int len1 = 0, len2 = 0; |
411 | int len1 = 0, len2 = 0; |
412 | |
412 | |
413 | if (buf1) |
413 | if (buf1) |
414 | len1 = strlen (buf1); |
414 | len1 = strlen (buf1); |
415 | if (buf2) |
415 | if (buf2) |
416 | len2 = strlen (buf2); |
416 | len2 = strlen (buf2); |
417 | if ((len1 + len2) >= bufsize) |
417 | if ((len1 + len2) >= bufsize) |
418 | return 1; |
418 | return 1; |
419 | return 0; |
419 | return 0; |
420 | } |
420 | } |
421 | |
421 | |