Edit File: misc.c
/* ======================================================================== * Copyright 1988-2006 University of Washington * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * * ======================================================================== */ /* * Program: Miscellaneous utility routines * * Author: Mark Crispin * Networks and Distributed Computing * Computing & Communications * University of Washington * Administration Building, AG-44 * Seattle, WA 98195 * Internet: MRC@CAC.Washington.EDU * * Date: 5 July 1988 * Last Edited: 6 December 2006 * * This original version of this file is * Copyright 1988 Stanford University * and was developed in the Symbolic Systems Resources Group of the Knowledge * Systems Laboratory at Stanford University in 1987-88, and was funded by the * Biomedical Research Technology Program of the NationalInstitutes of Health * under grant number RR-00785. */ #include <ctype.h> #include "c-client.h" /* Convert ASCII string to all uppercase * Accepts: string pointer * Returns: string pointer * * Don't use islower/toupper since this function must be ASCII only. */ unsigned char *ucase (unsigned char *s) { unsigned char *t; /* if lowercase covert to upper */ for (t = s; *t; t++) if ((*t >= 'a') && (*t <= 'z')) *t -= ('a' - 'A'); return s; /* return string */ } /* Convert string to all lowercase * Accepts: string pointer * Returns: string pointer * * Don't use isupper/tolower since this function must be ASCII only. */ unsigned char *lcase (unsigned char *s) { unsigned char *t; /* if uppercase covert to lower */ for (t = s; *t; t++) if ((*t >= 'A') && (*t <= 'Z')) *t += ('a' - 'A'); return s; /* return string */ } /* Copy string to free storage * Accepts: source string * Returns: free storage copy of string */ char *cpystr (const char *string) { return string ? strcpy ((char *) fs_get (1 + strlen (string)),string) : NIL; } /* Copy text/size to free storage as sized text * Accepts: destination sized text * pointer to source text * size of source text * Returns: text as a char * */ char *cpytxt (SIZEDTEXT *dst,char *text,unsigned long size) { /* flush old space */ if (dst->data) fs_give ((void **) &dst->data); /* copy data in sized text */ memcpy (dst->data = (unsigned char *) fs_get ((size_t) (dst->size = size) + 1),text,(size_t) size); dst->data[size] = '\0'; /* tie off text */ return (char *) dst->data; /* convenience return */ } /* Copy sized text to free storage as sized text * Accepts: destination sized text * source sized text * Returns: text as a char * */ char *textcpy (SIZEDTEXT *dst,SIZEDTEXT *src) { /* flush old space */ if (dst->data) fs_give ((void **) &dst->data); /* copy data in sized text */ memcpy (dst->data = (unsigned char *) fs_get ((size_t) (dst->size = src->size) + 1), src->data,(size_t) src->size); dst->data[dst->size] = '\0'; /* tie off text */ return (char *) dst->data; /* convenience return */ } /* Copy stringstruct to free storage as sized text * Accepts: destination sized text * source stringstruct * Returns: text as a char * */ char *textcpystring (SIZEDTEXT *text,STRING *bs) { unsigned long i = 0; /* clear old space */ if (text->data) fs_give ((void **) &text->data); /* make free storage space in sized text */ text->data = (unsigned char *) fs_get ((size_t) (text->size = SIZE (bs)) +1); while (i < text->size) text->data[i++] = SNX (bs); text->data[i] = '\0'; /* tie off text */ return (char *) text->data; /* convenience return */ } /* Copy stringstruct from offset to free storage as sized text * Accepts: destination sized text * source stringstruct * offset into stringstruct * size of source text * Returns: text as a char * */ char *textcpyoffstring (SIZEDTEXT *text,STRING *bs,unsigned long offset, unsigned long size) { unsigned long i = 0; /* clear old space */ if (text->data) fs_give ((void **) &text->data); SETPOS (bs,offset); /* offset the string */ /* make free storage space in sized text */ text->data = (unsigned char *) fs_get ((size_t) (text->size = size) + 1); while (i < size) text->data[i++] = SNX (bs); text->data[i] = '\0'; /* tie off text */ return (char *) text->data; /* convenience return */ } /* Returns index of rightmost bit in word * Accepts: pointer to a 32 bit value * Returns: -1 if word is 0, else index of rightmost bit * * Bit is cleared in the word */ unsigned long find_rightmost_bit (unsigned long *valptr) { unsigned long value = *valptr; unsigned long bit = 0; if (!(value & 0xffffffff)) return 0xffffffff; /* binary search for rightmost bit */ if (!(value & 0xffff)) value >>= 16, bit += 16; if (!(value & 0xff)) value >>= 8, bit += 8; if (!(value & 0xf)) value >>= 4, bit += 4; if (!(value & 0x3)) value >>= 2, bit += 2; if (!(value & 0x1)) value >>= 1, bit += 1; *valptr ^= (1 << bit); /* clear specified bit */ return bit; } /* Return minimum of two integers * Accepts: integer 1 * integer 2 * Returns: minimum */ long min (long i,long j) { return ((i < j) ? i : j); } /* Return maximum of two integers * Accepts: integer 1 * integer 2 * Returns: maximum */ long max (long i,long j) { return ((i > j) ? i : j); } /* Search, case-insensitive for ASCII characters * Accepts: base string * length of base string * pattern string * length of pattern string * Returns: T if pattern exists inside base, else NIL */ long search (unsigned char *base,long basec,unsigned char *pat,long patc) { long i,j,k; int c; unsigned char mask[256]; static unsigned char alphatab[256] = { 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 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,255,255,255,255,255, 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,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255, 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255 }; /* validate arguments */ if (base && (basec > 0) && pat && (basec >= patc)) { if (patc <= 0) return T; /* empty pattern always succeeds */ memset (mask,0,256); /* initialize search validity mask */ for (i = 0; i < patc; i++) if (!mask[c = pat[i]]) { /* mark single character if non-alphabetic */ if (alphatab[c] & 0x20) mask[c] = T; /* else mark both cases */ else mask[c & 0xdf] = mask[c | 0x20] = T; } /* Boyer-Moore type search */ for (i = --patc; i < basec; i += (mask[c] ? 1 : (j + 1))) for (j = patc,c = base[k = i]; !((c ^ pat[j]) & alphatab[c]); j--,c = base[--k]) if (!j) return T; /* found a match! */ } return NIL; /* pattern not found */ } /* Boyer-Moore string search * Accepts: base string * length of base string * pattern string * length of pattern string * Returns: T if pattern exists inside base, else NIL */ long ssearch (unsigned char *base,long basec,unsigned char *pat,long patc) { long i,j,k; int c; unsigned char mask[256]; /* validate arguments */ if (base && (basec > 0) && pat && (basec >= patc)) { if (patc <= 0) return T; /* empty pattern always succeeds */ memset (mask,0,256); /* initialize search validity mask */ for (i = 0; i < patc; i++) mask[pat[i]] = T; /* Boyer-Moore type search */ for (i = --patc, c = pat[i]; i < basec; i += (mask[c] ? 1 : (j + 1))) for (j = patc,c = base[k = i]; (c == pat[j]); j--,c = base[--k]) if (!j) return T; /* found a match! */ } return NIL; /* pattern not found */ } /* Create a hash table * Accepts: size of new table (note: should be a prime) * Returns: hash table */ HASHTAB *hash_create (size_t size) { size_t i = sizeof (size_t) + size * sizeof (HASHENT *); HASHTAB *ret = (HASHTAB *) memset (fs_get (i),0,i); ret->size = size; return ret; } /* Destroy hash table * Accepts: hash table */ void hash_destroy (HASHTAB **hashtab) { if (*hashtab) { hash_reset (*hashtab); /* reset hash table */ fs_give ((void **) hashtab); } } /* Reset hash table * Accepts: hash table */ void hash_reset (HASHTAB *hashtab) { size_t i; HASHENT *ent,*nxt; /* free each hash entry */ for (i = 0; i < hashtab->size; i++) if (ent = hashtab->table[i]) for (hashtab->table[i] = NIL; ent; ent = nxt) { nxt = ent->next; /* get successor */ fs_give ((void **) &ent); /* flush this entry */ } } /* Calculate index into hash table * Accepts: hash table * entry name * Returns: index */ unsigned long hash_index (HASHTAB *hashtab,char *key) { unsigned long i,ret; /* polynomial of letters of the word */ for (ret = 0; i = (unsigned int) *key++; ret += i) ret *= HASHMULT; return ret % (unsigned long) hashtab->size; } /* Look up name in hash table * Accepts: hash table * key * Returns: associated data */ void **hash_lookup (HASHTAB *hashtab,char *key) { HASHENT *ret; for (ret = hashtab->table[hash_index (hashtab,key)]; ret; ret = ret->next) if (!strcmp (key,ret->name)) return ret->data; return NIL; } /* Add entry to hash table * Accepts: hash table * key * associated data * number of extra data slots * Returns: hash entry * Caller is responsible for ensuring that entry isn't already in table */ HASHENT *hash_add (HASHTAB *hashtab,char *key,void *data,long extra) { unsigned long i = hash_index (hashtab,key); size_t j = sizeof (HASHENT) + (extra * sizeof (void *)); HASHENT *ret = (HASHENT *) memset (fs_get (j),0,j); ret->next = hashtab->table[i];/* insert as new head in this index */ ret->name = key; /* set up hash key */ ret->data[0] = data; /* and first data */ return hashtab->table[i] = ret; } /* Look up name in hash table * Accepts: hash table * key * associated data * number of extra data slots * Returns: associated data */ void **hash_lookup_and_add (HASHTAB *hashtab,char *key,void *data,long extra) { HASHENT *ret; unsigned long i = hash_index (hashtab,key); size_t j = sizeof (HASHENT) + (extra * sizeof (void *)); for (ret = hashtab->table[i]; ret; ret = ret->next) if (!strcmp (key,ret->name)) return ret->data; ret = (HASHENT *) memset (fs_get (j),0,j); ret->next = hashtab->table[i];/* insert as new head in this index */ ret->name = key; /* set up hash key */ ret->data[0] = data; /* and first data */ return (hashtab->table[i] = ret)->data; } /* Convert two hex characters into byte * Accepts: char for high nybble * char for low nybble * Returns: byte * * Arguments must be isxdigit validated */ unsigned char hex2byte (unsigned char c1,unsigned char c2) { /* merge the two nybbles */ return ((c1 -= (isdigit (c1) ? '0' : ((c1 <= 'Z') ? 'A' : 'a') - 10)) << 4) + (c2 - (isdigit (c2) ? '0' : ((c2 <= 'Z') ? 'A' : 'a') - 10)); } /* Compare two unsigned longs * Accepts: first value * second value * Returns: -1 if l1 < l2, 0 if l1 == l2, 1 if l1 > l2 */ int compare_ulong (unsigned long l1,unsigned long l2) { if (l1 < l2) return -1; if (l1 > l2) return 1; return 0; } /* Compare two unsigned chars, case-independent * Accepts: first value * second value * Returns: -1 if c1 < c2, 0 if c1 == c2, 1 if c1 > c2 * * Don't use isupper/tolower since this function must be ASCII only. */ int compare_uchar (unsigned char c1,unsigned char c2) { return compare_ulong (((c1 >= 'A') && (c1 <= 'Z')) ? c1 + ('a' - 'A') : c1, ((c2 >= 'A') && (c2 <= 'Z')) ? c2 + ('a' - 'A') : c2); } /* Compare two case-independent ASCII strings * Accepts: first string * second string * Returns: -1 if s1 < s2, 0 if s1 == s2, 1 if s1 > s2 */ int compare_cstring (unsigned char *s1,unsigned char *s2) { int i; if (!s1) return s2 ? -1 : 0; /* empty string cases */ else if (!s2) return 1; for (; *s1 && *s2; s1++,s2++) if (i = (compare_uchar (*s1,*s2))) return i; if (*s1) return 1; /* first string is longer */ return *s2 ? -1 : 0; /* second string longer : strings identical */ } /* Compare case-independent string with sized text * Accepts: first string * sized text * Returns: -1 if s1 < s2, 0 if s1 == s2, 1 if s1 > s2 */ int compare_csizedtext (unsigned char *s1,SIZEDTEXT *s2) { int i; unsigned char *s; unsigned long j; if (!s1) return s2 ? -1 : 0; /* null string cases */ else if (!s2) return 1; for (s = (char *) s2->data,j = s2->size; *s1 && j; ++s1,++s,--j) if (i = (compare_uchar (*s1,*s))) return i; if (*s1) return 1; /* first string is longer */ return j ? -1 : 0; /* second string longer : strings identical */ }