utils.cc

无线个域网（WPAN）就是在个人周围空间形成的无线网络

/* 
 * COPYRIGHT AND DISCLAIMER
 * 
 * Copyright (C) 1996-1997 by the Regents of the University of California.
 *
 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
 * OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY DERIVATIVES THEREOF,
 * EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT. THIS SOFTWARE IS
 * PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE NO
 * OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
 * MODIFICATIONS.
 *
 * For inquiries email Steve Gribble <[e-mail]>.
 */


/*
 * utils.c --
 *
 * This file provides utility routines for the core icp functions.
 * Included are:
 *
 *   o linked list routines
 *   o hash table routines
 *   o socket convenience routines
 *   o time munging routines
 *   o thread-safe strtok
 *   o thread-unsafe AVL trees (with dorky deletion)
 *
 * $Id: utils.cc,v 1.4 2002/05/23 21:26:03 buchheim Exp $
 * 
 */

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <sys/time.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <fcntl.h>
#include <sys/ioctl.h>
#include <errno.h>
#include <netdb.h>
#ifdef _AIX
#include <sys/select.h>
#endif

#include "utils.h"

/*
 *  Case-insensitive version of strstr()
 */


const char *
dumb_strcasestr(const char *string, const char *substr)
{
  int str_len, substr_len, cmplen, i;
  const char *ptr;

  str_len = strlen(string);
  substr_len = strlen(substr);
  cmplen = str_len - substr_len + 1;

  for (ptr = string, i=0; i<cmplen; i++, ptr++) {
    if (strncasecmp(ptr, substr, substr_len) == 0)
      return ptr;
  }
  return NULL;
}


/*
 ************* Dump out the hexification of the buffer ***********
 */
void dump_buf(FILE *std, char *buf, int retlen)
{
  int i, j;

  for (i=0; i<retlen/5; i++) {
    for (j=0; j<5; j++) {
      fprintf(std, "%.02x ", *(buf + (unsigned) 5*i + j));
    }
    fprintf(std, "     ");
    for (j=0; j<5; j++) {
      fprintf(std, "%c ", *(buf + (unsigned) 5*i + j));
    }
    fprintf(std, "\n");
  }
  if (retlen % 5 != 0) {
    for (j=0; j < retlen % 5; j++) {
      fprintf(std, "%.02x ", *(buf + (unsigned) 5*(retlen/5) + j));
    }
    fprintf(std, "     ");
    for (j=0; j<5; j++) {
      fprintf(std, "%c ", *(buf + (unsigned) 5*i + j));
    }
    fprintf(std, "\n");
  }
}

/*
 ************* Time munging utilities *****************
 */

tv_time  tv_timeadd(tv_time t1, tv_time t2)
{
  tv_time ret;

  ret.tv_sec = t1.tv_sec + t2.tv_sec;
  ret.tv_usec = t1.tv_usec + t2.tv_usec;
  if (ret.tv_usec > 1000000L) {
    ret.tv_sec += 1;
    ret.tv_usec -= 1000000L;
  }
  return ret;
}

tv_time  tv_timesub(tv_time t1, tv_time t2)
{
  tv_time ret;

  if (t2.tv_usec > t1.tv_usec) {
    t1.tv_usec += 1000000;
    t2.tv_sec += 1;
  }
  ret.tv_sec = t1.tv_sec - t2.tv_sec;
  ret.tv_usec = t1.tv_usec - t2.tv_usec;
  return ret;
}

tv_time  tv_timemul(tv_time t1, double mult)
{
  tv_time ret;
  double  rsec;
  double  rusec;

  rsec = mult * ((double) t1.tv_sec);
  rusec = mult * ((double) t1.tv_usec);

  ret.tv_sec = (long)rsec;
  ret.tv_usec = (long)rusec;

  ret.tv_usec += (long)((double) 1000000.0 * (rsec - (double) ret.tv_sec));
  while (ret.tv_usec > 1000000) {
    ret.tv_usec -= 1000000;
    ret.tv_sec += 1;
  }
  return ret;
}

int      tv_timecmp(tv_time t1, tv_time t2)
{
  if (t1.tv_sec > t2.tv_sec)
     return 1;
  if (t1.tv_sec < t2.tv_sec)
     return -1;
  if (t1.tv_usec > t2.tv_usec)
     return 1;
  if (t1.tv_usec < t2.tv_usec)
     return -1;
  return 0;
}

