imap/src/c-client/misc.c

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