Mercurial > hgrepos > hgweb.cgi > imapext
comparison src/c-client/misc.c @ 0:ada5e610ab86
imap-2007e
author | yuuji@gentei.org |
---|---|
date | Mon, 14 Sep 2009 15:17:45 +0900 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:ada5e610ab86 |
---|---|
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 } |