ts_time  ts_timeadd(ts_time t1, ts_time t2)
{
  ts_time ret;

  ret.tv_sec = t1.tv_sec + t2.tv_sec;
  ret.tv_nsec = t1.tv_nsec + t2.tv_nsec;
  if (ret.tv_nsec > 1000000000L) {
    ret.tv_sec += 1;
    ret.tv_nsec -= 1000000000L;
  }
  return ret;
}
ts_time  ts_timesub(ts_time t1, ts_time t2)
{
  ts_time ret;

  if (t2.tv_nsec > t1.tv_nsec) {
    t1.tv_nsec += 1000000000;
    t2.tv_sec += 1;
  }
  ret.tv_sec = t1.tv_sec - t2.tv_sec;
  ret.tv_nsec = t1.tv_nsec - t2.tv_nsec;
  return ret;
}

ts_time  ts_timemul(ts_time t1, double mult)
{
  ts_time ret;
  double  rsec;
  double  rnsec;

  rsec = mult * ((double) t1.tv_sec);
  rnsec = mult * ((double) t1.tv_nsec);

  ret.tv_sec = (long)rsec;
  ret.tv_nsec = (long)rnsec;

  ret.tv_nsec += (long)((double) 1000000000.0 * (rsec - (double) ret.tv_sec));
  while (ret.tv_nsec > 1000000000) {
    ret.tv_nsec -= 1000000000;
    ret.tv_sec += 1;
  }
  return ret;
}

int      ts_timecmp(ts_time t1, ts_time t2)
{
 if (t1.tv_sec > t2.tv_sec)
     return 1;
  if (t1.tv_sec < t2.tv_sec)
     return -1;
  if (t1.tv_nsec > t2.tv_nsec)
     return 1;
  if (t1.tv_nsec < t2.tv_nsec)
     return -1;
  return 0;
}

/*
 ************* Thread-safe strtok routines and state *************
 */

ts_strtok_state *ts_strtok_init(char *string)
{
  ts_strtok_state *retval;

  if (string == NULL)
    return NULL;

  retval = (ts_strtok_state *) malloc(sizeof(ts_strtok_state));
  if (retval == NULL)
    return NULL;

  retval->string_dupe = strdup(string);
  if (retval->string_dupe == NULL) {
    free(retval);
    return NULL;
  }
  retval->nxt_ptr = retval->string_dupe;
  retval->chars_remaining = strlen(retval->string_dupe);

  return retval;
}

char *ts_strtok(char *matching, ts_strtok_state *state)
{
  int len1, len2;
  char *tmpo;

  if ((matching == NULL) || (state == NULL) || (state->chars_remaining <= 0))
    return NULL;

  len1 = strspn(state->nxt_ptr, matching);
  if (len1 > state->chars_remaining) {
    return NULL;
  }

  tmpo = state->nxt_ptr + (unsigned) len1;
  len2 = strcspn(tmpo, matching);
  if (len2+len1 > state->chars_remaining) {
    return NULL;
  }
  *(tmpo+len2) = '\0';
  state->nxt_ptr = tmpo + len2 + 1;       /* +1 for the null */
  state->chars_remaining -= len1+len2+1;  /* +1 for the null */
  return tmpo;
}

int ts_strtok_finish(ts_strtok_state *state)
{
  if (state) {
    if (state->string_dupe)
      free(state->string_dupe);
    free(state);
  }
  return 1;
}

/************* A really dumb implementation of strnstr ***********/
char *dumb_strnstr(char *str, char *substr, int n)
{
  int i, substrlen, ml;
  char *tmp;

  substrlen = strlen(substr);

  for (i=0,tmp=str; i<=n-substrlen; i++, tmp++) {
    if (*tmp == '\0')
      return NULL;
    if ( (ml = memcmp(tmp, substr, substrlen)) == 0)
      return tmp;
  }
  return NULL;
}

/********* Socket convenience routines ***********/

int correct_write(int s, char *data, int len)
{
  int sofar, ret;
  char *tmp;

  if (len == -1) 
    len = strlen(data);
  
  sofar = 0;
  while (sofar != len) {
    tmp = data + (unsigned long) sofar;
    ret = write(s, tmp, len-sofar);
    if (ret <= 0) {
      if (! ((ret == -1) && ((errno == EAGAIN) || (errno == EINTR))) )
	/* BUG:: What if another thread generates an error and trounces errno? */
	return ret;
    } else
      sofar += ret;
  }
  return len;
}

int correct_read(int s, char *data, int len)
{
  int sofar, ret;
  char *tmp;

  sofar = 0;
  while(sofar != len) {
    tmp = data + (unsigned long) sofar;
    ret = read(s, tmp, len-sofar);
    if (ret <= 0) {
      if (! ((ret == -1) && ((errno == EAGAIN) || (errno == EINTR))) )
	/* BUG:: What if another thread generates an error and trounces errno? */
	return ret;
    } else
      sofar += ret;
  }
  return len;
}

