--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/c-client/misc.c	Mon Sep 14 15:17:45 2009 +0900
@@ -0,0 +1,475 @@
+/* ========================================================================
+ * 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 */
+}