Xref: utzoo comp.databases:1696 comp.lang.c:14629 Path: utzoo!attcan!uunet!steinmetz!davidsen From: davidsen@steinmetz.ge.com (William E. Davidsen Jr) Newsgroups: comp.databases,comp.lang.c Subject: Re: C DATABASE (source!) Keywords: dbm btree Message-ID: <12772@steinmetz.ge.com> Date: 9 Dec 88 16:36:36 GMT References: <161@lakesys.UUCP> Reply-To: davidsen@crdos1.UUCP (bill davidsen) Organization: General Electric CRD, Schenectady, NY Lines: 1588 In article <161@lakesys.UUCP> jamesd@lakesys.UUCP (James Dicke) writes: | Since there were so many requests sent to me about B-TREE databases | wanted after I had made the request myself - I will post the only | one I received which was written for MS C 5.0 so it need a few | changes to work under XENIX. It took quite a few to get it running under Xenix, and a few more for SunOS and Ultrix. Here are the patches I used, two routines which didn't work correctly in Xenix, and several test programs with a makefile. The utest3 program builds a case insensitive index for the last word on a line, while utest4 looks it up. If the input file has the result of find, you can have a easy was to look up the location of any file, case free. I hope that will be useful. #!/bin/sh # shar: Shell Archiver (v1.24) # # Run the following text with /bin/sh to create: # bplus.diff # filelen.c # memmove.c # utest.c # utest1.c # utest2.c # utest3.c # utest4.c # makefile # echo "x - extracting bplus.diff (Text)" sed 's/^X//' << 'SHAR_EOF' > bplus.diff && X*** bplus.h.orig X--- bplus.h X************** X*** 2,7 X /* bplus.h - data structures and constants */ X X X #define IX_OK 1 X #define IX_FAIL 0 X #define EOIX (-2) X--- 2,31 ----- X /* bplus.h - data structures and constants */ X X X+ /* the next two lines delete the 'pascal' and 'cdecl' keywords X+ to make the source compile on an ANSI compiler. X+ */ X+ #ifndef MSC /* not Microsoft C */ X+ #define cdecl X+ #define pascal X+ #endif /* MSC */ X+ X+ /* the following checks are to define things frequently not in X+ UNIX compilers, since they are recent ANSI additions. X+ */ X+ #ifndef SEEK_SET X+ #define SEEK_SET 0 X+ #endif X+ #ifndef O_BINARY X+ #define O_BINARY 0 X+ #endif X+ X+ #if defined(ANSI_C) | defined(MSC) | defined(M_XENIX) X+ #define Param(x) x X+ #else X+ #define Param(x) () X+ #endif /* ANSI or PCC style decls */ X+ X #define IX_OK 1 X #define IX_FAIL 0 X #define EOIX (-2) X************** X*** 55,71 X IX_DISK dx; X } IX_DESC; X X! int cdecl open_index(char *,IX_DESC *, int); X! int cdecl close_index(IX_DESC *); X! int cdecl make_index(char *,IX_DESC *, int); X! int cdecl first_key(IX_DESC *); X! int cdecl last_key(IX_DESC *); X! int cdecl next_key(ENTRY *, IX_DESC *); X! int cdecl prev_key(ENTRY *, IX_DESC *); X! int cdecl find_key(ENTRY *, IX_DESC *); X! int cdecl add_key(ENTRY *, IX_DESC *); X! int cdecl locate_key(ENTRY *, IX_DESC *); X! int cdecl delete_key(ENTRY *, IX_DESC *); X! int cdecl find_exact(ENTRY *, IX_DESC *); X X \032 X--- 79,89 ----- X IX_DISK dx; X } IX_DESC; X X! /* a few system procedure types here */ X! extern long filelength(), lseek(), tell(); X! extern char *mktemp(); X! extern int read(), write(), open(), close(); X! extern void exit(), memcpy(); X X /* ================ external interface ================ */ X int cdecl open_index Param((char *,IX_DESC *, int)); X************** X*** 68,71 X int cdecl delete_key(ENTRY *, IX_DESC *); X int cdecl find_exact(ENTRY *, IX_DESC *); X X! \032 X--- 85,100 ----- X extern int read(), write(), open(), close(); X extern void exit(), memcpy(); X X! /* ================ external interface ================ */ X! int cdecl open_index Param((char *,IX_DESC *, int)); X! int cdecl close_index Param((IX_DESC *)); X! int cdecl make_index Param((char *,IX_DESC *, int)); X! int cdecl first_key Param((IX_DESC *)); X! int cdecl last_key Param((IX_DESC *)); X! int cdecl next_key Param((ENTRY *, IX_DESC *)); X! int cdecl prev_key Param((ENTRY *, IX_DESC *)); X! int cdecl find_key Param((ENTRY *, IX_DESC *)); X! int cdecl add_key Param((ENTRY *, IX_DESC *)); X! int cdecl locate_key Param((ENTRY *, IX_DESC *)); X! int cdecl delete_key Param((ENTRY *, IX_DESC *)); X! int cdecl find_exact Param((ENTRY *, IX_DESC *)); X*** bplus.c.orig X--- bplus.c X************** X*** 17,22 X X #include X #include X #include X #include /* delete this line for Turbo C */ X #include X--- 17,23 ----- X X #include X #include X+ #ifdef MSC X #include X #endif X #include /* delete this line for Turbo C */ X************** X*** 18,25 X #include X #include X #include X! #include /* delete this line for Turbo C */ X! #include X #include X #include "bplus.h" X X--- 19,27 ----- X #include X #ifdef MSC X #include X! #endif X! #include /* delete this line for Turbo C */ X! #include X #include X #include "bplus.h" X X************** X*** 46,52 X /* must be used for Microsoft 5.0 */ X /* and the Quick C compiler. */ X X! /* #define memcpy memmove */ X X /* declare some global variables */ X X--- 48,56 ----- X /* must be used for Microsoft 5.0 */ X /* and the Quick C compiler. */ X X! #if 1 X! #define memcpy memmove X! #endif /* if not needed */ X X /* declare some global variables */ X X************** X*** 60,97 X int split_size = IXB_SPACE; X int comb_size = (IXB_SPACE/2); X X! void pascal error(int, long); X! void pascal read_if(long, char *, int); X! void pascal write_if(int, long, char *, int); X! int pascal creat_if(char *); X! int pascal open_if(char *); X! void pascal close_if(int); X! void pascal update_block(void); X! void pascal init_cache(void); X! int pascal find_cache(RECPOS); X! int pascal new_cache(void); X! void pascal load_cache(RECPOS); X! void pascal get_cache(RECPOS); X! void pascal retrieve_block(int, RECPOS); X! int pascal prev_entry(int); X! int pascal next_entry(int); X! int pascal copy_entry(ENTRY *, ENTRY *); X! int pascal scan_blk(int); X! int pascal last_entry(void); X! int pascal write_free( RECPOS, BLOCK *); X! RECPOS pascal get_free(void); X! int pascal find_block(ENTRY *, int *); X! void pascal movedown(BLOCK *, int, int); X! void pascal moveup(BLOCK *, int, int); X! void pascal ins_block(BLOCK *, ENTRY *, int); X! void pascal del_block(BLOCK *, int); X! int pascal split(int, ENTRY *, ENTRY *); X! void pascal ins_level(int, ENTRY *); X! int pascal insert_ix(ENTRY *, IX_DESC *); X! int pascal find_ix(ENTRY *, IX_DESC *, int); X! int pascal combineblk(RECPOS, int); X! void pascal replace_entry(ENTRY *); X! void print_blk(BLOCK *); X X X /* file I/O for B-PLUS module */ X--- 64,102 ----- X int split_size = IXB_SPACE; X int comb_size = (IXB_SPACE/2); X X! /* ================ internal procedures ================ */ X! static void pascal error Param((int, long)); X! static void pascal read_if Param((RECPOS, char *, int)); X! static void pascal write_if Param((int, RECPOS, char *, int)); X! static int pascal creat_if Param((char *)); X! static int pascal open_if Param((char *)); X! static void pascal close_if Param((int)); X! static void pascal update_block Param((void)); X! static void pascal init_cache Param((void)); X! static int pascal find_cache Param((RECPOS)); X! static int pascal new_cache Param((void)); X! static void pascal load_cache Param((RECPOS)); X! static void pascal get_cache Param((RECPOS)); X! static void pascal retrieve_block Param((int, RECPOS)); X! static int pascal prev_entry Param((int)); X! static int pascal next_entry Param((int)); X! static void pascal copy_entry Param((ENTRY *, ENTRY *)); X! static int pascal scan_blk Param((int)); X! static int pascal last_entry Param((void)); X! static void pascal write_free Param(( RECPOS, BLOCK *)); X! static RECPOS pascal get_free Param((void)); X! static int pascal find_block Param((ENTRY *, int *)); X! static void pascal movedown Param((BLOCK *, int, int)); X! static void pascal moveup Param((BLOCK *, int, int)); X! static void pascal ins_block Param((BLOCK *, ENTRY *, int)); X! static void pascal del_block Param((BLOCK *, int)); X! static void pascal split Param((int, ENTRY *, ENTRY *)); X! static void pascal ins_level Param((int, ENTRY *)); X! static int pascal insert_ix Param((ENTRY *, IX_DESC *)); X! static int pascal find_ix Param((ENTRY *, IX_DESC *, int)); X! static int pascal combineblk Param((RECPOS, int)); X! static void pascal replace_entry Param((ENTRY *)); X! static void print_blk Param((BLOCK *)); X X X /* file I/O for B-PLUS module */ X************** X*** 96,102 X X /* file I/O for B-PLUS module */ X X! void pascal error(j, l) X int j; X long l; X { X--- 101,108 ----- X X /* file I/O for B-PLUS module */ X X! static void pascal X! error(j, l) X int j; X long l; X { X************** X*** 103,109 X static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE", X "ERROR WHILE READING FILE", X "ERROR WHILE WRITING FILE"}; X! printf("\n %s - Record Number %ld\n", msg[j], l); X exit(1); X } /* error */ X X--- 109,115 ----- X static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE", X "ERROR WHILE READING FILE", X "ERROR WHILE WRITING FILE"}; X! (void) printf("\n %s - Record Number %ld\n", msg[j], l); X exit(1); X } /* error */ X X************** X*** 108,115 X } /* error */ X X X! void pascal read_if(start, buf, nwrt) X! long start; X char *buf; X int nwrt; X { X--- 114,122 ----- X } /* error */ X X X! static void pascal X! read_if(start, buf, nwrt) X! RECPOS start; X char *buf; X int nwrt; X { X************** X*** 120,126 X } /* read_if */ X X X! void pascal write_if(handle, start, buf, nwrt) X int handle; X long start; X char *buf; X--- 127,134 ----- X } /* read_if */ X X X! static void pascal X! write_if(handle, start, buf, nwrt) X int handle; X RECPOS start; X char *buf; X************** X*** 122,128 X X void pascal write_if(handle, start, buf, nwrt) X int handle; X! long start; X char *buf; X int nwrt; X { X--- 130,136 ----- X static void pascal X write_if(handle, start, buf, nwrt) X int handle; X! RECPOS start; X char *buf; X int nwrt; X { X************** X*** 133,139 X } /* write_if */ X X X! int pascal creat_if(fn) X char *fn; X { X int ret; X--- 141,148 ----- X } /* write_if */ X X X! static int pascal X! creat_if(fn) X char *fn; X { X int ret; X************** X*** 137,143 X char *fn; X { X int ret; X! ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE); X if (ret < 0) error(0,0L); X return (ret); X } /* creat_if */ X--- 146,152 ----- X char *fn; X { X int ret; X! ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IREAD|S_IWRITE); X if (ret < 0) error(0,0L); X return (ret); X } /* creat_if */ X************** X*** 143,149 X } /* creat_if */ X X X! int pascal open_if(fn) X char *fn; X { X int ret; X--- 152,159 ----- X } /* creat_if */ X X X! static int pascal X! open_if(fn) X char *fn; X { X int ret; X************** X*** 153,159 X } /* open_if */ X X X! void pascal close_if(handle) X int handle; X { X if(close(handle) < 0) error(2,0L); X--- 163,170 ----- X } /* open_if */ X X X! static void pascal X! close_if(handle) X int handle; X { X if(close(handle) < 0) error(2,0L); X************** X*** 160,166 X } /* close_if */ X X X! int cdecl open_index(name, pix, dup) X char *name; X IX_DESC *pix; X int dup; X--- 171,178 ----- X } /* close_if */ X X X! int cdecl X! open_index(name, pix, dup) X char *name; X IX_DESC *pix; X int dup; X************** X*** 179,185 X } /* open_index */ X X X! int cdecl close_index(pix) X IX_DESC *pix; X { X int i; X--- 191,198 ----- X } /* open_index */ X X X! int cdecl X! close_index(pix) X IX_DESC *pix; X { X int i; X************** X*** 193,199 X write_if(BUFHANDLE(i), X BUFBLOCK(i).brec, X (char *) &BUFBLOCK(i), X! sizeof(BLOCK)); X BUFDIRTY(i) = 0; X } X BUFBLOCK(i).brec = NULLREC; X--- 206,212 ----- X write_if(BUFHANDLE(i), X BUFBLOCK(i).brec, X (char *) &BUFBLOCK(i), X! (int) sizeof(BLOCK)); X BUFDIRTY(i) = 0; X } X BUFBLOCK(i).brec = NULLREC; X************** X*** 203,209 X } /* close_index */ X X X! int cdecl make_index(name, pix, dup) X char *name; X IX_DESC *pix; X int dup; X--- 216,223 ----- X } /* close_index */ X X X! int cdecl X! make_index(name, pix, dup) X char *name; X IX_DESC *pix; X int dup; X************** X*** 233,239 X X /* cache I/O for BPLUS */ X X! void pascal update_block() X { X if (block_ptr != &(pci->root)) X BUFDIRTY(cache_ptr) = 1; X--- 247,254 ----- X X /* cache I/O for BPLUS */ X X! static void pascal X! update_block() X { X if (block_ptr != &(pci->root)) X BUFDIRTY(cache_ptr) = 1; X************** X*** 240,246 X } /* update_block */ X X X! void pascal init_cache() X { X register int j; X for (j = 0; j < NUM_BUFS; j++) X--- 255,262 ----- X } /* update_block */ X X X! static void pascal X! init_cache() X { X register int j; X for (j = 0; j < NUM_BUFS; j++) X************** X*** 251,257 X } /* init_cache */ X X X! int pascal find_cache(r) X RECPOS r; X { X register int j; X--- 267,274 ----- X } /* init_cache */ X X X! static int pascal X! find_cache(r) X RECPOS r; X { X register int j; X************** X*** 265,271 X } /* find_cache */ X X X! int pascal new_cache() X { X register int i; X i = (cache_ptr + 1) % NUM_BUFS; X--- 282,289 ----- X } /* find_cache */ X X X! static int pascal X! new_cache() X { X register int i; X i = (cache_ptr + 1) % NUM_BUFS; X************** X*** 279,285 X } /* new_cache */ X X X! void pascal load_cache(r) X RECPOS r; X { X cache_ptr = new_cache(); X--- 297,304 ----- X } /* new_cache */ X X X! static void pascal X! load_cache(r) X RECPOS r; X { X cache_ptr = new_cache(); X************** X*** 287,293 X } /* load_cache */ X X X! void pascal get_cache(r) X RECPOS r; X { X if (find_cache(r) < 0) X--- 306,313 ----- X } /* load_cache */ X X X! static void pascal X! get_cache(r) X RECPOS r; X { X if (find_cache(r) < 0) X************** X*** 296,302 X } /* get_cache */ X X X! void pascal retrieve_block(j, r) X int j; X RECPOS r; X { X--- 316,323 ----- X } /* get_cache */ X X X! static void pascal X! retrieve_block(j, r) X int j; X RECPOS r; X { X************** X*** 309,315 X X /* low level functions of BPLUS */ X X! int pascal prev_entry(off) X int off; X { X if (off <= 0) X--- 330,337 ----- X X /* low level functions of BPLUS */ X X! static int pascal X! prev_entry(off) X int off; X { X if (off <= 0) X************** X*** 323,329 X } /* prev_entry */ X X X! int pascal next_entry(off) X int off; X { X if (off == -1) X--- 345,352 ----- X } /* prev_entry */ X X X! static int pascal X! next_entry(off) X int off; X { X if (off == -1) X************** X*** 338,344 X } /* next_entry */ X X X! int pascal copy_entry(to, from) X ENTRY *to; X ENTRY *from; X { X--- 361,368 ----- X } /* next_entry */ X X X! static void pascal X! copy_entry(to, from) X ENTRY *to; X ENTRY *from; X { X************** X*** 344,350 X { X int me; X me = ENT_SIZE(from); X! memcpy(to, from, me); X } /* copy_entry */ X X X--- 368,374 ----- X { X int me; X me = ENT_SIZE(from); X! (void) memcpy(to, from, me); X } /* copy_entry */ X X X************** X*** 348,354 X } /* copy_entry */ X X X! int pascal scan_blk(n) X int n; X { X register int off, last; X--- 372,379 ----- X } /* copy_entry */ X X X! static int pascal X! scan_blk(n) X int n; X { X register int off, last; X************** X*** 363,369 X } /* scan_blk */ X X X! int pascal last_entry() X { X return( scan_blk(block_ptr->bend) ); X } /* last_entry */ X--- 388,395 ----- X } /* scan_blk */ X X X! static int pascal X! last_entry() X { X return( scan_blk(block_ptr->bend) ); X } /* last_entry */ X************** X*** 371,377 X X /* maintain list of free index blocks */ X X! int pascal write_free(r, pb) X RECPOS r; X BLOCK *pb; X { X--- 397,404 ----- X X /* maintain list of free index blocks */ X X! static void pascal X! write_free(r, pb) X RECPOS r; X BLOCK *pb; X { X************** X*** 377,383 X { X pb->p0 = FREE_BLOCK; X pb->brec = pci->dx.ff; X! write_if(pci->ixfile, r, (char *) pb, sizeof(BLOCK)); X pci->dx.ff = r; X } /* write_free */ X X--- 404,410 ----- X { X pb->p0 = FREE_BLOCK; X pb->brec = pci->dx.ff; X! write_if(pci->ixfile, r, (char *) (char *) pb, sizeof(BLOCK)); X pci->dx.ff = r; X } /* write_free */ X X************** X*** 382,388 X } /* write_free */ X X X! RECPOS pascal get_free() X { X RECPOS r, rt; X X--- 409,416 ----- X } /* write_free */ X X X! static RECPOS pascal X! get_free() X { X RECPOS r, rt; X X************** X*** 388,394 X X r = pci->dx.ff; X if ( r != NULLREC ) X! { read_if(r, (char *)&rt, sizeof( RECPOS )); X pci->dx.ff = rt; X } X else X--- 416,422 ----- X X r = pci->dx.ff; X if ( r != NULLREC ) X! { read_if(r, (char *)&rt, (int) sizeof( RECPOS )); X pci->dx.ff = rt; X } X else X************** X*** 399,405 X X /* general BPLUS block level functions */ X X! int pascal find_block(pe, poff) X ENTRY *pe; X int *poff; X { X--- 427,434 ----- X X /* general BPLUS block level functions */ X X! static int pascal X! find_block(pe, poff) X ENTRY *pe; X int *poff; X { X************** X*** 425,431 X } /* find_block */ X X X! void pascal movedown(pb, off, n) X BLOCK *pb; X int off; X int n; X--- 454,461 ----- X } /* find_block */ X X X! static void pascal X! movedown(pb, off, n) X BLOCK *pb; X int off; X int n; X************** X*** 436,442 X } /* movedown */ X X X! void pascal moveup(pb, off, n) X BLOCK *pb; X int off; X int n; X--- 466,473 ----- X } /* movedown */ X X X! static void pascal X! moveup(pb, off, n) X BLOCK *pb; X int off; X int n; X************** X*** 447,453 X } /* moveup */ X X X! void pascal ins_block(pb, pe, off) X BLOCK *pb; X ENTRY *pe; X int off; X--- 478,485 ----- X } /* moveup */ X X X! static void pascal X! ins_block(pb, pe, off) X BLOCK *pb; X ENTRY *pe; X int off; X************** X*** 460,466 X } /* ins_block */ X X X! void pascal del_block(pb, off) X BLOCK *pb; X int off; X { X--- 492,499 ----- X } /* ins_block */ X X X! static void pascal X! del_block(pb, off) X BLOCK *pb; X int off; X { X************** X*** 473,479 X X /* position at start/end of index */ X X! int cdecl first_key(pix) X IX_DESC *pix; X { X pci = pix; X--- 506,513 ----- X X /* position at start/end of index */ X X! int cdecl X! first_key(pix) X IX_DESC *pix; X { X pci = pix; X************** X*** 490,496 X } /* first_key */ X X X! int cdecl last_key(pix) X IX_DESC *pix; X { X long ads; X--- 524,531 ----- X } /* first_key */ X X X! int cdecl X! last_key(pix) X IX_DESC *pix; X { X long ads; X************** X*** 510,516 X X /* get next, previous entries */ X X! int cdecl next_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X--- 545,552 ----- X X /* get next, previous entries */ X X! int cdecl X! next_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X************** X*** 544,550 X } /* next_key */ X X X! int cdecl prev_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X--- 580,587 ----- X } /* next_key */ X X X! int cdecl X! prev_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X************** X*** 582,588 X X /* insert new entries into tree */ X X! int pascal split(l, pe, e) X int l; X ENTRY *pe; X ENTRY *e; X--- 619,626 ----- X X /* insert new entries into tree */ X X! static void pascal X! split(l, pe, e) X int l; X ENTRY *pe; X ENTRY *e; X************** X*** 622,628 X } /* split */ X X X! void pascal ins_level(l, e) X int l; X ENTRY *e; X { X--- 660,667 ----- X } /* split */ X X X! static void pascal X! ins_level(l, e) X int l; X ENTRY *e; X { X************** X*** 647,653 X } /* ins_level */ X X X! int pascal insert_ix(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X--- 686,693 ----- X } /* ins_level */ X X X! static int pascal X! insert_ix(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X************** X*** 691,697 X X /* BPLUS find and add key functions */ X X! int pascal find_ix(pe, pix, find) X ENTRY *pe; X IX_DESC *pix; X int find; X--- 731,738 ----- X X /* BPLUS find and add key functions */ X X! static int pascal X! find_ix(pe, pix, find) X ENTRY *pe; X IX_DESC *pix; X int find; X************** X*** 717,723 X } /* find_ix */ X X X! int cdecl find_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X--- 758,765 ----- X } /* find_ix */ X X X! int cdecl X! find_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X************** X*** 728,734 X } /* find_key */ X X X! int cdecl add_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X--- 770,777 ----- X } /* find_key */ X X X! int cdecl X! add_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X************** X*** 740,746 X } /* add_key */ X X X! int cdecl locate_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X--- 783,790 ----- X } /* add_key */ X X X! int cdecl X! locate_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X************** X*** 753,759 X } /* locate_key */ X X X! int cdecl find_exact(pe, pix) X ENTRY *pe; X IX_DESC * pix; X { X--- 797,804 ----- X } /* locate_key */ X X X! int cdecl X! find_exact(pe, pix) X ENTRY *pe; X IX_DESC * pix; X { X************** X*** 778,784 X X /* BPLUS delete key functions */ X X! int cdecl delete_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X--- 823,830 ----- X X /* BPLUS delete key functions */ X X! int cdecl X! delete_key(pe, pix) X ENTRY *pe; X IX_DESC *pix; X { X************** X*** 831,837 X } /* delete_key */ X X X! int pascal combineblk(ads, size) X RECPOS ads; X int size; X { X--- 877,884 ----- X } /* delete_key */ X X X! static int pascal X! combineblk(ads, size) X RECPOS ads; X int size; X { X************** X*** 938,944 X } /* combineblk */ X X X! void pascal replace_entry(pe) X ENTRY *pe; X { X retrieve_block(pci->level, CB(pci->level)); X--- 985,992 ----- X } /* combineblk */ X X X! static void pascal X! replace_entry(pe) X ENTRY *pe; X { X retrieve_block(pci->level, CB(pci->level)); X************** X*** 947,951 X prev_entry(CO(pci->level)); X insert_ix(pe, pci); X } /* replace_entry */ X- X- \032 X--- 995,997 ----- X prev_entry(CO(pci->level)); X insert_ix(pe, pci); X } /* replace_entry */ SHAR_EOF chmod 0644 bplus.diff || echo "restore of bplus.diff fails" echo "x - extracting filelen.c (Text)" sed 's/^X//' << 'SHAR_EOF' > filelen.c && X/***************************************************************** X | filelength - returns the length of a file X ****************************************************************/ X Xlong filelength (fd) X int fd; X{ X#if 0 /* original version */ X long orig, last, lseek(); X X orig = lseek (fd, 0L, 1); /* seek to the current position */ X last = lseek (fd, 0L, 2); /* seek to the end */ X lseek (fd, orig, 0); /* reset the pointer */ X X return last; X#else /* new network version */ X#include X#include X#include X X struct stat sb; X fstat(fd, &sb); X return sb.st_size; X#endif X} SHAR_EOF chmod 0644 filelen.c || echo "restore of filelen.c fails" echo "x - extracting memmove.c (Text)" sed 's/^X//' << 'SHAR_EOF' > memmove.c && X/***************************************************************** X | memmove - move in memory with attention to order and overlap X |---------------------------------------------------------------- X | Arguments: X | 1) destination: char * X | 2) source: char * X | 3) length: int X | Returns: none X ****************************************************************/ X Xvoid memmove (to, from, length) X char *to, *from; X int length; X{ X register char *TO, *FROM; X X if (to < from) { X /* move left to right */ X TO = to; X FROM = from; X while (length--) X *(TO++) = *(FROM++); X } X else { X /* move right to left */ X TO = to + length - 1; X FROM = from + length - 1; X while (length--) X *(TO--) = *(FROM--); X } X} SHAR_EOF chmod 0644 memmove.c || echo "restore of memmove.c fails" echo "x - extracting utest.c (Text)" sed 's/^X//' << 'SHAR_EOF' > utest.c && X/* UNIX test, pipe the output of "find" into this and get a sorted list X The keys are printed in order after the data has been read. X*/ X X#include X#include "bplus.h" X Xmain() { X ENTRY wk, *ep = &wk; X IX_DESC pix, *ixptr = &pix; X char line[80]; X int stat; X X if (make_index("names.idx", ixptr, 0) != IX_OK) { X perror("Make index"); X exit(1); X } X X while (fgets(line, 80, stdin) != NULL) { X line[strlen(line)-1] = 0; X strcpy(wk.key, line); X if ((stat = add_key(ep, ixptr)) != IX_OK) { X printf("Status %d from add_key\n", stat); X exit(0); X } X } X X /* dump the file */ X first_key(ixptr); X while (next_key(ep, ixptr) == IX_OK) { X printf("%s\n", wk.key); X } X close_index(ixptr); X} SHAR_EOF chmod 0644 utest.c || echo "restore of utest.c fails" echo "x - extracting utest1.c (Text)" sed 's/^X//' << 'SHAR_EOF' > utest1.c && X/* UNIX test, pipe the output of "find" into this and get a sorted list X X The key value is the last non-blank data in the input record. This X works well using the output of "ls -l" as input. X X After the index has been built, the keys are read in order, the X record position is used to access the complete data record, and X the data record is displayed. X*/ X X#include X#include "bplus.h" X X#define DUPflag 1 /* allow dups */ X#define LineSize 180 /* input max line */ Xmain(argc, argv) X int argc; X char *argv[]; X{ X ENTRY wk, *ep = &wk; X IX_DESC pix, *ixptr = &pix; X char line[LineSize]; X FILE *infile, *fopen(); X long filepos, ftell(); X int stat, pos, rcount = 0; X X if (argc < 2) { X printf("Missing filename\n"); X exit(1); X } X X if ((infile = fopen(argv[1], "r")) == NULL) { X printf("Can't open input file %s\n", argv[1]); X exit(1); X } X X if (make_index("names.idx", ixptr, DUPflag) != IX_OK) { X perror("Make index"); X exit(1); X } X X while (filepos = ftell(infile), fgets(line, LineSize, infile) != NULL) { X rcount++; X pos = strlen(line) - 1; X line[pos] = 0; X while (pos && line[pos-1] != ' ') pos--; X strcpy(wk.key, &line[pos]); X wk.recptr = filepos; X if ((stat = add_key(ep, ixptr)) != IX_OK) { X printf("Status %d from add_key at record %d\n", stat, rcount); X exit(0); X } X } X X /* dump the file */ X first_key(ixptr); X while (next_key(ep, ixptr) == IX_OK) { X fseek(infile, wk.recptr, 0); X fgets(line, LineSize, infile); X printf("%s", line); X } X X close_index(ixptr); X fclose(infile); X} SHAR_EOF chmod 0644 utest1.c || echo "restore of utest1.c fails" echo "x - extracting utest2.c (Text)" sed 's/^X//' << 'SHAR_EOF' > utest2.c && X/* UNIX test, pipe the output of "find" into this and get a sorted list X X The key value is the last non-blank data in the input record. This X works well using the output of "ls -l" as input. Keys are stored X without regard to case. X X After the index has been built, the keys are read in order, the X record position is used to access the complete data record, and X the data record is displayed. X*/ X X#include X#include X#include "bplus.h" X X#define DUPflag 1 /* allow dups */ X#define LineSize 180 /* input max line */ Xmain(argc, argv) X int argc; X char *argv[]; X{ X ENTRY wk, *ep = &wk; X IX_DESC pix, *ixptr = &pix; X char line[LineSize]; X FILE *infile, *fopen(); X long filepos, ftell(); X int stat, pos, rcount = 0, wkch, wkpos; X X if (argc < 2) { X printf("Missing filename\n"); X exit(1); X } X X if ((infile = fopen(argv[1], "r")) == NULL) { X printf("Can't open input file %s\n", argv[1]); X exit(1); X } X X if (make_index("names.idx", ixptr, DUPflag) != IX_OK) { X perror("Make index"); X exit(1); X } X X while (filepos = ftell(infile), fgets(line, LineSize, infile) != NULL) { X rcount++; X pos = strlen(line) - 1; X line[pos] = 0; X while (pos && line[pos-1] != ' ' && line[pos-1] != '/') pos--; X X /* this forces the sort key into lower case */ X for (wkpos=pos; wkch = line[wkpos]; wkpos++) { X if (isupper(wkch)) line[wkpos] = tolower(wkch); X } X X strcpy(wk.key, &line[pos]); X wk.recptr = filepos; X if ((stat = add_key(ep, ixptr)) != IX_OK) { X printf("Status %d from add_key at record %d\n", stat, rcount); X exit(0); X } X } X X /* dump the file */ X first_key(ixptr); X while (next_key(ep, ixptr) == IX_OK) { X fseek(infile, wk.recptr, 0); X fgets(line, LineSize, infile); X printf("%s", line); X } X X close_index(ixptr); X fclose(infile); X} SHAR_EOF chmod 0644 utest2.c || echo "restore of utest2.c fails" echo "x - extracting utest3.c (Text)" sed 's/^X//' << 'SHAR_EOF' > utest3.c && X/* UNIX test, pipe the output of "find" into this and get a sorted list X X The key value is the last non-blank data in the input record. This X works well using the output of "ls -l" as input. Keys are stored X without regard to case. X*/ X X#include X#include X#include "bplus.h" X X#define DUPflag 1 /* allow dups */ X#define LineSize 180 /* input max line */ Xmain(argc, argv) X int argc; X char *argv[]; X{ X ENTRY wk, *ep = &wk; X IX_DESC pix, *ixptr = &pix; X char line[LineSize]; X FILE *infile, *fopen(); X long filepos, ftell(); X int stat, pos, rcount = 0, wkch, wkpos; X X if (argc < 2) { X printf("Missing filename\n"); X exit(1); X } X X if ((infile = fopen(argv[1], "r")) == NULL) { X printf("Can't open input file %s\n", argv[1]); X exit(1); X } X X if (make_index("names.idx", ixptr, DUPflag) != IX_OK) { X perror("Make index"); X exit(1); X } X X while (filepos = ftell(infile), fgets(line, LineSize, infile) != NULL) { X rcount++; X pos = strlen(line) - 1; X line[pos] = 0; X while (pos && line[pos-1] != ' ' && line[pos-1] != '/') pos--; X X /* this forces the sort key into lower case */ X for (wkpos=pos; wkch = line[wkpos]; wkpos++) { X if (isupper(wkch)) line[wkpos] = tolower(wkch); X } X X strcpy(wk.key, &line[pos]); X wk.recptr = filepos; X if ((stat = add_key(ep, ixptr)) != IX_OK) { X printf("Status %d from add_key at record %d\n", stat, rcount); X exit(0); X } X } X X close_index(ixptr); X fclose(infile); X} SHAR_EOF chmod 0644 utest3.c || echo "restore of utest3.c fails" echo "x - extracting utest4.c (Text)" sed 's/^X//' << 'SHAR_EOF' > utest4.c && X/* UNIX B+tree test, read a database created by the utest3 program and X display records matching given keys X*/ X X#include X#include X#include "bplus.h" X X#define DUPflag 1 /* allow dups */ X#define LineSize 180 /* input max line */ X Xmain (argc, argv) X int argc; X char *argv[]; X{ X ENTRY wk, *ep = &wk; X IX_DESC pix, *ixptr = &pix; X char line[LineSize], MyKey[MAXKEY]; X char *fgets(); X FILE *infile, *fopen (); X long filepos, ftell (); X int stat, pos, rcount = 0, wkch, wkpos; X X if (argc < 2) { X printf ("Missing filename\n"); X exit (1); X } X X if ((infile = fopen (argv[1], "r")) == NULL) { X printf ("Can't open input file %s\n", argv[1]); X exit (1); X } X X if (open_index ("names.idx", ixptr, DUPflag) != IX_OK) { X perror ("Open index"); X exit (1); X } X X /* dump the file */ X for (;;) { X printf ("Filename: "); X if (fgets (MyKey, MAXKEY, stdin) == NULL) break; X MyKey[pos = strlen (MyKey) - 1] = 0; X if (pos == 0) break; X for (pos = 0; wkch = MyKey[pos]; pos++) { X if (isupper (wkch)) X MyKey[pos] = tolower (wkch); X } X /* insure readable output if input is from a pipe */ X if (!isatty(0)) printf("%s\n", MyKey); X X /* get the first matching key */ X strcpy (wk.key, MyKey); X if (find_key (ep, ixptr) == IX_OK) { X /* at least one matching key */ X fseek (infile, wk.recptr, 0); X fgets (line, LineSize, infile); X printf ("%s", line); X X /* now look for more duplicates */ X while (next_key (ep, ixptr) == IX_OK && strcmp (wk.key, MyKey) == 0) { X /* display all duplicate keys */ X fseek (infile, wk.recptr, 0); X fgets (line, LineSize, infile); X printf ("%s", line); X } X } X } X X close_index (ixptr); X fclose (infile); X} SHAR_EOF chmod 0644 utest4.c || echo "restore of utest4.c fails" echo "x - extracting makefile (Text)" sed 's/^X//' << 'SHAR_EOF' > makefile && X# makefile for UNIX bplus test X XLIB = bplus.o filelen.o memmove.o XTESTS = utest utest1 utest2 utest3 utest4 XTESTOBJ = utest.o utest1.o utest2.o utest3.o utest4.o XCFLAGS = -O X Xall: $(TESTS) X X$(TESTS): bplus.a $$@.o X cc -o $@ $@.o bplus.a X Xbplus.o: bplus.h X$(TESTOBJ): bplus.h X Xbplus.a: $(LIB) X ar rv bplus.a $? X ranlib bplus.a SHAR_EOF chmod 0644 makefile || echo "restore of makefile fails" exit 0 -- bill davidsen (wedu@ge-crd.arpa) {uunet | philabs}!steinmetz!crdos1!davidsen "Stupidity, like virtue, is its own reward" -me