/*
* 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 <gribble@cs.berkeley.edu>.
*/
/*
* utils.h --
*
* Various utility functions - sockets, linked list, hash tables.
* $Id: utils.h,v 1.3 2002/05/23 21:26:03 buchheim Exp $
*
*/
#ifndef ICP_UTILS
#define ICP_UTILS
#ifdef __cplusplus
extern "C" {
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <fcntl.h>
#include <sys/ioctl.h>
#include "config.h"
#ifdef HAVE_TIME_H
#include <time.h>
#endif
#ifdef HAVE_SYS_TIME_H
#include <sys/time.h>
#endif
#ifdef HAVE_SYS_TIMERS_H
#include <sys/timers.h>
#endif
/*
************* Dump out the hexification of the buffer ***********
*/
void dump_buf(FILE *std, char *buf, int retlen);
/*
************* Time munging utilities *****************
*/
typedef struct timeval tv_time;
typedef struct timespec ts_time;
tv_time tv_timeadd(tv_time t1, tv_time t2);
tv_time tv_timesub(tv_time t1, tv_time t2);
tv_time tv_timemul(tv_time t1, double mult);
int tv_timecmp(tv_time t1, tv_time t2);
ts_time ts_timeadd(ts_time t1, ts_time t2);
ts_time ts_timesub(ts_time t1, ts_time t2);
ts_time ts_timemul(ts_time t1, double mult);
int ts_timecmp(ts_time t1, ts_time t2);
/*
************* Thread-safe strtok routines and state *************
*/
typedef struct ts_strtok_st {
char *string_dupe;
char *nxt_ptr;
int chars_remaining;
} ts_strtok_state;
/*
* Thread-safe strtok routines! Call ts_strtok_init with the string you
* want tokenized. It will return a pointer to some state. Then you
* call ts_strtok with the same semantics as strtok, more or less, except
* you have to pass this state around. When you're done, be sure to call
* ts_strtok_finish to clean up the state.
*
* ts_strtok_init returns NULL if it runs out of memory, or if it is passed
* a bogus string. ts_strtok returns NULL in case of error, ts_strtok_finish
* returns 1 on success, 0 on error.x
*/
ts_strtok_state *ts_strtok_init(char *string);
char *ts_strtok(char *matching, ts_strtok_state *state);
int ts_strtok_finish(ts_strtok_state *state);
/************* A really dumb implementation of strnstr and strcasestr ***********/
char *dumb_strnstr(char *str, char *substr, int n);
const char *dumb_strcasestr(const char *string, const char *substr);
/*
***************** Socket convenience utilities ****************
*/
/*
* correct_write will continue writing to a socket until it fails or
* until all len bytes have been written.
*/
int correct_write(int s, char *data, int len);
/*
* correct_read is like correct_write, but does a read.
*/
int correct_read(int s, char *data, int len);
/*
***************** Linked-list routines ****************
*/
/*
* the "ll_node" structure contains a node of a linked list. Note that
* a NULL "ll" type implies an empty linked-list.
*/
typedef struct ll_st {
void *data;
struct ll_st *next;
struct ll_st *prev;
} ll_node, *ll;
/*
* ll_add_to_end adds data to the end of a linked list. A new node
* is always created. If the list previously didn't exist, then a
* new list is created and the addToMe variable updated accordingly.
* This function returns 1 for success. If we run out of memory, die.
*/
int ll_add_to_end(ll *addToMe, void *data);
/*
* ll_add_to_start is identical to ll_add_to_end, except the new data
* is added to the start of the linked list.
*/
int ll_add_to_start(ll *addToMe, void *data);
/*
* ll_find traverses the linked list, looking for a node containing
* data that matches the "data" argument, according to the "compare"
* comparator function. "compare" should return 0 if for equal, -1
* for d1 less than d2, and +1 for d1 greater than d2. ll_find
* returns a pointer to the first found node, or NULL if such a node
* doesn't exist.
*/
ll ll_find(ll *findInMe, void *data, int (*compare)(void *d1, void *d2));
/*
* ll_sorted_insert will perform a list element insertion, but will
* do so in sorted (increasing) order. This function returns 1 for
* success, and dies on failure.
*/
int ll_sorted_insert(ll *insertme, void *data,
int (*compare)(void *d1, void *d2));
/*
* ll_del performs an ll_find operation on the "data" argument. If
* a node is found, it is removed from the linked list and the data field
* of the node freed with the "nukeElement" function. (If "nukeElement"
* is NULL, the free is avoided.) If the linked list becomes empty,
* "*delFromMe" becomes NULL. If multiple nodes match the "data" argument,
* only the first is removed. This function returns 1 if a node is found
* and removed, or 0 otherwise.
*/
int ll_del(ll *delFromMe, void *data, int (*compare)(void *d1, void *d2),
void (*nukeElement)(void *nukeMe));
/*
* ll_delfirst deletes the first element from the list, if it exists.
* If nukeElement is NULL, the element is not free'd. This function
* returns 1 on success, 0 otherwise.
*/
int ll_delfirst(ll *delFromMe, void (*nukeElement)(void *nukeMe));
/*
* ll_destroy removes all nodes from a list, and calls "nukeElement" on
* the data field of all nodes. If "nukeElement" is NULL, no operation
* is performed on the data field, but the destroy proceeds. This
* function always returns 1.
*/
int ll_destroy(ll *destroyMe, void (*nukeElement)(void *nukeMe));
/*
* ll_build takes a string of the form [a, b, c, .. ] and returns a linked
* list with elements from the string. It malloc's space for the new
* linked list element strings. The function returns 1 on success, and
* 0 in case of an error.
*/
int ll_build(ll *buildMe, char *buildFromMe);
/*
***************** Hash table routines ****************
*/
typedef ll hash_el;
typedef struct hash_table_st {
int num_elements;
hash_el *slot_array;
} hash_table;
typedef int (*hash_function)(void *element, int num_slots);
typedef int (*sc_comparator)(void *element1, void *element2);
typedef void (*deletor)(void *element);
/*
* chained_hash_create creates a new chained hash table, with room for
* "num_slots" slots. If the creation succeeds, the new table is passed back
* in the rt variable and 0 is returned, else -1 is returned.
*/
int chained_hash_create(int num_slots, hash_table *rt);
/*
* chained_hash_destroy destroys a previously created hash table. It
* first purges the chains of all non-empty slots in the table, and then
* frees the table itself. 0 is always returned.
*/
int chained_hash_destroy(hash_table ht, deletor d);
/*
* chained_hash_insert first uses the hash_function f to acquire the
* hash slot for the element "element", and then inserts that element
* into the slot's list. 0 is returned in case of success, and -1 in
* case of failure.
*/
int chained_hash_insert(hash_table ht, void *element, hash_function f);
/*
* chained_hash_search finds the stored element matching "element" in
* table ht according to comparator function "c". "c" must return 0
* if two elements match, 1 if the first argument is greater, and -1 if
* the first argument is less. If an element is found, it is returned,
* else NULL is returned.
*/
void *chained_hash_search(hash_table ht, void *element, hash_function f,
sc_comparator c);
/*
* chained_hash_delete removes the element from ht that would be found
* with chained_hash_search. It uses the deletor function d to purge
* the data found. If deletor is NULL, the purging is not performed.
* Comparator "c" is used to do the matching within the list. This function
* returns 1 if an element was deleted, and 0 otherwise.
*/
int chained_hash_delete(hash_table ht, void *element, hash_function f,
deletor d, sc_comparator c);
/*************************************************/
/* Filename: AVL_code.h */
/*************************************************/
#ifndef FALSE
#define FALSE 0
#endif
#ifndef TRUE
#define TRUE 1
#endif
typedef struct AVL_tree_st {
void *data;
int bal;
struct AVL_tree_st *left;
struct AVL_tree_st *right;
struct AVL_tree_st *parent;
} *AVL_tree, AVL_tree_element;
/**** AVL_comparator: if node > comparison return 1,
if node < comparison return -1,
if equal return 0
AVL_deletor: free any space taken up by data ****/
typedef int (*AVL_comparator)(void *node, void *comparison);
typedef void (*AVL_deletor)(void *deleteMe);
/* these functions return 0 on success, and a negative number on failure */
int Tree_Add(AVL_tree *addToMe, void *addMe, AVL_comparator theComp);
int Tree_Delete(AVL_tree *deleteFromMe, void *deleteMe,
AVL_comparator theComp, AVL_deletor theDel);
int Tree_Destroy(AVL_tree *destroyMe, AVL_deletor theDel);
/* these functions return a (+ve) pointer on success, and NULL on failure */
AVL_tree Tree_Search(AVL_tree searchMe, void *searchForMe, AVL_comparator theComp);
AVL_tree Tree_First(AVL_tree searchMe);
AVL_tree Tree_Last(AVL_tree searchMe);
AVL_tree Tree_Next(AVL_tree searchMe);
#ifdef __cplusplus
}
#endif
#endif
syntax highlighted by Code2HTML, v. 0.9.1