1.1 --- a/.rootkeys	Sun Nov 21 20:41:00 2004 +0000
     1.2 +++ b/.rootkeys	Mon Nov 22 16:41:50 2004 +0000
     1.3 @@ -336,20 +336,35 @@ 40589968UQFnJeOMn8UIFLbXBuwXjw tools/lib
     1.4  40e1b09dMYB4ItGCqcMIzirdMd9I-w tools/libxutil/Makefile
     1.5  40e033325Sjqs-_4TuzeUEprP_gYFg tools/libxutil/allocate.c
     1.6  40e03332KYz7o1bn2MG_KPbBlyoIMA tools/libxutil/allocate.h
     1.7 +41a216cav5JJbtDQnusfuMa_1x_Xpw tools/libxutil/debug.h
     1.8 +40e9808eyjiahG5uF6AMelNVujBzCg tools/libxutil/enum.c
     1.9 +40e9808eZpbdn9q2KSSMGCNvY_ZgpQ tools/libxutil/enum.h
    1.10  40e03332p5Dc_owJQRuN72ymJZddFQ tools/libxutil/file_stream.c
    1.11  40e03332jWfB2viAhLSkq1WK0r_iDQ tools/libxutil/file_stream.h
    1.12  40e03332rUjNMGg11n2rN6V4DCrvOg tools/libxutil/gzip_stream.c
    1.13  40e033321O5Qg22haLoq5lpmk4tooQ tools/libxutil/gzip_stream.h
    1.14 +40e9808easXCzzAZQodEfKAhgUXSPA tools/libxutil/hash_table.c
    1.15 +40e9808e94BNXIVVKBFHC3rnkvwtJg tools/libxutil/hash_table.h
    1.16  40e03332ihnBGzHykVwZnFmkAppb4g tools/libxutil/iostream.c
    1.17  40e03332UGwbLR4wsw4ft14p0Yw5pg tools/libxutil/iostream.h
    1.18  40e0333245DLDzJemeSVBLuutHtzEQ tools/libxutil/kernel_stream.c
    1.19  40e03332aK0GkgpDdc-PVTkWKTeOBg tools/libxutil/kernel_stream.h
    1.20 +40e9808epW9iHcLXuO3QfUfLzB7onw tools/libxutil/lexis.c
    1.21 +40e9808egccMhCizayQRGtpBA3L5MQ tools/libxutil/lexis.h
    1.22 +41a216caM4z39Fzjb91rv9Ed_4By1A tools/libxutil/socket_stream.c
    1.23 +41a216caqinvF1I5FQMHA4HTRz8MSA tools/libxutil/socket_stream.h
    1.24  40e03332KT_tnnoAMbPVAZBB7kSOAQ tools/libxutil/string_stream.c
    1.25  40e03332-VtK6_OZa1vMHXFil8uq6w tools/libxutil/string_stream.h
    1.26 +40e9808e5_PLdodqVOSx0b4T_f5aeg tools/libxutil/sxpr.c
    1.27 +40e9808e0O4sHZtkDv5hlSqjYcdQAQ tools/libxutil/sxpr.h
    1.28 +40ec1cc6SIiGbynOi-1NtPesOlzF-Q tools/libxutil/sxpr_parser.c
    1.29 +40ec1cc6wpvvGxZiq4EFvNOcw0tUFg tools/libxutil/sxpr_parser.h
    1.30  40e03332Rkvq6nn_UNjzAAK_Tk9v1g tools/libxutil/sys_net.c
    1.31  40e03332lQHvQHw4Rh7VsT1_sui29A tools/libxutil/sys_net.h
    1.32  40e033321smklZd7bDSdWvQCeIshtg tools/libxutil/sys_string.c
    1.33  40e03332h5V611rRWURRLqb1Ekatxg tools/libxutil/sys_string.h
    1.34 +41a216cayFe2FQroFuzvNPw1AvNiqQ tools/libxutil/util.c
    1.35 +41a216ca7mgVSnCBHPCLkGOIqPS1CQ tools/libxutil/util.h
    1.36  3f776bd2Xd-dUcPKlPN2vG89VGtfvQ tools/misc/Makefile
    1.37  40ab2cfawIw8tsYo0dQKtp83h4qfTQ tools/misc/fakei386xen
    1.38  3f6dc136ZKOjd8PIqLbFBl_v-rnkGg tools/misc/miniterm/Makefile
    1.39 @@ -544,23 +559,13 @@ 40e9808epTR4zWrYjGUnaaynK20Q5A tools/xfr
    1.40  40e9808eysqT4VNDlJFqsZB2rdg4Qw tools/xfrd/connection.c
    1.41  40e9808eyXfJUi4E0C3WSgrEXqQ1sQ tools/xfrd/connection.h
    1.42  40e9808eULGwffNOE4kBrAfZ9YAVMA tools/xfrd/debug.h
    1.43 -40e9808eyjiahG5uF6AMelNVujBzCg tools/xfrd/enum.c
    1.44 -40e9808eZpbdn9q2KSSMGCNvY_ZgpQ tools/xfrd/enum.h
    1.45 -40e9808easXCzzAZQodEfKAhgUXSPA tools/xfrd/hash_table.c
    1.46 -40e9808e94BNXIVVKBFHC3rnkvwtJg tools/xfrd/hash_table.h
    1.47  411b5139tfKZfWs1LQHmwDR_wjKoxQ tools/xfrd/http.h
    1.48 -40e9808epW9iHcLXuO3QfUfLzB7onw tools/xfrd/lexis.c
    1.49 -40e9808egccMhCizayQRGtpBA3L5MQ tools/xfrd/lexis.h
    1.50  40e9808ePADCSKL1YgGCt2TbYPnYkw tools/xfrd/lzi_stream.c
    1.51  40e9808eDNAdpF71o5teYb9DTT-PRw tools/xfrd/lzi_stream.h
    1.52  40e9808eQxi0EzTcPJtosrzxEIjA-Q tools/xfrd/marshal.c
    1.53  40e9808etg13xfRm0Lqd8vY-jHOoTg tools/xfrd/marshal.h
    1.54  40e9808eCsmywryb036TdtRMJHDMmQ tools/xfrd/select.c
    1.55  40e9808e99OcM547cKMTfmCVSoWVAw tools/xfrd/select.h
    1.56 -40e9808e5_PLdodqVOSx0b4T_f5aeg tools/xfrd/sxpr.c
    1.57 -40e9808e0O4sHZtkDv5hlSqjYcdQAQ tools/xfrd/sxpr.h
    1.58 -40ec1cc6SIiGbynOi-1NtPesOlzF-Q tools/xfrd/sxpr_parser.c
    1.59 -40ec1cc6wpvvGxZiq4EFvNOcw0tUFg tools/xfrd/sxpr_parser.h
    1.60  40e9808eF3NVldqRNS5IHM8gbFAvpw tools/xfrd/xdr.c
    1.61  40e9808ezXzoRHm7pybXU69NtnjimA tools/xfrd/xdr.h
    1.62  40e9808edpUtf4bJ8IbqClPJj_OvbA tools/xfrd/xen_domain.c

     2.1 --- a/tools/libxutil/Makefile	Sun Nov 21 20:41:00 2004 +0000
     2.2 +++ b/tools/libxutil/Makefile	Mon Nov 22 16:41:50 2004 +0000
     2.3 @@ -5,11 +5,18 @@ CC = gcc
     2.4  
     2.5  LIB_SRCS :=
     2.6  LIB_SRCS += allocate.c
     2.7 +LIB_SRCS += enum.c
     2.8  LIB_SRCS += file_stream.c
     2.9  LIB_SRCS += gzip_stream.c
    2.10 +LIB_SRCS += hash_table.c
    2.11  LIB_SRCS += iostream.c
    2.12 -#LIB_SRCS += sys_net.c
    2.13 +LIB_SRCS += lexis.c
    2.14 +LIB_SRCS += string_stream.c
    2.15 +LIB_SRCS += sxpr.c
    2.16 +LIB_SRCS += sxpr_parser.c
    2.17 +LIB_SRCS += sys_net.c
    2.18  LIB_SRCS += sys_string.c
    2.19 +LIB_SRCS += util.c
    2.20  
    2.21  LIB_OBJS := $(LIB_SRCS:.c=.o)
    2.22  
    2.23 @@ -29,6 +36,7 @@ LIB_NAME := libxutil
    2.24  LIB      := $(LIB_NAME).so 
    2.25  LIB      += $(LIB_NAME).so.$(MAJOR)
    2.26  LIB      += $(LIB_NAME).so.$(MAJOR).$(MINOR)
    2.27 +LIB      += $(LIB_NAME).a
    2.28  
    2.29  all: check-for-zlib
    2.30  	$(MAKE) $(LIB)
    2.31 @@ -42,6 +50,9 @@ all: check-for-zlib
    2.32  $(LIB_NAME).so.$(MAJOR).$(MINOR): $(LIB_OBJS)
    2.33  	$(CC) -Wl,-soname -Wl,$(LIB_NAME).so.$(MAJOR) -shared -o $@ $^
    2.34  
    2.35 +$(LIB_NAME).a: $(LIB_OBJS)
    2.36 +	$(AR) rc $@ $^
    2.37 +
    2.38  check-for-zlib:
    2.39  	@if [ ! -e /usr/include/zlib.h ]; then \
    2.40  	echo "***********************************************************"; \

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/tools/libxutil/debug.h	Mon Nov 22 16:41:50 2004 +0000
     3.3 @@ -0,0 +1,72 @@
     3.4 +/*
     3.5 + * Copyright (C) 2004 Mike Wray <mike.wray@hp.com>
     3.6 + *
     3.7 + * This library is free software; you can redistribute it and/or modify
     3.8 + * it under the terms of the GNU Lesser General Public License as published by
     3.9 + * the Free Software Foundation; either version 2.1 of the License, or
    3.10 + * (at your option) any later version.
    3.11 + *
    3.12 + * This library is distributed in the hope that it will be useful,
    3.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
    3.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    3.15 + * GNU Lesser General Public License for more details.
    3.16 + *
    3.17 + * You should have received a copy of the GNU Lesser General Public License
    3.18 + * along with this library; if not, write to the Free Software
    3.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    3.20 + */
    3.21 +#ifndef _XUTIL_DEBUG_H_
    3.22 +#define _XUTIL_DEBUG_H_
    3.23 +
    3.24 +#ifndef MODULE_NAME
    3.25 +#define MODULE_NAME ""
    3.26 +#endif
    3.27 +
    3.28 +#ifdef __KERNEL__
    3.29 +#include <linux/config.h>
    3.30 +#include <linux/kernel.h>
    3.31 +
    3.32 +#ifdef DEBUG
    3.33 +
    3.34 +#define dprintf(fmt, args...) printk(KERN_DEBUG   "[DBG] " MODULE_NAME ">%s" fmt, __FUNCTION__, ##args)
    3.35 +#define wprintf(fmt, args...) printk(KERN_WARNING "[WRN] " MODULE_NAME ">%s" fmt, __FUNCTION__, ##args)
    3.36 +#define iprintf(fmt, args...) printk(KERN_INFO    "[INF] " MODULE_NAME ">%s" fmt, __FUNCTION__, ##args)
    3.37 +#define eprintf(fmt, args...) printk(KERN_ERR     "[ERR] " MODULE_NAME ">%s" fmt, __FUNCTION__, ##args)
    3.38 +
    3.39 +#else
    3.40 +
    3.41 +#define dprintf(fmt, args...) do {} while(0)
    3.42 +#define wprintf(fmt, args...) printk(KERN_WARNING "[WRN] " MODULE_NAME fmt, ##args)
    3.43 +#define iprintf(fmt, args...) printk(KERN_INFO    "[INF] " MODULE_NAME fmt, ##args)
    3.44 +#define eprintf(fmt, args...) printk(KERN_ERR     "[ERR] " MODULE_NAME fmt, ##args)
    3.45 +
    3.46 +#endif
    3.47 +
    3.48 +#else
    3.49 +
    3.50 +#include <stdio.h>
    3.51 +
    3.52 +#ifdef DEBUG
    3.53 +
    3.54 +#define dprintf(fmt, args...) fprintf(stdout, "%d [DBG] " MODULE_NAME ">%s" fmt, getpid(), __FUNCTION__, ##args)
    3.55 +#define wprintf(fmt, args...) fprintf(stderr, "%d [WRN] " MODULE_NAME ">%s" fmt, getpid(),__FUNCTION__, ##args)
    3.56 +#define iprintf(fmt, args...) fprintf(stderr, "%d [INF] " MODULE_NAME ">%s" fmt, getpid(),__FUNCTION__, ##args)
    3.57 +#define eprintf(fmt, args...) fprintf(stderr, "%d [ERR] " MODULE_NAME ">%s" fmt, getpid(),__FUNCTION__, ##args)
    3.58 +
    3.59 +#else
    3.60 +
    3.61 +#define dprintf(fmt, args...) do {} while(0)
    3.62 +#define wprintf(fmt, args...) fprintf(stderr, "%d [WRN] " MODULE_NAME fmt, getpid(), ##args)
    3.63 +#define iprintf(fmt, args...) fprintf(stderr, "%d [INF] " MODULE_NAME fmt, getpid(), ##args)
    3.64 +#define eprintf(fmt, args...) fprintf(stderr, "%d [ERR] " MODULE_NAME fmt, getpid(), ##args)
    3.65 +
    3.66 +#endif
    3.67 +
    3.68 +#endif
    3.69 +
    3.70 +/** Print format for an IP address.
    3.71 + * See NIPQUAD(), HIPQUAD()
    3.72 + */
    3.73 +#define IPFMT "%u.%u.%u.%u"
    3.74 +
    3.75 +#endif /* ! _XUTIL_DEBUG_H_ */

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/tools/libxutil/enum.c	Mon Nov 22 16:41:50 2004 +0000
     4.3 @@ -0,0 +1,61 @@
     4.4 +/*
     4.5 + * Copyright (C) 2002, 2004 Mike Wray <mike.wray@hp.com>
     4.6 + *
     4.7 + * This library is free software; you can redistribute it and/or modify
     4.8 + * it under the terms of the GNU Lesser General Public License as
     4.9 + * published by the Free Software Foundation; either version 2.1 of the
    4.10 + * License, or  (at your option) any later version. This library is 
    4.11 + * distributed in the  hope that it will be useful, but WITHOUT ANY
    4.12 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or
    4.13 + * FITNESS FOR A PARTICULAR PURPOSE.
    4.14 + * See the GNU Lesser General Public License for more details.
    4.15 + *
    4.16 + * You should have received a copy of the GNU Lesser General Public License
    4.17 + * along with this library; if not, write to the Free Software Foundation,
    4.18 + * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
    4.19 + */
    4.20 +
    4.21 +#ifdef __KERNEL__
    4.22 +#include <linux/errno.h>
    4.23 +#else
    4.24 +#include <errno.h>
    4.25 +#endif
    4.26 +
    4.27 +#include "sys_string.h"
    4.28 +#include "enum.h"
    4.29 +
    4.30 +/** Map an enum name to its value using a table.
    4.31 + *
    4.32 + * @param name enum name
    4.33 + * @param defs enum definitions
    4.34 + * @return enum value or -1 if not known
    4.35 + */
    4.36 +int enum_name_to_val(char *name, EnumDef *defs){
    4.37 +    int val = -1;
    4.38 +    for(; defs->name; defs++){
    4.39 +	if(!strcmp(defs->name, name)){
    4.40 +	    val = defs->val;
    4.41 +	    break;
    4.42 +	}
    4.43 +    }
    4.44 +    return val;
    4.45 +}
    4.46 +
    4.47 +/** Map an enum value to its name using a table.
    4.48 + *
    4.49 + * @param val enum value
    4.50 + * @param defs enum definitions
    4.51 + * @param defs_n number of definitions
    4.52 + * @return enum name or NULL if not known
    4.53 + */
    4.54 +char *enum_val_to_name(int val, EnumDef *defs){
    4.55 +    char *name = NULL;
    4.56 +    for(; defs->name; defs++){
    4.57 +	if(val == defs->val){
    4.58 +	    name = defs->name;
    4.59 +	    break;
    4.60 +	}
    4.61 +    }
    4.62 +    return name;
    4.63 +}
    4.64 +

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/tools/libxutil/enum.h	Mon Nov 22 16:41:50 2004 +0000
     5.3 @@ -0,0 +1,30 @@
     5.4 +/*
     5.5 + * Copyright (C) 2002, 2004 Mike Wray <mike.wray@hp.com>
     5.6 + *
     5.7 + * This library is free software; you can redistribute it and/or modify
     5.8 + * it under the terms of the GNU Lesser General Public License as
     5.9 + * published by the Free Software Foundation; either version 2.1 of the
    5.10 + * License, or  (at your option) any later version. This library is 
    5.11 + * distributed in the  hope that it will be useful, but WITHOUT ANY
    5.12 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or
    5.13 + * FITNESS FOR A PARTICULAR PURPOSE.
    5.14 + * See the GNU Lesser General Public License for more details.
    5.15 + *
    5.16 + * You should have received a copy of the GNU Lesser General Public License
    5.17 + * along with this library; if not, write to the Free Software Foundation,
    5.18 + * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
    5.19 + */
    5.20 +
    5.21 +#ifndef _XUTIL_ENUM_H_
    5.22 +#define _XUTIL_ENUM_H_
    5.23 +
    5.24 +/** Mapping of an enum value to a name. */
    5.25 +typedef struct EnumDef {
    5.26 +    int val;
    5.27 +    char *name;
    5.28 +} EnumDef;
    5.29 +
    5.30 +extern int enum_name_to_val(char *name, EnumDef *defs);
    5.31 +extern char *enum_val_to_name(int val, EnumDef *defs);
    5.32 +
    5.33 +#endif /* _XUTIL_ENUM_H_ */

     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/tools/libxutil/hash_table.c	Mon Nov 22 16:41:50 2004 +0000
     6.3 @@ -0,0 +1,640 @@
     6.4 +/*
     6.5 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
     6.6 + *
     6.7 + * This library is free software; you can redistribute it and/or modify
     6.8 + * it under the terms of the GNU Lesser General Public License as published by
     6.9 + * the Free Software Foundation; either version 2.1 of the License, or
    6.10 + * (at your option) any later version.
    6.11 + *
    6.12 + * This library is distributed in the hope that it will be useful,
    6.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
    6.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    6.15 + * GNU Lesser General Public License for more details.
    6.16 + *
    6.17 + * You should have received a copy of the GNU Lesser General Public License
    6.18 + * along with this library; if not, write to the Free Software
    6.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    6.20 + */
    6.21 +
    6.22 +#ifdef __KERNEL__
    6.23 +#  include <linux/config.h>
    6.24 +#  include <linux/module.h>
    6.25 +#  include <linux/kernel.h>
    6.26 +#  include <linux/errno.h>
    6.27 +#else
    6.28 +#  include <errno.h>
    6.29 +#  include <stddef.h>
    6.30 +#endif
    6.31 +
    6.32 +//#include <limits.h>
    6.33 +
    6.34 +#include "allocate.h"
    6.35 +#include "hash_table.h"
    6.36 +
    6.37 +/** @file
    6.38 + * Base support for hashtables.
    6.39 + *
    6.40 + * Hash codes are reduced modulo the number of buckets to index tables,
    6.41 + * so there is no need for hash functions to limit the range of hashcodes.
    6.42 + * In fact it is assumed that hashcodes do not change when the number of
    6.43 + * buckets in the table changes.
    6.44 + */
    6.45 +
    6.46 +/*==========================================================================*/
    6.47 +/** Number of bits in half a word. */
    6.48 +//#if __WORDSIZE == 64
    6.49 +//#define HALF_WORD_BITS 32
    6.50 +//#else
    6.51 +#define HALF_WORD_BITS 16
    6.52 +//#endif
    6.53 +
    6.54 +/** Mask for lo half of a word. On 32-bit this is 
    6.55 + * (1<<16) - 1 = 65535 = 0xffff
    6.56 + * It's 4294967295 = 0xffffffff on 64-bit.
    6.57 + */
    6.58 +#define LO_HALF_MASK ((1 << HALF_WORD_BITS) - 1)
    6.59 +
    6.60 +/** Get the lo half of a word. */
    6.61 +#define LO_HALF(x) ((x) & LO_HALF_MASK)
    6.62 +
    6.63 +/** Get the hi half of a word. */
    6.64 +#define HI_HALF(x) ((x) >> HALF_WORD_BITS)
    6.65 +
    6.66 +/** Do a full hash on both inputs, using DES-style non-linear scrambling.
    6.67 + * Both inputs are replaced with the results of the hash.
    6.68 + *
    6.69 + * @param pleft input/output word
    6.70 + * @param pright input/output word
    6.71 + */
    6.72 +void pseudo_des(unsigned long *pleft, unsigned long *pright){
    6.73 +    // Bit-rich mixing constant.
    6.74 +    static const unsigned long a_mixer[] = {
    6.75 +        0xbaa96887L, 0x1e17d32cL, 0x03bcdc3cL, 0x0f33d1b2L, };
    6.76 +
    6.77 +    // Bit-rich mixing constant.
    6.78 +    static const unsigned long b_mixer[] = {
    6.79 +        0x4b0f3b58L, 0xe874f0c3L, 0x6955c5a6L, 0x55a7ca46L, };
    6.80 +
    6.81 +    // Number of iterations - must be 2 or 4.
    6.82 +    static const int ncycle = 4;
    6.83 +    //static const int ncycle = 2;
    6.84 +
    6.85 +    unsigned long left = *pleft, right = *pright;
    6.86 +    unsigned long v, v_hi, v_lo;
    6.87 +    int i;
    6.88 +
    6.89 +    for(i=0; i<ncycle; i++){
    6.90 +        // Flip some bits in right to get v.
    6.91 +        v = right;
    6.92 +        v ^= a_mixer[i];
    6.93 +        // Get lo and hi halves of v.
    6.94 +        v_lo = LO_HALF(v);
    6.95 +        v_hi = HI_HALF(v);
    6.96 +        // Non-linear mix of the halves of v.
    6.97 +        v = ((v_lo * v_lo) + ~(v_hi * v_hi));
    6.98 +        // Swap the halves of v.
    6.99 +        v = (HI_HALF(v) | (LO_HALF(v) << HALF_WORD_BITS));
   6.100 +        // Flip some bits.
   6.101 +        v ^= b_mixer[i];
   6.102 +        // More non-linear mixing.
   6.103 +        v += (v_lo * v_hi);
   6.104 +        v ^= left;
   6.105 +        left = right;
   6.106 +        right = v;
   6.107 +    }
   6.108 +    *pleft = left;
   6.109 +    *pright = right;
   6.110 +}
   6.111 +
   6.112 +/** Hash a string.
   6.113 + *
   6.114 + * @param s input to hash
   6.115 + * @return hashcode
   6.116 + */
   6.117 +Hashcode hash_string(char *s){
   6.118 +    Hashcode h = 0;
   6.119 +    if(s){
   6.120 +        for( ; *s; s++){
   6.121 +            h = hash_2ul(h, *s);
   6.122 +        }
   6.123 +    }
   6.124 +    return h;
   6.125 +}
   6.126 +
   6.127 +/** Get the bucket for a hashcode in a hash table.
   6.128 + *
   6.129 + * @param table to get bucket from
   6.130 + * @param hashcode to get bucket for
   6.131 + * @return bucket
   6.132 + */
   6.133 +inline HTBucket * get_bucket(HashTable *table, Hashcode hashcode){
   6.134 +    return table->buckets + (hashcode % table->buckets_n);
   6.135 +}
   6.136 +
   6.137 +/** Initialize a hash table.
   6.138 + * Can be safely called more than once.
   6.139 + *
   6.140 + * @param table to initialize
   6.141 + */
   6.142 +void HashTable_init(HashTable *table){
   6.143 +    int i;
   6.144 +
   6.145 +    if(!table->init_done){
   6.146 +        table->init_done = 1;
   6.147 +        table->next_id = 0;
   6.148 +        for(i=0; i<table->buckets_n; i++){
   6.149 +            HTBucket *bucket = get_bucket(table, i);
   6.150 +            bucket->head = 0;
   6.151 +            bucket->count = 0;
   6.152 +        }
   6.153 +        table->entry_count = 0;
   6.154 +    }
   6.155 +}
   6.156 +
   6.157 +/** Allocate a new hashtable.
   6.158 + * If the number of buckets is not positive the default is used.
   6.159 + * The number of buckets should usually be prime.
   6.160 + *
   6.161 + * @param buckets_n number of buckets
   6.162 + * @return new hashtable or null
   6.163 + */
   6.164 +HashTable *HashTable_new(int buckets_n){
   6.165 +    HashTable *z = ALLOCATE(HashTable);
   6.166 +    if(!z) goto exit;
   6.167 +    if(buckets_n <= 0){
   6.168 +        buckets_n = HT_BUCKETS_N;
   6.169 +    }
   6.170 +    z->buckets = (HTBucket*)allocate(buckets_n * sizeof(HTBucket));
   6.171 +    if(!z->buckets){
   6.172 +        deallocate(z);
   6.173 +        z = 0;
   6.174 +        goto exit;
   6.175 +    }
   6.176 +    z->buckets_n = buckets_n;
   6.177 +    HashTable_init(z);
   6.178 +  exit:
   6.179 +    return z;
   6.180 +}
   6.181 +
   6.182 +/** Free a hashtable.
   6.183 + * Any entries are removed and freed.
   6.184 + *
   6.185 + * @param h hashtable (ignored if null)
   6.186 + */
   6.187 +void HashTable_free(HashTable *h){
   6.188 +    if(h){
   6.189 +        HashTable_clear(h);
   6.190 +        deallocate(h->buckets);
   6.191 +        deallocate(h);
   6.192 +    }
   6.193 +}
   6.194 +
   6.195 +/** Push an entry on the list in the bucket for a given hashcode.
   6.196 + *
   6.197 + * @param table to add entry to
   6.198 + * @param hashcode for the entry
   6.199 + * @param entry to add
   6.200 + */
   6.201 +static inline void push_on_bucket(HashTable *table, Hashcode hashcode,
   6.202 +				  HTEntry *entry){
   6.203 +    HTBucket *bucket;
   6.204 +    HTEntry *old_head;
   6.205 +
   6.206 +    bucket = get_bucket(table, hashcode);
   6.207 +    old_head = bucket->head;
   6.208 +    bucket->count++;
   6.209 +    bucket->head = entry;
   6.210 +    entry->next = old_head;
   6.211 +}
   6.212 +
   6.213 +/** Change the number of buckets in a hashtable.
   6.214 + * No-op if the number of buckets is not positive.
   6.215 + * Existing entries are reallocated to buckets based on their hashcodes.
   6.216 + * The table is unmodified if the number of buckets cannot be changed.
   6.217 + *
   6.218 + * @param table hashtable
   6.219 + * @param buckets_n new number of buckets
   6.220 + * @return 0 on success, error code otherwise
   6.221 + */
   6.222 +int HashTable_set_buckets_n(HashTable *table, int buckets_n){
   6.223 +    int err = 0;
   6.224 +    HTBucket *old_buckets = table->buckets;
   6.225 +    int old_buckets_n = table->buckets_n;
   6.226 +    int i;
   6.227 +
   6.228 +    if(buckets_n <= 0){
   6.229 +        err = -EINVAL;
   6.230 +        goto exit;
   6.231 +    }
   6.232 +    table->buckets = (HTBucket*)allocate(buckets_n * sizeof(HTBucket));
   6.233 +    if(!table->buckets){
   6.234 +        err = -ENOMEM;
   6.235 +        table->buckets = old_buckets;
   6.236 +        goto exit;
   6.237 +    }
   6.238 +    table->buckets_n = buckets_n;
   6.239 +    for(i=0; i<old_buckets_n; i++){
   6.240 +        HTBucket *bucket = old_buckets + i;
   6.241 +        HTEntry *entry, *next;
   6.242 +        for(entry = bucket->head; entry; entry = next){
   6.243 +            next = entry->next;
   6.244 +            push_on_bucket(table, entry->hashcode, entry);
   6.245 +        }
   6.246 +    }
   6.247 +    deallocate(old_buckets);
   6.248 +  exit:
   6.249 +    return err;
   6.250 +}
   6.251 +
   6.252 +/** Adjust the number of buckets so the table is neither too full nor too empty.
   6.253 + * The table is unmodified if adjusting fails.
   6.254 + *
   6.255 + * @param table hash table
   6.256 + * @param buckets_min minimum number of buckets (use default if 0 or negative)
   6.257 + * @return 0 on success, error code otherwise
   6.258 + */
   6.259 +int HashTable_adjust(HashTable *table, int buckets_min){
   6.260 +    int buckets_n = 0;
   6.261 +    int err = 0;
   6.262 +    if(buckets_min <= 0) buckets_min = HT_BUCKETS_N;
   6.263 +    if(table->entry_count >= table->buckets_n){
   6.264 +        // The table is dense - expand it.
   6.265 +        buckets_n = 2 * table->buckets_n;
   6.266 +    } else if((table->buckets_n > buckets_min) &&
   6.267 +              (4 * table->entry_count < table->buckets_n)){
   6.268 +        // The table is more than minimum size and sparse - shrink it.
   6.269 +        buckets_n = 2 * table->entry_count;
   6.270 +        if(buckets_n < buckets_min) buckets_n = buckets_min;
   6.271 +    }
   6.272 +    if(buckets_n){
   6.273 +        err = HashTable_set_buckets_n(table, buckets_n);
   6.274 +    }
   6.275 +    return err;
   6.276 +}
   6.277 +
   6.278 +/** Allocate a new entry for a given value.
   6.279 + *
   6.280 + * @param value to put in the entry
   6.281 + * @return entry, or 0 on failure
   6.282 + */
   6.283 +HTEntry * HTEntry_new(Hashcode hashcode, void *key, void *value){
   6.284 +    HTEntry *z = ALLOCATE(HTEntry);
   6.285 +    if(z){
   6.286 +        z->hashcode = hashcode;
   6.287 +        z->key = key;
   6.288 +        z->value = value;
   6.289 +    }
   6.290 +    return z;
   6.291 +}
   6.292 +
   6.293 +/** Free an entry.
   6.294 + *
   6.295 + * @param z entry to free
   6.296 + */
   6.297 +inline void HTEntry_free(HTEntry *z){
   6.298 +    if(z){
   6.299 +        deallocate(z);
   6.300 +    }
   6.301 +}
   6.302 +
   6.303 +/** Free an entry in a hashtable.
   6.304 + * The table's entry_free_fn is used is defined, otherwise 
   6.305 + * the HTEntry itself is freed.
   6.306 + *
   6.307 + * @param table hashtable
   6.308 + * @param entry to free
   6.309 + */
   6.310 +inline void HashTable_free_entry(HashTable *table, HTEntry *entry){
   6.311 +    if(!entry)return;
   6.312 +    if(table && table->entry_free_fn){
   6.313 +        table->entry_free_fn(table, entry);
   6.314 +    } else {
   6.315 +        HTEntry_free(entry);
   6.316 +    }
   6.317 +}
   6.318 +
   6.319 +/** Get the first entry satisfying a test from the bucket for the
   6.320 + * given hashcode.
   6.321 + *
   6.322 + * @param table to look in
   6.323 + * @param hashcode indicates the bucket
   6.324 + * @param test_fn test to apply to elements
   6.325 + * @param arg first argument to calls to test_fn
   6.326 + * @return entry found, or 0
   6.327 + */
   6.328 +inline HTEntry * HashTable_find_entry(HashTable *table, Hashcode hashcode,
   6.329 +				      TableTestFn *test_fn, TableArg arg){
   6.330 +    HTBucket *bucket;
   6.331 +    HTEntry *entry = 0;
   6.332 +    HTEntry *next;
   6.333 +
   6.334 +    bucket = get_bucket(table, hashcode);
   6.335 +    for(entry = bucket->head; entry; entry = next){
   6.336 +        next = entry->next;
   6.337 +        if(test_fn(arg, table, entry)){
   6.338 +            break;
   6.339 +        }
   6.340 +    }
   6.341 +    return entry;
   6.342 +}
   6.343 +
   6.344 +/** Test hashtable keys for equality.
   6.345 + * Uses the table's key_equal_fn if defined, otherwise pointer equality.
   6.346 + *
   6.347 + * @param key1 key to compare
   6.348 + * @param key2 key to compare
   6.349 + * @return 1 if equal, 0 otherwise
   6.350 + */
   6.351 +inline int HashTable_key_equal(HashTable *table, void *key1, void *key2){
   6.352 +    return (table->key_equal_fn ? table->key_equal_fn(key1, key2) : key1==key2);
   6.353 +}
   6.354 +
   6.355 +/** Compute the hashcode of a hashtable key.
   6.356 + * The table's key_hash_fn is used if defined, otherwise the address of
   6.357 + * the key is hashed.
   6.358 + *
   6.359 + * @param table hashtable
   6.360 + * @param key to hash
   6.361 + * @return hashcode
   6.362 + */
   6.363 +inline Hashcode HashTable_key_hash(HashTable *table, void *key){
   6.364 +    return (table->key_hash_fn ? table->key_hash_fn(key) : hash_ul((unsigned long)key));
   6.365 +}
   6.366 +
   6.367 +/** Test if an entry has a given key.
   6.368 + *
   6.369 + * @param arg containing key to test for
   6.370 + * @param table the entry is in
   6.371 + * @param entry to test
   6.372 + * @return 1 if the entry has the key, 0 otherwise
   6.373 + */
   6.374 +static inline int has_key(TableArg arg, HashTable *table, HTEntry *entry){
   6.375 +    return HashTable_key_equal(table, arg.ptr, entry->key);
   6.376 +}
   6.377 +
   6.378 +/** Get an entry with a given key.
   6.379 + *
   6.380 + * @param table to search
   6.381 + * @param key to look for
   6.382 + * @return entry if found, null otherwise
   6.383 + */
   6.384 +#if 0
   6.385 +inline HTEntry * HashTable_get_entry(HashTable *table, void *key){
   6.386 +    TableArg arg = { ptr: key };
   6.387 +    return HashTable_find_entry(table, HashTable_key_hash(table, key), has_key, arg);
   6.388 +}
   6.389 +#else
   6.390 +inline HTEntry * HashTable_get_entry(HashTable *table, void *key){
   6.391 +    Hashcode hashcode;
   6.392 +    HTBucket *bucket;
   6.393 +    HTEntry *entry = 0;
   6.394 +    HTEntry *next;
   6.395 +
   6.396 +    hashcode = HashTable_key_hash(table, key);
   6.397 +    bucket = get_bucket(table, hashcode);
   6.398 +    for(entry = bucket->head; entry; entry = next){
   6.399 +        next = entry->next;
   6.400 +        if(HashTable_key_equal(table, key, entry->key)){
   6.401 +            break;
   6.402 +        }
   6.403 +    }
   6.404 +    return entry;
   6.405 +}
   6.406 +#endif
   6.407 +
   6.408 +/** Get the value of an entry with a given key.
   6.409 + *
   6.410 + * @param table to search
   6.411 + * @param key to look for
   6.412 + * @return value if an entry was found, null otherwise
   6.413 + */
   6.414 +inline void * HashTable_get(HashTable *table, void *key){
   6.415 +    HTEntry *entry = HashTable_get_entry(table, key);
   6.416 +    return (entry ? entry->value : 0);
   6.417 +}
   6.418 +
   6.419 +/** Print the buckets in a table.
   6.420 + *
   6.421 + * @param table to print
   6.422 + */
   6.423 +void show_buckets(HashTable *table, IOStream *io){
   6.424 +    int i,j ;
   6.425 +    IOStream_print(io, "entry_count=%d buckets_n=%d\n", table->entry_count, table->buckets_n);
   6.426 +    for(i=0; i<table->buckets_n; i++){
   6.427 +        if(0 || table->buckets[i].count>0){
   6.428 +            IOStream_print(io, "bucket %3d %3d %10p ", i,
   6.429 +                        table->buckets[i].count,
   6.430 +                        table->buckets[i].head);
   6.431 +            for(j = table->buckets[i].count; j>0; j--){
   6.432 +                IOStream_print(io, "+");
   6.433 +            }
   6.434 +            IOStream_print(io, "\n");
   6.435 +        }
   6.436 +    }
   6.437 +    HashTable_print(table, io); 
   6.438 +}
   6.439 +    
   6.440 +/** Print an entry in a table.
   6.441 + *
   6.442 + * @param entry to print
   6.443 + * @param arg a pointer to an IOStream to print to
   6.444 + * @return 0
   6.445 + */
   6.446 +static int print_entry(TableArg arg, HashTable *table, HTEntry *entry){
   6.447 +    IOStream *io = (IOStream*)arg.ptr;
   6.448 +    IOStream_print(io, " b=%4lx h=%08lx i=%08lx |-> e=%8p k=%8p v=%8p\n",
   6.449 +                entry->hashcode % table->buckets_n,
   6.450 +                entry->hashcode,
   6.451 +                entry->index,
   6.452 +                entry, entry->key, entry->value);
   6.453 +    return 0;
   6.454 +}
   6.455 +
   6.456 +/** Print a hash table.
   6.457 + *
   6.458 + * @param table to print
   6.459 + */
   6.460 +void HashTable_print(HashTable *table, IOStream *io){
   6.461 +    IOStream_print(io, "{\n");
   6.462 +    HashTable_map(table, print_entry, (TableArg){ ptr: io });
   6.463 +    IOStream_print(io, "}\n");
   6.464 +}
   6.465 +/*==========================================================================*/
   6.466 +
   6.467 +/** Get the next entry id to use for a table.
   6.468 + *
   6.469 + * @param table hash table
   6.470 + * @return non-zero entry id
   6.471 + */
   6.472 +static inline unsigned long get_next_id(HashTable *table){
   6.473 +    unsigned long id;
   6.474 +
   6.475 +    if(table->next_id == 0){
   6.476 +        table->next_id = 1;
   6.477 +    }
   6.478 +    id = table->next_id++;
   6.479 +    return id;
   6.480 +}
   6.481 +
   6.482 +/** Add an entry to the bucket for the
   6.483 + * given hashcode.
   6.484 + *
   6.485 + * @param table to insert in
   6.486 + * @param hashcode indicates the bucket
   6.487 + * @param key to add an entry for
   6.488 + * @param value to add an entry for
   6.489 + * @return entry on success, 0 on failure
   6.490 + */
   6.491 +inline HTEntry * HashTable_add_entry(HashTable *table, Hashcode hashcode, void *key, void *value){
   6.492 +    HTEntry *entry = HTEntry_new(hashcode, key, value);
   6.493 +    if(entry){
   6.494 +        entry->index = get_next_id(table);
   6.495 +        push_on_bucket(table, hashcode, entry);
   6.496 +        table->entry_count++;
   6.497 +    }
   6.498 +    return entry;
   6.499 +}
   6.500 +
   6.501 +/** Move the front entry for a bucket to the correct point in the bucket order as
   6.502 + * defined by the order function. If this is called every time a new entry is added
   6.503 + * the bucket will be maintained in sorted order.
   6.504 + *
   6.505 + * @param table to modify
   6.506 + * @param hashcode indicates the bucket
   6.507 + * @param order entry comparison function
   6.508 + * @return 0 if an entry was moved, 1 if not
   6.509 + */
   6.510 +int HashTable_order_bucket(HashTable *table, Hashcode hashcode, TableOrderFn *order){
   6.511 +    HTEntry *new_entry = NULL, *prev = NULL, *entry = NULL;
   6.512 +    HTBucket *bucket;
   6.513 +    int err = 1;
   6.514 +
   6.515 +    bucket = get_bucket(table, hashcode);
   6.516 +    new_entry = bucket->head;
   6.517 +    if(!new_entry || !new_entry->next) goto exit;
   6.518 +    for(entry = new_entry->next; entry; prev = entry, entry = entry->next){
   6.519 +        if(order(new_entry, entry) <= 0) break;
   6.520 +    }
   6.521 +    if(prev){
   6.522 +        err = 0;
   6.523 +        bucket->head = new_entry->next; 
   6.524 +        new_entry->next = entry;
   6.525 +        prev->next = new_entry;
   6.526 +    }
   6.527 +  exit:
   6.528 +    return err;
   6.529 +}
   6.530 +
   6.531 +/** Add an entry to a hashtable.
   6.532 + * The entry is added to the bucket for its key's hashcode.
   6.533 + *
   6.534 + * @param table to insert in
   6.535 + * @param key to add an entry for
   6.536 + * @param value to add an entry for
   6.537 + * @return entry on success, 0 on failure
   6.538 + */
   6.539 +inline HTEntry * HashTable_add(HashTable *table, void *key, void *value){
   6.540 +    return HashTable_add_entry(table, HashTable_key_hash(table, key), key, value);
   6.541 +}
   6.542 +
   6.543 +
   6.544 +/** Remove entries satisfying a test from the bucket for the
   6.545 + * given hashcode. 
   6.546 + *
   6.547 + * @param table to remove from
   6.548 + * @param hashcode indicates the bucket
   6.549 + * @param test_fn test to apply to elements
   6.550 + * @param arg first argument to calls to test_fn
   6.551 + * @return number of entries removed
   6.552 + */
   6.553 +inline int HashTable_remove_entry(HashTable *table, Hashcode hashcode,
   6.554 +				  TableTestFn *test_fn, TableArg arg){
   6.555 +    HTBucket *bucket;
   6.556 +    HTEntry *entry, *prev = 0, *next;
   6.557 +    int removed_count = 0;
   6.558 +
   6.559 +    bucket = get_bucket(table, hashcode);
   6.560 +    for(entry = bucket->head; entry; entry = next){
   6.561 +        next = entry->next;
   6.562 +        if(test_fn(arg, table, entry)){
   6.563 +            if(prev){
   6.564 +                prev->next = next;
   6.565 +            } else {
   6.566 +                bucket->head = next;
   6.567 +            }
   6.568 +            bucket->count--;
   6.569 +            table->entry_count--;
   6.570 +            removed_count++;
   6.571 +            HashTable_free_entry(table, entry);
   6.572 +            entry = 0;
   6.573 +        }
   6.574 +        prev = entry;
   6.575 +    }
   6.576 +    return removed_count;
   6.577 +}
   6.578 +
   6.579 +/** Remove entries with a given key. 
   6.580 + *
   6.581 + * @param table to remove from
   6.582 + * @param key of entries to remove
   6.583 + * @return number of entries removed
   6.584 + */
   6.585 +inline int HashTable_remove(HashTable *table, void *key){
   6.586 +#if 1
   6.587 +    Hashcode hashcode;
   6.588 +    HTBucket *bucket;
   6.589 +    HTEntry *entry, *prev = 0, *next;
   6.590 +    int removed_count = 0;
   6.591 +
   6.592 +    hashcode = HashTable_key_hash(table, key);
   6.593 +    bucket = get_bucket(table, hashcode);
   6.594 +    for(entry = bucket->head; entry; entry = next){
   6.595 +        next = entry->next;
   6.596 +        if(HashTable_key_equal(table, key, entry->key)){
   6.597 +            if(prev){
   6.598 +                prev->next = next;
   6.599 +            } else {
   6.600 +                bucket->head = next;
   6.601 +            }
   6.602 +            bucket->count--;
   6.603 +            table->entry_count--;
   6.604 +            removed_count++;
   6.605 +            HashTable_free_entry(table, entry);
   6.606 +            entry = 0;
   6.607 +        }
   6.608 +        prev = entry;
   6.609 +    }
   6.610 +    return removed_count;
   6.611 +#else
   6.612 +    return HashTable_remove_entry(table, HashTable_key_hash(table, key),
   6.613 +				  has_key, (TableArg){ ptr: key});
   6.614 +#endif
   6.615 +}
   6.616 +
   6.617 +/** Remove (and free) all the entries in a bucket.
   6.618 + *
   6.619 + * @param bucket to clear
   6.620 + */
   6.621 +static inline void bucket_clear(HashTable *table, HTBucket *bucket){
   6.622 +    HTEntry *entry, *next;
   6.623 +
   6.624 +    for(entry = bucket->head; entry; entry = next){
   6.625 +        next = entry->next;
   6.626 +        HashTable_free_entry(table, entry);
   6.627 +    }
   6.628 +    bucket->head = 0;
   6.629 +    table->entry_count -= bucket->count;
   6.630 +    bucket->count = 0;
   6.631 +}
   6.632 +
   6.633 +/** Remove (and free) all the entries in a table.
   6.634 + *
   6.635 + * @param table to clear
   6.636 + */
   6.637 +void HashTable_clear(HashTable *table){
   6.638 +    int i, n = table->buckets_n;
   6.639 +
   6.640 +    for(i=0; i<n; i++){
   6.641 +        bucket_clear(table, table->buckets + i);
   6.642 +    }
   6.643 +}

     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/tools/libxutil/hash_table.h	Mon Nov 22 16:41:50 2004 +0000
     7.3 @@ -0,0 +1,294 @@
     7.4 +/*
     7.5 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
     7.6 + *
     7.7 + * This library is free software; you can redistribute it and/or modify
     7.8 + * it under the terms of the GNU Lesser General Public License as published by
     7.9 + * the Free Software Foundation; either version 2.1 of the License, or
    7.10 + * (at your option) any later version.
    7.11 + *
    7.12 + * This library is distributed in the hope that it will be useful,
    7.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
    7.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    7.15 + * GNU Lesser General Public License for more details.
    7.16 + *
    7.17 + * You should have received a copy of the GNU Lesser General Public License
    7.18 + * along with this library; if not, write to the Free Software
    7.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    7.20 + */
    7.21 +
    7.22 +#ifndef _XUTIL_HASH_TABLE_H_
    7.23 +#define _XUTIL_HASH_TABLE_H_
    7.24 +
    7.25 +#include "iostream.h"
    7.26 +
    7.27 +typedef unsigned long Hashcode;
    7.28 +
    7.29 +/** Type used to pass parameters to table functions. */
    7.30 +typedef union TableArg {
    7.31 +    unsigned long ul;
    7.32 +    void *ptr;
    7.33 +} TableArg;
    7.34 +
    7.35 +/** An entry in a bucket list. */
    7.36 +typedef struct HTEntry {
    7.37 +    /** Hashcode of the entry's key. */
    7.38 +    Hashcode hashcode;
    7.39 +    /** Identifier for this entry in the table. */
    7.40 +    int index;
    7.41 +    /** The key for this entry. */
    7.42 +    void *key;
    7.43 +    /** The value in this entry. */
    7.44 +    void *value;
    7.45 +    /** The next entry in the list. */
    7.46 +    struct HTEntry *next;
    7.47 +} HTEntry;
    7.48 +
    7.49 +/** A bucket in a rule table. */
    7.50 +typedef struct HTBucket {
    7.51 +    /** Number of entries in the bucket. */
    7.52 +    int count;
    7.53 +    /** First entry in the bucket (may be null). */
    7.54 +    HTEntry *head;
    7.55 +} HTBucket;
    7.56 +
    7.57 +/** Default number of buckets in a hash table.
    7.58 + * You want enough buckets so the lists in the buckets will typically be short.
    7.59 + * It's a good idea if this is prime, since that will help to spread hashcodes
    7.60 + * around the table.
    7.61 + */
    7.62 +//#define HT_BUCKETS_N 1
    7.63 +//#define HT_BUCKETS_N 3
    7.64 +//#define HT_BUCKETS_N 7
    7.65 +//#define HT_BUCKETS_N 17
    7.66 +//#define HT_BUCKETS_N 97
    7.67 +//#define HT_BUCKETS_N 211
    7.68 +//#define HT_BUCKETS_N 401
    7.69 +#define HT_BUCKETS_N 1021
    7.70 +
    7.71 +typedef struct HashTable HashTable;
    7.72 +
    7.73 +/** Type for a function used to select table entries. */
    7.74 +typedef int TableTestFn(TableArg arg, HashTable *table, HTEntry *entry);
    7.75 +
    7.76 +/** Type for a function to map over table entries. */
    7.77 +typedef int TableMapFn(TableArg arg, HashTable *table, HTEntry *entry);
    7.78 +
    7.79 +/** Type for a function to free table entries. */
    7.80 +typedef void TableFreeFn(HashTable *table, HTEntry *entry);
    7.81 +
    7.82 +/** Type for a function to hash table keys. */
    7.83 +typedef Hashcode TableHashFn(void *key);
    7.84 +
    7.85 +/** Type for a function to test table keys for equality. */
    7.86 +typedef int TableEqualFn(void *key1, void *key2);
    7.87 +
    7.88 +/** Type for a function to order table entries. */
    7.89 +typedef int TableOrderFn(HTEntry *e1, HTEntry *e2);
    7.90 +
    7.91 +/** General hash table.
    7.92 + * A hash table with a list in each bucket.
    7.93 + * Functions can be supplied for freeing entries, hashing keys, and comparing keys.
    7.94 + * These all default to 0, when default behaviour treating keys as integers is used.
    7.95 + */
    7.96 +struct HashTable {
    7.97 +    /** Flag indicating whether the table has been initialised. */
    7.98 +    int init_done;
    7.99 +    /** Next value for the id field in inserted rules. */
   7.100 +    unsigned long next_id;
   7.101 +    /** Number of buckets in the bucket array. */
   7.102 +    int buckets_n;
   7.103 +    /** Array of buckets, each with its own list. */
   7.104 +    HTBucket *buckets;
   7.105 +    /** Number of entries in the table. */
   7.106 +    int entry_count;
   7.107 +    /** Function to free keys and values in entries. */
   7.108 +    TableFreeFn *entry_free_fn;
   7.109 +    /** Function to hash keys. */
   7.110 +    TableHashFn *key_hash_fn;
   7.111 +    /** Function to compare keys for equality. */
   7.112 +    TableEqualFn *key_equal_fn;
   7.113 +    /** Place for the user of the table to hang extra data. */
   7.114 +    void *user_data;
   7.115 +};
   7.116 +
   7.117 +extern HashTable *HashTable_new(int bucket_n);
   7.118 +extern void HashTable_free(HashTable *table);
   7.119 +extern HTEntry * HTEntry_new(Hashcode hashcode, void *key, void *value);
   7.120 +extern void HTEntry_free(HTEntry *entry);
   7.121 +extern int HashTable_set_bucket_n(HashTable *table, int bucket_n);
   7.122 +extern void HashTable_clear(HashTable *table);
   7.123 +extern HTEntry * HashTable_add_entry(HashTable *table, Hashcode hashcode, void *key, void *value);
   7.124 +extern HTEntry * HashTable_get_entry(HashTable *table, void *key);
   7.125 +extern HTEntry * HashTable_add(HashTable *table, void *key, void *value);
   7.126 +extern void * HashTable_get(HashTable *table, void *key);
   7.127 +extern int HashTable_remove(HashTable *table, void *key);
   7.128 +extern HTEntry * HashTable_find_entry(HashTable *table, Hashcode hashcode,
   7.129 +                                      TableTestFn *test_fn, TableArg arg);
   7.130 +extern int HashTable_remove_entry(HashTable *table, Hashcode hashcode,
   7.131 +                                   TableTestFn *test_fn, TableArg arg);
   7.132 +//extern int HashTable_map(HashTable *table, TableMapFn *map_fn, TableArg arg);
   7.133 +extern void HashTable_print(HashTable *table, IOStream *out);
   7.134 +extern int HashTable_set_buckets_n(HashTable *table, int buckets_n);
   7.135 +extern int HashTable_adjust(HashTable *table, int buckets_min);
   7.136 +extern void pseudo_des(unsigned long *pleft, unsigned long *pright);
   7.137 +extern Hashcode hash_string(char *s);
   7.138 +
   7.139 +extern int HashTable_order_bucket(HashTable *table, Hashcode hashcode, TableOrderFn *order);
   7.140 +
   7.141 +/** Control whether to use hashing based on DES or simple
   7.142 + * hashing. DES hashing is `more random' but much more expensive.
   7.143 + */
   7.144 +#define HASH_PSEUDO_DES 0
   7.145 +
   7.146 +/** Hash a long using a quick and dirty linear congruential random number generator.
   7.147 + *  See `Numerical Recipes in C', Chapter 7, "An Even Quicker Generator".
   7.148 + *
   7.149 + * @param a value to hash
   7.150 + * @return hashed input
   7.151 + */
   7.152 +static inline unsigned long lcrng_hash(unsigned long a){
   7.153 +    return (1664525L * a + 1013904223L);
   7.154 +}
   7.155 +
   7.156 +/** Hash an unsigned long.
   7.157 + *
   7.158 + * @param a input to hash
   7.159 + * @return hashcode
   7.160 + */
   7.161 +static inline Hashcode hash_ul(unsigned long a){
   7.162 +#if HASH_PSEUDO_DES
   7.163 +    unsigned long left = a;
   7.164 +    unsigned long right = 0L;
   7.165 +    pseudo_des(&left, &right);
   7.166 +    return right;
   7.167 +#else
   7.168 +    a = lcrng_hash(a);
   7.169 +    a = lcrng_hash(a);
   7.170 +    return a;
   7.171 +#endif
   7.172 +}
   7.173 +
   7.174 +/** Hash two unsigned longs together.
   7.175 + *
   7.176 + * @param a input to hash
   7.177 + * @param b input to hash
   7.178 + * @return hashcode
   7.179 + */
   7.180 +static inline Hashcode hash_2ul(unsigned long a, unsigned long b){
   7.181 +#if HASH_PSEUDO_DES
   7.182 +    unsigned long left = a;
   7.183 +    unsigned long right = b;
   7.184 +    pseudo_des(&left, &right);
   7.185 +    return right;
   7.186 +#else
   7.187 +    a = lcrng_hash(a);
   7.188 +    a ^= b;
   7.189 +    a = lcrng_hash(a);
   7.190 +    return a;
   7.191 +#endif
   7.192 +}
   7.193 +
   7.194 +/** Hash a hashcode and an unsigned long together.
   7.195 + *
   7.196 + * @param a input hashcode
   7.197 + * @param b input to hash
   7.198 + * @return hashcode
   7.199 + */
   7.200 +static inline Hashcode hash_hul(Hashcode a, unsigned long b){
   7.201 +#if HASH_PSEUDO_DES
   7.202 +    unsigned long left = a;
   7.203 +    unsigned long right = b;
   7.204 +    pseudo_des(&left, &right);
   7.205 +    return right;
   7.206 +#else
   7.207 +    a ^= b;
   7.208 +    a = lcrng_hash(a);
   7.209 +    return a;
   7.210 +#endif
   7.211 +}
   7.212 +
   7.213 +/** Macro to declare variables for HashTable_for_each() to use.
   7.214 + *
   7.215 + * @param entry variable that is set to entries in the table
   7.216 + */
   7.217 +#define HashTable_for_decl(entry) \
   7.218 +  HashTable *_var_table; \
   7.219 +  HTBucket *_var_bucket; \
   7.220 +  HTBucket *_var_end; \
   7.221 +  HTEntry *_var_next; \
   7.222 +  HTEntry *entry
   7.223 +
   7.224 +/** Macro to iterate over the entries in a hashtable.
   7.225 + * Must be in a scope where HashTable_for_decl() has been used to declare
   7.226 + * variables for it to use.
   7.227 + * The variable 'entry' is iterated over entries in the table.
   7.228 + * The code produced is syntactically a loop, so it must be followed by
   7.229 + * a loop body, typically some statements in braces:
   7.230 + * HashTable_for_each(entry, table){ ...loop body... }
   7.231 + *
   7.232 + * HashTable_for_each() and HashTable_for_decl() cannot be used for nested
   7.233 + * loops as variables will clash.
   7.234 + *
   7.235 + * @note The simplest way to code a direct loop over the entries in a hashtable
   7.236 + * is to use a loop over the buckets, with a nested loop over the entries
   7.237 + * in a bucket. Using this approach in a macro means the macro contains
   7.238 + * an opening brace, and calls to it must be followed by 2 braces!
   7.239 + * To avoid this the code has been restructured so that it is a for loop.
   7.240 + * So that statements could be used in the test expression of the for loop,
   7.241 + * we have used the gcc statement expression extension ({ ... }).
   7.242 + *
   7.243 + * @param entry variable to iterate over the entries
   7.244 + * @param table to iterate over (non-null)
   7.245 + */
   7.246 +#define HashTable_for_each(entry, table) \
   7.247 +  _var_table = table; \
   7.248 +  _var_bucket = _var_table->buckets; \
   7.249 +  _var_end = _var_bucket + _var_table->buckets_n; \
   7.250 +  for(entry=0, _var_next=0; \
   7.251 +      ({ if(_var_next){ \
   7.252 +             entry = _var_next; \
   7.253 +             _var_next = entry->next; \
   7.254 +          } else { \
   7.255 +             while(_var_bucket < _var_end){ \
   7.256 +                 entry = _var_bucket->head; \
   7.257 +                 _var_bucket++; \
   7.258 +                 if(entry){ \
   7.259 +                      _var_next = entry->next; \
   7.260 +                      break; \
   7.261 +                 } \
   7.262 +             } \
   7.263 +          }; \
   7.264 +         entry; }); \
   7.265 +      entry = _var_next )
   7.266 +
   7.267 +/** Map a function over the entries in a table.
   7.268 + * Mapping stops when the function returns a non-zero value.
   7.269 + * Uses the gcc statement expression extension ({ ... }).
   7.270 + *
   7.271 + * @param table to map over
   7.272 + * @param fn function to apply to entries
   7.273 + * @param arg first argument to call the function with
   7.274 + * @return 0 if fn always returned 0, first non-zero value otherwise
   7.275 + */
   7.276 +#define HashTable_map(table, fn, arg) \
   7.277 +  ({ HashTable_for_decl(_var_entry); \
   7.278 +    TableArg _var_arg = arg; \
   7.279 +    int _var_value = 0; \
   7.280 +    HashTable_for_each(_var_entry, table){ \
   7.281 +        if((_var_value = fn(_var_arg, _var_table, _var_entry))) break; \
   7.282 +    } \
   7.283 +    _var_value; })
   7.284 +
   7.285 +/** Cast x to the type for a key or value in a hash table.
   7.286 + * This avoids compiler warnings when using short integers
   7.287 + * as keys or values (especially on 64-bit platforms).
   7.288 + */
   7.289 +#define HKEY(x) ((void*)(unsigned long)(x))
   7.290 +
   7.291 +/** Cast x from the type for a key or value in a hash table.
   7.292 + * to an unsigned long. This avoids compiler warnings when using
   7.293 + * short integers as keys or values (especially on 64-bit platforms).
   7.294 + */
   7.295 +#define HVAL(x) ((unsigned long)(x))
   7.296 +
   7.297 +#endif /* !_XUTIL_HASH_TABLE_H_ */

     8.1 --- a/tools/libxutil/iostream.c	Sun Nov 21 20:41:00 2004 +0000
     8.2 +++ b/tools/libxutil/iostream.c	Mon Nov 22 16:41:50 2004 +0000
     8.3 @@ -1,3 +1,21 @@
     8.4 +/*
     8.5 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
     8.6 + *
     8.7 + * This library is free software; you can redistribute it and/or modify
     8.8 + * it under the terms of the GNU Lesser General Public License as published by
     8.9 + * the Free Software Foundation; either version 2.1 of the License, or
    8.10 + * (at your option) any later version.
    8.11 + *
    8.12 + * This library is distributed in the hope that it will be useful,
    8.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
    8.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    8.15 + * GNU Lesser General Public License for more details.
    8.16 + *
    8.17 + * You should have received a copy of the GNU Lesser General Public License
    8.18 + * along with this library; if not, write to the Free Software
    8.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    8.20 + */
    8.21 +
    8.22  #include "iostream.h"
    8.23  #include "sys_string.h"
    8.24  

     9.1 --- a/tools/libxutil/iostream.h	Sun Nov 21 20:41:00 2004 +0000
     9.2 +++ b/tools/libxutil/iostream.h	Mon Nov 22 16:41:50 2004 +0000
     9.3 @@ -1,14 +1,34 @@
     9.4 -#ifndef _XC_LINUX_SAVE_H_
     9.5 -#define _XC_LINUX_SAVE_H_
     9.6 +/*
     9.7 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
     9.8 + *
     9.9 + * This library is free software; you can redistribute it and/or modify
    9.10 + * it under the terms of the GNU Lesser General Public License as published by
    9.11 + * the Free Software Foundation; either version 2.1 of the License, or
    9.12 + * (at your option) any later version.
    9.13 + *
    9.14 + * This library is distributed in the hope that it will be useful,
    9.15 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
    9.16 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    9.17 + * GNU Lesser General Public License for more details.
    9.18 + *
    9.19 + * You should have received a copy of the GNU Lesser General Public License
    9.20 + * along with this library; if not, write to the Free Software
    9.21 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    9.22 + */
    9.23 +
    9.24 +#ifndef _XUTIL_IOSTREAM_H_
    9.25 +#define _XUTIL_IOSTREAM_H_
    9.26  
    9.27  #include <stdarg.h>
    9.28 -#include <stdint.h>
    9.29 -#include <stddef.h>
    9.30  
    9.31  #ifdef __KERNEL__
    9.32 +#include <linux/config.h>
    9.33 +#include <linux/types.h>
    9.34  #include <linux/errno.h>
    9.35  #else
    9.36  #include <errno.h>
    9.37 +#include <stdint.h>
    9.38 +#include <stddef.h>
    9.39  #endif
    9.40  
    9.41  #include "allocate.h"
    9.42 @@ -240,4 +260,4 @@ static inline int IOStream_get_written(I
    9.43  }
    9.44  
    9.45  
    9.46 -#endif /* ! _XC_LINUX_SAVE_H_ */
    9.47 +#endif /* ! _XUTIL_IOSTREAM_H_ */

    10.1 --- a/tools/libxutil/kernel_stream.c	Sun Nov 21 20:41:00 2004 +0000
    10.2 +++ b/tools/libxutil/kernel_stream.c	Mon Nov 22 16:41:50 2004 +0000
    10.3 @@ -50,7 +50,7 @@ typedef struct KernelData {
    10.4      char buf[BUF_N];
    10.5  } KernelData;
    10.6  
    10.7 -static int kernel_write(IOStream *s, const char *msg, int n);
    10.8 +static int kernel_write(IOStream *s, const void *msg, size_t n);
    10.9  static void kernel_free(IOStream *s);
   10.10  static void kernel_stream_lock(IOStream *s);
   10.11  static void kernel_stream_unlock(IOStream *s);
   10.12 @@ -145,13 +145,13 @@ void kernel_stream_unlock(IOStream *s){
   10.13   * @param args print arguments
   10.14   * @return result of the print
   10.15   */
   10.16 -static int kernel_write(IOStream *stream, const char *buf, int n){
   10.17 +static int kernel_write(IOStream *stream, const void *buf, size_t n){
   10.18    KernelData *kdata = get_kernel_data(stream);
   10.19    int k;
   10.20    k = kdata->buf_n - 1;
   10.21    if(n < k) k = n;
   10.22    memcpy(kdata->buf, buf, k);
   10.23 -  kdata->buf[k] = '\0'
   10.24 +  kdata->buf[k] = '\0';
   10.25    printk(kdata->buf);
   10.26    return k;
   10.27  }
   10.28 @@ -167,7 +167,7 @@ static void kernel_free(IOStream *io){
   10.29    KernelData *kdata;
   10.30    if(io == &iokernel) return;
   10.31    kdata = get_kernel_data(io);
   10.32 -  zero(kdata, sizeof(*kdata));
   10.33 +  memset(kdata, 0, sizeof(*kdata));
   10.34    deallocate(kdata);
   10.35  }
   10.36  #endif /* __KERNEL__ */

    11.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    11.2 +++ b/tools/libxutil/lexis.c	Mon Nov 22 16:41:50 2004 +0000
    11.3 @@ -0,0 +1,94 @@
    11.4 +/*
    11.5 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
    11.6 + *
    11.7 + * This library is free software; you can redistribute it and/or modify
    11.8 + * it under the terms of the GNU Lesser General Public License as
    11.9 + * published by the Free Software Foundation; either version 2.1 of the
   11.10 + * License, or  (at your option) any later version. This library is 
   11.11 + * distributed in the  hope that it will be useful, but WITHOUT ANY
   11.12 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or
   11.13 + * FITNESS FOR A PARTICULAR PURPOSE.
   11.14 + * See the GNU Lesser General Public License for more details.
   11.15 + *
   11.16 + * You should have received a copy of the GNU Lesser General Public License
   11.17 + * along with this library; if not, write to the Free Software Foundation,
   11.18 + * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
   11.19 + */
   11.20 +
   11.21 +/** @file
   11.22 + * Lexical analysis.
   11.23 + */
   11.24 +
   11.25 +#include "sys_string.h"
   11.26 +#include "lexis.h"
   11.27 +#include <errno.h>
   11.28 +
   11.29 +/** Check if a value lies in a (closed) range.
   11.30 + *
   11.31 + * @param x value to test
   11.32 + * @param lo low end of the range
   11.33 + * @param hi high end of the range
   11.34 + * @return 1 if x is in the interval [lo, hi], 0 otherwise
   11.35 + */
   11.36 +inline static int in_range(int x, int lo, int hi){
   11.37 +    return (lo <= x) && (x <= hi);
   11.38 +}
   11.39 +
   11.40 +/** Determine if a string is an (unsigned) decimal number.
   11.41 + * 
   11.42 + * @param s pointer to characters to test
   11.43 + * @param n length of string
   11.44 + * @return 1 if s is a decimal number, 0 otherwise.
   11.45 + */
   11.46 +int is_decimal_number(const char *s, int n){
   11.47 +    int i;
   11.48 +    if(n <= 0)return 0;
   11.49 +    for(i = 0; i < n; i++){
   11.50 +        if(!in_decimal_digit_class(s[i])) return 0;
   11.51 +    }
   11.52 +    return 1;
   11.53 +}
   11.54 +
   11.55 +/** Determine if a string is a hex number.
   11.56 + * Hex numbers are 0, or start with 0x or 0X followed
   11.57 + * by a non-zero number of hex digits (0-9,a-f,A-F).
   11.58 + * 
   11.59 + * @param s pointer to characters to test
   11.60 + * @param n length of string
   11.61 + * @return 1 if s is a hex number, 0 otherwise.
   11.62 + */
   11.63 +int is_hex_number(const char *s, int n){
   11.64 +    int i;
   11.65 +    if(n <= 0) return 0;
   11.66 +    if(n == 1){
   11.67 +        return s[0]=='0';
   11.68 +    }
   11.69 +    if(n <= 3) return 0;
   11.70 +    if(s[0] != '0' || (s[1] != 'x' && s[1] != 'X')) return 0;
   11.71 +    for(i = 2; i < n; i++){
   11.72 +        if(!in_hex_digit_class(s[i])) return 0;
   11.73 +    }
   11.74 +    return 1;
   11.75 +}
   11.76 +
   11.77 +/** Test if a string matches a keyword.
   11.78 + * The comparison is case-insensitive.
   11.79 + * The comparison fails if either argument is null.
   11.80 + *
   11.81 + * @param s string
   11.82 + * @param k keyword
   11.83 + * @return 1 if they match, 0 otherwise
   11.84 + */
   11.85 +int is_keyword(const char *s, const char *k){
   11.86 +  return s && k && !strcasecmp(s, k);
   11.87 +}
   11.88 +
   11.89 +/** Test if a string matches a character.
   11.90 + *
   11.91 + * @param s string
   11.92 + * @param c character (non-null)
   11.93 + * @return 1 if s contains exactly c, 0 otherwise
   11.94 + */
   11.95 +int is_keychar(const char *s, char c){
   11.96 +  return c && (s[0] == c) && !s[1];
   11.97 +}

    12.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    12.2 +++ b/tools/libxutil/lexis.h	Mon Nov 22 16:41:50 2004 +0000
    12.3 @@ -0,0 +1,128 @@
    12.4 +/*
    12.5 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
    12.6 + *
    12.7 + * This library is free software; you can redistribute it and/or modify
    12.8 + * it under the terms of the GNU Lesser General Public License as
    12.9 + * published by the Free Software Foundation; either version 2.1 of the
   12.10 + * License, or  (at your option) any later version. This library is 
   12.11 + * distributed in the  hope that it will be useful, but WITHOUT ANY
   12.12 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or
   12.13 + * FITNESS FOR A PARTICULAR PURPOSE.
   12.14 + * See the GNU Lesser General Public License for more details.
   12.15 + *
   12.16 + * You should have received a copy of the GNU Lesser General Public License
   12.17 + * along with this library; if not, write to the Free Software Foundation,
   12.18 + * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
   12.19 + */
   12.20 +
   12.21 +#ifndef _XUTIL_LEXIS_H_
   12.22 +#define _XUTIL_LEXIS_H_
   12.23 +
   12.24 +#include "sys_string.h"
   12.25 +
   12.26 +#ifdef __KERNEL__
   12.27 +#  include <linux/ctype.h>
   12.28 +#else
   12.29 +#  include <ctype.h>
   12.30 +#endif
   12.31 +
   12.32 +/** @file
   12.33 + * Lexical analysis.
   12.34 + */
   12.35 +
   12.36 +/** Class of characters treated as space. */
   12.37 +#define space_class ((char []){ '\n', '\r', '\t', ' ', '\f' , 0 })
   12.38 +
   12.39 +/** Class of separator characters. */
   12.40 +#define sep_class "{}()<>[]@!;"
   12.41 +
   12.42 +#define comment_class "#"
   12.43 +
   12.44 +/** Determine if a character is in a given class.
   12.45 + * 
   12.46 + * @param c character to test
   12.47 + * @param s null-terminated string of characters in the class
   12.48 + * @return 1 if c is in the class, 0 otherwise.
   12.49 + */
   12.50 +static inline int in_class(int c, const char *s){
   12.51 +  return s && (strchr(s, c) != 0);
   12.52 +}
   12.53 +
   12.54 +/** Determine if a character is in the space class.
   12.55 + * 
   12.56 + * @param c character to test
   12.57 + * @return 1 if c is in the class, 0 otherwise.
   12.58 + */
   12.59 +static inline int in_space_class(int c){
   12.60 +    return in_class(c, space_class);
   12.61 +}
   12.62 +
   12.63 +static inline int in_comment_class(int c){
   12.64 +    return in_class(c, comment_class);
   12.65 +}
   12.66 +
   12.67 +/** Determine if a character is in the separator class.
   12.68 + * Separator characters terminate tokens, and do not need space
   12.69 + * to separate them.
   12.70 + * 
   12.71 + * @param c character to test
   12.72 + * @return 1 if c is in the class, 0 otherwise.
   12.73 + */
   12.74 +static inline int in_sep_class(int c){
   12.75 +    return in_class(c, sep_class);
   12.76 +}
   12.77 +
   12.78 +/** Determine if a character is in the alpha class.
   12.79 + * 
   12.80 + * @param c character to test
   12.81 + * @return 1 if c is in the class, 0 otherwise.
   12.82 + */
   12.83 +static inline int in_alpha_class(int c){
   12.84 +    return isalpha(c);
   12.85 +}
   12.86 +
   12.87 +/** Determine if a character is in the octal digit class.
   12.88 + * 
   12.89 + * @param c character to test
   12.90 + * @return 1 if c is in the class, 0 otherwise.
   12.91 + */
   12.92 +static inline int in_octal_digit_class(int c){
   12.93 +    return '0' <= c && c <= '7';
   12.94 +}
   12.95 +
   12.96 +/** Determine if a character is in the decimal digit class.
   12.97 + * 
   12.98 + * @param c character to test
   12.99 + * @return 1 if c is in the class, 0 otherwise.
  12.100 + */
  12.101 +static inline int in_decimal_digit_class(int c){
  12.102 +    return isdigit(c);
  12.103 +}
  12.104 +
  12.105 +/** Determine if a character is in the hex digit class.
  12.106 + * 
  12.107 + * @param c character to test
  12.108 + * @return 1 if c is in the class, 0 otherwise.
  12.109 + */
  12.110 +static inline int in_hex_digit_class(int c){
  12.111 +    return isdigit(c) || in_class(c, "abcdefABCDEF");
  12.112 +}
  12.113 +
  12.114 +
  12.115 +static inline int in_string_quote_class(int c){
  12.116 +    return in_class(c, "'\"");
  12.117 +}
  12.118 +
  12.119 +static inline int in_printable_class(int c){
  12.120 +    return ('A' <= c && c <= 'Z')
  12.121 +        || ('a' <= c && c <= 'z')
  12.122 +        || ('0' <= c && c <= '9')
  12.123 +        || in_class(c, "!$%&*+,-./:;<=>?@^_`{|}~");
  12.124 +}
  12.125 +
  12.126 +extern int is_decimal_number(const char *s, int n);
  12.127 +extern int is_hex_number(const char *s, int n);
  12.128 +extern int is_keyword(const char *s, const char *k);
  12.129 +extern int is_keychar(const char *s, char c);
  12.130 +
  12.131 +#endif /* !_XUTIL_LEXIS_H_ */

    13.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    13.2 +++ b/tools/libxutil/socket_stream.c	Mon Nov 22 16:41:50 2004 +0000
    13.3 @@ -0,0 +1,230 @@
    13.4 +/*
    13.5 + * Copyright (C) 2004 Mike Wray <mike.wray@hp.com>
    13.6 + *
    13.7 + * This library is free software; you can redistribute it and/or modify
    13.8 + * it under the terms of the GNU Lesser General Public License as published by
    13.9 + * the Free Software Foundation; either version 2.1 of the License, or
   13.10 + * (at your option) any later version.
   13.11 + *
   13.12 + * This library is distributed in the hope that it will be useful,
   13.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
   13.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   13.15 + * GNU Lesser General Public License for more details.
   13.16 + *
   13.17 + * You should have received a copy of the GNU Lesser General Public License
   13.18 + * along with this library; if not, write to the Free Software
   13.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   13.20 + */
   13.21 +
   13.22 +/** @file
   13.23 + * An IOStream implementation using sockets.
   13.24 + */
   13.25 +#ifndef __KERNEL__
   13.26 +
   13.27 +#include <stdio.h>
   13.28 +#include <stdlib.h>
   13.29 +#include <string.h>
   13.30 +#include <unistd.h>
   13.31 +#include <errno.h>
   13.32 +#include "allocate.h"
   13.33 +#include "socket_stream.h"
   13.34 +
   13.35 +#define MODULE_NAME "sock"
   13.36 +#define DEBUG 0
   13.37 +//#undef DEBUG
   13.38 +#include "debug.h"
   13.39 +
   13.40 +static int socket_read(IOStream *s, void *buf, size_t n);
   13.41 +static int socket_write(IOStream *s, const void *buf, size_t n);
   13.42 +static int socket_error(IOStream *s);
   13.43 +static int socket_close(IOStream *s);
   13.44 +static void socket_free(IOStream *s);
   13.45 +static int socket_flush(IOStream *s);
   13.46 +
   13.47 +/** Methods used by a socket IOStream. */
   13.48 +static const IOMethods socket_methods = {
   13.49 +    read:  socket_read,
   13.50 +    write: socket_write,
   13.51 +    error: socket_error,
   13.52 +    close: socket_close,
   13.53 +    free:  socket_free,
   13.54 +    flush: socket_flush,
   13.55 +};
   13.56 +
   13.57 +/** Get the socket data.
   13.58 + * 
   13.59 + * @param io socket stream
   13.60 + * @return data
   13.61 + */
   13.62 +static inline SocketData * socket_data(IOStream *io){
   13.63 +    return (SocketData *)io->data;
   13.64 +}
   13.65 +
   13.66 +/** Test if a stream is a socket stream.
   13.67 + *
   13.68 + * @param io stream
   13.69 + * @return 0 if a socket stream, -EINVAL if not
   13.70 + */
   13.71 +int socket_stream_check(IOStream *io){
   13.72 +    return (io && io->methods == &socket_methods ? 0 : -EINVAL);
   13.73 +}
   13.74 +
   13.75 +/** Get the data for a socket stream.
   13.76 + *
   13.77 + * @param io stream
   13.78 + * @param data return value for the data
   13.79 + * @return 0 if a socket stream, -EINVAL if not
   13.80 + */
   13.81 +int socket_stream_data(IOStream *io, SocketData **data){
   13.82 +    int err = socket_stream_check(io);
   13.83 +    if(err){
   13.84 +        *data = NULL;
   13.85 +    } else {
   13.86 +        *data = socket_data(io);
   13.87 +    }
   13.88 +    return err;
   13.89 +}
   13.90 +
   13.91 +/** Set the destination address for a socket stream.
   13.92 + *
   13.93 + * @param io stream
   13.94 + * @param addr address
   13.95 + * @return 0 if a socket stream, -EINVAL if not
   13.96 + */
   13.97 +int socket_stream_set_addr(IOStream *io, struct sockaddr_in *addr){
   13.98 +    int err = 0;
   13.99 +    SocketData *data = NULL;
  13.100 +    err = socket_stream_data(io, &data);
  13.101 +    if(!err){
  13.102 +        data->daddr = *addr;
  13.103 +    }
  13.104 +    return err;
  13.105 +}
  13.106 +
  13.107 +/** Set the send flags for a socket stream.
  13.108 + *
  13.109 + * @param io stream
  13.110 + * @param flags flags
  13.111 + * @return 0 if a socket stream, -EINVAL if not
  13.112 + */
  13.113 +int socket_stream_set_flags(IOStream *io, int flags){
  13.114 +    int err = 0;
  13.115 +    SocketData *data = NULL;
  13.116 +    err = socket_stream_data(io, &data);
  13.117 +    if(!err){
  13.118 +        data->flags = flags;
  13.119 +    }
  13.120 +    return err;
  13.121 +}
  13.122 +
  13.123 +/** Write to the underlying socket using sendto.
  13.124 + *
  13.125 + * @param stream input
  13.126 + * @param buf where to put input
  13.127 + * @param n number of bytes to write
  13.128 + * @return number of bytes written
  13.129 + */
  13.130 +static int socket_write(IOStream *s, const void *buf, size_t n){
  13.131 +    SocketData *data = socket_data(s);
  13.132 +    struct sockaddr *daddr = (struct sockaddr *)&data->daddr;
  13.133 +    socklen_t daddr_n = sizeof(data->daddr);
  13.134 +    int k;
  13.135 +    dprintf("> sock=%d addr=%s:%d n=%d\n",
  13.136 +            data->fd, inet_ntoa(data->daddr.sin_addr), ntohs(data->daddr.sin_port), n);
  13.137 +    if(0){
  13.138 +        struct sockaddr_in self = {};
  13.139 +        socklen_t self_n;
  13.140 +        getsockname(data->fd, (struct sockaddr *)&self, &self_n);
  13.141 +        dprintf("> sockname sock=%d %s:%d\n",
  13.142 +                data->fd, inet_ntoa(self.sin_addr), ntohs(self.sin_port));
  13.143 +    }
  13.144 +    k = sendto(data->fd, buf, n, data->flags, daddr, daddr_n);
  13.145 +    dprintf("> sendto=%d\n", k);
  13.146 +    return k;
  13.147 +}
  13.148 +
  13.149 +/** Read from the underlying stream using recv();
  13.150 + *
  13.151 + * @param stream input
  13.152 + * @param buf where to put input
  13.153 + * @param n number of bytes to read
  13.154 + * @return number of bytes read
  13.155 + */
  13.156 +static int socket_read(IOStream *s, void *buf, size_t n){
  13.157 +    SocketData *data = socket_data(s);
  13.158 +    int k;
  13.159 +    struct sockaddr *saddr = (struct sockaddr *)&data->saddr;
  13.160 +    socklen_t saddr_n = sizeof(data->saddr);
  13.161 +    k = recvfrom(data->fd, buf, n, data->flags, saddr, &saddr_n);
  13.162 +    return k;
  13.163 +}
  13.164 +
  13.165 +/** Flush the socket (no-op).
  13.166 + *
  13.167 + * @param s socket stream
  13.168 + * @return 0 on success, error code otherwise
  13.169 + */
  13.170 +static int socket_flush(IOStream *s){
  13.171 +    return 0;
  13.172 +}
  13.173 +
  13.174 +/** Check if a socket stream has an error (no-op).
  13.175 + *
  13.176 + * @param s socket stream
  13.177 + * @return 1 if has an error, 0 otherwise
  13.178 + */
  13.179 +static int socket_error(IOStream *s){
  13.180 +    // Read SOL_SOCKET/SO_ERROR ?
  13.181 +    return 0;
  13.182 +}
  13.183 +
  13.184 +/** Close a socket stream.
  13.185 + *
  13.186 + * @param s socket stream to close
  13.187 + * @return result of the close
  13.188 + */
  13.189 +static int socket_close(IOStream *s){
  13.190 +    SocketData *data = socket_data(s);
  13.191 +    return close(data->fd);
  13.192 +}
  13.193 +
  13.194 +/** Free a socket stream.
  13.195 + *
  13.196 + * @param s socket stream
  13.197 + */
  13.198 +static void socket_free(IOStream *s){
  13.199 +    SocketData *data = socket_data(s);
  13.200 +    deallocate(data);
  13.201 +}
  13.202 +
  13.203 +/** Create an IOStream for a socket.
  13.204 + *
  13.205 + * @param fd socket to wtap
  13.206 + * @return new IOStream using fd for i/o
  13.207 + */
  13.208 +IOStream *socket_stream_new(int fd){
  13.209 +    int err = -ENOMEM;
  13.210 +    IOStream *io = NULL;
  13.211 +    SocketData *data = NULL;
  13.212 +
  13.213 +    io = ALLOCATE(IOStream);
  13.214 +    if(!io) goto exit;
  13.215 +    io->methods = &socket_methods;
  13.216 +    data = ALLOCATE(SocketData);
  13.217 +    if(!data) goto exit;
  13.218 +    io->data = data;
  13.219 +    data->fd = fd;
  13.220 +    data->buf_n = sizeof(data->buf);
  13.221 +    err = 0;
  13.222 +  exit:
  13.223 +    if(err){
  13.224 +        if(io){
  13.225 +            if(data) deallocate(data);
  13.226 +            deallocate(io);
  13.227 +            io = NULL;
  13.228 +        }
  13.229 +    }
  13.230 +    return io;
  13.231 +}
  13.232 +
  13.233 +#endif

    14.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    14.2 +++ b/tools/libxutil/socket_stream.h	Mon Nov 22 16:41:50 2004 +0000
    14.3 @@ -0,0 +1,53 @@
    14.4 +/*
    14.5 + * Copyright (C) 2004 Mike Wray <mike.wray@hp.com>
    14.6 + *
    14.7 + * This library is free software; you can redistribute it and/or modify
    14.8 + * it under the terms of the GNU Lesser General Public License as published by
    14.9 + * the Free Software Foundation; either version 2.1 of the License, or
   14.10 + * (at your option) any later version.
   14.11 + *
   14.12 + * This library is distributed in the hope that it will be useful,
   14.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
   14.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   14.15 + * GNU Lesser General Public License for more details.
   14.16 + *
   14.17 + * You should have received a copy of the GNU Lesser General Public License
   14.18 + * along with this library; if not, write to the Free Software
   14.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   14.20 + */
   14.21 +
   14.22 +#ifndef _XEN_LIB_SOCKET_STREAM_H_
   14.23 +#define _XEN_LIB_SOCKET_STREAM_H_
   14.24 +
   14.25 +#ifndef __KERNEL__
   14.26 +#include "iostream.h"
   14.27 +#include <stdio.h>
   14.28 +
   14.29 +#include <sys/socket.h>
   14.30 +#include <netinet/in.h>
   14.31 +#include <arpa/inet.h>
   14.32 +
   14.33 +/** Data associated with a socket stream. */
   14.34 +typedef struct SocketData {
   14.35 +    /** The socket file descriptor. */
   14.36 +    int fd;
   14.37 +    /** Source address from last read (recvfrom). */
   14.38 +    struct sockaddr_in saddr;
   14.39 +    /** Destination address for writes (sendto). */
   14.40 +    struct sockaddr_in daddr;
   14.41 +    /** Write flags (sendto). */
   14.42 +    int flags;
   14.43 +    /** Buffer size. */
   14.44 +    int buf_n;
   14.45 +    /** Buffer for formatted printing. */
   14.46 +    char buf[1024];
   14.47 +} SocketData;
   14.48 +
   14.49 +extern IOStream *socket_stream_new(int fd);
   14.50 +extern int socket_stream_data(IOStream *io, SocketData **data);
   14.51 +extern int socket_stream_check(IOStream *io);
   14.52 +extern int socket_stream_set_addr(IOStream *io, struct sockaddr_in *addr);
   14.53 +extern int socket_stream_set_flags(IOStream *io, int flags);
   14.54 +
   14.55 +#endif
   14.56 +#endif /* !_XEN_LIB_SOCKET_STREAM_H_ */

    15.1 --- a/tools/libxutil/string_stream.c	Sun Nov 21 20:41:00 2004 +0000
    15.2 +++ b/tools/libxutil/string_stream.c	Mon Nov 22 16:41:50 2004 +0000
    15.3 @@ -1,5 +1,5 @@
    15.4  /*
    15.5 - * Copyright (C) 2001, 2002 Hewlett-Packard Company.
    15.6 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
    15.7   *
    15.8   * This library is free software; you can redistribute it and/or modify
    15.9   * it under the terms of the GNU Lesser General Public License as published by

    16.1 --- a/tools/libxutil/string_stream.h	Sun Nov 21 20:41:00 2004 +0000
    16.2 +++ b/tools/libxutil/string_stream.h	Mon Nov 22 16:41:50 2004 +0000
    16.3 @@ -1,5 +1,5 @@
    16.4  /*
    16.5 - * Copyright (C) 2001, 2002 Hewlett-Packard Company.
    16.6 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
    16.7   *
    16.8   * This library is free software; you can redistribute it and/or modify
    16.9   * it under the terms of the GNU Lesser General Public License as published by

    17.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    17.2 +++ b/tools/libxutil/sxpr.c	Mon Nov 22 16:41:50 2004 +0000
    17.3 @@ -0,0 +1,956 @@
    17.4 +/*
    17.5 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
    17.6 + *
    17.7 + * This library is free software; you can redistribute it and/or modify
    17.8 + * it under the terms of the GNU Lesser General Public License as
    17.9 + * published by the Free Software Foundation; either version 2.1 of the
   17.10 + * License, or  (at your option) any later version. This library is 
   17.11 + * distributed in the  hope that it will be useful, but WITHOUT ANY
   17.12 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or
   17.13 + * FITNESS FOR A PARTICULAR PURPOSE.
   17.14 + * See the GNU Lesser General Public License for more details.
   17.15 + *
   17.16 + * You should have received a copy of the GNU Lesser General Public License
   17.17 + * along with this library; if not, write to the Free Software Foundation,
   17.18 + * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
   17.19 + */
   17.20 +
   17.21 +#include <stdarg.h>
   17.22 +#include "sys_string.h"
   17.23 +#include "lexis.h"
   17.24 +#include "sys_net.h"
   17.25 +#include "hash_table.h"
   17.26 +#include "sxpr.h"
   17.27 +
   17.28 +#ifdef __KERNEL__
   17.29 +#include <linux/errno.h>
   17.30 +#else
   17.31 +#include <errno.h>
   17.32 +#endif
   17.33 +
   17.34 +#undef free
   17.35 +
   17.36 +/** @file
   17.37 + * General representation of sxprs.
   17.38 + * Includes print, equal, and free functions for the sxpr types.
   17.39 + *
   17.40 + * Zero memory containing an Sxpr will have the value ONONE - this is intentional.
   17.41 + * When a function returning an sxpr cannot allocate memory we return ONOMEM.
   17.42 + *
   17.43 + */
   17.44 +
   17.45 +static int atom_print(IOStream *io, Sxpr obj, unsigned flags);
   17.46 +static int atom_equal(Sxpr x, Sxpr y);
   17.47 +static void atom_free(Sxpr obj);
   17.48 +
   17.49 +static int string_print(IOStream *io, Sxpr obj, unsigned flags);
   17.50 +static int string_equal(Sxpr x, Sxpr y);
   17.51 +static void string_free(Sxpr obj);
   17.52 +
   17.53 +static int cons_print(IOStream *io, Sxpr obj, unsigned flags);
   17.54 +static int cons_equal(Sxpr x, Sxpr y);
   17.55 +static void cons_free(Sxpr obj);
   17.56 +
   17.57 +static int null_print(IOStream *io, Sxpr obj, unsigned flags);
   17.58 +static int none_print(IOStream *io, Sxpr obj, unsigned flags);
   17.59 +static int int_print(IOStream *io, Sxpr obj, unsigned flags);
   17.60 +static int bool_print(IOStream *io, Sxpr obj, unsigned flags);
   17.61 +
   17.62 +/** Type definitions. */
   17.63 +static SxprType types[1024] = {
   17.64 +    [T_NONE]     { type:    T_NONE,     name: "none",       print: none_print      },
   17.65 +    [T_NULL]     { type:    T_NULL,     name: "null",       print: null_print      },
   17.66 +    [T_UINT]     { type:    T_UINT,     name: "int",        print: int_print,      },
   17.67 +    [T_BOOL]     { type:    T_BOOL,     name: "bool",       print: bool_print,     },
   17.68 +    [T_ATOM]     { type:    T_ATOM,     name: "atom",       print: atom_print,
   17.69 +		   pointer: TRUE,
   17.70 +		   free:    atom_free,
   17.71 +		   equal:   atom_equal,
   17.72 +		 },
   17.73 +    [T_STRING]   { type:    T_STRING,   name: "string",     print: string_print,
   17.74 +		   pointer: TRUE,
   17.75 +		   free:    string_free,
   17.76 +		   equal:   string_equal,
   17.77 +		 },
   17.78 +    [T_CONS]     { type:    T_CONS,     name: "cons",       print: cons_print,
   17.79 +		   pointer: TRUE,
   17.80 +		   free:    cons_free,
   17.81 +		   equal:   cons_equal,
   17.82 +		 },
   17.83 +};
   17.84 +
   17.85 +/** Number of entries in the types array. */
   17.86 +static int type_sup = sizeof(types)/sizeof(types[0]);
   17.87 +
   17.88 +/** Get the type definition for a given type code.
   17.89 + *
   17.90 + * @param ty type code
   17.91 + * @return type definition or null
   17.92 + */
   17.93 +SxprType *get_sxpr_type(int ty){
   17.94 +    if(0 <= ty && ty < type_sup){
   17.95 +        return types+ty;
   17.96 +    }
   17.97 +    return NULL;
   17.98 +}
   17.99 +
  17.100 +/** The default print function.
  17.101 + *
  17.102 + * @param io stream to print to
  17.103 + * @param x sxpr to print
  17.104 + * @param flags print flags
  17.105 + * @return number of bytes written on success
  17.106 + */
  17.107 +int default_print(IOStream *io, Sxpr x, unsigned flags){
  17.108 +    return IOStream_print(io, "#<%u %lu>\n", get_type(x), get_ul(x));
  17.109 +}
  17.110 +
  17.111 +/** The default equal function.
  17.112 + * Uses eq().
  17.113 + *
  17.114 + * @param x sxpr to compare
  17.115 + * @param y sxpr to compare
  17.116 + * @return 1 if equal, 0 otherwise
  17.117 + */
  17.118 +int default_equal(Sxpr x, Sxpr y){
  17.119 +    return eq(x, y);
  17.120 +}
  17.121 +
  17.122 +/** General sxpr print function.
  17.123 + * Prints an sxpr on a stream using the print function for the sxpr type.
  17.124 + * Printing is controlled by flags from the PrintFlags enum.
  17.125 + * If PRINT_TYPE is in the flags the sxpr type is printed before the sxpr
  17.126 + * (for debugging).
  17.127 + *
  17.128 + * @param io stream to print to
  17.129 + * @param x sxpr to print
  17.130 + * @param flags print flags
  17.131 + * @return number of bytes written
  17.132 + */
  17.133 +int objprint(IOStream *io, Sxpr x, unsigned flags){
  17.134 +    SxprType *def = get_sxpr_type(get_type(x));
  17.135 +    ObjPrintFn *print_fn = (def && def->print ? def->print : default_print);
  17.136 +    int k = 0;
  17.137 +    if(!io) return k;
  17.138 +    if(flags & PRINT_TYPE){
  17.139 +	k += IOStream_print(io, "%s:", def->name);
  17.140 +    }
  17.141 +    k += print_fn(io, x, flags);
  17.142 +    return k;
  17.143 +}
  17.144 +
  17.145 +/** General sxpr free function.
  17.146 + * Frees an sxpr using the free function for its type.
  17.147 + * Free functions must recursively free any subsxprs.
  17.148 + * If no function is defined then the default is to
  17.149 + * free sxprs whose type has pointer true.
  17.150 + * Sxprs must not be used after freeing.
  17.151 + *
  17.152 + * @param x sxpr to free
  17.153 + */
  17.154 +void objfree(Sxpr x){
  17.155 +    SxprType *def = get_sxpr_type(get_type(x));
  17.156 +
  17.157 +    if(def){
  17.158 +	if(def->free){
  17.159 +	    def->free(x);
  17.160 +	} else if (def->pointer){
  17.161 +	    hfree(x);
  17.162 +	}
  17.163 +    }
  17.164 +}
  17.165 +
  17.166 +/** General sxpr equality function.
  17.167 + * Compares x and y using the equal function for x.
  17.168 + * Uses default_equal() if x has no equal function.
  17.169 + *
  17.170 + * @param x sxpr to compare
  17.171 + * @param y sxpr to compare
  17.172 + * @return 1 if equal, 0 otherwise
  17.173 + */
  17.174 +int objequal(Sxpr x, Sxpr y){
  17.175 +    SxprType *def = get_sxpr_type(get_type(x));
  17.176 +    ObjEqualFn *equal_fn = (def && def->equal ? def->equal : default_equal);
  17.177 +    return equal_fn(x, y);
  17.178 +}
  17.179 +
  17.180 +/** Search for a key in an alist.
  17.181 + * An alist is a list of conses, where the cars
  17.182 + * of the conses are the keys. Compares keys using equality.
  17.183 + *
  17.184 + * @param k key
  17.185 + * @param l alist to search
  17.186 + * @return first element of l with car k, or ONULL
  17.187 + */
  17.188 +Sxpr assoc(Sxpr k, Sxpr l){
  17.189 +    for( ; CONSP(l) ; l = CDR(l)){
  17.190 +        Sxpr x = CAR(l);
  17.191 +        if(CONSP(x) && objequal(k, CAR(x))){
  17.192 +            return x;   
  17.193 +        }
  17.194 +    }
  17.195 +    return ONULL;
  17.196 +}
  17.197 +
  17.198 +/** Search for a key in an alist.
  17.199 + * An alist is a list of conses, where the cars
  17.200 + * of the conses are the keys. Compares keys using eq.
  17.201 + *
  17.202 + * @param k key
  17.203 + * @param l alist to search
  17.204 + * @return first element of l with car k, or ONULL
  17.205 + */
  17.206 +Sxpr assocq(Sxpr k, Sxpr l){
  17.207 +    for( ; CONSP(l); l = CDR(l)){
  17.208 +        Sxpr x = CAR(l);
  17.209 +        if(CONSP(x) && eq(k, CAR(x))){
  17.210 +            return x;
  17.211 +        }
  17.212 +    }
  17.213 +    return ONULL;
  17.214 +}
  17.215 +
  17.216 +/** Add a new key and value to an alist.
  17.217 + *
  17.218 + * @param k key
  17.219 + * @param l value
  17.220 + * @param l alist
  17.221 + * @return l with the new cell added to the front
  17.222 + */
  17.223 +Sxpr acons(Sxpr k, Sxpr v, Sxpr l){
  17.224 +    Sxpr x, y;
  17.225 +    x = cons_new(k, v);
  17.226 +    if(NOMEMP(x)) return x;
  17.227 +    y = cons_new(x, l);
  17.228 +    if(NOMEMP(y)) cons_free_cells(x);
  17.229 +    return y;
  17.230 +}
  17.231 +
  17.232 +/** Test if a list contains an element.
  17.233 + * Uses sxpr equality.
  17.234 + *
  17.235 + * @param l list
  17.236 + * @param x element to look for
  17.237 + * @return a tail of l with x as car, or ONULL
  17.238 + */
  17.239 +Sxpr cons_member(Sxpr l, Sxpr x){
  17.240 +    for( ; CONSP(l) && !eq(x, CAR(l)); l = CDR(l)){}
  17.241 +    return l;
  17.242 +}
  17.243 +
  17.244 +/** Test if a list contains an element satisfying a test.
  17.245 + * The test function is called with v and an element of the list.
  17.246 + *
  17.247 + * @param l list
  17.248 + * @param test_fn test function to use
  17.249 + * @param v value for first argument to the test
  17.250 + * @return a tail of l with car satisfying the test, or 0
  17.251 + */
  17.252 +Sxpr cons_member_if(Sxpr l, ObjEqualFn *test_fn, Sxpr v){
  17.253 +    for( ; CONSP(l) && !test_fn(v, CAR(l)); l = CDR(l)){ }
  17.254 +    return l;
  17.255 +}
  17.256 +
  17.257 +/** Test if the elements of list 't' are a subset of the elements
  17.258 + * of list 's'. Element order is not significant.
  17.259 + *
  17.260 + * @param s element list to check subset of
  17.261 + * @param t element list to check if is a subset
  17.262 + * @return 1 if is a subset, 0 otherwise
  17.263 + */
  17.264 +int cons_subset(Sxpr s, Sxpr t){
  17.265 +    for( ; CONSP(t); t = CDR(t)){
  17.266 +	if(!CONSP(cons_member(s, CAR(t)))){
  17.267 +	    return 0;
  17.268 +	}
  17.269 +    }
  17.270 +    return 1;
  17.271 +}
  17.272 +
  17.273 +/** Test if two lists have equal sets of elements.
  17.274 + * Element order is not significant.
  17.275 + *
  17.276 + * @param s list to check
  17.277 + * @param t list to check
  17.278 + * @return 1 if equal, 0 otherwise
  17.279 + */
  17.280 +int cons_set_equal(Sxpr s, Sxpr t){
  17.281 +    return cons_subset(s, t) && cons_subset(t, s);
  17.282 +}
  17.283 +
  17.284 +#ifdef USE_GC
  17.285 +/*============================================================================*/
  17.286 +/* The functions inside this ifdef are only safe if GC is used.
  17.287 + * Otherwise they may leak memory.
  17.288 + */
  17.289 +
  17.290 +/** Remove an element from a list (GC only).
  17.291 + * Uses sxpr equality and removes all instances, even
  17.292 + * if there are more than one.
  17.293 + *
  17.294 + * @param l list to remove elements from
  17.295 + * @param x element to remove
  17.296 + * @return modified input list
  17.297 + */
  17.298 +Sxpr cons_remove(Sxpr l, Sxpr x){
  17.299 +    return cons_remove_if(l, eq, x);
  17.300 +}
  17.301 +
  17.302 +/** Remove elements satisfying a test (GC only).
  17.303 + * The test function is called with v and an element of the set.
  17.304 + *
  17.305 + * @param l list to remove elements from
  17.306 + * @param test_fn function to use to decide if an element should be removed
  17.307 + * @return modified input list
  17.308 + */
  17.309 +Sxpr cons_remove_if(Sxpr l, ObjEqualFn *test_fn, Sxpr v){
  17.310 +    Sxpr prev = ONULL, elt, next;
  17.311 +
  17.312 +    for(elt = l; CONSP(elt); elt = next){
  17.313 +        next = CDR(elt);
  17.314 +        if(test_fn(v, CAR(elt))){
  17.315 +            if(NULLP(prev)){
  17.316 +                l = next;
  17.317 +            } else {
  17.318 +                CDR(prev) = next;
  17.319 +            }
  17.320 +        }
  17.321 +    }
  17.322 +    return l;
  17.323 +}
  17.324 +
  17.325 +/** Set the value for a key in an alist (GC only).
  17.326 + * If the key is present, changes the value, otherwise
  17.327 + * adds a new cell.
  17.328 + *
  17.329 + * @param k key
  17.330 + * @param v value
  17.331 + * @param l alist
  17.332 + * @return modified or extended list
  17.333 + */
  17.334 +Sxpr setf(Sxpr k, Sxpr v, Sxpr l){
  17.335 +    Sxpr e = assoc(k, l);
  17.336 +    if(NULLP(e)){
  17.337 +        l = acons(k, v, l);
  17.338 +    } else {
  17.339 +        CAR(CDR(e)) = v;
  17.340 +    }
  17.341 +    return l;
  17.342 +}
  17.343 +/*============================================================================*/
  17.344 +#endif /* USE_GC */
  17.345 +
  17.346 +/** Create a new atom with the given name.
  17.347 + *
  17.348 + * @param name the name
  17.349 + * @return new atom
  17.350 + */
  17.351 +Sxpr atom_new(char *name){
  17.352 +    Sxpr n, obj = ONOMEM;
  17.353 +
  17.354 +    n = string_new(name);
  17.355 +    if(NOMEMP(n)) goto exit;
  17.356 +    obj = HALLOC(ObjAtom, T_ATOM);
  17.357 +    if(NOMEMP(obj)) goto exit;
  17.358 +    OBJ_ATOM(obj)->name = n;
  17.359 +  exit:
  17.360 +    return obj;
  17.361 +}
  17.362 +
  17.363 +/** Free an atom.
  17.364 + *
  17.365 + * @param obj to free
  17.366 + */
  17.367 +void atom_free(Sxpr obj){
  17.368 +    // Interned atoms are shared, so do not free.
  17.369 +    if(OBJ_ATOM(obj)->interned) return;
  17.370 +    objfree(OBJ_ATOM(obj)->name);
  17.371 +    hfree(obj);
  17.372 +}
  17.373 +
  17.374 +/** Print an atom. Prints the atom name.
  17.375 + *
  17.376 + * @param io stream to print to
  17.377 + * @param obj to print
  17.378 + * @param flags print flags
  17.379 + * @return number of bytes printed
  17.380 + */
  17.381 +int atom_print(IOStream *io, Sxpr obj, unsigned flags){
  17.382 +    //return string_print(io, OBJ_ATOM(obj)->name, (flags | PRINT_RAW));
  17.383 +    return string_print(io, OBJ_ATOM(obj)->name, flags);
  17.384 +}
  17.385 +
  17.386 +/** Atom equality.
  17.387 + *
  17.388 + * @param x to compare
  17.389 + * @param y to compare
  17.390 + * @return 1 if equal, 0 otherwise
  17.391 + */
  17.392 +int atom_equal(Sxpr x, Sxpr y){
  17.393 +    int ok;
  17.394 +    ok = eq(x, y);
  17.395 +    if(ok) goto exit;
  17.396 +    ok = ATOMP(y) && string_equal(OBJ_ATOM(x)->name, OBJ_ATOM(y)->name);
  17.397 +    if(ok) goto exit;
  17.398 +    ok = STRINGP(y) && string_equal(OBJ_ATOM(x)->name, y);
  17.399 +  exit:
  17.400 +    return ok;
  17.401 +}
  17.402 +
  17.403 +/** Get the name of an atom.
  17.404 + *
  17.405 + * @param obj atom
  17.406 + * @return name
  17.407 + */
  17.408 +char * atom_name(Sxpr obj){
  17.409 +    return string_string(OBJ_ATOM(obj)->name);
  17.410 +}
  17.411 +
  17.412 +/** Get the C string from a string sxpr.
  17.413 + *
  17.414 + * @param obj string sxpr
  17.415 + * @return string
  17.416 + */
  17.417 +char * string_string(Sxpr obj){
  17.418 +    return OBJ_STRING(obj);
  17.419 +}
  17.420 +
  17.421 +/** Get the length of a string.
  17.422 + *
  17.423 + * @param obj string
  17.424 + * @return length
  17.425 + */
  17.426 +int string_length(Sxpr obj){
  17.427 +    return strlen(OBJ_STRING(obj));
  17.428 +}
  17.429 +
  17.430 +/** Create a new string. The input string is copied,
  17.431 + * and must be null-terminated.
  17.432 + *
  17.433 + * @param s characters to put in the string
  17.434 + * @return new sxpr
  17.435 + */
  17.436 +Sxpr string_new(char *s){
  17.437 +    int n = (s ? strlen(s) : 0);
  17.438 +    Sxpr obj;
  17.439 +    obj = halloc(n+1, T_STRING);
  17.440 +    if(!NOMEMP(obj)){
  17.441 +        char *str = OBJ_STRING(obj);
  17.442 +        strncpy(str, s, n);
  17.443 +        str[n] = '\0';
  17.444 +    }
  17.445 +    return obj;
  17.446 +}
  17.447 +
  17.448 +/** Free a string.
  17.449 + *
  17.450 + * @param obj to free
  17.451 + */
  17.452 +void string_free(Sxpr obj){
  17.453 +    hfree(obj);
  17.454 +}
  17.455 +
  17.456 +/** Determine if a string needs escapes when printed
  17.457 + * using the given flags.
  17.458 + *
  17.459 + * @param str string to check
  17.460 + * @param flags print flags
  17.461 + * @return 1 if needs escapes, 0 otherwise
  17.462 + */
  17.463 +int needs_escapes(char *str, unsigned flags){
  17.464 +    char *c;
  17.465 +    int val = 0;
  17.466 +
  17.467 +    if(str){
  17.468 +	for(c=str; *c; c++){
  17.469 +	    if(in_alpha_class(*c)) continue;
  17.470 +	    if(in_decimal_digit_class(*c)) continue;
  17.471 +	    if(in_class(*c, "/._+:@~-")) continue;
  17.472 +	    val = 1;
  17.473 +	    break;
  17.474 +	}
  17.475 +    }
  17.476 +    //printf("\n> val=%d str=|%s|\n", val, str);
  17.477 +    return val;
  17.478 +}
  17.479 +
  17.480 +/** Print a string to a stream, with escapes if necessary.
  17.481 + *
  17.482 + * @param io stream to print to
  17.483 + * @param str string
  17.484 + * @param flags print flags
  17.485 + * @return number of bytes written
  17.486 + */
  17.487 +int _string_print(IOStream *io, char *str, unsigned flags){
  17.488 +    int k = 0;
  17.489 +    if((flags & PRINT_RAW) || !needs_escapes(str, flags)){
  17.490 +        k += IOStream_print(io, str);
  17.491 +    } else {
  17.492 +	k += IOStream_print(io, "\"");
  17.493 +	if(str){
  17.494 +            char *s;
  17.495 +            for(s = str; *s; s++){
  17.496 +                if(*s < ' ' || *s >= 127 ){
  17.497 +                    switch(*s){
  17.498 +                    case '\a': k += IOStream_print(io, "\\a");  break;
  17.499 +                    case '\b': k += IOStream_print(io, "\\b");  break;
  17.500 +                    case '\f': k += IOStream_print(io, "\\f");  break;
  17.501 +                    case '\n': k += IOStream_print(io, "\\n");  break;
  17.502 +                    case '\r': k += IOStream_print(io, "\\r");  break;
  17.503 +                    case '\t': k += IOStream_print(io, "\\t");  break;
  17.504 +                    case '\v': k += IOStream_print(io, "\\v");  break;
  17.505 +                    default:
  17.506 +                        // Octal escape;
  17.507 +                        k += IOStream_print(io, "\\%o", *s);
  17.508 +                        break;
  17.509 +                    }
  17.510 +                } else if(*s == c_double_quote ||
  17.511 +                          *s == c_single_quote ||
  17.512 +                          *s == c_escape){
  17.513 +                    k += IOStream_print(io, "\\%c", *s);
  17.514 +                } else {
  17.515 +                    k+= IOStream_print(io, "%c", *s);
  17.516 +                }
  17.517 +            }
  17.518 +	}
  17.519 +	k += IOStream_print(io, "\"");
  17.520 +    }
  17.521 +    return k;
  17.522 +}
  17.523 +
  17.524 +/** Print a string to a stream, with escapes if necessary.
  17.525 + *
  17.526 + * @param io stream to print to
  17.527 + * @param obj string
  17.528 + * @param flags print flags
  17.529 + * @return number of bytes written
  17.530 + */
  17.531 +int string_print(IOStream *io, Sxpr obj, unsigned flags){
  17.532 +    return _string_print(io, OBJ_STRING(obj), flags);
  17.533 +}
  17.534 +
  17.535 +/** Compare an sxpr with a string for equality.
  17.536 + *
  17.537 + * @param x string to compare with
  17.538 + * @param y sxpr to compare
  17.539 + * @return 1 if equal, 0 otherwise
  17.540 + */
  17.541 +int string_equal(Sxpr x, Sxpr y){
  17.542 +    int ok = 0;
  17.543 +    ok = eq(x,y);
  17.544 +    if(ok) goto exit;
  17.545 +    ok = has_type(y, T_STRING) && !strcmp(OBJ_STRING(x), OBJ_STRING(y));
  17.546 +    if(ok) goto exit;
  17.547 +    ok = has_type(y, T_ATOM) && !strcmp(OBJ_STRING(x), atom_name(y));
  17.548 +  exit:
  17.549 +    return ok;
  17.550 +}
  17.551 +
  17.552 +/** Create a new cons cell.
  17.553 + * The cell is ONOMEM if either argument is.
  17.554 + *
  17.555 + * @param car sxpr for the car
  17.556 + * @param cdr sxpr for the cdr
  17.557 + * @return new cons
  17.558 + */
  17.559 +Sxpr cons_new(Sxpr car, Sxpr cdr){
  17.560 +    Sxpr obj;
  17.561 +    if(NOMEMP(car) || NOMEMP(cdr)){
  17.562 +        obj = ONOMEM;
  17.563 +    } else {
  17.564 +        obj = HALLOC(ObjCons, T_CONS);
  17.565 +        if(!NOMEMP(obj)){
  17.566 +            ObjCons *z = OBJ_CONS(obj);
  17.567 +            z->car = car;
  17.568 +            z->cdr = cdr;
  17.569 +        }
  17.570 +    }
  17.571 +    return obj;
  17.572 +}
  17.573 +
  17.574 +/** Push a new element onto a list.
  17.575 + *
  17.576 + * @param list list to add to
  17.577 + * @param elt element to add
  17.578 + * @return 0 if successful, error code otherwise
  17.579 + */
  17.580 +int cons_push(Sxpr *list, Sxpr elt){
  17.581 +    Sxpr l;
  17.582 +    l = cons_new(elt, *list);
  17.583 +    if(NOMEMP(l)) return -ENOMEM;
  17.584 +    *list = l;
  17.585 +    return 0;
  17.586 +}
  17.587 +
  17.588 +/** Free a cons. Recursively frees the car and cdr.
  17.589 + *
  17.590 + * @param obj to free
  17.591 + */
  17.592 +void cons_free(Sxpr obj){
  17.593 +    Sxpr next;
  17.594 +    for(; CONSP(obj); obj = next){
  17.595 +	next = CDR(obj);
  17.596 +	objfree(CAR(obj));
  17.597 +	hfree(obj);
  17.598 +    }
  17.599 +    if(!NULLP(obj)){
  17.600 +	objfree(obj);
  17.601 +    }
  17.602 +}
  17.603 +
  17.604 +/** Free a cons and its cdr cells, but not the car sxprs.
  17.605 + * Does nothing if called on something that is not a cons.
  17.606 + *
  17.607 + * @param obj to free
  17.608 + */
  17.609 +void cons_free_cells(Sxpr obj){
  17.610 +    Sxpr next;
  17.611 +    for(; CONSP(obj); obj = next){
  17.612 +	next = CDR(obj);
  17.613 +	hfree(obj);
  17.614 +    }
  17.615 +}
  17.616 +
  17.617 +/** Print a cons.
  17.618 + * Prints the cons in list format if the cdrs are conses.
  17.619 + * uses pair (dot) format if the last cdr is not a cons (or null).
  17.620 + *
  17.621 + * @param io stream to print to
  17.622 + * @param obj to print
  17.623 + * @param flags print flags
  17.624 + * @return number of bytes written
  17.625 + */
  17.626 +int cons_print(IOStream *io, Sxpr obj, unsigned flags){
  17.627 +    int first = 1;
  17.628 +    int k = 0;
  17.629 +    k += IOStream_print(io, "(");
  17.630 +    for( ; CONSP(obj) ; obj = CDR(obj)){
  17.631 +        if(first){ 
  17.632 +            first = 0;
  17.633 +        } else {
  17.634 +            k += IOStream_print(io, " ");
  17.635 +        }
  17.636 +        k += objprint(io, CAR(obj), flags);
  17.637 +    }
  17.638 +    if(!NULLP(obj)){
  17.639 +        k += IOStream_print(io, " . ");
  17.640 +        k += objprint(io, obj, flags);
  17.641 +    }
  17.642 +    k += IOStream_print(io, ")");
  17.643 +    return (IOStream_error(io) ? -1 : k);
  17.644 +}
  17.645 +
  17.646 +/** Compare a cons with another sxpr for equality.
  17.647 + * If y is a cons, compares the cars and cdrs recursively.
  17.648 + *
  17.649 + * @param x cons to compare
  17.650 + * @param y sxpr to compare
  17.651 + * @return 1 if equal, 0 otherwise
  17.652 + */
  17.653 +int cons_equal(Sxpr x, Sxpr y){
  17.654 +    return CONSP(y) &&
  17.655 +        objequal(CAR(x), CAR(y)) &&
  17.656 +        objequal(CDR(x), CDR(y));
  17.657 +}
  17.658 +
  17.659 +/** Return the length of a cons list.
  17.660 + *
  17.661 + * @param obj list
  17.662 + * @return length
  17.663 + */
  17.664 +int cons_length(Sxpr obj){
  17.665 +    int count = 0;
  17.666 +    for( ; CONSP(obj); obj = CDR(obj)){
  17.667 +        count++;
  17.668 +    }
  17.669 +    return count;
  17.670 +}
  17.671 +
  17.672 +/** Destructively reverse a cons list in-place.
  17.673 + * If the argument is not a cons it is returned unchanged.
  17.674 + * 
  17.675 + * @param l to reverse
  17.676 + * @return reversed list
  17.677 + */
  17.678 +Sxpr nrev(Sxpr l){
  17.679 +    if(CONSP(l)){
  17.680 +	// Iterate down the cells in the list making the cdr of
  17.681 +	// each cell point to the previous cell. The last cell 
  17.682 +	// is the head of the reversed list.
  17.683 +	Sxpr prev = ONULL;
  17.684 +	Sxpr cell = l;
  17.685 +	Sxpr next;
  17.686 +
  17.687 +	while(1){
  17.688 +	    next = CDR(cell);
  17.689 +	    CDR(cell) = prev;
  17.690 +	    if(!CONSP(next)) break;
  17.691 +	    prev = cell;
  17.692 +	    cell = next;
  17.693 +	}
  17.694 +	l = cell;
  17.695 +    }
  17.696 +    return l;
  17.697 +}
  17.698 +
  17.699 +/** Print the null sxpr.	
  17.700 + *
  17.701 + * @param io stream to print to
  17.702 + * @param obj to print
  17.703 + * @param flags print flags
  17.704 + * @return number of bytes written
  17.705 + */
  17.706 +static int null_print(IOStream *io, Sxpr obj, unsigned flags){
  17.707 +    return IOStream_print(io, "()");
  17.708 +}
  17.709 +
  17.710 +/** Print the `unspecified' sxpr none.
  17.711 + *
  17.712 + * @param io stream to print to
  17.713 + * @param obj to print
  17.714 + * @param flags print flags
  17.715 + * @return number of bytes written
  17.716 + */
  17.717 +static int none_print(IOStream *io, Sxpr obj, unsigned flags){
  17.718 +    return IOStream_print(io, "<none>");
  17.719 +}
  17.720 +
  17.721 +/** Print an integer.
  17.722 + *
  17.723 + * @param io stream to print to
  17.724 + * @param obj to print
  17.725 + * @param flags print flags
  17.726 + * @return number of bytes written
  17.727 + */
  17.728 +static int int_print(IOStream *io, Sxpr obj, unsigned flags){
  17.729 +    return IOStream_print(io, "%d", OBJ_INT(obj));
  17.730 +}
  17.731 +
  17.732 +/** Print a boolean.
  17.733 + *
  17.734 + * @param io stream to print to
  17.735 + * @param obj to print
  17.736 + * @param flags print flags
  17.737 + * @return number of bytes written
  17.738 + */
  17.739 +static int bool_print(IOStream *io, Sxpr obj, unsigned flags){
  17.740 +    return IOStream_print(io, (OBJ_UINT(obj) ? k_true : k_false));
  17.741 +}
  17.742 +
  17.743 +int sxprp(Sxpr obj, Sxpr name){
  17.744 +    return CONSP(obj) && objequal(CAR(obj), name);
  17.745 +}
  17.746 +
  17.747 +/** Get the name of an element.
  17.748 + * 
  17.749 + * @param obj element
  17.750 + * @return name
  17.751 + */
  17.752 +Sxpr sxpr_name(Sxpr obj){
  17.753 +    Sxpr val = ONONE;
  17.754 +    if(CONSP(obj)){
  17.755 +        val = CAR(obj);
  17.756 +    } else if(STRINGP(obj) || ATOMP(obj)){
  17.757 +        val = obj;
  17.758 +    }
  17.759 +    return val;
  17.760 +}
  17.761 +
  17.762 +int sxpr_is(Sxpr obj, char *s){
  17.763 +    if(ATOMP(obj)) return !strcmp(atom_name(obj), s);
  17.764 +    if(STRINGP(obj)) return !strcmp(string_string(obj), s);
  17.765 +    return 0;
  17.766 +}
  17.767 +
  17.768 +int sxpr_elementp(Sxpr obj, Sxpr name){
  17.769 +    int ok = 0;
  17.770 +    ok = CONSP(obj) && objequal(CAR(obj), name);
  17.771 +    return ok;
  17.772 +}
  17.773 +
  17.774 +/** Get the attributes of an sxpr.
  17.775 + * 
  17.776 + * @param obj sxpr
  17.777 + * @return attributes
  17.778 + */
  17.779 +Sxpr sxpr_attributes(Sxpr obj){
  17.780 +    Sxpr val = ONULL;
  17.781 +    if(CONSP(obj)){
  17.782 +        obj = CDR(obj);
  17.783 +        if(CONSP(obj)){
  17.784 +            obj = CAR(obj);
  17.785 +            if(sxprp(obj, intern("@"))){
  17.786 +                val = CDR(obj);
  17.787 +            }
  17.788 +        }
  17.789 +    }
  17.790 +    return val;
  17.791 +}
  17.792 +
  17.793 +Sxpr sxpr_attribute(Sxpr obj, Sxpr key, Sxpr def){
  17.794 +    Sxpr val = ONONE;
  17.795 +    val = assoc(sxpr_attributes(obj), key);
  17.796 +    if(CONSP(val) && CONSP(CDR(val))){
  17.797 +        val = CADR(def);
  17.798 +    } else {
  17.799 +        val = def;
  17.800 +    }
  17.801 +    return val;
  17.802 +}
  17.803 +
  17.804 +/** Get the children of an sxpr.
  17.805 + * 
  17.806 + * @param obj sxpr
  17.807 + * @return children
  17.808 + */
  17.809 +Sxpr sxpr_children(Sxpr obj){
  17.810 +    Sxpr val = ONULL;
  17.811 +    if(CONSP(obj)){
  17.812 +        val = CDR(obj);
  17.813 +        if(CONSP(val) && sxprp(CAR(val), intern("@"))){
  17.814 +            val = CDR(val);
  17.815 +        }
  17.816 +    }
  17.817 +    return val;
  17.818 +}
  17.819 +
  17.820 +Sxpr sxpr_child(Sxpr obj, Sxpr name, Sxpr def){
  17.821 +    Sxpr val = ONONE;
  17.822 +    Sxpr l;
  17.823 +    for(l = sxpr_children(obj); CONSP(l); l = CDR(l)){
  17.824 +        if(sxprp(CAR(l), name)){
  17.825 +            val = CAR(l);
  17.826 +            break;
  17.827 +        }
  17.828 +    }
  17.829 +    if(NONEP(val)) val = def;
  17.830 +    return val;
  17.831 +}
  17.832 +
  17.833 +Sxpr sxpr_child0(Sxpr obj, Sxpr def){
  17.834 +    Sxpr val = ONONE;
  17.835 +    Sxpr l = sxpr_children(obj);
  17.836 +    if(CONSP(l)){
  17.837 +        val = CAR(l);
  17.838 +    } else {
  17.839 +        val = def;
  17.840 +    }
  17.841 +    return val;
  17.842 +}
  17.843 +
  17.844 +Sxpr sxpr_childN(Sxpr obj, int n, Sxpr def){
  17.845 +    Sxpr val = def;
  17.846 +    Sxpr l;
  17.847 +    int i;
  17.848 +    for (i = 0, l = sxpr_children(obj); CONSP(l); i++, l = CDR(l)){
  17.849 +        if(i == n){
  17.850 +            val = CAR(l);
  17.851 +            break;
  17.852 +        }
  17.853 +    }
  17.854 +    return val;
  17.855 +}
  17.856 +    
  17.857 +Sxpr sxpr_child_value(Sxpr obj, Sxpr name, Sxpr def){
  17.858 +    Sxpr val = ONONE;
  17.859 +    val = sxpr_child(obj, name, ONONE);
  17.860 +    if(NONEP(val)){
  17.861 +        val = def;
  17.862 +    } else {
  17.863 +        val = sxpr_child0(val, def);
  17.864 +    }
  17.865 +    return val;
  17.866 +}
  17.867 +
  17.868 +/** Table of interned symbols. Indexed by symbol name. */
  17.869 +static HashTable *symbols = NULL;
  17.870 +
  17.871 +/** Hash function for entries in the symbol table.
  17.872 + *
  17.873 + * @param key to hash
  17.874 + * @return hashcode
  17.875 + */
  17.876 +static Hashcode sym_hash_fn(void *key){
  17.877 +    return hash_string((char*)key);
  17.878 +}
  17.879 +
  17.880 +/** Key equality function for the symbol table.
  17.881 + *
  17.882 + * @param x to compare
  17.883 + * @param y to compare
  17.884 + * @return 1 if equal, 0 otherwise
  17.885 + */
  17.886 +static int sym_equal_fn(void *x, void *y){
  17.887 +    return !strcmp((char*)x, (char*)y);
  17.888 +}
  17.889 +
  17.890 +/** Entry free function for the symbol table.
  17.891 + *
  17.892 + * @param table the entry is in
  17.893 + * @param entry being freed
  17.894 + */
  17.895 +static void sym_free_fn(HashTable *table, HTEntry *entry){
  17.896 +    if(entry){
  17.897 +	objfree(((ObjAtom*)entry->value)->name);
  17.898 +	HTEntry_free(entry);
  17.899 +    }
  17.900 +}
  17.901 +	
  17.902 +/** Initialize the symbol table.
  17.903 + *
  17.904 + * @return 0 on sucess, error code otherwise
  17.905 + */
  17.906 +static int init_symbols(void){
  17.907 +    symbols = HashTable_new(100);
  17.908 +    if(symbols){
  17.909 +        symbols->key_hash_fn = sym_hash_fn;
  17.910 +        symbols->key_equal_fn = sym_equal_fn;
  17.911 +	symbols->entry_free_fn = sym_free_fn;
  17.912 +        return 0;
  17.913 +    }
  17.914 +    return -1;
  17.915 +}
  17.916 +
  17.917 +/** Cleanup the symbol table. Frees the table and all its symbols.
  17.918 + */
  17.919 +void cleanup_symbols(void){
  17.920 +    HashTable_free(symbols);
  17.921 +    symbols = NULL;
  17.922 +}
  17.923 +
  17.924 +/** Get the interned symbol with the given name.
  17.925 + * No new symbol is created.
  17.926 + *
  17.927 + * @return symbol or null
  17.928 + */
  17.929 +Sxpr get_symbol(char *sym){
  17.930 +    HTEntry *entry;
  17.931 +    if(!symbols){
  17.932 +	if(init_symbols()) return ONOMEM;
  17.933 +	return ONULL;
  17.934 +    }
  17.935 +    entry = HashTable_get_entry(symbols, sym);
  17.936 +    if(entry){
  17.937 +        return OBJP(T_ATOM, entry->value);
  17.938 +    } else {
  17.939 +        return ONULL;
  17.940 +    }
  17.941 +}
  17.942 +
  17.943 +/** Get the interned symbol with the given name.
  17.944 + * Creates a new symbol if necessary.
  17.945 + *
  17.946 + * @return symbol
  17.947 + */
  17.948 +Sxpr intern(char *sym){
  17.949 +    Sxpr symbol = get_symbol(sym);
  17.950 +    if(NULLP(symbol)){
  17.951 +	if(!symbols) return ONOMEM;
  17.952 +        symbol = atom_new(sym);
  17.953 +        if(!NOMEMP(symbol)){
  17.954 +	    OBJ_ATOM(symbol)->interned = TRUE;
  17.955 +            HashTable_add(symbols, atom_name(symbol), get_ptr(symbol));
  17.956 +        }
  17.957 +    }
  17.958 +    return symbol;
  17.959 +}

    18.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    18.2 +++ b/tools/libxutil/sxpr.h	Mon Nov 22 16:41:50 2004 +0000
    18.3 @@ -0,0 +1,420 @@
    18.4 +/*
    18.5 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
    18.6 + *
    18.7 + * This library is free software; you can redistribute it and/or modify
    18.8 + * it under the terms of the GNU Lesser General Public License as
    18.9 + * published by the Free Software Foundation; either version 2.1 of the
   18.10 + * License, or  (at your option) any later version. This library is 
   18.11 + * distributed in the  hope that it will be useful, but WITHOUT ANY
   18.12 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or
   18.13 + * FITNESS FOR A PARTICULAR PURPOSE.
   18.14 + * See the GNU Lesser General Public License for more details.
   18.15 + *
   18.16 + * You should have received a copy of the GNU Lesser General Public License
   18.17 + * along with this library; if not, write to the Free Software Foundation,
   18.18 + * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
   18.19 + */
   18.20 +#ifndef _XUTIL_SXPR_H_
   18.21 +#define _XUTIL_SXPR_H_
   18.22 +
   18.23 +#ifdef __KERNEL__
   18.24 +#include <linux/config.h>
   18.25 +#include <linux/types.h>
   18.26 +#else
   18.27 +#include <stdint.h>
   18.28 +#endif
   18.29 +
   18.30 +#include "hash_table.h"
   18.31 +#include "iostream.h"
   18.32 +#include "allocate.h"
   18.33 +
   18.34 +/** @file
   18.35 + * Definitions for rules and sxprs.
   18.36 + */
   18.37 +
   18.38 +#ifndef NULL
   18.39 +#define NULL 0
   18.40 +#endif
   18.41 +
   18.42 +#ifndef TRUE
   18.43 +#define TRUE 1
   18.44 +#endif
   18.45 +
   18.46 +#ifndef FALSE
   18.47 +#define FALSE 0
   18.48 +#endif
   18.49 +
   18.50 +/** Sxpr type. */
   18.51 +typedef int16_t TypeCode;
   18.52 +
   18.53 +/** A typed sxpr handle.*/
   18.54 +typedef struct Sxpr {
   18.55 +    /** Sxpr type. */
   18.56 +    TypeCode type;
   18.57 +    union {
   18.58 +	/** Sxpr value. */
   18.59 +        unsigned long ul;
   18.60 +	/** Pointer. */
   18.61 +        void *ptr;
   18.62 +    } v;
   18.63 +} Sxpr;
   18.64 +
   18.65 +/** Sxpr type to indicate out of memory. */
   18.66 +#define T_NOMEM      ((TypeCode)-1)
   18.67 +/** The 'unspecified' sxpr. */
   18.68 +#define T_NONE       ((TypeCode)0)
   18.69 +/** The empty list. */
   18.70 +#define T_NULL       ((TypeCode)1)
   18.71 +/** Unsigned integer. */
   18.72 +#define T_UINT       ((TypeCode)2)
   18.73 +/** A string. */
   18.74 +#define T_STRING     ((TypeCode)3)
   18.75 +/** An atom. */
   18.76 +#define T_ATOM       ((TypeCode)4)
   18.77 +/** A boolean. */
   18.78 +#define T_BOOL       ((TypeCode)5)
   18.79 +
   18.80 +/** A cons (pair or list). */
   18.81 +#define T_CONS       ((TypeCode)10)
   18.82 +
   18.83 +/** An error. */
   18.84 +#define T_ERR        ((TypeCode)40)
   18.85 +
   18.86 +/** An atom. */
   18.87 +typedef struct ObjAtom {
   18.88 +    Sxpr name;
   18.89 +    Hashcode hashcode;
   18.90 +    int interned;
   18.91 +} ObjAtom;
   18.92 +
   18.93 +/** A cons (pair). */
   18.94 +typedef struct ObjCons {
   18.95 +    Sxpr car;
   18.96 +    Sxpr cdr;
   18.97 +} ObjCons;
   18.98 +
   18.99 +/** A vector. */
  18.100 +typedef struct ObjVector {
  18.101 +    int n;
  18.102 +    Sxpr data[0];
  18.103 +} ObjVector;
  18.104 +
  18.105 +/** Flags for sxpr printing. */
  18.106 +enum PrintFlags {
  18.107 +    PRINT_RAW           = 0x001,
  18.108 +    PRINT_TYPE          = 0x002,
  18.109 +    PRINT_PRETTY        = 0x004,
  18.110 +    PRINT_NUM           = 0x008,
  18.111 +};
  18.112 +
  18.113 +/** An integer sxpr.
  18.114 + *
  18.115 + * @param ty type
  18.116 + * @param val integer value
  18.117 + */
  18.118 +#define OBJI(ty, val) (Sxpr){ type: (ty), v: { ul: (val) }}
  18.119 +
  18.120 +/** A pointer sxpr.
  18.121 + * If the pointer is non-null, returns an sxpr containing it.
  18.122 + * If the pointer is null, returns ONOMEM.
  18.123 + *
  18.124 + * @param ty type
  18.125 + * @param val pointer
  18.126 + */
  18.127 +#define OBJP(ty, val) ((val) ? (Sxpr){ type: (ty), v: { ptr: (val) }} : ONOMEM)
  18.128 +
  18.129 +/** Make an integer sxpr containing a pointer.
  18.130 + *
  18.131 + * @param val pointer
  18.132 + */
  18.133 +#define PTR(val) OBJP(T_UINT, (void*)(val))
  18.134 +
  18.135 +/** Make an integer sxpr.
  18.136 + * @param x value
  18.137 + */
  18.138 +#define OINT(x)       OBJI(T_UINT,  x)
  18.139 +
  18.140 +/** Make an error sxpr.
  18.141 + *
  18.142 + * @param x value
  18.143 + */
  18.144 +#define OERR(x)       OBJI(T_ERR,   x)
  18.145 +
  18.146 +/** Out of memory constant. */
  18.147 +#define ONOMEM        OBJI(T_NOMEM, 0)
  18.148 +
  18.149 +/** The `unspecified' constant. */
  18.150 +#define ONONE         OBJI(T_NONE,  0)
  18.151 +
  18.152 +/** Empty list constant. */
  18.153 +#define ONULL         OBJI(T_NULL,  0)
  18.154 +
  18.155 +/** False constant. */
  18.156 +#define OFALSE        OBJI(T_BOOL,  0)
  18.157 +
  18.158 +/** True constant. */
  18.159 +#define OTRUE         OBJI(T_BOOL,  1)
  18.160 +
  18.161 +/* Recognizers for the various sxpr types.  */
  18.162 +#define ATOMP(obj)        has_type(obj, T_ATOM)
  18.163 +#define BOOLP(obj)        has_type(obj, T_BOOL)
  18.164 +#define CONSP(obj)        has_type(obj, T_CONS)
  18.165 +#define ERRP(obj)         has_type(obj, T_ERR)
  18.166 +#define INTP(obj)         has_type(obj, T_UINT)
  18.167 +#define NOMEMP(obj)       has_type(obj, T_NOMEM)
  18.168 +#define NONEP(obj)        has_type(obj, T_NONE)
  18.169 +#define NULLP(obj)        has_type(obj, T_NULL)
  18.170 +#define STRINGP(obj)      has_type(obj, T_STRING)
  18.171 +
  18.172 +#define TRUEP(obj)    get_ul(obj)
  18.173 +
  18.174 +/** Convert an sxpr to an unsigned integer. */
  18.175 +#define OBJ_UINT(x)   get_ul(x)
  18.176 +/** Convert an sxpr to an integer. */
  18.177 +#define OBJ_INT(x)    (int)get_ul(x)
  18.178 +
  18.179 +/* Conversions of sxprs to their values.
  18.180 + * No checking is done.
  18.181 + */
  18.182 +#define OBJ_STRING(x)  ((char*)get_ptr(x))
  18.183 +#define OBJ_CONS(x)    ((ObjCons*)get_ptr(x))
  18.184 +#define OBJ_ATOM(x)    ((ObjAtom*)get_ptr(x))
  18.185 +#define OBJ_SET(x)     ((ObjSet*)get_ptr(x))
  18.186 +#define CAR(x)         (OBJ_CONS(x)->car)
  18.187 +#define CDR(x)         (OBJ_CONS(x)->cdr)
  18.188 +
  18.189 +#define CAAR(x)        (CAR(CAR(x)))
  18.190 +#define CADR(x)        (CAR(CDR(x)))
  18.191 +#define CDAR(x)        (CDR(CAR(x)))
  18.192 +#define CDDR(x)        (CDR(CDR(x)))
  18.193 +
  18.194 +/** Get the integer value from an sxpr.
  18.195 + *
  18.196 + * @param obj sxpr
  18.197 + * @return value
  18.198 + */
  18.199 +static inline unsigned long get_ul(Sxpr obj){
  18.200 +    return obj.v.ul;
  18.201 +}
  18.202 +
  18.203 +/** Get the pointer value from an sxpr.
  18.204 + *
  18.205 + * @param obj sxpr
  18.206 + * @return value
  18.207 + */
  18.208 +static inline void * get_ptr(Sxpr obj){
  18.209 +    return obj.v.ptr;
  18.210 +}
  18.211 +
  18.212 +/** Create an sxpr containing a pointer.
  18.213 + *
  18.214 + * @param type typecode
  18.215 + * @param val pointer
  18.216 + * @return sxpr
  18.217 + */
  18.218 +static inline Sxpr obj_ptr(TypeCode type, void *val){
  18.219 +    return (Sxpr){ type: type, v: { ptr: val } };
  18.220 +}
  18.221 +
  18.222 +/** Create an sxpr containing an integer.
  18.223 + *
  18.224 + * @param type typecode
  18.225 + * @param val integer
  18.226 + * @return sxpr
  18.227 + */
  18.228 +static inline Sxpr obj_ul(TypeCode type, unsigned long val){
  18.229 +    return (Sxpr){ type: type, v: { ul: val } };
  18.230 +}
  18.231 +
  18.232 +/** Get the type of an sxpr.
  18.233 + *
  18.234 + * @param obj sxpr
  18.235 + * @return type
  18.236 + */
  18.237 +static inline TypeCode get_type(Sxpr obj){
  18.238 +    return obj.type;
  18.239 +}
  18.240 +
  18.241 +/** Check the type of an sxpr.
  18.242 + *
  18.243 + * @param obj sxpr
  18.244 + * @param type to check
  18.245 + * @return 1 if has the type, 0 otherwise
  18.246 + */
  18.247 +static inline int has_type(Sxpr obj, TypeCode type){
  18.248 +    return get_type(obj) == type;
  18.249 +}
  18.250 +
  18.251 +/** Compare sxprs for literal equality of type and value.
  18.252 + *
  18.253 + * @param x sxpr to compare
  18.254 + * @param y sxpr to compare
  18.255 + * @return 1 if equal, 0 otherwise
  18.256 + */
  18.257 +static inline int eq(Sxpr x, Sxpr y){
  18.258 +    return ((get_type(x) == get_type(y)) && (get_ul(x) == get_ul(y)));
  18.259 +}
  18.260 +
  18.261 +/** Checked version of CAR
  18.262 + *
  18.263 + * @param x sxpr
  18.264 + * @return CAR if a cons, x otherwise
  18.265 + */
  18.266 +static inline Sxpr car(Sxpr x){
  18.267 +    return (CONSP(x) ? CAR(x) : x);
  18.268 +}
  18.269 +
  18.270 +/** Checked version of CDR.
  18.271 + *
  18.272 + * @param x sxpr
  18.273 + * @return CDR if a cons, null otherwise
  18.274 + */
  18.275 +static inline Sxpr cdr(Sxpr x){
  18.276 +    return (CONSP(x) ? CDR(x) : ONULL);
  18.277 +}
  18.278 +
  18.279 +/** Allocate some memory and return an sxpr containing it.
  18.280 + * Returns ONOMEM if allocation failed.
  18.281 + *
  18.282 + * @param n number of bytes to allocate
  18.283 + * @param ty typecode
  18.284 + * @return sxpr
  18.285 + */
  18.286 +static inline Sxpr halloc(size_t n,  TypeCode ty){
  18.287 +    return OBJP(ty, allocate(n));
  18.288 +}
  18.289 +
  18.290 +/** Allocate an sxpr containing a pointer to the given type.
  18.291 + *
  18.292 + * @param ty type (uses sizeof to determine how many bytes to allocate)
  18.293 + * @param code typecode
  18.294 + * @return sxpr, ONOMEM if allocation failed
  18.295 + */
  18.296 +#define HALLOC(ty, code) halloc(sizeof(ty), code)
  18.297 +
  18.298 +typedef int ObjPrintFn(IOStream *io, Sxpr obj, unsigned flags);
  18.299 +typedef int ObjEqualFn(Sxpr obj, Sxpr other);
  18.300 +typedef void ObjFreeFn(Sxpr obj);
  18.301 +
  18.302 +/** An sxpr type definition. */
  18.303 +typedef struct SxprType {
  18.304 +    TypeCode type;
  18.305 +    char *name;
  18.306 +    int pointer;
  18.307 +    ObjPrintFn *print;
  18.308 +    ObjEqualFn *equal;
  18.309 +    ObjFreeFn *free;
  18.310 +} SxprType;
  18.311 +
  18.312 +
  18.313 +extern SxprType *get_sxpr_type(int ty);
  18.314 +
  18.315 +/** Free the pointer in an sxpr.
  18.316 + *
  18.317 + * @param x sxpr containing a pointer
  18.318 + */
  18.319 +static inline void hfree(Sxpr x){
  18.320 +    deallocate(get_ptr(x));
  18.321 +}
  18.322 +
  18.323 +extern int objprint(IOStream *io, Sxpr x, unsigned flags);
  18.324 +extern int objequal(Sxpr x, Sxpr y);
  18.325 +extern void objfree(Sxpr x);
  18.326 +
  18.327 +extern void cons_free_cells(Sxpr obj);
  18.328 +extern Sxpr intern(char *s);
  18.329 +
  18.330 +extern Sxpr assoc(Sxpr k, Sxpr l);
  18.331 +extern Sxpr assocq(Sxpr k, Sxpr l);
  18.332 +extern Sxpr acons(Sxpr k, Sxpr v, Sxpr l);
  18.333 +extern Sxpr nrev(Sxpr l);
  18.334 +extern Sxpr cons_member(Sxpr l, Sxpr x);
  18.335 +extern Sxpr cons_member_if(Sxpr l, ObjEqualFn *test_fn, Sxpr v);
  18.336 +extern int cons_subset(Sxpr s, Sxpr t);
  18.337 +extern int cons_set_equal(Sxpr s, Sxpr t);
  18.338 +
  18.339 +#ifdef USE_GC
  18.340 +extern Sxpr cons_remove(Sxpr l, Sxpr x);
  18.341 +extern Sxpr cons_remove_if(Sxpr l, ObjEqualFn *test_fn, Sxpr v);
  18.342 +#endif
  18.343 +
  18.344 +extern Sxpr atom_new(char *name);
  18.345 +extern char * atom_name(Sxpr obj);
  18.346 +
  18.347 +extern Sxpr string_new(char *s);
  18.348 +extern char * string_string(Sxpr obj);
  18.349 +extern int string_length(Sxpr obj);
  18.350 +
  18.351 +extern Sxpr cons_new(Sxpr car, Sxpr cdr);
  18.352 +extern int cons_push(Sxpr *list, Sxpr elt);
  18.353 +extern int cons_length(Sxpr obj);
  18.354 +
  18.355 +Sxpr sxpr_name(Sxpr obj);
  18.356 +int sxpr_is(Sxpr obj, char *s);
  18.357 +int sxpr_elementp(Sxpr obj, Sxpr name);
  18.358 +Sxpr sxpr_attributes(Sxpr obj);
  18.359 +Sxpr sxpr_attribute(Sxpr obj, Sxpr key, Sxpr def);
  18.360 +Sxpr sxpr_children(Sxpr obj);
  18.361 +Sxpr sxpr_child(Sxpr obj, Sxpr name, Sxpr def);
  18.362 +Sxpr sxpr_childN(Sxpr obj, int n, Sxpr def);
  18.363 +Sxpr sxpr_child0(Sxpr obj, Sxpr def);
  18.364 +Sxpr sxpr_child_value(Sxpr obj, Sxpr name, Sxpr def);
  18.365 +
  18.366 +/** Create a new atom.
  18.367 + *
  18.368 + * @param s atom name
  18.369 + * @return new atom
  18.370 + */
  18.371 +static inline Sxpr mkatom(char *s){
  18.372 +    return atom_new(s);
  18.373 +}
  18.374 +
  18.375 +/** Create a new string sxpr.
  18.376 + *
  18.377 + * @param s string bytes (copied)
  18.378 + * @return new string
  18.379 + */
  18.380 +static inline Sxpr mkstring(char *s){
  18.381 +    return string_new(s);
  18.382 +}
  18.383 +
  18.384 +/** Create an integer sxpr.
  18.385 + *
  18.386 + * @param i value
  18.387 + * @return sxpr
  18.388 + */
  18.389 +static inline Sxpr mkint(int i){
  18.390 +    return OBJI(T_UINT, i);
  18.391 +}
  18.392 +
  18.393 +/** Create a boolean sxpr.
  18.394 + *
  18.395 + * @param b value
  18.396 + * @return sxpr
  18.397 + */
  18.398 +static inline Sxpr mkbool(int b){
  18.399 +    return OBJI(T_BOOL, (b ? 1 : 0));
  18.400 +}
  18.401 +
  18.402 +/* Constants used in parsing and printing. */
  18.403 +#define k_list_open    "("
  18.404 +#define c_list_open    '('
  18.405 +#define k_list_close   ")"
  18.406 +#define c_list_close   ')'
  18.407 +#define k_true         "true"
  18.408 +#define k_false        "false"
  18.409 +
  18.410 +#define c_var          '$'
  18.411 +#define c_escape       '\\'
  18.412 +#define c_single_quote '\''
  18.413 +#define c_double_quote '"'
  18.414 +#define c_string_open  c_double_quote
  18.415 +#define c_string_close c_double_quote
  18.416 +#define c_data_open    '['
  18.417 +#define c_data_close   ']'
  18.418 +#define c_binary       '*'
  18.419 +#define c_eval         '!'
  18.420 +#define c_concat_open  '{'
  18.421 +#define c_concat_close '}'
  18.422 +
  18.423 +#endif /* ! _XUTIL_SXPR_H_ */

    19.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    19.2 +++ b/tools/libxutil/sxpr_parser.c	Mon Nov 22 16:41:50 2004 +0000
    19.3 @@ -0,0 +1,959 @@
    19.4 +/*
    19.5 + * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
    19.6 + *
    19.7 + * This library is free software; you can redistribute it and/or modify
    19.8 + * it under the terms of the GNU Lesser General Public License as
    19.9 + * published by the Free Software Foundation; either version 2.1 of the
   19.10 + * License, or  (at your option) any later version. This library is 
   19.11 + * distributed in the  hope that it will be useful, but WITHOUT ANY
   19.12 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or
   19.13 + * FITNESS FOR A PARTICULAR PURPOSE.
   19.14 + * See the GNU Lesser General Public License for more details.
   19.15 + *
   19.16 + * You should have received a copy of the GNU Lesser General Public License
   19.17 + * along with this library; if not, write to the Free Software Foundation,
   19.18 + * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
   19.19 + */
   19.20 +
   19.21 +#ifdef __KERNEL__
   19.22 +#  include <linux/config.h>
   19.23 +#  include <linux/module.h>
   19.24 +#  include <linux/kernel.h>
   19.25 +#  include <linux/string.h>
   19.26 +#  include <linux/errno.h>
   19.27 +#else
   19.28 +#  include <stdlib.h>
   19.29 +#  include <errno.h>
   19.30 +#endif
   19.31 +
   19.32 +#include "iostream.h"
   19.33 +#include "lexis.h"
   19.34 +#include "sxpr_parser.h"
   19.35 +#include "sys_string.h"
   19.36 +#include "enum.h"
   19.37 +
   19.38 +/** @file
   19.39 + * Sxpr parsing.
   19.40 + *
   19.41 + * So that the parser does not leak memory, all sxprs constructed by
   19.42 + * the parser must be freed on error.  On successful parse the sxpr
   19.43 + * returned becomes the responsibility of the caller.
   19.44 + *
   19.45 + * @author Mike Wray <mike.wray@hpl.hp.com>
   19.46 + */
   19.47 +
   19.48 +#define dprintf(fmt, args...) IOStream_print(iostdout, "[DEBUG] %s" fmt, __FUNCTION__, ##args)
   19.49 +#define printf(fmt, args...)   IOStream_print(iostdout, fmt, ##args)
   19.50 +
   19.51 +static void reset(Parser *z);
   19.52 +static int inputchar(Parser *p, char c);
   19.53 +static int savechar(Parser *p, char c);
   19.54 +extern void parse_error(Parser *in);
   19.55 +extern void parse_error_id(Parser *in, ParseErrorId id);
   19.56 +
   19.57 +static int begin_start(Parser *p, char c);
   19.58 +static int state_start(Parser *p, char c);
   19.59 +static int end_start(Parser *p);
   19.60 +
   19.61 +static int begin_comment(Parser *p, char c);
   19.62 +static int state_comment(Parser *p, char c);
   19.63 +static int end_comment(Parser *p);
   19.64 +
   19.65 +static int begin_string(Parser *p, char c);
   19.66 +static int state_string(Parser *p, char c);
   19.67 +static int end_string(Parser *p);
   19.68 +static int state_escape(Parser *p, char c);
   19.69 +static int state_octal(Parser *p, char c);
   19.70 +static int state_hex(Parser *p, char c);
   19.71 +
   19.72 +static int begin_atom(Parser *p, char c);
   19.73 +static int state_atom(Parser *p, char c);
   19.74 +static int end_atom(Parser *p);
   19.75 +
   19.76 +static int state_list(Parser *p, char c);
   19.77 +static int begin_list(Parser *p, char c);
   19.78 +static int end_list(Parser *p);
   19.79 +
   19.80 +/** Print a parse error.
   19.81 + *
   19.82 + * @param in parser
   19.83 + * @param msg format followed by printf arguments
   19.84 + */
   19.85 +void eprintf(Parser *in, char *msg, ...){
   19.86 +    va_list args;
   19.87 +    if(in->error_out){
   19.88 +        va_start(args, msg);
   19.89 +        IOStream_vprint(in->error_out, msg, args);
   19.90 +        va_end(args);
   19.91 +    }
   19.92 +}
   19.93 +
   19.94 +/** Print a parse warning.
   19.95 + *
   19.96 + * @param in parser
   19.97 + * @param msg format followed by printf arguments
   19.98 + */
   19.99 +void wprintf(Parser *in, char *msg, ...){
  19.100 +    va_list args;
  19.101 +    if(in->error_out){
  19.102 +        va_start(args, msg);
  19.103 +        IOStream_vprint(in->error_out, msg, args);
  19.104 +        va_end(args);
  19.105 +    }
  19.106 +}
  19.107 +
  19.108 +/*============================================================================*/
  19.109 +
  19.110 +/** Record defining the message for a parse error. */
  19.111 +typedef struct {
  19.112 +  ParseErrorId id;
  19.113 +  char *message;
  19.114 +} ParseError;
  19.115 +
  19.116 +/** Format for printing parse error messages. */
  19.117 +#define PARSE_ERR_FMT "parse error> line %3d, column %2d: %s"
  19.118 +
  19.119 +/** Message catalog for the parse error codes. */
  19.120 +static ParseError catalog[] = {
  19.121 +  { PARSE_ERR_UNSPECIFIED,            "unspecified error" },
  19.122 +  { PARSE_ERR_NOMEM,                  "out of memory" },
  19.123 +  { PARSE_ERR_UNEXPECTED_EOF,         "unexpected end of input" },
  19.124 +  { PARSE_ERR_TOKEN_TOO_LONG,         "token too long" },
  19.125 +  { PARSE_ERR_INVALID_SYNTAX,         "syntax error" },
  19.126 +  { PARSE_ERR_INVALID_ESCAPE,         "invalid escape" },
  19.127 +  { 0, NULL }
  19.128 +};
  19.129 +
  19.130 +/** Number of entries in the message catalog. */
  19.131 +const static int catalog_n = sizeof(catalog)/sizeof(ParseError);
  19.132 +
  19.133 +void ParserState_free(ParserState *z){
  19.134 +    if(!z) return;
  19.135 +    objfree(z->val);
  19.136 +    deallocate(z);
  19.137 +}
  19.138 +
  19.139 +int ParserState_new(ParserStateFn *fn, char *name,
  19.140 +                    ParserState *parent, ParserState **val){
  19.141 +    int err = 0;
  19.142 +    ParserState *z;
  19.143 +    z = ALLOCATE(ParserState);
  19.144 +    if(z){
  19.145 +        z->name = name;
  19.146 +        z->fn = fn;
  19.147 +        z->parent = parent;
  19.148 +        z->val = ONULL;
  19.149 +    } else {
  19.150 +        err = -ENOMEM;
  19.151 +    }
  19.152 +    if(!err) *val = z;
  19.153 +    return err;
  19.154 +}
  19.155 +
  19.156 +/** Free a parser.
  19.157 + * No-op if the parser is null.
  19.158 + *
  19.159 + * @param z parser 
  19.160 + */
  19.161 +void Parser_free(Parser *z){
  19.162 +    if(!z) return;
  19.163 +    objfree(z->val);
  19.164 +    z->val = ONONE;
  19.165 +    deallocate(z);
  19.166 +}
  19.167 +
  19.168 +/** Create a new parser. The error stream defaults to null.
  19.169 + */
  19.170 +Parser * Parser_new(void){
  19.171 +    Parser *z = ALLOCATE(Parser);
  19.172 +    int err = -ENOMEM;
  19.173 +  
  19.174 +    if(!z) goto exit;
  19.175 +    err = 0;
  19.176 +    reset(z);
  19.177 +  exit:
  19.178 +    if(err){
  19.179 +        Parser_free(z);
  19.180 +        z = NULL;
  19.181 +    }
  19.182 +    return z;
  19.183 +}
  19.184 +
  19.185 +/** Get the next character.
  19.186 + * Records the character read in the parser,
  19.187 + * and sets the line and character counts.
  19.188 + *
  19.189 + * @param p parser
  19.190 + * @return error flag: 0 on success, non-zero on error
  19.191 + */
  19.192 +static int inputchar(Parser *p, char c){
  19.193 +    int err = 0;
  19.194 +    if(c=='\n'){
  19.195 +        p->line_no++;
  19.196 +        p->char_no = 0;
  19.197 +    } else {
  19.198 +        p->char_no++;
  19.199 +    }
  19.200 +    return err;
  19.201 +}
  19.202 +
  19.203 +static int savechar(Parser *p, char c){
  19.204 +    int err = 0;
  19.205 +    if(p->buf_i >= p->buf_n){
  19.206 +        err = -ENOMEM;
  19.207 +        goto exit;
  19.208 +    }
  19.209 +    p->buf[p->buf_i] = c;
  19.210 +    p->buf_i++;
  19.211 +  exit:
  19.212 +    return err;
  19.213 +}
  19.214 +
  19.215 +int Parser_input_char(Parser *p, char c){
  19.216 +    int err = 0;
  19.217 +    if(at_eof(p)){
  19.218 +        //skip;
  19.219 +    } else {
  19.220 +        inputchar(p, c);
  19.221 +    }
  19.222 +    if(!p->state){
  19.223 +        err = begin_start(p, c);
  19.224 +        if(err) goto exit;
  19.225 +    }
  19.226 +    err = p->state->fn(p, c);
  19.227 +  exit:
  19.228 +    return err;
  19.229 +}
  19.230 +
  19.231 +int Parser_input_eof(Parser *p){
  19.232 +    int err = 0;
  19.233 +    p->eof = 1;
  19.234 +    err = Parser_input_char(p, IOSTREAM_EOF);
  19.235 +    return err;
  19.236 +}
  19.237 +
  19.238 +int Parser_input(Parser *p, char *buf, int buf_n){
  19.239 +    int err = 0;
  19.240 +    int i = 0;
  19.241 +    if(buf_n <= 0){
  19.242 +        err = Parser_input_eof(p);
  19.243 +        goto exit;
  19.244 +    }
  19.245 +    for(i = 0; i<buf_n; i++){
  19.246 +        err = Parser_input_char(p, buf[i]);
  19.247 +        if(err) goto exit;
  19.248 +    }
  19.249 +  exit:
  19.250 +    err = (err < 0 ? err : buf_n);
  19.251 +    return err;
  19.252 +}
  19.253 +
  19.254 +int Parser_push(Parser *p, ParserStateFn *fn, char *name){
  19.255 +    int err = 0;
  19.256 +    err = ParserState_new(fn, name, p->state, &p->state);
  19.257 +    return err;
  19.258 +}
  19.259 +        
  19.260 +int Parser_pop(Parser *p){
  19.261 +    int err = 0;
  19.262 +    ParserState *s = p->state;
  19.263 +    p->state = s->parent;
  19.264 +    ParserState_free(s);
  19.265 +    return err;
  19.266 +}
  19.267 +
  19.268 +int Parser_return(Parser *p){
  19.269 +    int err = 0;
  19.270 +    Sxpr val = ONONE;
  19.271 +    if(!p->state){
  19.272 +        err = -EINVAL;
  19.273 +        goto exit;
  19.274 +    }
  19.275 +    val = p->state->val;
  19.276 +    p->state->val = ONONE;
  19.277 +    err = Parser_pop(p);
  19.278 +    if(err) goto exit;
  19.279 +    if(p->state){
  19.280 +        err = cons_push(&p->state->val, val);
  19.281 +    } else {
  19.282 +        val = nrev(val);
  19.283 +        p->val = val;
  19.284 +    }
  19.285 +  exit:
  19.286 +    if(err){
  19.287 +        objfree(val);
  19.288 +    }
  19.289 +    return err;
  19.290 +}
  19.291 +
  19.292 +/** Determine if a character is a separator.
  19.293 + *
  19.294 + * @param p parser
  19.295 + * @param c character to test
  19.296 + * @return 1 if a separator, 0 otherwise
  19.297 + */
  19.298 +static int is_separator(Parser *p, char c){
  19.299 +    return in_sep_class(c);
  19.300 +}
  19.301 +
  19.302 +/** Return the current token.
  19.303 + * The return value points at the internal buffer, so
  19.304 + * it must not be modified (or freed). Use copy_token() if you need a copy.
  19.305 + *
  19.306 + * @param p parser
  19.307 + * @return token
  19.308 + */
  19.309 +char *peek_token(Parser *p){
  19.310 +    return p->buf;
  19.311 +}
  19.312 +
  19.313 +/** Return a copy of the current token.
  19.314 + * The returned value should be freed when finished with.
  19.315 + *
  19.316 + * @param p parser
  19.317 + * @return copy of token
  19.318 + */
  19.319 +char *copy_token(Parser *p){
  19.320 +    return strdup(peek_token(p));
  19.321 +}
  19.322 +
  19.323 +static int do_intern(Parser *p){
  19.324 +    int err = 0;
  19.325 +    Sxpr obj = intern(peek_token(p));
  19.326 +    if(NOMEMP(obj)){
  19.327 +        err = -ENOMEM;
  19.328 +    } else {
  19.329 +        p->state->val = obj;
  19.330 +    }
  19.331 +    return err;
  19.332 +}
  19.333 +
  19.334 +static int do_string(Parser *p){
  19.335 +    int err = 0;
  19.336 +    Sxpr obj;
  19.337 +    obj = string_new(peek_token(p));
  19.338 +    if(NOMEMP(obj)){
  19.339 +        err = -ENOMEM;
  19.340 +    } else {
  19.341 +        p->state->val = obj;
  19.342 +    }
  19.343 +    return err;
  19.344 +}
  19.345 +
  19.346 +void newtoken(Parser *p){
  19.347 +    memset(p->buf, 0, p->buf_n);
  19.348 +    p->buf_i = 0;
  19.349 +    p->tok_begin_line = p->line_no;
  19.350 +    p->tok_begin_char = p->char_no;
  19.351 +}
  19.352 +
  19.353 +int get_escape(char c, char *d){
  19.354 +    int err = 0;
  19.355 +    switch(c){
  19.356 +    case 'a':            *d = '\a'; break;
  19.357 +    case 'b':            *d = '\b'; break;
  19.358 +    case 'f':            *d = '\f'; break;
  19.359 +    case 'n':            *d = '\n'; break;
  19.360 +    case 'r':            *d = '\r'; break;
  19.361 +    case 't':            *d = '\t'; break;
  19.362 +    case 'v':            *d = '\v'; break;
  19.363 +    case c_escape:       *d = c_escape; break;
  19.364 +    case c_single_quote: *d = c_single_quote; break;
  19.365 +    case c_double_quote: *d = c_double_quote; break;
  19.366 +    default:
  19.367 +        err = -EINVAL;
  19.368 +    }
  19.369 +    return err;
  19.370 +}
  19.371 +
  19.372 +int Parser_ready(Parser *p){
  19.373 +    return CONSP(p->val) || (p->start_state && CONSP(p->start_state->val));
  19.374 +}
  19.375 +
  19.376 +Sxpr Parser_get_val(Parser *p){
  19.377 +    Sxpr v = ONONE;
  19.378 +    if(CONSP(p->val)){
  19.379 +        v = CAR(p->val);
  19.380 +        p->val = CDR(p->val);
  19.381 +    } else if (CONSP(p->start_state->val)){
  19.382 +        p->val = p->start_state->val;
  19.383 +        p->val = nrev(p->val);
  19.384 +        p->start_state->val = ONULL;
  19.385 +        v = CAR(p->val);
  19.386 +        p->val = CDR(p->val);
  19.387 +    }        
  19.388 +    return v;
  19.389 +}
  19.390 +
  19.391 +Sxpr Parser_get_all(Parser *p){
  19.392 +    Sxpr v = ONULL;
  19.393 +    if(CONSP(p->val)){
  19.394 +        v = p->val;
  19.395 +        p->val = ONONE;
  19.396 +    } else if(CONSP(p->start_state->val)){
  19.397 +        v = p->start_state->val;
  19.398 +        p->start_state->val = ONULL;
  19.399 +        v = nrev(v);
  19.400 +    }
  19.401 +    return v;
  19.402 +}
  19.403 +    
  19.404 +int begin_start(Parser *p, char c){
  19.405 +    int err = 0;
  19.406 +    err = Parser_push(p, state_start, "start");
  19.407 +    if(err) goto exit;
  19.408 +    p->start_state = p->state;
  19.409 +  exit:
  19.410 +    return err;
  19.411 +}
  19.412 +
  19.413 +int state_start(Parser *p, char c){
  19.414 +    int err = 0;
  19.415 +    if(at_eof(p)){
  19.416 +        err = end_start(p);
  19.417 +    } else if(in_space_class(c)){
  19.418 +        //skip
  19.419 +    } else if(in_comment_class(c)){
  19.420 +        begin_comment(p, c);
  19.421 +    } else if(c == c_list_open){
  19.422 +        begin_list(p, c);
  19.423 +    } else if(c == c_list_close){
  19.424 +        parse_error(p);
  19.425 +        err = -EINVAL;
  19.426 +    } else if(in_string_quote_class(c)){
  19.427 +        begin_string(p, c);
  19.428 +    } else if(in_printable_class(c)){
  19.429 +        begin_atom(p, c);
  19.430 +    } else if(c == 0x04){
  19.431 +        //ctrl-D, EOT: end-of-text.
  19.432 +        Parser_input_eof(p);
  19.433 +    } else {
  19.434 +        parse_error(p);
  19.435 +        err = -EINVAL;
  19.436 +    }
  19.437 +    return err;
  19.438 +}
  19.439 +
  19.440 +int end_start(Parser *p){
  19.441 +    int err = 0;
  19.442 +    err = Parser_return(p);
  19.443 +    return err;
  19.444 +}
  19.445 +
  19.446 +int begin_comment(Parser *p, char c){
  19.447 +    int err = 0;
  19.448 +    err = Parser_push(p, state_comment, "comment");
  19.449 +    if(err) goto exit;
  19.450 +    err = inputchar(p, c);
  19.451 +  exit:
  19.452 +    return err;
  19.453 +}
  19.454 +
  19.455 +int state_comment(Parser *p, char c){
  19.456 +    int err = 0;
  19.457 +    if(c == '\n' || at_eof(p)){
  19.458 +        err = end_comment(p);
  19.459 +    } else {
  19.460 +        err = inputchar(p, c);
  19.461 +    }
  19.462 +    return err;
  19.463 +}
  19.464 +
  19.465 +int end_comment(Parser *p){
  19.466 +    return Parser_pop(p);
  19.467 +}
  19.468 +
  19.469 +int begin_string(Parser *p, char c){
  19.470 +    int err = 0;
  19.471 +    err = Parser_push(p, state_string, "string");
  19.472 +    if(err) goto exit;
  19.473 +    newtoken(p);
  19.474 +    p->state->delim = c;
  19.475 +  exit:
  19.476 +    return err;
  19.477 +}
  19.478 +
  19.479 +int state_string(Parser *p, char c){
  19.480 +    int err = 0;
  19.481 +    if(at_eof(p)){
  19.482 +        parse_error_id(p, PARSE_ERR_UNEXPECTED_EOF);
  19.483 +        err = -EINVAL;
  19.484 +    } else if(c == p->state->delim){
  19.485 +        err = end_string(p);
  19.486 +    } else if(c == '\\'){
  19.487 +        err = Parser_push(p, state_escape, "escape");
  19.488 +    } else {
  19.489 +        err = savechar(p, c);
  19.490 +    }
  19.491 +    return err;
  19.492 +}
  19.493 +
  19.494 +int end_string(Parser *p){
  19.495 +    int err = 0;
  19.496 +    err = do_string(p);
  19.497 +    if(err) goto exit;
  19.498 +    err = Parser_return(p);
  19.499 +  exit:
  19.500 +    return err;
  19.501 +}
  19.502 +
  19.503 +int state_escape(Parser *p, char c){
  19.504 +    int err = 0;
  19.505 +    char d;
  19.506 +    if(at_eof(p)){
  19.507 +        parse_error_id(p, PARSE_ERR_UNEXPECTED_EOF);
  19.508 +        err = -EINVAL;
  19.509 +        goto exit;
  19.510 +    }
  19.511 +    if(get_escape(c, &d) == 0){
  19.512 +        err = savechar(p, d);
  19.513 +        if(err) goto exit;
  19.514 +        err = Parser_pop(p);
  19.515 +    } else if(c == 'x'){
  19.516 +        p->state->fn = state_hex;
  19.517 +        p->state->ival = 0;
  19.518 +        p->state->count = 0;
  19.519 +    } else {
  19.520 +        p->state->fn = state_octal;
  19.521 +        p->state->ival = 0;
  19.522 +        p->state->count = 0;
  19.523 +        err = Parser_input_char(p, c);
  19.524 +    }
  19.525 +  exit:
  19.526 +    return err;
  19.527 +}
  19.528 +
  19.529 +int octaldone(Parser *p){
  19.530 +    int err = 0;
  19.531 +    char d = (char)(p->state->ival & 0xff);
  19.532 +    err = Parser_pop(p);
  19.533 +    if(err) goto exit;
  19.534 +    err = Parser_input_char(p, d);
  19.535 +  exit:
  19.536 +    return err;
  19.537 +}
  19.538 +
  19.539 +int octaldigit(Parser *p, char c){
  19.540 +    int err = 0;
  19.541 +    p->state->ival *= 8;
  19.542 +    p->state->ival += c - '0'; 
  19.543 +    p->state->count++;
  19.544 +    if(err) goto exit;
  19.545 +    if(p->state->ival < 0 || p->state->ival > 0xff){
  19.546 +        parse_error(p);
  19.547 +        err = -EINVAL;
  19.548 +        goto exit;
  19.549 +    }
  19.550 +    if(p->state->count == 3){
  19.551 +        err = octaldone(p);
  19.552 +    }
  19.553 +  exit:
  19.554 +    return err;
  19.555 +}
  19.556 +
  19.557 +int state_octal(Parser *p, char c){
  19.558 +    int err = 0;
  19.559 +    if(at_eof(p)){
  19.560 +        parse_error_id(p, PARSE_ERR_UNEXPECTED_EOF);
  19.561 +        err = -EINVAL;
  19.562 +        goto exit;
  19.563 +    } else if('0' <= c && c <= '7'){
  19.564 +        err = octaldigit(p, c);
  19.565 +    } else {
  19.566 +        err = octaldone(p);
  19.567 +        if(err) goto exit;
  19.568 +        Parser_input_char(p, c);
  19.569 +    }
  19.570 +  exit:
  19.571 +    return err;
  19.572 +}
  19.573 +
  19.574 +int hexdone(Parser *p){
  19.575 +    int err = 0;
  19.576 +    char d = (char)(p->state->ival & 0xff);
  19.577 +    err = Parser_pop(p);
  19.578 +    if(err) goto exit;
  19.579 +    err = Parser_input_char(p, d);
  19.580 +  exit:
  19.581 +    return err;
  19.582 +}
  19.583 +    
  19.584 +int hexdigit(Parser *p, char c, char d){
  19.585 +    int err = 0;
  19.586 +    p->state->ival *= 16;
  19.587 +    p->state->ival += c - d; 
  19.588 +    p->state->count++;
  19.589 +    if(err) goto exit;
  19.590 +    if(p->state->ival < 0 || p->state->ival > 0xff){
  19.591 +        parse_error(p);
  19.592 +        err = -EINVAL;
  19.593 +        goto exit;
  19.594 +    }
  19.595 +    if(p->state->count == 2){
  19.596 +        err = hexdone(p);
  19.597 +    }
  19.598 +  exit:
  19.599 +    return err;
  19.600 +}
  19.601 +    
  19.602 +int state_hex(Parser *p, char c){
  19.603 +    int err = 0;
  19.604 +    if(at_eof(p)){
  19.605 +        parse_error_id(p, PARSE_ERR_UNEXPECTED_EOF);
  19.606 +        err = -EINVAL;
  19.607 +        goto exit;
  19.608 +    } else if('0' <= c && c <= '9'){
  19.609 +        err = hexdigit(p, c, '0');
  19.610 +    } else if('A' <= c && c <= 'F'){
  19.611 +        err = hexdigit(p, c, 'A');
  19.612 +    } else if('a' <= c && c <= 'f'){
  19.613 +        err = hexdigit(p, c, 'a');
  19.614 +    } else if(p->state->count){
  19.615 +        err =hexdone(p);
  19.616 +        if(err) goto exit;
  19.617 +        Parser_input_char(p, c);
  19.618 +    }
  19.619 +  exit:
  19.620 +    return err;
  19.621 +}
  19.622 +
  19.623 +int begin_atom(Parser *p, char c){
  19.624 +    int err = 0;
  19.625 +    err = Parser_push(p, state_atom, "atom");
  19.626 +    if(err) goto exit;
  19.627 +    newtoken(p);
  19.628 +    err = savechar(p, c);
  19.629 +  exit:
  19.630 +    return err;
  19.631 +}
  19.632 +
  19.633 +int state_atom(Parser *p, char c){
  19.634 +    int err = 0;
  19.635 +    if(at_eof(p)){
  19.636 +        err = end_atom(p);
  19.637 +    } else if(is_separator(p, c) ||
  19.638 +              in_space_class(c) ||
  19.639 +              in_comment_class(c)){
  19.640 +        err = end_atom(p);
  19.641 +        if(err) goto exit;
  19.642 +        err = Parser_input_char(p, c);
  19.643 +    } else {
  19.644 +        err = savechar(p, c);
  19.645 +    }
  19.646 +  exit:
  19.647 +    return err;
  19.648 +}
  19.649 +
  19.650 +int end_atom(Parser *p){
  19.651 +    int err = 0;
  19.652 +    err = do_intern(p);
  19.653 +    if(err) goto exit;
  19.654 +    err = Parser_return(p);
  19.655 +  exit:
  19.656 +    return err;
  19.657 +}
  19.658 +
  19.659 +int state_list(Parser *p, char c){
  19.660 +    int err = 0;
  19.661 +    if(at_eof(p)){
  19.662 +        parse_error_id(p, PARSE_ERR_UNEXPECTED_EOF);
  19.663 +        err = -EINVAL;
  19.664 +    } else if(c == c_list_close){
  19.665 +        p->state->val = nrev(p->state->val);
  19.666 +        err = end_list(p);
  19.667 +    } else {
  19.668 +        err = state_start(p, c);
  19.669 +    }
  19.670 +    return err;
  19.671 +    
  19.672 +}
  19.673 +
  19.674 +int begin_list(Parser *p, char c){
  19.675 +    return Parser_push(p, state_list, "list");
  19.676 +}
  19.677 +
  19.678 +int end_list(Parser *p){
  19.679 +    return Parser_return(p);
  19.680 +}
  19.681 +
  19.682 +/** Reset the fields of a parser to initial values.
  19.683 + *
  19.684 + * @param z parser
  19.685 + */
  19.686 +static void reset(Parser *z){
  19.687 +  IOStream *error_out = z->error_out;
  19.688 +  int flags = z->flags;
  19.689 +  memzero(z, sizeof(Parser));
  19.690 +  z->buf_n = sizeof(z->buf) - 1;
  19.691 +  z->buf_i = 0;
  19.692 +  z->line_no = 1;
  19.693 +  z->char_no = 0;
  19.694 +  z->error_out = error_out;
  19.695 +  z->flags = flags;
  19.696 +}
  19.697 +
  19.698 +/** Set the parser error stream.
  19.699 + * Parse errors are reported on the the error stream if it is non-null.
  19.700 + * 
  19.701 + * @param z parser
  19.702 + * @param error_out error stream
  19.703 + */
  19.704 +void set_error_stream(Parser *z, IOStream *error_out){
  19.705 +  if(z){
  19.706 +    z->error_out = error_out;
  19.707 +  }
  19.708 +}
  19.709 +
  19.710 +/** Get the parser error message for an error code.
  19.711 + *
  19.712 + * @param id error code
  19.713 + * @return error message (empty string if the code is unknown)
  19.714 + */
  19.715 +static char *get_message(ParseErrorId id){
  19.716 +  int i;
  19.717 +  for(i=0; i<catalog_n; i++){
  19.718 +    if(id == catalog[i].id){
  19.719 +      return catalog[i].message;
  19.720 +    }
  19.721 +  }
  19.722 +  return "";
  19.723 +}
  19.724 +
  19.725 +/** Get the line number.
  19.726 + *
  19.727 + * @param in parser
  19.728 + */
  19.729 +int get_line(Parser *in){
  19.730 +  return in->line_no;
  19.731 +}
  19.732 +
  19.733 +/** Get the column number.
  19.734 + *
  19.735 + * @param in parser
  19.736 + */
  19.737 +int get_column(Parser *in){
  19.738 +  return in->char_no;
  19.739 +}
  19.740 +
  19.741 +/** Get the line number the current token started on.
  19.742 + *
  19.743 + * @param in parser
  19.744 + */
  19.745 +int get_tok_line(Parser *in){
  19.746 +  return in->tok_begin_line;
  19.747 +}
  19.748 +
  19.749 +/** Get the column number the current token started on.
  19.750 + *
  19.751 + * @param in parser
  19.752 + */
  19.753 +int get_tok_column(Parser *in){
  19.754 +  return in->tok_begin_char;
  19.755 +}
  19.756 +
  19.757 +/** Report a parse error.
  19.758 + * Does nothing if the error stream is null or there is no error.
  19.759 + *
  19.760 + * @param in parser
  19.761 + */
  19.762 +static void report_error(Parser *in){
  19.763 +  if(in->error_out && in->err){
  19.764 +    char *msg = get_message(in->err);
  19.765 +    char *tok = peek_token(in);
  19.766 +    IOStream_print(in->error_out, PARSE_ERR_FMT,
  19.767 +		   get_tok_line(in), get_tok_column(in), msg);
  19.768 +    if(tok && tok[0]){
  19.769 +        IOStream_print(in->error_out, " '%s'", tok);
  19.770 +    }
  19.771 +    IOStream_print(in->error_out, "\n");
  19.772 +  }
  19.773 +}
  19.774 +
  19.775 +/** Get the error message for the current parse error code.
  19.776 + * Does nothing if there is no error.
  19.777 + *
  19.778 + * @param in parser
  19.779 + * @param buf where to place the message
  19.780 + * @param n maximum number of characters to place in buf
  19.781 + * @return current error code (zero for no error)
  19.782 + */
  19.783 +int parse_error_message(Parser *in, char *buf, int n){
  19.784 +    if(in->err){
  19.785 +        char *msg = get_message(in->err);
  19.786 +        snprintf(buf, n, PARSE_ERR_FMT, get_tok_line(in), get_tok_column(in), msg);
  19.787 +    }
  19.788 +    return in->err;
  19.789 +}
  19.790 +
  19.791 +/** Flag an unspecified parse error. All subsequent reads will fail.
  19.792 + *
  19.793 + * @param in parser
  19.794 + */
  19.795 +void parse_error(Parser *in){
  19.796 +    parse_error_id(in, PARSE_ERR_INVALID_SYNTAX);
  19.797 +}
  19.798 +
  19.799 +/** Flag a parse error. All subsequent reads will fail.
  19.800 + * Does not change the parser error code if it is already set.
  19.801 + *
  19.802 + * @param in parser
  19.803 + * @param id error code
  19.804 + */
  19.805 +void parse_error_id(Parser *in, ParseErrorId id){
  19.806 +    if(!in->err){
  19.807 +        in->err = id;
  19.808 +        report_error(in);
  19.809 +    }
  19.810 +}
  19.811 +
  19.812 +/** Test if the parser's error flag is set.
  19.813 + *
  19.814 + * @param in parser
  19.815 + * @return 1 if set, 0 otherwise
  19.816 + */
  19.817 +int has_error(Parser *in){
  19.818 +    return (in->err > 0);
  19.819 +}
  19.820 +
  19.821 +/** Test if the parser is at end of input.
  19.822 + *
  19.823 + * @param in parser
  19.824 + * @return 1 if at EOF, 0 otherwise
  19.825 + */
  19.826 +int at_eof(Parser *p){
  19.827 +    return p->eof;
  19.828 +}
  19.829 +
  19.830 +//#define SXPR_PARSER_MAIN
  19.831 +#ifdef SXPR_PARSER_MAIN
  19.832 +/* Stuff for standalone testing. */
  19.833 +
  19.834 +#include "file_stream.h"
  19.835 +#include "string_stream.h"
  19.836 +
  19.837 +int stringof(Sxpr exp, char **s){
  19.838 +    int err = 0;
  19.839 +    if(ATOMP(exp)){
  19.840 +        *s = atom_name(exp);
  19.841 +    } else if(STRINGP(exp)){
  19.842 +        *s = string_string(exp);
  19.843 +    } else {
  19.844 +        err = -EINVAL;
  19.845 +        *s = NULL;
  19.846 +    }
  19.847 +    return err;
  19.848 +}
  19.849 +
  19.850 +int child_string(Sxpr exp, Sxpr key, char **s){
  19.851 +    int err = 0;
  19.852 +    Sxpr val = sxpr_child_value(exp, key, ONONE);
  19.853 +    err = stringof(val, s);
  19.854 +    return err;
  19.855 +}
  19.856 +
  19.857 +int intof(Sxpr exp, int *v){
  19.858 +    int err = 0;
  19.859 +    char *s;
  19.860 +    unsigned long l;
  19.861 +    if(INTP(exp)){
  19.862 +        *v = OBJ_INT(exp);
  19.863 +    } else {
  19.864 +        err = stringof(exp, &s);
  19.865 +        if(err) goto exit;
  19.866 +        err = convert_atoul(s, &l);
  19.867 +        *v = (int)l;
  19.868 +    }
  19.869 + exit:
  19.870 +    return err;
  19.871 +}
  19.872 +
  19.873 +int child_int(Sxpr exp, Sxpr key, int *v){
  19.874 +    int err = 0;
  19.875 +    Sxpr val = sxpr_child_value(exp, key, ONONE);
  19.876 +    err = intof(val, v);
  19.877 +    return err;
  19.878 +}
  19.879 +
  19.880 +int eval_vnet(Sxpr exp){
  19.881 +    int err = 0;
  19.882 +    Sxpr oid = intern("id");
  19.883 +    int id;
  19.884 +    err = child_int(exp, oid, &id);
  19.885 +    if(err) goto exit;
  19.886 +    dprintf("> vnet id=%d\n", id);
  19.887 + exit:
  19.888 +    dprintf("< err=%d\n", err);
  19.889 +    return err;
  19.890 +}
  19.891 +
  19.892 +int eval_connect(Sxpr exp){
  19.893 +    int err = 0;
  19.894 +    Sxpr ovif = intern("vif");
  19.895 +    Sxpr ovnet = intern("vnet");
  19.896 +    char *vif;
  19.897 +    int vnet;
  19.898 +
  19.899 +    err = child_string(exp, ovif, &vif);
  19.900 +    if(err) goto exit;
  19.901 +    err = child_int(exp, ovnet, &vnet);
  19.902 +    if(err) goto exit;
  19.903 +    dprintf("> connect vif=%s vnet=%d\n", vif, vnet);
  19.904 + exit:
  19.905 +    dprintf("< err=%d\n", err);
  19.906 +    return err;
  19.907 +}
  19.908 +
  19.909 +int eval(Sxpr exp){
  19.910 +    int err = 0;
  19.911 +    Sxpr oconnect = intern("connect");
  19.912 +    Sxpr ovnet = intern("vnet");
  19.913 +    
  19.914 +    if(sxpr_elementp(exp, ovnet)){
  19.915 +        err = eval_vnet(exp);
  19.916 +    } else if(sxpr_elementp(exp, oconnect)){
  19.917 +        err = eval_connect(exp);
  19.918 +    } else {
  19.919 +        err = -EINVAL;
  19.920 +    }
  19.921 +    return err;
  19.922 +}
  19.923 +
  19.924 +/** Main program for testing.
  19.925 + * Parses input and prints it.
  19.926 + *
  19.927 + * @param argc number of arguments
  19.928 + * @param argv arguments
  19.929 + * @return error code
  19.930 + */
  19.931 +int main(int argc, char *argv[]){
  19.932 +    Parser *pin;
  19.933 +    int err = 0;
  19.934 +    char buf[1024];
  19.935 +    int k;
  19.936 +    Sxpr obj;
  19.937 +    //Sxpr l, x;
  19.938 +    int i = 0;
  19.939 +
  19.940 +    pin = Parser_new();
  19.941 +    set_error_stream(pin, iostdout);
  19.942 +    dprintf("> parse...\n");
  19.943 +    while(1){
  19.944 +        k = fread(buf, 1, 1, stdin);
  19.945 +        err = Parser_input(pin, buf, k);
  19.946 +        while(Parser_ready(pin)){
  19.947 +            obj = Parser_get_val(pin);
  19.948 +            printf("obj %d\n", i++);
  19.949 +            objprint(iostdout, obj, 0); printf("\n");
  19.950 +        }
  19.951 +        if(k <= 0) break;
  19.952 +    }
  19.953 +/*     obj = Parser_get_all(pin); */
  19.954 +/*     for(l = obj ; CONSP(l); l = CDR(l)){ */
  19.955 +/*         x = CAR(l); */
  19.956 +/*         objprint(iostdout, x, 0); printf("\n"); */
  19.957 +/*         eval(x); */
  19.958 +/*     } */
  19.959 +    dprintf("> err=%d\n", err);
  19.960 +    return 0;
  19.961 +}
  19.962 +#endif