From 76474239da7b68e6dd05b3cc7528b85cb3d29b84 Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Mon, 26 Sep 1994 16:31:06 +0000 Subject: [PATCH 01/16] Minor changes. --- dict/lookupec.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/dict/lookupec.c b/dict/lookupec.c index d34027b..9147b17 100644 --- a/dict/lookupec.c +++ b/dict/lookupec.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: lookupec.c,v $ - * Revision 1.2 1994-09-22 14:43:57 adam + * Revision 1.3 1994-09-26 16:31:06 adam + * Minor changes. + * + * Revision 1.2 1994/09/22 14:43:57 adam * First functional version of lookup with error correction. A 'range' * specified the maximum number of insertions+deletions+substitutions. * @@ -14,7 +17,6 @@ * Type 2 is default. depend rule chooses current rule. * */ - #include #include #include -- 1.7.10.4 From be5261b7025fd670361de0268978158eefac2a3c Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Mon, 26 Sep 1994 16:31:23 +0000 Subject: [PATCH 02/16] Minor changes. xmalloc declares xcalloc now. --- include/dfa.h | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) diff --git a/include/dfa.h b/include/dfa.h index 0d58314..55f1f3a 100644 --- a/include/dfa.h +++ b/include/dfa.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: dfa.h,v $ - * Revision 1.1 1994-09-26 10:17:43 adam + * Revision 1.2 1994-09-26 16:31:23 adam + * Minor changes. xmalloc declares xcalloc now. + * + * Revision 1.1 1994/09/26 10:17:43 adam * Dfa-module header files. * */ @@ -115,8 +118,6 @@ extern int debug_dfa_followpos; extern int dfa_verbose; extern unsigned short - thompson_chars[], - brief_chars[], - grep_chars[], - ccl_chars[]; + dfa_thompson_chars[], + dfa_ccl_chars[]; #endif -- 1.7.10.4 From 78e91b9656e1f6b9f47db50083b1dda4af66787f Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Mon, 26 Sep 1994 17:05:54 +0000 Subject: [PATCH 03/16] Trivial. --- include/isam.h | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) diff --git a/include/isam.h b/include/isam.h index dd70f69..bf96583 100644 --- a/include/isam.h +++ b/include/isam.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.h,v $ - * Revision 1.3 1994-09-26 16:08:42 quinn + * Revision 1.4 1994-09-26 17:05:54 quinn + * Trivial. + * + * Revision 1.3 1994/09/26 16:08:42 quinn * Most of the functionality in place. * * Revision 1.2 1994/09/14 13:10:35 quinn @@ -19,7 +22,6 @@ #define ISAM_H #include -#include #define IS_MAX_BLOCKTYPES 4 #define IS_MAX_RECORD 512 @@ -59,11 +61,10 @@ typedef struct isam_struct int (*cmp)(const void *k1, const void *k2); /* compare function */ } isam_struct, *ISAM; +struct is_mtable; typedef struct ispt_struct { - ISAM is; /* which file do we belong to? */ - int ptr; /* current key offset */ - + struct is_mtable *tab; struct ispt_struct *next; /* freelist */ } ispt_struct, *ISPT; -- 1.7.10.4 From 8fa8b7c5d10dd87654e5c219cceebe1a9664544a Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Mon, 26 Sep 1994 17:06:34 +0000 Subject: [PATCH 04/16] Back again... --- isam/Makefile | 4 ++++ isam/isam.c | 21 ++++++++++++++++----- isam/memory.c | 7 +++++-- isam/physical.c | 7 +++++-- isam/physical.h | 7 ++++++- 5 files changed, 36 insertions(+), 10 deletions(-) diff --git a/isam/Makefile b/isam/Makefile index 7ee1081..dd4180b 100644 --- a/isam/Makefile +++ b/isam/Makefile @@ -8,6 +8,10 @@ CPP=cc -E all: $(LIB) +test: test.c $(LIB) + $(CC) -g -o test -I../include test.c \ + ../lib/isam.a ../lib/bfile.a ../lib/util.a + isam-test: isam-test.c $(LIB) $(CC) -g -o isam-test -I../include isam-test.c \ ../lib/isam.a ../lib/bfile.a ../lib/util.a diff --git a/isam/isam.c b/isam/isam.c index ad2f90c..5c847cb 100644 --- a/isam/isam.c +++ b/isam/isam.c @@ -4,8 +4,8 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.c,v $ - * Revision 1.2 1994-09-26 16:07:53 quinn - * Most of the functionality in place. + * Revision 1.3 1994-09-26 17:06:35 quinn + * Back again... * * Revision 1.1 1994/09/12 08:02:13 quinn * Not functional yet @@ -17,12 +17,12 @@ #include #include -#include "isutil.h" -#include "rootblk.h" #include #include #include -#include "memory.h" +#include "isutil.h" +#include "rootblk.h" +#include #include "physical.h" #include "keyops.h" @@ -345,3 +345,14 @@ ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data) is_p_sync(&tab); return is_address(tab.pos_type, tab.data->diskpos); } + +/* + * Locate a table of keys in an isam file. The ISPT is an individual + * position marker for that table. + */ +ISPT is_position(ISAM is, ISAM_P pos); + +/* + * Release ISPT. + */ +void is_pt_free(ISPT ip); diff --git a/isam/memory.c b/isam/memory.c index 13be94b..ba39802 100644 --- a/isam/memory.c +++ b/isam/memory.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: memory.c,v $ - * Revision 1.1 1994-09-26 16:07:56 quinn + * Revision 1.2 1994-09-26 17:06:35 quinn + * Back again... + * + * Revision 1.1 1994/09/26 16:07:56 quinn * Most of the functionality in place. * */ @@ -16,7 +19,7 @@ #include #include -#include "memory.h" +#include #include "physical.h" #include diff --git a/isam/physical.c b/isam/physical.c index d188a2b..3ea43b9 100644 --- a/isam/physical.c +++ b/isam/physical.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: physical.c,v $ - * Revision 1.1 1994-09-26 16:07:57 quinn + * Revision 1.2 1994-09-26 17:06:36 quinn + * Back again... + * + * Revision 1.1 1994/09/26 16:07:57 quinn * Most of the functionality in place. * */ @@ -16,7 +19,7 @@ #include #include -#include "memory.h" +#include static int is_freestore_alloc(ISAM is, int type) { diff --git a/isam/physical.h b/isam/physical.h index 5e9cd54..a31fdd0 100644 --- a/isam/physical.h +++ b/isam/physical.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: physical.h,v $ - * Revision 1.1 1994-09-26 16:07:59 quinn + * Revision 1.2 1994-09-26 17:06:37 quinn + * Back again... + * + * Revision 1.1 1994/09/26 16:07:59 quinn * Most of the functionality in place. * */ @@ -12,6 +15,8 @@ #ifndef PHYSICAL_H #define PHYSICAL_H +#include + void is_p_sync(is_mtable *tab); void is_p_unmap(is_mtable *tab); void is_p_align(is_mtable *tab); -- 1.7.10.4 From 5bcaf79fcb3264b26d896eb2bdda907cf9fb9f5f Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Mon, 26 Sep 1994 17:11:29 +0000 Subject: [PATCH 05/16] Trivial --- isam/isam.c | 7 +++++-- isam/memory.c | 7 +++++-- isam/physical.c | 7 +++++-- isam/physical.h | 7 +++++-- 4 files changed, 20 insertions(+), 8 deletions(-) diff --git a/isam/isam.c b/isam/isam.c index 5c847cb..2f58aa1 100644 --- a/isam/isam.c +++ b/isam/isam.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.c,v $ - * Revision 1.3 1994-09-26 17:06:35 quinn + * Revision 1.4 1994-09-26 17:11:29 quinn + * Trivial + * + * Revision 1.3 1994/09/26 17:06:35 quinn * Back again... * * Revision 1.1 1994/09/12 08:02:13 quinn @@ -22,7 +25,7 @@ #include #include "isutil.h" #include "rootblk.h" -#include +#include "memory.h" #include "physical.h" #include "keyops.h" diff --git a/isam/memory.c b/isam/memory.c index ba39802..38091b2 100644 --- a/isam/memory.c +++ b/isam/memory.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: memory.c,v $ - * Revision 1.2 1994-09-26 17:06:35 quinn + * Revision 1.3 1994-09-26 17:11:30 quinn + * Trivial + * + * Revision 1.2 1994/09/26 17:06:35 quinn * Back again... * * Revision 1.1 1994/09/26 16:07:56 quinn @@ -19,7 +22,7 @@ #include #include -#include +#include "memory.h" #include "physical.h" #include diff --git a/isam/physical.c b/isam/physical.c index 3ea43b9..afb5343 100644 --- a/isam/physical.c +++ b/isam/physical.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: physical.c,v $ - * Revision 1.2 1994-09-26 17:06:36 quinn + * Revision 1.3 1994-09-26 17:11:31 quinn + * Trivial + * + * Revision 1.2 1994/09/26 17:06:36 quinn * Back again... * * Revision 1.1 1994/09/26 16:07:57 quinn @@ -19,7 +22,7 @@ #include #include -#include +#include "memory.h" static int is_freestore_alloc(ISAM is, int type) { diff --git a/isam/physical.h b/isam/physical.h index a31fdd0..fe0766c 100644 --- a/isam/physical.h +++ b/isam/physical.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: physical.h,v $ - * Revision 1.2 1994-09-26 17:06:37 quinn + * Revision 1.3 1994-09-26 17:11:32 quinn + * Trivial + * + * Revision 1.2 1994/09/26 17:06:37 quinn * Back again... * * Revision 1.1 1994/09/26 16:07:59 quinn @@ -15,7 +18,7 @@ #ifndef PHYSICAL_H #define PHYSICAL_H -#include +#include "memory.h" void is_p_sync(is_mtable *tab); void is_p_unmap(is_mtable *tab); -- 1.7.10.4 From 5c1d5fc3fe386e41537259b6268b510a1011c185 Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Mon, 26 Sep 1994 17:12:32 +0000 Subject: [PATCH 06/16] Back again --- isam/memory.h | 88 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 88 insertions(+) create mode 100644 isam/memory.h diff --git a/isam/memory.h b/isam/memory.h new file mode 100644 index 0000000..2948448 --- /dev/null +++ b/isam/memory.h @@ -0,0 +1,88 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: memory.h,v $ + * Revision 1.1 1994-09-26 17:12:32 quinn + * Back again + * + * Revision 1.1 1994/09/26 16:07:57 quinn + * Most of the functionality in place. + * + */ + +#ifndef MEMORY_H +#define MEMORY_H + +#include + +extern int is_mbuf_size[3]; + +/* + * Memory buffer. Used to manage records (keys) in memory for + * reading and insertion/deletion. + */ +typedef struct is_mbuf +{ + int refcount; + int type; +#define IS_MBUF_TYPE_SMALL 0 +#define IS_MBUF_TYPE_MEDIUM 1 +#define IS_MBUF_TYPE_LARGE 2 + int offset; + int num; + int cur_record; + struct is_mbuf *next; + char *data; /* dummy */ +} is_mbuf; + +/* + * Structure describing the virtual image of a disk block. + * (these blocks may grow beyond the blocksize during insertion). + */ +typedef struct is_mblock +{ + int num_records; /* number of records */ + int diskpos; /* positive if this block is mapped */ + int nextpos; /* pos of nxt blk. Only valid imm aft. rd. */ + int bread; /* number of bytes read */ + int state; /* state of block in rel. to disk block */ +#define IS_MBSTATE_UNREAD 0 /* block hasn't been read */ +#define IS_MBSTATE_PARTIAL 1 /* block has been partially read */ +#define IS_MBSTATE_CLEAN 2 /* block is clean (unmodified) */ +#define IS_MBSTATE_DIRTY 3 /* block has been modified */ + is_mbuf *cur_mbuf; + is_mbuf *data; /* data contained in block */ + + struct is_mblock *next; /* next diskblock */ +} is_mblock; + +/* + * Descriptor for a specific table. + */ +typedef struct is_mtable +{ + int num_records; /* total number of records */ + int pos_type; /* blocktype */ + is_mblock *cur_mblock; + is_mblock *data; /* blocks contained in this table */ + ISAM is; +} is_mtable; + +is_mblock *xmalloc_mblock(); +is_mbuf *xmalloc_mbuf(int type); +void xfree_mblock(is_mblock *p); +void xfree_mbuf(is_mblock *p); +void is_m_establish_tab(ISAM is, is_mtable *tab, ISAM_P pos); +void is_m_rewind(is_mtable *tab); +void is_m_replace_record(is_mtable *tab, const void *rec); +int is_m_write_record(is_mtable *tab, const void *rec); +void is_m_unread_record(is_mtable *tab); +int is_m_read_record(is_mtable *tab, void *buf); +int is_m_seek_record(is_mtable *tab, const void *rec); +void is_m_delete_record(is_mtable *tab); +int is_m_peek_record(is_mtable *tab, void *rec); +int is_m_read_full(is_mtable *tab, is_mblock *mblock); + +#endif -- 1.7.10.4 From 25711769a3fb5c6bf0ab3eb9634bf74ba07dc48d Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Tue, 27 Sep 1994 16:31:17 +0000 Subject: [PATCH 07/16] First version of grepper: grep with error correction. --- dfa/Makefile | 15 ++- dfa/agrep.c | 141 +++++++++++++------------ dfa/grepper.c | 325 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ dfa/imalloc.c | 7 +- dfa/lexer.c | 67 ++++++------ 5 files changed, 446 insertions(+), 109 deletions(-) create mode 100644 dfa/grepper.c diff --git a/dfa/Makefile b/dfa/Makefile index 5c5c02e..b0ad65d 100644 --- a/dfa/Makefile +++ b/dfa/Makefile @@ -1,13 +1,14 @@ # Copyright (C) 1994, Index Data I/S # All rights reserved. # Sebastian Hammer, Adam Dickmeiss -# $Id: Makefile,v 1.2 1994-09-26 16:30:55 adam Exp $ +# $Id: Makefile,v 1.3 1994-09-27 16:31:17 adam Exp $ SHELL=/bin/sh INCLUDE=-I../include TPROG1=agrep TPROG2=lexer -CFLAGS=-g -Wall -pedantic +TPROG3=grepper +CFLAGS=-g -Wall DEFS=$(INCLUDE) -DYACC -DYYDEBUG=1 -DMEMDEBUG=1 LIB=../lib/dfa.a PO = regexp.o imalloc.o states.o set.o bset.o @@ -16,12 +17,16 @@ YACC=yacc all: $(LIB) +alll: $(LIB) $(TPROG1) $(TPROG2) $(TPROG3) + $(TPROG1): $(TPROG1).o $(LIB) $(CC) $(CFLAGS) -o $(TPROG1) $(TPROG1).o $(LIB) ../lib/util.a $(TPROG2): $(TPROG2).o readfile.o $(LIB) - $(CC) $(CFLAGS) -o $(TPROG2) $(TPROG2).o readfile.o \ - $(LIB) ../lib/util.a + $(CC) $(CFLAGS) -o $(TPROG2) $(TPROG2).o readfile.o $(LIB) ../lib/util.a + +$(TPROG3): $(TPROG3).o $(LIB) + $(CC) $(CFLAGS) -o $(TPROG3) $(TPROG3).o $(LIB) ../lib/util.a $(LIB): $(PO) rm -f $(LIB) @@ -37,7 +42,7 @@ $(LIB): $(PO) mv y.tab.o $*.o clean: - rm -f *.[oa] $(TPROG1) $(TPROG2) core mon.out gmon.out errlist y.tab.c + rm -f *.[oa] $(TPROG1) $(TPROG2) $(TPROG3) core mon.out gmon.out errlist y.tab* depend: depend2 diff --git a/dfa/agrep.c b/dfa/agrep.c index 3c4e242..c8cdf7e 100644 --- a/dfa/agrep.c +++ b/dfa/agrep.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: agrep.c,v $ - * Revision 1.2 1994-09-26 16:30:56 adam + * Revision 1.3 1994-09-27 16:31:18 adam + * First version of grepper: grep with error correction. + * + * Revision 1.2 1994/09/26 16:30:56 adam * Minor changes. imalloc uses xmalloc now. * * Revision 1.1 1994/09/26 10:16:52 adam @@ -34,14 +37,14 @@ static char *prog; -void error( const char *format, ... ) +void error (const char *format, ...) { va_list argptr; - va_start( argptr, format ); - fprintf( stderr, "%s error: ", prog ); - (void) vfprintf( stderr, format, argptr ); - putc( '\n', stderr ); - exit( 1 ); + va_start (argptr, format); + fprintf (stderr, "%s error: ", prog); + (void) vfprintf (stderr, format, argptr); + putc ('\n', stderr); + exit (1); } #ifdef YYDEBUG @@ -54,18 +57,18 @@ extern int alexdebug; static int show_lines = 0; -int agrep_options( argc, argv ) +int agrep_options (argc, argv) int argc; char **argv; { - while( --argc > 0 ) - if( **++argv == '-' ) - while( *++*argv ) + while (--argc > 0) + if (**++argv == '-') + while (*++*argv) { - switch( **argv ) + switch (**argv) { case 'V': - fprintf( stderr, "%s: %s %s\n", prog, __DATE__, __TIME__ ); + fprintf (stderr, "%s: %s %s\n", prog, __DATE__, __TIME__); continue; case 'v': dfa_verbose = 1; @@ -83,7 +86,7 @@ char **argv; continue; #endif case 'd': - switch( *++*argv ) + switch (*++*argv) { case 's': debug_dfa_tran = 1; @@ -102,7 +105,7 @@ char **argv; } continue; default: - fprintf( stderr, "%s: unknown option `-%s'\n", prog, *argv ); + fprintf (stderr, "%s: unknown option `-%s'\n", prog, *argv); return 1; } break; @@ -115,21 +118,21 @@ static char *inf_buf; static char *inf_ptr, *inf_flsh; static int inf_eof, line_no; -static int inf_flush( fd ) +static int inf_flush (fd) int fd; { char *p; unsigned b, r; r = (unsigned) (inf_buf+INF_BUF_SIZE - inf_ptr); /* no of `wrap' bytes */ - if( r ) - memcpy( inf_buf, inf_ptr, r ); + if (r) + memcpy (inf_buf, inf_ptr, r); inf_ptr = p = inf_buf + r; b = INF_BUF_SIZE - r; do - if( (r = read( fd, p, b ) ) == (unsigned) -1 ) + if ((r = read (fd, p, b)) == (unsigned) -1) return -1; - else if( r ) + else if (r) p += r; else { @@ -137,36 +140,36 @@ int fd; inf_eof = 1; break; } - while( (b -= r) > 0 ); - while( p != inf_buf && *--p != '\n' ) + while ((b -= r) > 0); + while (p != inf_buf && *--p != '\n') ; - while( p != inf_buf && *--p != '\n' ) + while (p != inf_buf && *--p != '\n') ; inf_flsh = p+1; return 0; } -static char *prline( p ) +static char *prline (p) char *p; { char *p0; --p; - while( p != inf_buf && p[-1] != '\n' ) + while (p != inf_buf && p[-1] != '\n') --p; p0 = p; - while( *p++ != '\n' ) + while (*p++ != '\n') ; p[-1] = '\0'; - if( show_lines ) - printf( "%5d:\t%s\n", line_no, p0 ); + if (show_lines) + printf ("%5d:\t%s\n", line_no, p0); else - puts( p0 ); + puts (p0); p[-1] = '\n'; return p; } -static int go( fd, dfaar ) +static int go (fd, dfaar) int fd; DFA_state **dfaar; { @@ -176,40 +179,40 @@ DFA_state **dfaar; int i; unsigned char c; - while( 1 ) + while (1) { - for( c = *inf_ptr++, t=s->trans, i=s->tran_no; --i >= 0; t++ ) - if( c >= t->ch[0] && c <= t->ch[1] ) + for (c = *inf_ptr++, t=s->trans, i=s->tran_no; --i >= 0; t++) + if (c >= t->ch[0] && c <= t->ch[1]) { p = inf_ptr; do { - if( (s = dfaar[t->to] )->rule_no ) + if ((s = dfaar[t->to])->rule_no) { - inf_ptr = prline( inf_ptr ); + inf_ptr = prline (inf_ptr); c = '\n'; break; } - for( t=s->trans, i=s->tran_no; --i >= 0; t++ ) - if( (unsigned) *p >= t->ch[0] - && (unsigned) *p <= t->ch[1] ) + for (t=s->trans, i=s->tran_no; --i >= 0; t++) + if ((unsigned) *p >= t->ch[0] + && (unsigned) *p <= t->ch[1]) break; p++; - } while( i >= 0 ); + } while (i >= 0); s = dfaar[0]; break; } - if( c == '\n' ) + if (c == '\n') { ++line_no; - if( inf_ptr == inf_flsh ) + if (inf_ptr == inf_flsh) { - if( inf_eof ) + if (inf_eof) break; ++line_no; - if( inf_flush( fd ) ) + if (inf_flush (fd)) { - fprintf( stderr, "%s: read error\n", prog ); + fprintf (stderr, "%s: read error\n", prog); return -1; } } @@ -218,24 +221,24 @@ DFA_state **dfaar; return 0; } -int agrep( dfas, fd ) +int agrep (dfas, fd) DFA_states *dfas; int fd; { - inf_buf = imalloc( sizeof(char)*INF_BUF_SIZE ); + inf_buf = imalloc (sizeof(char)*INF_BUF_SIZE); inf_eof = 0; inf_ptr = inf_buf+INF_BUF_SIZE; - inf_flush( fd ); + inf_flush (fd); line_no = 1; - go( fd, dfas->sortarray); + go (fd, dfas->sortarray); - ifree( inf_buf ); + ifree (inf_buf); return 0; } -int main( argc, argv ) +int main (argc, argv) int argc; char **argv; { @@ -253,42 +256,42 @@ char **argv; alexdebug = 0; #endif #endif - setbuf( stdout, outbuf ); - i = agrep_options( argc, argv ); - if( i ) + setbuf (stdout, outbuf); + i = agrep_options (argc, argv); + if (i) return i; - while( --argc > 0 ) - if( **++argv != '-' && **argv ) - if( !pattern ) + while (--argc > 0) + if (**++argv != '-' && **argv) + if (!pattern) { pattern = *argv; - i = parse_dfa( dfa, &pattern, dfa_thompson_chars ); - if( i || *pattern ) + i = parse_dfa (dfa, &pattern, dfa_thompson_chars); + if (i || *pattern) { - fprintf( stderr, "%s: illegal pattern\n", prog ); + fprintf (stderr, "%s: illegal pattern\n", prog); return 1; } dfa->root = dfa->top; - dfas = mk_dfas( dfa, 200 ); - rm_dfa( &dfa ); + dfas = mk_dfas (dfa, 200); + rm_dfa (&dfa); } else { ++no; - fd = open( *argv, O_RDONLY | O_BINARY); - if( fd == -1 ) + fd = open (*argv, O_RDONLY | O_BINARY); + if (fd == -1) { - fprintf( stderr, "%s: couldn't open `%s'\n", prog, *argv ); + fprintf (stderr, "%s: couldn't open `%s'\n", prog, *argv); return 1; } - i = agrep( dfas, fd ); - close( fd ); - if( i ) + i = agrep (dfas, fd); + close (fd); + if (i) return i; } - if( !no ) + if (!no) { - fprintf( stderr, "%s: no files specified\n", prog ); + fprintf (stderr, "%s: no files specified\n", prog); return 2; } fflush(stdout); diff --git a/dfa/grepper.c b/dfa/grepper.c new file mode 100644 index 0000000..afc8927 --- /dev/null +++ b/dfa/grepper.c @@ -0,0 +1,325 @@ +/* + * Copyright (C) 1994, Index Data I/S + * All rights reserved. + * Sebastian Hammer, Adam Dickmeiss + * + * $Log: grepper.c,v $ + * Revision 1.1 1994-09-27 16:31:18 adam + * First version of grepper: grep with error correction. + * + */ +#include +#include +#include +#include +#include + +#include +#include +#include "imalloc.h" + +char *prog; +static int show_line = 0; + +typedef unsigned MatchWord; +#define WORD_BITS 32 + +typedef struct { + int n; /* no of MatchWord needed */ + int range; /* max no. of errors */ + MatchWord *Sc; /* Mask Sc */ +} MatchContext; + +#define INFBUF_SIZE 16384 + +static inline void set_bit (MatchContext *mc, MatchWord *m, int ch, int state) +{ + int off = state & (WORD_BITS-1); + int wno = state / WORD_BITS; + + m[mc->n * ch + wno] |= 1<n * ch + wno] &= ~(1<n * ch + wno] & (1<n = (dfas->no+WORD_BITS) / WORD_BITS; + mc->range = range; + mc->Sc = icalloc (sizeof(*mc->Sc) * 256 * mc->n); + + for (i=0; ino; i++) + { + int j; + DFA_state *state = dfas->sortarray[i]; + + for (j=0; jtran_no; j++) + { + int ch; + int ch0 = state->trans[j].ch[0]; + int ch1 = state->trans[j].ch[1]; + assert (ch0 >= 0 && ch1 >= 0); + + for (ch = ch0; ch <= ch1; ch++) + set_bit (mc, mc->Sc, ch, i); + } + } + return mc; +} + +static void mask_shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc, + DFA_states *dfas, int ch) +{ + int i, s; + Rdst[0] = 1; + for (i = 1; in; i++) + Rdst[i] = 0; + for (s = 0; sno; s++) + if (get_bit (mc, Rsrc, 0, s)) + { + DFA_state *state = dfas->sortarray[s]; + int i = state->tran_no; + while (--i >= 0) + if (ch >= state->trans[i].ch[0] && ch <= state->trans[i].ch[1]) + set_bit (mc, Rdst, 0, state->trans[i].to); + } +} + +static void shift (MatchContext *mc, MatchWord *Rdst, MatchWord *Rsrc, + DFA_states *dfas) +{ + int i, s; + for (i = 0; in; i++) + Rdst[i] = 0; + for (s = 0; sno; s++) + if (get_bit (mc, Rsrc, 0, s)) + { + DFA_state *state = dfas->sortarray[s]; + int i = state->tran_no; + while (--i >= 0) + set_bit (mc, Rdst, 0, state->trans[i].to); + } +} + +static void or (MatchContext *mc, MatchWord *Rdst, + MatchWord *Rsrc1, MatchWord *Rsrc2) +{ + int i; + for (i = 0; in; i++) + Rdst[i] = Rsrc1[i] | Rsrc2[i]; +} + + +static int go (MatchContext *mc, DFA_states *dfas, FILE *inf) +{ + MatchWord *Rj, *Rj1, *Rj_a, *Rj_b; + int s, d, ch; + int lineno = 1; + char *infbuf; + int inf_ptr = 1; + int no_match = 0; + + infbuf = imalloc (INFBUF_SIZE); + infbuf[0] = '\n'; + Rj = icalloc (mc->n * (mc->range+1) * sizeof(*Rj)); + Rj1 = icalloc (mc->n * (mc->range+1) * sizeof(*Rj)); + Rj_a = icalloc (mc->n * sizeof(*Rj)); + Rj_b = icalloc (mc->n * sizeof(*Rj)); + + set_bit (mc, Rj, 0, 0); + for (d = 1; d<=mc->range; d++) + { + int s; + memcpy (Rj + mc->n * d, Rj + mc->n * (d-1), mc->n * sizeof(*Rj)); + for (s = 0; sno; s++) + { + if (get_bit (mc, Rj, d-1, s)) + { + DFA_state *state = dfas->sortarray[s]; + int i = state->tran_no; + while (--i >= 0) + set_bit (mc, Rj, d, state->trans[i].to); + } + } + } + while ((ch = getc (inf)) != EOF) + { + MatchWord *Rj_t; + if (ch == '\n') + { + if (no_match) + { + int i = inf_ptr; + if (show_line) + printf ("%5d:", lineno); + while (infbuf[i] != '\n') + { + if (--i < 0) + i = INFBUF_SIZE-1; + } + do + { + if (++i == INFBUF_SIZE) + i = 0; + putchar (infbuf[i]); + } while (infbuf[i] != '\n'); + no_match = 0; + } + lineno++; + } + infbuf[inf_ptr++] = ch; + if (inf_ptr == INFBUF_SIZE) + inf_ptr = 0; + mask_shift (mc, Rj1, Rj, dfas, ch); + for (d = 1; d <= mc->range; d++) + { + mask_shift (mc, Rj_b, Rj+d*mc->n, dfas, ch);/* 1 */ + + shift (mc, Rj_a, Rj+(d-1)*mc->n, dfas); /* 2 */ + + or (mc, Rj_a, Rj_a, Rj_b); /* 1,2 */ + + shift (mc, Rj_b, Rj1+(d-1)*mc->n, dfas); /* 3 */ + + or (mc, Rj_a, Rj_a, Rj_b); /* 1,2,3 */ + + or (mc, Rj1+d*mc->n, Rj_a, Rj+(d-1)*mc->n); /* 1,2,3,4 */ + } + for (s = 0; sno; s++) + { + if (dfas->sortarray[s]->rule_no) + if (get_bit (mc, Rj1+mc->range*mc->n, 0, s)) + no_match++; + } + for (d = 0; d <= mc->range; d++) + reset_bit (mc, Rj1+d*mc->n, 0, dfas->no); + Rj_t = Rj1; + Rj1 = Rj; + Rj = Rj_t; + } + ifree (Rj); + ifree (Rj1); + ifree (Rj_a); + ifree (Rj_b); + ifree (infbuf); + return 0; +} + +static int grep_file (DFA_states *dfas, const char *fname, int range) +{ + FILE *inf; + MatchContext *mc; + + if (fname) + { + inf = fopen (fname, "r"); + if (!inf) + { + log (LOG_FATAL|LOG_ERRNO, "cannot open `%s'", fname); + exit (1); + } + } + else + inf = stdin; + + mc = mk_MatchContext (dfas, range); + + go (mc, dfas, inf); + + if (fname) + fclose (inf); + return 0; +} + +int main (int argc, char **argv) +{ + int ret; + int range = 0; + char *arg; + char *pattern = NULL; + DFA_states *dfas = NULL; + int no_files = 0; + + prog = argv[0]; + while ((ret = options ("nr:dsv:", argv, argc, &arg)) != -2) + { + if (ret == 0) + { + if (!pattern) + { + int i; + DFA *dfa = init_dfa(); + pattern = arg; + i = parse_dfa (dfa, &pattern, dfa_thompson_chars); + if (i || *pattern) + { + fprintf (stderr, "%s: illegal pattern\n", prog); + return 1; + } + dfa->root = dfa->top; + dfas = mk_dfas (dfa, 200); + rm_dfa (&dfa); + } + else + { + no_files++; + grep_file (dfas, arg, range); + } + } + else if (ret == 'v') + { + log_init (atoi(arg), prog, NULL); + } + else if (ret == 's') + { + dfa_verbose = 1; + } + else if (ret == 'd') + { + debug_dfa_tran = 1; + debug_dfa_followpos = 1; + debug_dfa_trav = 1; + } + else if (ret == 'r') + { + range = atoi (arg); + } + else if (ret == 'n') + { + show_line = 1; + } + else + { + log (LOG_FATAL, "unknown option"); + exit (1); + } + } + if (!pattern) + { + fprintf (stderr, "usage:\n " + " %s [-d] [-n] [-r n] [-s] [-v n] pattern file ..\n", prog); + exit (1); + } + else if (no_files == 0) + { + grep_file (dfas, NULL, range); + } + return 0; +} diff --git a/dfa/imalloc.c b/dfa/imalloc.c index 7e9ec71..a0a98f1 100644 --- a/dfa/imalloc.c +++ b/dfa/imalloc.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: imalloc.c,v $ - * Revision 1.2 1994-09-26 16:30:56 adam + * Revision 1.3 1994-09-27 16:31:19 adam + * First version of grepper: grep with error correction. + * + * Revision 1.2 1994/09/26 16:30:56 adam * Minor changes. imalloc uses xmalloc now. * * Revision 1.1 1994/09/26 10:16:54 adam @@ -73,7 +76,7 @@ void *icalloc (size_t size) ++alloc_calls; return (void *)p; #else - void p = (void) xcalloc( size, 1 ); + void *p = (void) xcalloc( size, 1 ); if( !p ) log (LOG_FATAL, "Out of memory (icalloc)" ); return p; diff --git a/dfa/lexer.c b/dfa/lexer.c index 98337d1..9729d9e 100644 --- a/dfa/lexer.c +++ b/dfa/lexer.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: lexer.c,v $ - * Revision 1.1 1994-09-26 10:16:55 adam + * Revision 1.2 1994-09-27 16:31:20 adam + * First version of grepper: grep with error correction. + * + * Revision 1.1 1994/09/26 10:16:55 adam * First version of dfa module in alex. This version uses yacc to parse * regular expressions. This should be hand-made instead. * @@ -27,14 +30,14 @@ static char *prog; -void error( const char *format, ... ) +void error (const char *format, ...) { va_list argptr; - va_start( argptr, format ); - fprintf( stderr, "%s error: ", prog ); - (void) vfprintf( stderr, format, argptr ); - putc( '\n', stderr ); - exit( 1 ); + va_start (argptr, format); + fprintf (stderr, "%s error: ", prog); + (void) vfprintf (stderr, format, argptr); + putc ('\n', stderr); + exit (1); } #ifdef YACC @@ -44,21 +47,17 @@ extern int alexdebug; #endif int ccluse = 0; -static int alex_options (int argc, char **argv); - -static int alex_options (int argc, char **argv) +static int lexer_options (int argc, char **argv) { - while( --argc > 0 ) - if( **++argv == '-' ) - while( *++*argv ) + while (--argc > 0) + if (**++argv == '-') + while (*++*argv) { - switch( **argv ) + switch (**argv) { -#ifdef __STDC__ case 'V': - fprintf( stderr, "%s: %s %s\n", prog, __DATE__, __TIME__ ); + fprintf (stderr, "%s: %s %s\n", prog, __DATE__, __TIME__); continue; -#endif case 'v': dfa_verbose = 1; continue; @@ -73,7 +72,7 @@ static int alex_options (int argc, char **argv) ccluse = 1; continue; case 'd': - switch( *++*argv ) + switch (*++*argv) { case 's': debug_dfa_tran = 1; @@ -92,7 +91,8 @@ static int alex_options (int argc, char **argv) } continue; default: - fprintf( stderr, "%s: unknown option `-%s'\n", prog, *argv ); + fprintf (stderr, "%s: unknown option `-%s'\n", + prog, *argv); return 1; } break; @@ -100,7 +100,7 @@ static int alex_options (int argc, char **argv) return 0; } -int main (int argc, char **argv ) +int main (int argc, char **argv) { int i, no = 0; DFA *dfa; @@ -112,32 +112,33 @@ int main (int argc, char **argv ) #else alexdebug = 0; #endif - i = alex_options( argc, argv ); - if( i ) + i = lexer_options (argc, argv); + if (i) return i; - if( argc < 2 ) + if (argc < 2) { - fprintf( stderr, "%s: usage %s -cVvt -d[stf]\n", prog, prog ); + fprintf (stderr, "usage\n %s [-c] [-V] [-v] [-t] [-d[stf]] file\n", + prog); return 1; } - else while( --argc > 0 ) - if( **++argv != '-' && **argv ) + else while (--argc > 0) + if (**++argv != '-' && **argv) { ++no; - i = read_file( *argv, &dfa ); - if( i ) + i = read_file (*argv, &dfa); + if (i) return i; - dfas = mk_dfas( dfa, 2000 ); - rm_dfa( &dfa ); - rm_dfas( &dfas ); + dfas = mk_dfas (dfa, 2000); + rm_dfa (&dfa); + rm_dfas (&dfas); } #ifdef MEMDEBUG imemstat(); #endif - if( !no ) + if (!no) { - fprintf( stderr, "%s: no files specified\n", prog ); + fprintf (stderr, "%s: no files specified\n", prog); return 2; } return 0; -- 1.7.10.4 From f5004e23c618ff466c82dda165f6a1c6c34400ec Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Tue, 27 Sep 1994 16:31:40 +0000 Subject: [PATCH 08/16] Added id-header. --- isam/Makefile | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/isam/Makefile b/isam/Makefile index dd4180b..345135a 100644 --- a/isam/Makefile +++ b/isam/Makefile @@ -1,3 +1,8 @@ +# Copyright (C) 1994, Index Data I/S +# All rights reserved. +# Sebastian Hammer, Adam Dickmeiss +# $Id: Makefile,v 1.10 1994-09-27 16:31:40 adam Exp $ + SHELL=/bin/sh INCLUDE=-I../include CFLAGS=-g -Wall -pedantic -- 1.7.10.4 From a5545de18b5d3762a1f29569a4b10ca5017506db Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Tue, 27 Sep 1994 20:03:36 +0000 Subject: [PATCH 09/16] Seems relatively bug-free. --- include/isam.h | 14 +++++--- isam/Makefile | 6 ++-- isam/isam.c | 36 +++++++++++++------ isam/issh.c | 1 - isam/memory.c | 103 +++++++++++++++++++++++++++++++++++++++++++------------ isam/memory.h | 16 ++++++--- isam/physical.c | 91 ++++++++++++++++++++++++++++++++++++++++-------- 7 files changed, 207 insertions(+), 60 deletions(-) diff --git a/include/isam.h b/include/isam.h index bf96583..3b694bd 100644 --- a/include/isam.h +++ b/include/isam.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.h,v $ - * Revision 1.4 1994-09-26 17:05:54 quinn + * Revision 1.5 1994-09-27 20:03:36 quinn + * Seems relatively bug-free. + * + * Revision 1.4 1994/09/26 17:05:54 quinn * Trivial. * * Revision 1.3 1994/09/26 16:08:42 quinn @@ -23,12 +26,14 @@ #include +#include "../isam/memory.h" +#include "../isam/physical.h" + #define IS_MAX_BLOCKTYPES 4 #define IS_MAX_RECORD 512 #define IS_DEF_REPACK_PERCENT "30" /* how much relative change before repack */ typedef unsigned int SYSNO; /* should be somewhere else */ -typedef unsigned int ISAM_P; /* * Description of a blocktype (part of an isam file) @@ -42,7 +47,7 @@ typedef struct isam_blocktype int max_keys_block0; /* max num of keys in first block */ int nice_keys_block; /* nice number of keys per block */ int max_keys; /* max number of keys per table */ - int freelist; /* fist free block */ + int freelist; /* first free block */ int top; /* first unused block */ int index; /* placeholder. Always 0. */ char *dbuf; /* buffer for use in I/O operations */ @@ -59,9 +64,8 @@ typedef struct isam_struct int keysize; /* size of the keys (records) used */ int repack; /* how many percent to grow before repack */ int (*cmp)(const void *k1, const void *k2); /* compare function */ -} isam_struct, *ISAM; +} isam_struct; -struct is_mtable; typedef struct ispt_struct { struct is_mtable *tab; diff --git a/isam/Makefile b/isam/Makefile index 345135a..341ee3e 100644 --- a/isam/Makefile +++ b/isam/Makefile @@ -1,7 +1,7 @@ # Copyright (C) 1994, Index Data I/S # All rights reserved. # Sebastian Hammer, Adam Dickmeiss -# $Id: Makefile,v 1.10 1994-09-27 16:31:40 adam Exp $ +# $Id: Makefile,v 1.11 1994-09-27 20:03:50 quinn Exp $ SHELL=/bin/sh INCLUDE=-I../include @@ -13,6 +13,8 @@ CPP=cc -E all: $(LIB) +alll: $(LIB) isam-test issh + test: test.c $(LIB) $(CC) -g -o test -I../include test.c \ ../lib/isam.a ../lib/bfile.a ../lib/util.a @@ -37,7 +39,7 @@ $(LIB): $(PO) $(CC) -c $(DEFS) $(CFLAGS) $< clean: - rm -f *.[oa] $(TPROG) core mon.out gmon.out errlist isam-test issh + rm -f *.[oa] $(TPROG) core mon.out gmon.out errlist test isam-test issh depend: depend2 diff --git a/isam/isam.c b/isam/isam.c index 2f58aa1..3ae755c 100644 --- a/isam/isam.c +++ b/isam/isam.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.c,v $ - * Revision 1.4 1994-09-26 17:11:29 quinn + * Revision 1.5 1994-09-27 20:03:50 quinn + * Seems relatively bug-free. + * + * Revision 1.4 1994/09/26 17:11:29 quinn * Trivial * * Revision 1.3 1994/09/26 17:06:35 quinn @@ -25,8 +28,6 @@ #include #include "isutil.h" #include "rootblk.h" -#include "memory.h" -#include "physical.h" #include "keyops.h" static int splitargs(const char *s, char *bf[], int max) @@ -266,7 +267,7 @@ ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data) is_mtable tab; int res; char keybuf[IS_MAX_RECORD]; - int oldnum, oldtype; + int oldnum, oldtype, i; char operation, *record; is_m_establish_tab(is, &tab, pos); @@ -282,10 +283,10 @@ ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data) while (num) { operation = *(data)++; - record = (char*)data; + record = (char*) data; data += is_keysize(is); num--; - while (num && !memcmp(record, data, is_keysize(tab.is) + 1)) + while (num && !memcmp(record - 1, data, is_keysize(tab.is) + 1)) { data += 1 + is_keysize(is); num--; @@ -337,16 +338,29 @@ ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data) } } } - while (tab.pos_type < tab.is->num_types - 1 && tab.num_records > - tab.is->types[tab.pos_type].max_keys) - tab.pos_type++; + i = tab.pos_type; + while (i < tab.is->num_types - 1 && tab.num_records > + tab.is->types[i].max_keys) + i++; + if (i != tab.pos_type) + { + is_p_unmap(&tab); + tab.pos_type = i; + } if (!oldnum || tab.pos_type != oldtype || (abs(oldnum - tab.num_records) * 100) / oldnum > tab.is->repack) is_p_remap(&tab); else is_p_align(&tab); - is_p_sync(&tab); - return is_address(tab.pos_type, tab.data->diskpos); + if (tab.data) + { + is_p_sync(&tab); + pos = is_address(tab.pos_type, tab.data->diskpos); + } + else + pos = 0; + is_m_release_tab(&tab); + return pos; } /* diff --git a/isam/issh.c b/isam/issh.c index 0b5fb8b..15232bb 100644 --- a/isam/issh.c +++ b/isam/issh.c @@ -3,7 +3,6 @@ #include #include -#include #include static ISAM is = 0; diff --git a/isam/memory.c b/isam/memory.c index 38091b2..7962a0e 100644 --- a/isam/memory.c +++ b/isam/memory.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: memory.c,v $ - * Revision 1.3 1994-09-26 17:11:30 quinn + * Revision 1.4 1994-09-27 20:03:52 quinn + * Seems relatively bug-free. + * + * Revision 1.3 1994/09/26 17:11:30 quinn * Trivial * * Revision 1.2 1994/09/26 17:06:35 quinn @@ -22,22 +25,32 @@ #include #include -#include "memory.h" -#include "physical.h" #include int is_mbuf_size[3] = { 0, 1024, 4096 }; -/* - * TODO: make internal memory-management scheme for these units. - */ +static is_mblock *mblock_tmplist = 0, *mblock_freelist = 0; +static is_mbuf *mbuf_freelist[3] = {0, 0, 0}; + +#define MALLOC_CHUNK 20 is_mblock *xmalloc_mblock() { is_mblock *tmp; + int i; - tmp = xmalloc(sizeof(is_mblock)); + if (!mblock_freelist) + { + mblock_freelist = xmalloc(sizeof(is_mblock) * MALLOC_CHUNK); + for (i = 0; i < MALLOC_CHUNK - 1; i++) + mblock_freelist[i].next = &mblock_freelist[i+1]; + mblock_freelist[i].next = 0; + } + tmp = mblock_freelist; + mblock_freelist = mblock_freelist->next; tmp->next = 0; + tmp->state = IS_MBSTATE_UNREAD; + tmp->data = 0; return tmp; } @@ -45,8 +58,16 @@ is_mbuf *xmalloc_mbuf(int type) { is_mbuf *tmp; - tmp = xmalloc(sizeof(is_mbuf) + is_mbuf_size[type]); - tmp->type = type; + if (mbuf_freelist[type]) + { + tmp = mbuf_freelist[type]; + mbuf_freelist[type] = tmp->next; + } + else + { + tmp = xmalloc(sizeof(is_mbuf) + is_mbuf_size[type]); + tmp->type = type; + } tmp->refcount = type ? 1 : 0; tmp->offset = tmp->num = tmp->cur_record = 0; tmp->data = (char*) tmp + sizeof(is_mbuf); @@ -54,19 +75,48 @@ is_mbuf *xmalloc_mbuf(int type) return tmp; } -#if 0 +void xfree_mbuf(is_mbuf *p) +{ + p->next = mbuf_freelist[p->type]; + mbuf_freelist[p->type] = p; +} + +void xfree_mbufs(is_mbuf *l) +{ + is_mbuf *p; + + while (l) + { + p = l->next; + xfree_mbuf(l); + l = p; + } +} + void xfree_mblock(is_mblock *p) { - xfree(p); + xfree_mbufs(p->data); + p->next = mblock_freelist; + mblock_freelist = p; } -#endif -#if 0 -void xfree_mbuf(is_mblock *p) +void xrelease_mblock(is_mblock *p) { - xfree(p); + p->next = mblock_tmplist; + mblock_tmplist = p; +} + +void xfree_mblocks(is_mblock *l) +{ + is_mblock *p; + + while (l) + { + p = l->next; + xfree_mblock(l); + l = p; + } } -#endif void is_m_establish_tab(ISAM is, is_mtable *tab, ISAM_P pos) { @@ -97,6 +147,13 @@ void is_m_establish_tab(ISAM is, is_mtable *tab, ISAM_P pos) tab->is = is; } +void is_m_release_tab(is_mtable *tab) +{ + xfree_mblocks(tab->data); + xfree_mblocks(mblock_tmplist); + mblock_tmplist = 0; +} + void is_m_rewind(is_mtable *tab) { tab->cur_mblock = tab->data; @@ -234,23 +291,25 @@ void is_m_unread_record(is_mtable *tab) int is_m_peek_record(is_mtable *tab, void *rec) { is_mbuf *mbuf; + is_mblock *mblock; /* make sure block is all in memory */ if (tab->cur_mblock->state <= IS_MBSTATE_PARTIAL) if (read_current_full(tab, tab->cur_mblock) < 0) return -1; - mbuf = tab->cur_mblock->cur_mbuf; + mblock = tab->cur_mblock; + mbuf = mblock->cur_mbuf; if (mbuf->cur_record >= mbuf->num) /* are we at end of mbuf? */ { if (!mbuf->next) /* end of mblock */ { - if (tab->cur_mblock->next) + if (mblock->next) { - tab->cur_mblock = tab->cur_mblock->next; - if (tab->cur_mblock->next->state <= IS_MBSTATE_PARTIAL) - if (read_current_full(tab, tab->cur_mblock->next) < 0) + mblock = mblock->next; + if (mblock->state <= IS_MBSTATE_PARTIAL) + if (read_current_full(tab, mblock) < 0) return -1; - mbuf = tab->cur_mblock->next->data; + mbuf = mblock->data; } else return 0; /* EOTable */ diff --git a/isam/memory.h b/isam/memory.h index 2948448..59e726d 100644 --- a/isam/memory.h +++ b/isam/memory.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: memory.h,v $ - * Revision 1.1 1994-09-26 17:12:32 quinn + * Revision 1.2 1994-09-27 20:03:52 quinn + * Seems relatively bug-free. + * + * Revision 1.1 1994/09/26 17:12:32 quinn * Back again * * Revision 1.1 1994/09/26 16:07:57 quinn @@ -15,10 +18,10 @@ #ifndef MEMORY_H #define MEMORY_H -#include - extern int is_mbuf_size[3]; +typedef unsigned int ISAM_P; + /* * Memory buffer. Used to manage records (keys) in memory for * reading and insertion/deletion. @@ -58,6 +61,7 @@ typedef struct is_mblock struct is_mblock *next; /* next diskblock */ } is_mblock; +typedef struct isam_struct *ISAM; /* * Descriptor for a specific table. */ @@ -73,8 +77,12 @@ typedef struct is_mtable is_mblock *xmalloc_mblock(); is_mbuf *xmalloc_mbuf(int type); void xfree_mblock(is_mblock *p); -void xfree_mbuf(is_mblock *p); +void xfree_mblocks(is_mblock *l); +void xfree_mbuf(is_mbuf *p); +void xfree_mbufs(is_mbuf *l); +void xrelease_mblock(is_mblock *p); void is_m_establish_tab(ISAM is, is_mtable *tab, ISAM_P pos); +void is_m_release_tab(is_mtable *tab); void is_m_rewind(is_mtable *tab); void is_m_replace_record(is_mtable *tab, const void *rec); int is_m_write_record(is_mtable *tab, const void *rec); diff --git a/isam/physical.c b/isam/physical.c index afb5343..ae1f584 100644 --- a/isam/physical.c +++ b/isam/physical.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: physical.c,v $ - * Revision 1.3 1994-09-26 17:11:31 quinn + * Revision 1.4 1994-09-27 20:03:53 quinn + * Seems relatively bug-free. + * + * Revision 1.3 1994/09/26 17:11:31 quinn * Trivial * * Revision 1.2 1994/09/26 17:06:36 quinn @@ -22,7 +25,6 @@ #include #include -#include "memory.h" static int is_freestore_alloc(ISAM is, int type) { @@ -41,6 +43,7 @@ static int is_freestore_alloc(ISAM is, int type) else tmp = is->types[type].top++; + log(LOG_DEBUG, "Allocating block #%d", tmp); return tmp; } @@ -48,6 +51,7 @@ static void is_freestore_free(ISAM is, int type, int block) { int tmp; + log(LOG_DEBUG, "Releasing block #%d", block); tmp = is->types[type].freelist; is->types[type].freelist = block; if (bf_write(is->types[type].bf, block, 0, sizeof(tmp), &tmp) < 0) @@ -138,6 +142,7 @@ int is_p_read_full(is_mtable *tab, is_mblock *block) block->bread += toread * is_keysize(tab->is); } } + log(LOG_DEBUG, "R: Block #%d contains %d records.", block->diskpos, block->num_records); return 0; } @@ -155,6 +160,13 @@ void is_p_sync(is_mtable *tab) type = &tab->is->types[tab->pos_type]; for (p = tab->data; p; p = p->next) { + int fummy; +/* +if (p->num_records == 0) + fummy = 1/0; +*/ + if (p->state < IS_MBSTATE_DIRTY) + continue; /* make sure that blocks are allocated. */ if (p->diskpos < 0) p->diskpos = is_freestore_alloc(tab->is, tab->pos_type); @@ -166,6 +178,8 @@ void is_p_sync(is_mtable *tab) else p->nextpos = p->next->diskpos; } + else + p->nextpos = 0; sum = 0; memcpy(type->dbuf, &p->num_records, sizeof(p->num_records)); sum += sizeof(p->num_records); @@ -189,6 +203,7 @@ void is_p_sync(is_mtable *tab) log(LOG_FATAL, "Failed to write block."); exit(1); } + log(LOG_DEBUG, "W: Block #%d contains %d records.", p->diskpos, p->num_records); } } @@ -212,6 +227,8 @@ static is_mbuf *mbuf_takehead(is_mbuf **mb, int *num, int keysize) is_mbuf *p = 0, **pp = &p, *new; int toget = *num; + if (!toget) + return 0; while (*mb && toget >= (*mb)->num) { toget -= (*mb)->num; @@ -246,14 +263,33 @@ static is_mbuf *mbuf_takehead(is_mbuf **mb, int *num, int keysize) */ void is_p_align(is_mtable *tab) { - is_mblock *mblock, *new; + is_mblock *mblock, *new, *last = 0, *next; is_mbuf *mbufs, *mbp; int blocks, recsblock; log(LOG_DEBUG, "Realigning table."); - for (mblock = tab->data; mblock; mblock = mblock->next) + for (mblock = tab->data; mblock; mblock = next) { - if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records > + next = mblock->next; + if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records == 0) + { + if (last) + { + last->next = mblock->next; + last->state = IS_MBSTATE_DIRTY; + next = mblock->next; + } + else + { + tab->data = tab->data->next; + tab->data->state = IS_MBSTATE_DIRTY; + next = tab->data; + } + if (mblock->diskpos >= 0) + is_freestore_free(tab->is, tab->pos_type, mblock->diskpos); + xrelease_mblock(mblock); + } + else if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records > (mblock == tab->data ? tab->is->types[tab->pos_type].max_keys_block0 : tab->is->types[tab->pos_type].max_keys_block)) @@ -268,18 +304,25 @@ void is_p_align(is_mtable *tab) recsblock = 1; mbufs = mblock->data; while ((mbp = mbuf_takehead(&mbufs, &recsblock, - is_keysize(tab->is)))) + is_keysize(tab->is))) && recsblock) { - new = xmalloc_mblock(); - new->diskpos = -1; - new->state = IS_MBSTATE_DIRTY; - new->next = mblock->next; - mblock->next = new; + if (mbufs) + { + new = xmalloc_mblock(); + new->diskpos = -1; + new->state = IS_MBSTATE_DIRTY; + new->next = mblock->next; + mblock->next = new; + } mblock->data = mbp; mblock->num_records = recsblock; + last = mblock; mblock = mblock->next; } + next = mblock; } + else + last = mblock; } } @@ -300,6 +343,11 @@ void is_p_remap(is_mtable *tab) bufpp = &mbufs; for (blockp = tab->data; blockp; blockp = blockp->next) { + if (blockp->state < IS_MBSTATE_CLEAN && is_m_read_full(tab, blockp) < 0) + { + log(LOG_FATAL, "Read-full failed in remap."); + exit(1); + } *bufpp = blockp->data; while (*bufpp) bufpp = &(*bufpp)->next; @@ -308,11 +356,14 @@ void is_p_remap(is_mtable *tab) blocks = tab->num_records / tab->is->types[tab->pos_type].nice_keys_block; if (tab->num_records % tab->is->types[tab->pos_type].nice_keys_block) blocks++; - recsblock = tab->num_records / blocks; - if (recsblock < 1) - recsblock = 1; + if (blocks == 0) + blocks = 1; + recsblock = tab->num_records / blocks + 1; + if (recsblock > tab->is->types[tab->pos_type].nice_keys_block) + recsblock--; blockpp = &tab->data; - while ((mbp = mbuf_takehead(&mbufs, &recsblock, is_keysize(tab->is)))) + while ((mbp = mbuf_takehead(&mbufs, &recsblock, is_keysize(tab->is))) && + recsblock) { if (!*blockpp) { @@ -324,4 +375,14 @@ void is_p_remap(is_mtable *tab) (*blockpp)->state = IS_MBSTATE_DIRTY; blockpp = &(*blockpp)->next; } + if (mbp) + xfree_mbufs(mbp); + if (*blockpp) + { + for (blockp = *blockpp; blockp; blockp = blockp->next) + if (blockp->diskpos >= 0) + is_freestore_free(tab->is, tab->pos_type, blockp->diskpos); + xfree_mblocks(*blockpp); + *blockpp = 0; + } } -- 1.7.10.4 From 260110f86881af35eecd7fe3ac9dfdda5615a365 Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Wed, 28 Sep 1994 11:29:28 +0000 Subject: [PATCH 10/16] Added cmp parameter. --- include/isam.h | 8 ++++++-- isam/isam.c | 10 +++++++--- isam/physical.c | 10 ++++------ 3 files changed, 17 insertions(+), 11 deletions(-) diff --git a/include/isam.h b/include/isam.h index 3b694bd..5dcf571 100644 --- a/include/isam.h +++ b/include/isam.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.h,v $ - * Revision 1.5 1994-09-27 20:03:36 quinn + * Revision 1.6 1994-09-28 11:29:28 quinn + * Added cmp parameter. + * + * Revision 1.5 1994/09/27 20:03:36 quinn * Seems relatively bug-free. * * Revision 1.4 1994/09/26 17:05:54 quinn @@ -85,7 +88,8 @@ typedef struct ispt_struct /* * Open isam file. */ -ISAM is_open(const char *name, int writeflag); +ISAM is_open(const char *name, int (*cmp)(const void *p1, const void *p2), + int writeflag); /* * Close isam file. diff --git a/isam/isam.c b/isam/isam.c index 3ae755c..0d37142 100644 --- a/isam/isam.c +++ b/isam/isam.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.c,v $ - * Revision 1.5 1994-09-27 20:03:50 quinn + * Revision 1.6 1994-09-28 11:29:33 quinn + * Added cmp parameter. + * + * Revision 1.5 1994/09/27 20:03:50 quinn * Seems relatively bug-free. * * Revision 1.4 1994/09/26 17:11:29 quinn @@ -56,7 +59,8 @@ static int splitargs(const char *s, char *bf[], int max) * Open isam file. * Process resources. */ -ISAM is_open(const char *name, int writeflag) +ISAM is_open(const char *name, int (*cmp)(const void *p1, const void *p2), + int writeflag) { ISAM new; char *nm, *r, *pp[IS_MAX_BLOCKTYPES+1], m[2]; @@ -217,7 +221,7 @@ ISAM is_open(const char *name, int writeflag) new->types[i].nice_keys_block = 1; } - new->cmp = is_default_cmp; + new->cmp = cmp ? cmp : is_default_cmp; return new; } diff --git a/isam/physical.c b/isam/physical.c index ae1f584..312d3e2 100644 --- a/isam/physical.c +++ b/isam/physical.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: physical.c,v $ - * Revision 1.4 1994-09-27 20:03:53 quinn + * Revision 1.5 1994-09-28 11:29:33 quinn + * Added cmp parameter. + * + * Revision 1.4 1994/09/27 20:03:53 quinn * Seems relatively bug-free. * * Revision 1.3 1994/09/26 17:11:31 quinn @@ -160,11 +163,6 @@ void is_p_sync(is_mtable *tab) type = &tab->is->types[tab->pos_type]; for (p = tab->data; p; p = p->next) { - int fummy; -/* -if (p->num_records == 0) - fummy = 1/0; -*/ if (p->state < IS_MBSTATE_DIRTY) continue; /* make sure that blocks are allocated. */ -- 1.7.10.4 From b9087a03bcec441e67c314db88d87e0b0596b850 Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Wed, 28 Sep 1994 11:56:13 +0000 Subject: [PATCH 11/16] Removed const from input to is_merge --- include/isam.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) diff --git a/include/isam.h b/include/isam.h index 5dcf571..2ad05ee 100644 --- a/include/isam.h +++ b/include/isam.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.h,v $ - * Revision 1.6 1994-09-28 11:29:28 quinn + * Revision 1.7 1994-09-28 11:56:13 quinn + * Removed const from input to is_merge + * + * Revision 1.6 1994/09/28 11:29:28 quinn * Added cmp parameter. * * Revision 1.5 1994/09/27 20:03:36 quinn @@ -114,6 +117,6 @@ int is_readkey(ISPT ip, void *buf); int is_writekey(ISPT ip, const void *buf); -ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data); +ISAM_P is_merge(ISAM is, ISAM_P pos, int num, char *data); #endif -- 1.7.10.4 From 0e643dd5ce707178394c0e9d82ec2eeb80f330ec Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Wed, 28 Sep 1994 11:56:25 +0000 Subject: [PATCH 12/16] Added sort of input to is_merge --- isam/isam.c | 20 ++++++++++++++++++-- 1 file changed, 18 insertions(+), 2 deletions(-) diff --git a/isam/isam.c b/isam/isam.c index 0d37142..c84e42e 100644 --- a/isam/isam.c +++ b/isam/isam.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.c,v $ - * Revision 1.6 1994-09-28 11:29:33 quinn + * Revision 1.7 1994-09-28 11:56:25 quinn + * Added sort of input to is_merge + * + * Revision 1.6 1994/09/28 11:29:33 quinn * Added cmp parameter. * * Revision 1.5 1994/09/27 20:03:50 quinn @@ -33,6 +36,8 @@ #include "rootblk.h" #include "keyops.h" +static int (*extcmp)(const void *p1, const void *p2); + static int splitargs(const char *s, char *bf[], int max) { int ct = 0; @@ -266,7 +271,16 @@ static ISAM_P is_address(int type, int pos) return r; } -ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data) +int sort_input(const void *p1, const void *p2) +{ + int rs; + + if ((rs = (*extcmp)(((char *)p1) + 1, ((char *)p2) + 1))) + return rs; + return *((char *)p1) - *((char*)p2); +} + +ISAM_P is_merge(ISAM is, ISAM_P pos, int num, char *data) { is_mtable tab; int res; @@ -274,6 +288,8 @@ ISAM_P is_merge(ISAM is, ISAM_P pos, int num, const char *data) int oldnum, oldtype, i; char operation, *record; + extcmp = is->cmp; + qsort(data, num, is_keysize(is) + 1, sort_input); is_m_establish_tab(is, &tab, pos); /* TODO: do something to aquire oldnum at this point */ if (pos) -- 1.7.10.4 From c2bc863fadfe038670d50483df9a3e80562108a5 Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Wed, 28 Sep 1994 12:32:17 +0000 Subject: [PATCH 13/16] Trivial --- isam/isam.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/isam/isam.c b/isam/isam.c index c84e42e..7fee014 100644 --- a/isam/isam.c +++ b/isam/isam.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.c,v $ - * Revision 1.7 1994-09-28 11:56:25 quinn + * Revision 1.8 1994-09-28 12:32:17 quinn + * Trivial + * + * Revision 1.7 1994/09/28 11:56:25 quinn * Added sort of input to is_merge * * Revision 1.6 1994/09/28 11:29:33 quinn @@ -291,7 +294,6 @@ ISAM_P is_merge(ISAM is, ISAM_P pos, int num, char *data) extcmp = is->cmp; qsort(data, num, is_keysize(is) + 1, sort_input); is_m_establish_tab(is, &tab, pos); - /* TODO: do something to aquire oldnum at this point */ if (pos) if (is_m_read_full(&tab, tab.data) < 0) { -- 1.7.10.4 From 5b403723fdd074e1b510aa4fbe1e2685fda156e3 Mon Sep 17 00:00:00 2001 From: Sebastian Hammer Date: Wed, 28 Sep 1994 12:56:09 +0000 Subject: [PATCH 14/16] Added access functions (ISPT) --- include/isam.h | 7 +++++-- isam/isam.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 51 insertions(+), 5 deletions(-) diff --git a/include/isam.h b/include/isam.h index 2ad05ee..4febc17 100644 --- a/include/isam.h +++ b/include/isam.h @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.h,v $ - * Revision 1.7 1994-09-28 11:56:13 quinn + * Revision 1.8 1994-09-28 12:56:09 quinn + * Added access functions (ISPT) + * + * Revision 1.7 1994/09/28 11:56:13 quinn * Removed const from input to is_merge * * Revision 1.6 1994/09/28 11:29:28 quinn @@ -74,7 +77,7 @@ typedef struct isam_struct typedef struct ispt_struct { - struct is_mtable *tab; + struct is_mtable tab; struct ispt_struct *next; /* freelist */ } ispt_struct, *ISPT; diff --git a/isam/isam.c b/isam/isam.c index 7fee014..98a1f01 100644 --- a/isam/isam.c +++ b/isam/isam.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: isam.c,v $ - * Revision 1.8 1994-09-28 12:32:17 quinn + * Revision 1.9 1994-09-28 12:56:15 quinn + * Added access functions (ISPT) + * + * Revision 1.8 1994/09/28 12:32:17 quinn * Trivial * * Revision 1.7 1994/09/28 11:56:25 quinn @@ -40,6 +43,27 @@ #include "keyops.h" static int (*extcmp)(const void *p1, const void *p2); +static ispt_struct *ispt_freelist = 0; + +static ISPT ispt_alloc() +{ + ISPT p; + + if (ispt_freelist) + { + p = ispt_freelist; + ispt_freelist = ispt_freelist->next; + } + else + p = xmalloc(sizeof(ispt_struct)); + return p; +} + +static void ispt_free(ISPT pt) +{ + pt->next = ispt_freelist; + ispt_freelist = pt; +} static int splitargs(const char *s, char *bf[], int max) { @@ -389,9 +413,28 @@ ISAM_P is_merge(ISAM is, ISAM_P pos, int num, char *data) * Locate a table of keys in an isam file. The ISPT is an individual * position marker for that table. */ -ISPT is_position(ISAM is, ISAM_P pos); +ISPT is_position(ISAM is, ISAM_P pos) +{ + ispt_struct *p; + + p = ispt_alloc(); + is_m_establish_tab(is, &p->tab, pos); + return p; +} /* * Release ISPT. */ -void is_pt_free(ISPT ip); +void is_pt_free(ISPT ip) +{ + is_m_release_tab(&ip->tab); + ispt_free(ip); +} + +/* + * Read a key from a table. + */ +int is_readkey(ISPT ip, void *buf) +{ + return is_m_read_record(&ip->tab, buf); +} -- 1.7.10.4 From 4cffe59757ef27b3764029c39415a13a2756e0a1 Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Wed, 28 Sep 1994 13:06:52 +0000 Subject: [PATCH 15/16] Minor changes. --- Makefile | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/Makefile b/Makefile index 74d5e56..4f31650 100644 --- a/Makefile +++ b/Makefile @@ -1,11 +1,11 @@ # Copyright (C) 1994, Index Data I/S # All rights reserved. # Sebastian Hammer, Adam Dickmeiss -# $Id: Makefile,v 1.16 1994-09-26 16:10:27 quinn Exp $ +# $Id: Makefile,v 1.17 1994-09-28 13:06:52 adam Exp $ SHELL=/bin/sh MAKE=make -SUBDIR=util bfile dfa dict isam +SUBDIR=util bfile dfa dict isam it all: for i in $(SUBDIR); do cd $$i; if $(MAKE); then cd ..; else exit 1; fi; done -- 1.7.10.4 From 60603b577514c9e6559d37e11b4ce3aa26e51be3 Mon Sep 17 00:00:00 2001 From: Adam Dickmeiss Date: Wed, 28 Sep 1994 13:07:08 +0000 Subject: [PATCH 16/16] Use log_mask_str now. --- dict/dictext.c | 7 +++++-- dict/dicttest.c | 7 +++++-- 2 files changed, 10 insertions(+), 4 deletions(-) diff --git a/dict/dictext.c b/dict/dictext.c index cec1845..cb8f41e 100644 --- a/dict/dictext.c +++ b/dict/dictext.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: dictext.c,v $ - * Revision 1.1 1994-09-16 15:39:11 adam + * Revision 1.2 1994-09-28 13:07:08 adam + * Use log_mask_str now. + * + * Revision 1.1 1994/09/16 15:39:11 adam * Initial code of lookup - not tested yet. * */ @@ -42,7 +45,7 @@ int main (int argc, char **argv) } else if (ret == 'v') { - log_init (atoi(arg), prog, NULL); + log_init (log_mask_str(arg), prog, NULL); } else if (ret == 'h') { diff --git a/dict/dicttest.c b/dict/dicttest.c index 6b6ff00..c461b84 100644 --- a/dict/dicttest.c +++ b/dict/dicttest.c @@ -4,7 +4,10 @@ * Sebastian Hammer, Adam Dickmeiss * * $Log: dicttest.c,v $ - * Revision 1.10 1994-09-26 10:17:24 adam + * Revision 1.11 1994-09-28 13:07:09 adam + * Use log_mask_str now. + * + * Revision 1.10 1994/09/26 10:17:24 adam * Minor changes. * * Revision 1.9 1994/09/22 14:43:56 adam @@ -124,7 +127,7 @@ int main (int argc, char **argv) } else if (ret == 'v') { - log_init (atoi(arg), prog, NULL); + log_init (log_mask_str(arg), prog, NULL); } else { -- 1.7.10.4