/********* Linked-list utilities ***********/

#define LL_HEAPSIZE 50
static ll heap_o_ll = NULL;   /* Heap of free nodes for alloc and dealloc */

/* Some private functions */
ll   Allocate_ll(void);
void Free_ll(ll freeMe);

int ll_add_to_end(ll *addToMe, void *data)
{
   ll temp;

   temp = *addToMe;
   if (temp == NULL)
   {
      *addToMe = temp = Allocate_ll();
      temp->data = data;
      temp->prev = temp->next = NULL;
      return 1;
   }

   while (temp->next != NULL)
     temp = temp->next;

   temp->next = Allocate_ll();
   (temp->next)->prev = temp;
   (temp->next)->next = NULL;
   (temp->next)->data = data;
   return 1;
}

int ll_add_to_start(ll *addToMe, void *data)
{
   ll temp;

   temp = *addToMe;
   if (temp == NULL)
   {
      *addToMe = temp = Allocate_ll();
      temp->data = data;
      temp->prev = temp->next = NULL; 
      return 1;
   }

   temp->prev = Allocate_ll();
   (temp->prev)->next = temp;
   (temp->prev)->prev = NULL;
   (temp->prev)->data = data;
   *addToMe = temp->prev;

   return 1;

}

ll  ll_find(ll *findInMe, void *data, int (*compare)(void *d1, void *d2))
{
   ll temp = *findInMe;

   while (temp != NULL)
   {
     if (compare(data, temp->data) == 0)  /* ie the same */
        return temp;
     
     temp = temp->next;
   }
   return temp;
}

int ll_sorted_insert(ll *insertme, void *data, 
		     int (*compare)(void *d1, void *d2))
{
  ll temp = *insertme, addEl;

  while (temp != NULL) {
    if (compare(data, temp->data) <= 0) {/* ie. the same or smaller */
      /* insert before temp */
      addEl = Allocate_ll();
      addEl->data = data;
      addEl->prev = temp->prev;
      addEl->next = temp;
      temp->prev = addEl;
      if (addEl->prev == NULL)
	*insertme = addEl;
      else
	(addEl->prev)->next = addEl;
      return 1;
    }
    temp = temp->next;
  }
  
  /* We hit the end, so add to the end */
  return ll_add_to_end(insertme, data);
}

int  ll_del(ll *delFromMe, void *data, int (*compare)(void *d1, void *d2),
            void (*nukeElement)(void *nukeMe))
{
   ll temp = *delFromMe;

   while (temp != NULL)
   {
      if (compare(data, temp->data) == 0)  /* ie the same */
      {
         if (temp->prev != NULL)
           (temp->prev)->next = temp->next;

         if (temp->next != NULL)
           (temp->next)->prev = temp->prev;

         if (temp == *delFromMe)
            *delFromMe = temp->next;

         if (nukeElement != NULL)
            nukeElement(temp->data);
         Free_ll(temp);
         return 1;
      }
      temp = temp->next;
   }
   return 0;
}

int ll_delfirst(ll *delFromMe, void (*nukeElement)(void *nukeMe))
{
   ll temp = *delFromMe;

   if (temp == NULL)
      return 0;

   if (temp->prev != NULL)
     (temp->prev)->next = temp->next;

   if (temp->next != NULL)
     (temp->next)->prev = temp->prev;

   if (temp == *delFromMe)
     *delFromMe = temp->next;

   if (nukeElement != NULL)
     nukeElement(temp->data);
   Free_ll(temp);
   return 1;
}

int ll_destroy(ll *destroyMe, void (*nukeElement)(void *nukeMe))
{
   ll temp = *destroyMe, next;

   while (temp != NULL)
   {
      next = temp->next;
      if (nukeElement != NULL)
         nukeElement(temp->data);
      Free_ll(temp);
      temp = next;
   }
   *destroyMe = NULL;
   return 1;
}

ll   Allocate_ll(void)
{
   int counter;
   ll  temp_pointer;

   /* if heap is null, am out of ll elements and must allocate more */
   if (heap_o_ll == NULL)
   {
      heap_o_ll = (ll_node *) malloc(LL_HEAPSIZE * sizeof(ll_node));
      if (heap_o_ll == NULL)
      {
         fprintf(stderr, "Out of memory in Allocate_ll!\n");
         exit(1);
      }
      for (counter=0; counter < LL_HEAPSIZE - 1; counter++)
      {
          (heap_o_ll + counter)->data = NULL;
          (heap_o_ll + counter)->prev = NULL;
          (heap_o_ll + counter)->next = (heap_o_ll + counter + 1);
      }