|
0
|
1 /* ========================================================================
|
|
|
2 * Copyright 1988-2006 University of Washington
|
|
|
3 *
|
|
|
4 * Licensed under the Apache License, Version 2.0 (the "License");
|
|
|
5 * you may not use this file except in compliance with the License.
|
|
|
6 * You may obtain a copy of the License at
|
|
|
7 *
|
|
|
8 * http://www.apache.org/licenses/LICENSE-2.0
|
|
|
9 *
|
|
|
10 *
|
|
|
11 * ========================================================================
|
|
|
12 */
|
|
|
13
|
|
|
14 /*
|
|
|
15 * Program: Miscellaneous utility routines
|
|
|
16 *
|
|
|
17 * Author: Mark Crispin
|
|
|
18 * Networks and Distributed Computing
|
|
|
19 * Computing & Communications
|
|
|
20 * University of Washington
|
|
|
21 * Administration Building, AG-44
|
|
|
22 * Seattle, WA 98195
|
|
|
23 * Internet: MRC@CAC.Washington.EDU
|
|
|
24 *
|
|
|
25 * Date: 5 July 1988
|
|
|
26 * Last Edited: 6 December 2006
|
|
|
27 *
|
|
|
28 * This original version of this file is
|
|
|
29 * Copyright 1988 Stanford University
|
|
|
30 * and was developed in the Symbolic Systems Resources Group of the Knowledge
|
|
|
31 * Systems Laboratory at Stanford University in 1987-88, and was funded by the
|
|
|
32 * Biomedical Research Technology Program of the NationalInstitutes of Health
|
|
|
33 * under grant number RR-00785.
|
|
|
34 */
|
|
|
35
|
|
|
36
|
|
|
37 #include <ctype.h>
|
|
|
38 #include "c-client.h"
|
|
|
39
|
|
|
40 /* Convert ASCII string to all uppercase
|
|
|
41 * Accepts: string pointer
|
|
|
42 * Returns: string pointer
|
|
|
43 *
|
|
|
44 * Don't use islower/toupper since this function must be ASCII only.
|
|
|
45 */
|
|
|
46
|
|
|
47 unsigned char *ucase (unsigned char *s)
|
|
|
48 {
|
|
|
49 unsigned char *t;
|
|
|
50 /* if lowercase covert to upper */
|
|
|
51 for (t = s; *t; t++) if ((*t >= 'a') && (*t <= 'z')) *t -= ('a' - 'A');
|
|
|
52 return s; /* return string */
|
|
|
53 }
|
|
|
54
|
|
|
55
|
|
|
56 /* Convert string to all lowercase
|
|
|
57 * Accepts: string pointer
|
|
|
58 * Returns: string pointer
|
|
|
59 *
|
|
|
60 * Don't use isupper/tolower since this function must be ASCII only.
|
|
|
61 */
|
|
|
62
|
|
|
63 unsigned char *lcase (unsigned char *s)
|
|
|
64 {
|
|
|
65 unsigned char *t;
|
|
|
66 /* if uppercase covert to lower */
|
|
|
67 for (t = s; *t; t++) if ((*t >= 'A') && (*t <= 'Z')) *t += ('a' - 'A');
|
|
|
68 return s; /* return string */
|
|
|
69 }
|
|
|
70
|
|
|
71 /* Copy string to free storage
|
|
|
72 * Accepts: source string
|
|
|
73 * Returns: free storage copy of string
|
|
|
74 */
|
|
|
75
|
|
|
76 char *cpystr (const char *string)
|
|
|
77 {
|
|
|
78 return string ? strcpy ((char *) fs_get (1 + strlen (string)),string) : NIL;
|
|
|
79 }
|
|
|
80
|
|
|
81
|
|
|
82 /* Copy text/size to free storage as sized text
|
|
|
83 * Accepts: destination sized text
|
|
|
84 * pointer to source text
|
|
|
85 * size of source text
|
|
|
86 * Returns: text as a char *
|
|
|
87 */
|
|
|
88
|
|
|
89 char *cpytxt (SIZEDTEXT *dst,char *text,unsigned long size)
|
|
|
90 {
|
|
|
91 /* flush old space */
|
|
|
92 if (dst->data) fs_give ((void **) &dst->data);
|
|
|
93 /* copy data in sized text */
|
|
|
94 memcpy (dst->data = (unsigned char *)
|
|
|
95 fs_get ((size_t) (dst->size = size) + 1),text,(size_t) size);
|
|
|
96 dst->data[size] = '\0'; /* tie off text */
|
|
|
97 return (char *) dst->data; /* convenience return */
|
|
|
98 }
|
|
|
99
|
|
|
100 /* Copy sized text to free storage as sized text
|
|
|
101 * Accepts: destination sized text
|
|
|
102 * source sized text
|
|
|
103 * Returns: text as a char *
|
|
|
104 */
|
|
|
105
|
|
|
106 char *textcpy (SIZEDTEXT *dst,SIZEDTEXT *src)
|
|
|
107 {
|
|
|
108 /* flush old space */
|
|
|
109 if (dst->data) fs_give ((void **) &dst->data);
|
|
|
110 /* copy data in sized text */
|
|
|
111 memcpy (dst->data = (unsigned char *)
|
|
|
112 fs_get ((size_t) (dst->size = src->size) + 1),
|
|
|
113 src->data,(size_t) src->size);
|
|
|
114 dst->data[dst->size] = '\0'; /* tie off text */
|
|
|
115 return (char *) dst->data; /* convenience return */
|
|
|
116 }
|
|
|
117
|
|
|
118
|
|
|
119 /* Copy stringstruct to free storage as sized text
|
|
|
120 * Accepts: destination sized text
|
|
|
121 * source stringstruct
|
|
|
122 * Returns: text as a char *
|
|
|
123 */
|
|
|
124
|
|
|
125 char *textcpystring (SIZEDTEXT *text,STRING *bs)
|
|
|
126 {
|
|
|
127 unsigned long i = 0;
|
|
|
128 /* clear old space */
|
|
|
129 if (text->data) fs_give ((void **) &text->data);
|
|
|
130 /* make free storage space in sized text */
|
|
|
131 text->data = (unsigned char *) fs_get ((size_t) (text->size = SIZE (bs)) +1);
|
|
|
132 while (i < text->size) text->data[i++] = SNX (bs);
|
|
|
133 text->data[i] = '\0'; /* tie off text */
|
|
|
134 return (char *) text->data; /* convenience return */
|
|
|
135 }
|
|
|
136
|
|
|
137
|
|
|
138 /* Copy stringstruct from offset to free storage as sized text
|
|
|
139 * Accepts: destination sized text
|
|
|
140 * source stringstruct
|
|
|
141 * offset into stringstruct
|
|
|
142 * size of source text
|
|
|
143 * Returns: text as a char *
|
|
|
144 */
|
|
|
145
|
|
|
146 char *textcpyoffstring (SIZEDTEXT *text,STRING *bs,unsigned long offset,
|
|
|
147 unsigned long size)
|
|
|
148 {
|
|
|
149 unsigned long i = 0;
|
|
|
150 /* clear old space */
|
|
|
151 if (text->data) fs_give ((void **) &text->data);
|
|
|
152 SETPOS (bs,offset); /* offset the string */
|
|
|
153 /* make free storage space in sized text */
|
|
|
154 text->data = (unsigned char *) fs_get ((size_t) (text->size = size) + 1);
|
|
|
155 while (i < size) text->data[i++] = SNX (bs);
|
|
|
156 text->data[i] = '\0'; /* tie off text */
|
|
|
157 return (char *) text->data; /* convenience return */
|
|
|
158 }
|
|
|
159
|
|
|
160 /* Returns index of rightmost bit in word
|
|
|
161 * Accepts: pointer to a 32 bit value
|
|
|
162 * Returns: -1 if word is 0, else index of rightmost bit
|
|
|
163 *
|
|
|
164 * Bit is cleared in the word
|
|
|
165 */
|
|
|
166
|
|
|
167 unsigned long find_rightmost_bit (unsigned long *valptr)
|
|
|
168 {
|
|
|
169 unsigned long value = *valptr;
|
|
|
170 unsigned long bit = 0;
|
|
|
171 if (!(value & 0xffffffff)) return 0xffffffff;
|
|
|
172 /* binary search for rightmost bit */
|
|
|
173 if (!(value & 0xffff)) value >>= 16, bit += 16;
|
|
|
174 if (!(value & 0xff)) value >>= 8, bit += 8;
|
|
|
175 if (!(value & 0xf)) value >>= 4, bit += 4;
|
|
|
176 if (!(value & 0x3)) value >>= 2, bit += 2;
|
|
|
177 if (!(value & 0x1)) value >>= 1, bit += 1;
|
|
|
178 *valptr ^= (1 << bit); /* clear specified bit */
|
|
|
179 return bit;
|
|
|
180 }
|
|
|
181
|
|
|
182
|
|
|
183 /* Return minimum of two integers
|
|
|
184 * Accepts: integer 1
|
|
|
185 * integer 2
|
|
|
186 * Returns: minimum
|
|
|
187 */
|
|
|
188
|
|
|
189 long min (long i,long j)
|
|
|
190 {
|
|
|
191 return ((i < j) ? i : j);
|
|
|
192 }
|
|
|
193
|
|
|
194
|
|
|
195 /* Return maximum of two integers
|
|
|
196 * Accepts: integer 1
|
|
|
197 * integer 2
|
|
|
198 * Returns: maximum
|
|
|
199 */
|
|
|
200
|
|
|
201 long max (long i,long j)
|
|
|
202 {
|
|
|
203 return ((i > j) ? i : j);
|
|
|
204 }
|
|
|
205
|
|
|
206 /* Search, case-insensitive for ASCII characters
|
|
|
207 * Accepts: base string
|
|
|
208 * length of base string
|
|
|
209 * pattern string
|
|
|
210 * length of pattern string
|
|
|
211 * Returns: T if pattern exists inside base, else NIL
|
|
|
212 */
|
|
|
213
|
|
|
214 long search (unsigned char *base,long basec,unsigned char *pat,long patc)
|
|
|
215 {
|
|
|
216 long i,j,k;
|
|
|
217 int c;
|
|
|
218 unsigned char mask[256];
|
|
|
219 static unsigned char alphatab[256] = {
|
|
|
220 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
221 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
222 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
223 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
224 255,223,223,223,223,223,223,223,223,223,223,223,223,223,223,223,
|
|
|
225 223,223,223,223,223,223,223,223,223,223,223,255,255,255,255,255,
|
|
|
226 255,223,223,223,223,223,223,223,223,223,223,223,223,223,223,223,
|
|
|
227 223,223,223,223,223,223,223,223,223,223,223,255,255,255,255,255,
|
|
|
228 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
229 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
230 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
231 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
232 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
233 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
234 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
|
|
|
235 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255
|
|
|
236 };
|
|
|
237 /* validate arguments */
|
|
|
238 if (base && (basec > 0) && pat && (basec >= patc)) {
|
|
|
239 if (patc <= 0) return T; /* empty pattern always succeeds */
|
|
|
240 memset (mask,0,256); /* initialize search validity mask */
|
|
|
241 for (i = 0; i < patc; i++) if (!mask[c = pat[i]]) {
|
|
|
242 /* mark single character if non-alphabetic */
|
|
|
243 if (alphatab[c] & 0x20) mask[c] = T;
|
|
|
244 /* else mark both cases */
|
|
|
245 else mask[c & 0xdf] = mask[c | 0x20] = T;
|
|
|
246 }
|
|
|
247 /* Boyer-Moore type search */
|
|
|
248 for (i = --patc; i < basec; i += (mask[c] ? 1 : (j + 1)))
|
|
|
249 for (j = patc,c = base[k = i]; !((c ^ pat[j]) & alphatab[c]);
|
|
|
250 j--,c = base[--k])
|
|
|
251 if (!j) return T; /* found a match! */
|
|
|
252 }
|
|
|
253 return NIL; /* pattern not found */
|
|
|
254 }
|
|
|
255
|
|
|
256 /* Boyer-Moore string search
|
|
|
257 * Accepts: base string
|
|
|
258 * length of base string
|
|
|
259 * pattern string
|
|
|
260 * length of pattern string
|
|
|
261 * Returns: T if pattern exists inside base, else NIL
|
|
|
262 */
|
|
|
263
|
|
|
264 long ssearch (unsigned char *base,long basec,unsigned char *pat,long patc)
|
|
|
265 {
|
|
|
266 long i,j,k;
|
|
|
267 int c;
|
|
|
268 unsigned char mask[256];
|
|
|
269 /* validate arguments */
|
|
|
270 if (base && (basec > 0) && pat && (basec >= patc)) {
|
|
|
271 if (patc <= 0) return T; /* empty pattern always succeeds */
|
|
|
272 memset (mask,0,256); /* initialize search validity mask */
|
|
|
273 for (i = 0; i < patc; i++) mask[pat[i]] = T;
|
|
|
274 /* Boyer-Moore type search */
|
|
|
275 for (i = --patc, c = pat[i]; i < basec; i += (mask[c] ? 1 : (j + 1)))
|
|
|
276 for (j = patc,c = base[k = i]; (c == pat[j]); j--,c = base[--k])
|
|
|
277 if (!j) return T; /* found a match! */
|
|
|
278 }
|
|
|
279 return NIL; /* pattern not found */
|
|
|
280 }
|
|
|
281
|
|
|
282 /* Create a hash table
|
|
|
283 * Accepts: size of new table (note: should be a prime)
|
|
|
284 * Returns: hash table
|
|
|
285 */
|
|
|
286
|
|
|
287 HASHTAB *hash_create (size_t size)
|
|
|
288 {
|
|
|
289 size_t i = sizeof (size_t) + size * sizeof (HASHENT *);
|
|
|
290 HASHTAB *ret = (HASHTAB *) memset (fs_get (i),0,i);
|
|
|
291 ret->size = size;
|
|
|
292 return ret;
|
|
|
293 }
|
|
|
294
|
|
|
295
|
|
|
296 /* Destroy hash table
|
|
|
297 * Accepts: hash table
|
|
|
298 */
|
|
|
299
|
|
|
300 void hash_destroy (HASHTAB **hashtab)
|
|
|
301 {
|
|
|
302 if (*hashtab) {
|
|
|
303 hash_reset (*hashtab); /* reset hash table */
|
|
|
304 fs_give ((void **) hashtab);
|
|
|
305 }
|
|
|
306 }
|
|
|
307
|
|
|
308
|
|
|
309 /* Reset hash table
|
|
|
310 * Accepts: hash table
|
|
|
311 */
|
|
|
312
|
|
|
313 void hash_reset (HASHTAB *hashtab)
|
|
|
314 {
|
|
|
315 size_t i;
|
|
|
316 HASHENT *ent,*nxt;
|
|
|
317 /* free each hash entry */
|
|
|
318 for (i = 0; i < hashtab->size; i++) if (ent = hashtab->table[i])
|
|
|
319 for (hashtab->table[i] = NIL; ent; ent = nxt) {
|
|
|
320 nxt = ent->next; /* get successor */
|
|
|
321 fs_give ((void **) &ent); /* flush this entry */
|
|
|
322 }
|
|
|
323 }
|
|
|
324
|
|
|
325 /* Calculate index into hash table
|
|
|
326 * Accepts: hash table
|
|
|
327 * entry name
|
|
|
328 * Returns: index
|
|
|
329 */
|
|
|
330
|
|
|
331 unsigned long hash_index (HASHTAB *hashtab,char *key)
|
|
|
332 {
|
|
|
333 unsigned long i,ret;
|
|
|
334 /* polynomial of letters of the word */
|
|
|
335 for (ret = 0; i = (unsigned int) *key++; ret += i) ret *= HASHMULT;
|
|
|
336 return ret % (unsigned long) hashtab->size;
|
|
|
337 }
|
|
|
338
|
|
|
339
|
|
|
340 /* Look up name in hash table
|
|
|
341 * Accepts: hash table
|
|
|
342 * key
|
|
|
343 * Returns: associated data
|
|
|
344 */
|
|
|
345
|
|
|
346 void **hash_lookup (HASHTAB *hashtab,char *key)
|
|
|
347 {
|
|
|
348 HASHENT *ret;
|
|
|
349 for (ret = hashtab->table[hash_index (hashtab,key)]; ret; ret = ret->next)
|
|
|
350 if (!strcmp (key,ret->name)) return ret->data;
|
|
|
351 return NIL;
|
|
|
352 }
|
|
|
353
|
|
|
354 /* Add entry to hash table
|
|
|
355 * Accepts: hash table
|
|
|
356 * key
|
|
|
357 * associated data
|
|
|
358 * number of extra data slots
|
|
|
359 * Returns: hash entry
|
|
|
360 * Caller is responsible for ensuring that entry isn't already in table
|
|
|
361 */
|
|
|
362
|
|
|
363 HASHENT *hash_add (HASHTAB *hashtab,char *key,void *data,long extra)
|
|
|
364 {
|
|
|
365 unsigned long i = hash_index (hashtab,key);
|
|
|
366 size_t j = sizeof (HASHENT) + (extra * sizeof (void *));
|
|
|
367 HASHENT *ret = (HASHENT *) memset (fs_get (j),0,j);
|
|
|
368 ret->next = hashtab->table[i];/* insert as new head in this index */
|
|
|
369 ret->name = key; /* set up hash key */
|
|
|
370 ret->data[0] = data; /* and first data */
|
|
|
371 return hashtab->table[i] = ret;
|
|
|
372 }
|
|
|
373
|
|
|
374
|
|
|
375 /* Look up name in hash table
|
|
|
376 * Accepts: hash table
|
|
|
377 * key
|
|
|
378 * associated data
|
|
|
379 * number of extra data slots
|
|
|
380 * Returns: associated data
|
|
|
381 */
|
|
|
382
|
|
|
383 void **hash_lookup_and_add (HASHTAB *hashtab,char *key,void *data,long extra)
|
|
|
384 {
|
|
|
385 HASHENT *ret;
|
|
|
386 unsigned long i = hash_index (hashtab,key);
|
|
|
387 size_t j = sizeof (HASHENT) + (extra * sizeof (void *));
|
|
|
388 for (ret = hashtab->table[i]; ret; ret = ret->next)
|
|
|
389 if (!strcmp (key,ret->name)) return ret->data;
|
|
|
390 ret = (HASHENT *) memset (fs_get (j),0,j);
|
|
|
391 ret->next = hashtab->table[i];/* insert as new head in this index */
|
|
|
392 ret->name = key; /* set up hash key */
|
|
|
393 ret->data[0] = data; /* and first data */
|
|
|
394 return (hashtab->table[i] = ret)->data;
|
|
|
395 }
|
|
|
396
|
|
|
397 /* Convert two hex characters into byte
|
|
|
398 * Accepts: char for high nybble
|
|
|
399 * char for low nybble
|
|
|
400 * Returns: byte
|
|
|
401 *
|
|
|
402 * Arguments must be isxdigit validated
|
|
|
403 */
|
|
|
404
|
|
|
405 unsigned char hex2byte (unsigned char c1,unsigned char c2)
|
|
|
406 {
|
|
|
407 /* merge the two nybbles */
|
|
|
408 return ((c1 -= (isdigit (c1) ? '0' : ((c1 <= 'Z') ? 'A' : 'a') - 10)) << 4) +
|
|
|
409 (c2 - (isdigit (c2) ? '0' : ((c2 <= 'Z') ? 'A' : 'a') - 10));
|
|
|
410 }
|
|
|
411
|
|
|
412
|
|
|
413 /* Compare two unsigned longs
|
|
|
414 * Accepts: first value
|
|
|
415 * second value
|
|
|
416 * Returns: -1 if l1 < l2, 0 if l1 == l2, 1 if l1 > l2
|
|
|
417 */
|
|
|
418
|
|
|
419 int compare_ulong (unsigned long l1,unsigned long l2)
|
|
|
420 {
|
|
|
421 if (l1 < l2) return -1;
|
|
|
422 if (l1 > l2) return 1;
|
|
|
423 return 0;
|
|
|
424 }
|
|
|
425
|
|
|
426
|
|
|
427 /* Compare two unsigned chars, case-independent
|
|
|
428 * Accepts: first value
|
|
|
429 * second value
|
|
|
430 * Returns: -1 if c1 < c2, 0 if c1 == c2, 1 if c1 > c2
|
|
|
431 *
|
|
|
432 * Don't use isupper/tolower since this function must be ASCII only.
|
|
|
433 */
|
|
|
434
|
|
|
435 int compare_uchar (unsigned char c1,unsigned char c2)
|
|
|
436 {
|
|
|
437 return compare_ulong (((c1 >= 'A') && (c1 <= 'Z')) ? c1 + ('a' - 'A') : c1,
|
|
|
438 ((c2 >= 'A') && (c2 <= 'Z')) ? c2 + ('a' - 'A') : c2);
|
|
|
439 }
|
|
|
440
|
|
|
441 /* Compare two case-independent ASCII strings
|
|
|
442 * Accepts: first string
|
|
|
443 * second string
|
|
|
444 * Returns: -1 if s1 < s2, 0 if s1 == s2, 1 if s1 > s2
|
|
|
445 */
|
|
|
446
|
|
|
447 int compare_cstring (unsigned char *s1,unsigned char *s2)
|
|
|
448 {
|
|
|
449 int i;
|
|
|
450 if (!s1) return s2 ? -1 : 0; /* empty string cases */
|
|
|
451 else if (!s2) return 1;
|
|
|
452 for (; *s1 && *s2; s1++,s2++) if (i = (compare_uchar (*s1,*s2))) return i;
|
|
|
453 if (*s1) return 1; /* first string is longer */
|
|
|
454 return *s2 ? -1 : 0; /* second string longer : strings identical */
|
|
|
455 }
|
|
|
456
|
|
|
457
|
|
|
458 /* Compare case-independent string with sized text
|
|
|
459 * Accepts: first string
|
|
|
460 * sized text
|
|
|
461 * Returns: -1 if s1 < s2, 0 if s1 == s2, 1 if s1 > s2
|
|
|
462 */
|
|
|
463
|
|
|
464 int compare_csizedtext (unsigned char *s1,SIZEDTEXT *s2)
|
|
|
465 {
|
|
|
466 int i;
|
|
|
467 unsigned char *s;
|
|
|
468 unsigned long j;
|
|
|
469 if (!s1) return s2 ? -1 : 0; /* null string cases */
|
|
|
470 else if (!s2) return 1;
|
|
|
471 for (s = (char *) s2->data,j = s2->size; *s1 && j; ++s1,++s,--j)
|
|
|
472 if (i = (compare_uchar (*s1,*s))) return i;
|
|
|
473 if (*s1) return 1; /* first string is longer */
|
|
|
474 return j ? -1 : 0; /* second string longer : strings identical */
|
|
|
475 }
|
