00001 /* 00002 * COPYRIGHT AND DISCLAIMER 00003 * 00004 * Copyright (C) 1996-1997 by the Regents of the University of California. 00005 * 00006 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR 00007 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT 00008 * OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY DERIVATIVES THEREOF, 00009 * EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00010 * 00011 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES, 00012 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, 00013 * FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT. THIS SOFTWARE IS 00014 * PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE NO 00015 * OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR 00016 * MODIFICATIONS. 00017 * 00018 * For inquiries email Steve Gribble <gribble@cs.berkeley.edu>. 00019 */ 00020 00021 00022 /* 00023 * utils.h -- 00024 * 00025 * Various utility functions - sockets, linked list, hash tables. 00026 * $Id: utils.h,v 1.3 2002/05/23 21:26:03 buchheim Exp $ 00027 * 00028 */ 00029 00030 #ifndef ICP_UTILS 00031 #define ICP_UTILS 00032 00033 #ifdef __cplusplus 00034 extern "C" { 00035 #endif 00036 00037 #include <stdio.h> 00038 #include <stdlib.h> 00039 #include <string.h> 00040 #include <unistd.h> 00041 #include <sys/socket.h> 00042 #include <sys/types.h> 00043 #include <netinet/in.h> 00044 #include <fcntl.h> 00045 #include <sys/ioctl.h> 00046 00047 #include "config.h" 00048 00049 #ifdef HAVE_TIME_H 00050 #include <time.h> 00051 #endif 00052 #ifdef HAVE_SYS_TIME_H 00053 #include <sys/time.h> 00054 #endif 00055 #ifdef HAVE_SYS_TIMERS_H 00056 #include <sys/timers.h> 00057 #endif 00058 00059 00060 /* 00061 ************* Dump out the hexification of the buffer *********** 00062 */ 00063 void dump_buf(FILE *std, char *buf, int retlen); 00064 00065 /* 00066 ************* Time munging utilities ***************** 00067 */ 00068 00069 typedef struct timeval tv_time; 00070 typedef struct timespec ts_time; 00071 00072 tv_time tv_timeadd(tv_time t1, tv_time t2); 00073 tv_time tv_timesub(tv_time t1, tv_time t2); 00074 tv_time tv_timemul(tv_time t1, double mult); 00075 int tv_timecmp(tv_time t1, tv_time t2); 00076 00077 ts_time ts_timeadd(ts_time t1, ts_time t2); 00078 ts_time ts_timesub(ts_time t1, ts_time t2); 00079 ts_time ts_timemul(ts_time t1, double mult); 00080 int ts_timecmp(ts_time t1, ts_time t2); 00081 00082 /* 00083 ************* Thread-safe strtok routines and state ************* 00084 */ 00085 00086 typedef struct ts_strtok_st { 00087 char *string_dupe; 00088 char *nxt_ptr; 00089 int chars_remaining; 00090 } ts_strtok_state; 00091 00092 /* 00093 * Thread-safe strtok routines! Call ts_strtok_init with the string you 00094 * want tokenized. It will return a pointer to some state. Then you 00095 * call ts_strtok with the same semantics as strtok, more or less, except 00096 * you have to pass this state around. When you're done, be sure to call 00097 * ts_strtok_finish to clean up the state. 00098 * 00099 * ts_strtok_init returns NULL if it runs out of memory, or if it is passed 00100 * a bogus string. ts_strtok returns NULL in case of error, ts_strtok_finish 00101 * returns 1 on success, 0 on error.x 00102 */ 00103 00104 ts_strtok_state *ts_strtok_init(char *string); 00105 char *ts_strtok(char *matching, ts_strtok_state *state); 00106 int ts_strtok_finish(ts_strtok_state *state); 00107 00108 /************* A really dumb implementation of strnstr and strcasestr ***********/ 00109 char *dumb_strnstr(char *str, char *substr, int n); 00110 const char *dumb_strcasestr(const char *string, const char *substr); 00111 00112 /* 00113 ***************** Socket convenience utilities **************** 00114 */ 00115 00116 /* 00117 * correct_write will continue writing to a socket until it fails or 00118 * until all len bytes have been written. 00119 */ 00120 00121 int correct_write(int s, char *data, int len); 00122 00123 /* 00124 * correct_read is like correct_write, but does a read. 00125 */ 00126 00127 int correct_read(int s, char *data, int len); 00128 00129 /* 00130 ***************** Linked-list routines **************** 00131 */ 00132 00133 /* 00134 * the "ll_node" structure contains a node of a linked list. Note that 00135 * a NULL "ll" type implies an empty linked-list. 00136 */ 00137 00138 typedef struct ll_st { 00139 void *data; 00140 struct ll_st *next; 00141 struct ll_st *prev; 00142 } ll_node, *ll; 00143 00144 /* 00145 * ll_add_to_end adds data to the end of a linked list. A new node 00146 * is always created. If the list previously didn't exist, then a 00147 * new list is created and the addToMe variable updated accordingly. 00148 * This function returns 1 for success. If we run out of memory, die. 00149 */ 00150 00151 int ll_add_to_end(ll *addToMe, void *data); 00152 00153 /* 00154 * ll_add_to_start is identical to ll_add_to_end, except the new data 00155 * is added to the start of the linked list. 00156 */ 00157 00158 int ll_add_to_start(ll *addToMe, void *data); 00159 00160 /* 00161 * ll_find traverses the linked list, looking for a node containing 00162 * data that matches the "data" argument, according to the "compare" 00163 * comparator function. "compare" should return 0 if for equal, -1 00164 * for d1 less than d2, and +1 for d1 greater than d2. ll_find 00165 * returns a pointer to the first found node, or NULL if such a node 00166 * doesn't exist. 00167 */ 00168 00169 ll ll_find(ll *findInMe, void *data, int (*compare)(void *d1, void *d2)); 00170 00171 /* 00172 * ll_sorted_insert will perform a list element insertion, but will 00173 * do so in sorted (increasing) order. This function returns 1 for 00174 * success, and dies on failure. 00175 */ 00176 00177 int ll_sorted_insert(ll *insertme, void *data, 00178 int (*compare)(void *d1, void *d2)); 00179 00180 00181 /* 00182 * ll_del performs an ll_find operation on the "data" argument. If 00183 * a node is found, it is removed from the linked list and the data field 00184 * of the node freed with the "nukeElement" function. (If "nukeElement" 00185 * is NULL, the free is avoided.) If the linked list becomes empty, 00186 * "*delFromMe" becomes NULL. If multiple nodes match the "data" argument, 00187 * only the first is removed. This function returns 1 if a node is found 00188 * and removed, or 0 otherwise. 00189 */ 00190 00191 int ll_del(ll *delFromMe, void *data, int (*compare)(void *d1, void *d2), 00192 void (*nukeElement)(void *nukeMe)); 00193 00194 /* 00195 * ll_delfirst deletes the first element from the list, if it exists. 00196 * If nukeElement is NULL, the element is not free'd. This function 00197 * returns 1 on success, 0 otherwise. 00198 */ 00199 00200 int ll_delfirst(ll *delFromMe, void (*nukeElement)(void *nukeMe)); 00201 00202 00203 /* 00204 * ll_destroy removes all nodes from a list, and calls "nukeElement" on 00205 * the data field of all nodes. If "nukeElement" is NULL, no operation 00206 * is performed on the data field, but the destroy proceeds. This 00207 * function always returns 1. 00208 */ 00209 00210 int ll_destroy(ll *destroyMe, void (*nukeElement)(void *nukeMe)); 00211 00212 /* 00213 * ll_build takes a string of the form [a, b, c, .. ] and returns a linked 00214 * list with elements from the string. It malloc's space for the new 00215 * linked list element strings. The function returns 1 on success, and 00216 * 0 in case of an error. 00217 */ 00218 00219 int ll_build(ll *buildMe, char *buildFromMe); 00220 00221 /* 00222 ***************** Hash table routines **************** 00223 */ 00224 00225 typedef ll hash_el; 00226 typedef struct hash_table_st { 00227 int num_elements; 00228 hash_el *slot_array; 00229 } hash_table; 00230 typedef int (*hash_function)(void *element, int num_slots); 00231 typedef int (*sc_comparator)(void *element1, void *element2); 00232 typedef void (*deletor)(void *element); 00233 00234 /* 00235 * chained_hash_create creates a new chained hash table, with room for 00236 * "num_slots" slots. If the creation succeeds, the new table is passed back 00237 * in the rt variable and 0 is returned, else -1 is returned. 00238 */ 00239 00240 int chained_hash_create(int num_slots, hash_table *rt); 00241 00242 /* 00243 * chained_hash_destroy destroys a previously created hash table. It 00244 * first purges the chains of all non-empty slots in the table, and then 00245 * frees the table itself. 0 is always returned. 00246 */ 00247 00248 int chained_hash_destroy(hash_table ht, deletor d); 00249 00250 /* 00251 * chained_hash_insert first uses the hash_function f to acquire the 00252 * hash slot for the element "element", and then inserts that element 00253 * into the slot's list. 0 is returned in case of success, and -1 in 00254 * case of failure. 00255 */ 00256 00257 int chained_hash_insert(hash_table ht, void *element, hash_function f); 00258 00259 /* 00260 * chained_hash_search finds the stored element matching "element" in 00261 * table ht according to comparator function "c". "c" must return 0 00262 * if two elements match, 1 if the first argument is greater, and -1 if 00263 * the first argument is less. If an element is found, it is returned, 00264 * else NULL is returned. 00265 */ 00266 00267 void *chained_hash_search(hash_table ht, void *element, hash_function f, 00268 sc_comparator c); 00269 00270 /* 00271 * chained_hash_delete removes the element from ht that would be found 00272 * with chained_hash_search. It uses the deletor function d to purge 00273 * the data found. If deletor is NULL, the purging is not performed. 00274 * Comparator "c" is used to do the matching within the list. This function 00275 * returns 1 if an element was deleted, and 0 otherwise. 00276 */ 00277 00278 int chained_hash_delete(hash_table ht, void *element, hash_function f, 00279 deletor d, sc_comparator c); 00280 00281 00282 /*************************************************/ 00283 /* Filename: AVL_code.h */ 00284 /*************************************************/ 00285 00286 #ifndef FALSE 00287 #define FALSE 0 00288 #endif 00289 #ifndef TRUE 00290 #define TRUE 1 00291 #endif 00292 00293 typedef struct AVL_tree_st { 00294 void *data; 00295 int bal; 00296 struct AVL_tree_st *left; 00297 struct AVL_tree_st *right; 00298 struct AVL_tree_st *parent; 00299 } *AVL_tree, AVL_tree_element; 00300 00301 00302 /**** AVL_comparator: if node > comparison return 1, 00303 if node < comparison return -1, 00304 if equal return 0 00305 AVL_deletor: free any space taken up by data ****/ 00306 typedef int (*AVL_comparator)(void *node, void *comparison); 00307 typedef void (*AVL_deletor)(void *deleteMe); 00308 00309 /* these functions return 0 on success, and a negative number on failure */ 00310 int Tree_Add(AVL_tree *addToMe, void *addMe, AVL_comparator theComp); 00311 int Tree_Delete(AVL_tree *deleteFromMe, void *deleteMe, 00312 AVL_comparator theComp, AVL_deletor theDel); 00313 int Tree_Destroy(AVL_tree *destroyMe, AVL_deletor theDel); 00314 00315 /* these functions return a (+ve) pointer on success, and NULL on failure */ 00316 AVL_tree Tree_Search(AVL_tree searchMe, void *searchForMe, AVL_comparator theComp); 00317 AVL_tree Tree_First(AVL_tree searchMe); 00318 AVL_tree Tree_Last(AVL_tree searchMe); 00319 AVL_tree Tree_Next(AVL_tree searchMe); 00320 00321 00322 #ifdef __cplusplus 00323 } 00324 #endif 00325 00326 #endif