imapext-2007
view src/c-client/misc.c @ 0:ada5e610ab86
imap-2007e
| author | yuuji@gentei.org |
|---|---|
| date | Mon, 14 Sep 2009 15:17:45 +0900 |
| parents | |
| children |
line source
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 */
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 */
37 #include <ctype.h>
38 #include "c-client.h"
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 */
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 }
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 */
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 }
71 /* Copy string to free storage
72 * Accepts: source string
73 * Returns: free storage copy of string
74 */
76 char *cpystr (const char *string)
77 {
78 return string ? strcpy ((char *) fs_get (1 + strlen (string)),string) : NIL;
79 }
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 */
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 }
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 */
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 }
119 /* Copy stringstruct to free storage as sized text
120 * Accepts: destination sized text
121 * source stringstruct
122 * Returns: text as a char *
123 */
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 }
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 */
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 }
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 */
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 }
183 /* Return minimum of two integers
184 * Accepts: integer 1
185 * integer 2
186 * Returns: minimum
187 */
189 long min (long i,long j)
190 {
191 return ((i < j) ? i : j);
192 }
195 /* Return maximum of two integers
196 * Accepts: integer 1
197 * integer 2
198 * Returns: maximum
199 */
201 long max (long i,long j)
202 {
203 return ((i > j) ? i : j);
204 }
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 */
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 }
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 */
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 }
282 /* Create a hash table
283 * Accepts: size of new table (note: should be a prime)
284 * Returns: hash table
285 */
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 }
296 /* Destroy hash table
297 * Accepts: hash table
298 */
300 void hash_destroy (HASHTAB **hashtab)
301 {
302 if (*hashtab) {
303 hash_reset (*hashtab); /* reset hash table */
304 fs_give ((void **) hashtab);
305 }
306 }
309 /* Reset hash table
310 * Accepts: hash table
311 */
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 }
325 /* Calculate index into hash table
326 * Accepts: hash table
327 * entry name
328 * Returns: index
329 */
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 }
340 /* Look up name in hash table
341 * Accepts: hash table
342 * key
343 * Returns: associated data
344 */
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 }
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 */
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 }
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 */
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 }
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 */
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 }
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 */
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 }
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 */
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 }
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 */
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 }
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 */
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 }