home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume3 / btree < prev    next >
Encoding:
Internet Message Format  |  1989-02-03  |  47.3 KB
  1. Path: xanth!mcnc!uvaarpa!umd5!ames!necntc!ncoast!allbery
  2. From: mjr@welchsun2.UUCP (Marcus J. Ranum)
  3. Newsgroups: comp.sources.misc
  4. Subject: v03i049: btree library
  5. Message-ID: <8806020220.AA18235@welchsun2>
  6. Date: 2 Jun 88 02:20:14 GMT
  7. Sender: allbery@ncoast.UUCP
  8. Reply-To: mjr@welchsun2.UUCP (Marcus J. Ranum)
  9. Lines: 2053
  10. Approved: allbery@ncoast.UUCP
  11.  
  12. comp.sources.misc: Volume 3, Issue 49
  13. Submitted-By: "Marcus J. Ranum" <mjr@welchsun2.UUCP>
  14. Archive-Name: btree
  15.  
  16. Poor Man's Btree Library
  17.  
  18. This is a library that maintains a simple balanced btree index. Nothing
  19. more is provided than routines to insert, set, find (specific, next,
  20. and previous), and delete keys. Each key, however, has a spare long
  21. value that can be used to contain an offset to a data file. A library
  22. to handle fixed-length records based on these pointers should be
  23. trivial. (Can you say 'dBASEIII'?) Another failing of this library is
  24. its total inability to cope with having several programs modifying
  25. indices at the same time. (it *CAN*, but I won't vouch for the result)
  26. The good solutions to that particular problem are OS dependent,
  27. unfortunately, and I am not a database guru anyhow.
  28.  
  29. ---mangle------mangle------mangle------mangle------mangle------mangle---
  30. #!/bin/sh
  31. #    This is a shell archive.
  32. #    run the file through sh.
  33. # shar:    Shell Archiver
  34. #    Run the following text with /bin/sh to create:
  35. #    README
  36. #    Makefile
  37. #    btree.c
  38. #    btree.h
  39. #    btree.3
  40. #    bench.c
  41. #    loadtree.c
  42. #    treedump.c
  43. #    sizes.c
  44. #    example.c
  45. # This archive created: Wed Jun  1 22:09:41 1988
  46. echo shar: extracting README '(3153 characters)'
  47. sed 's/^XX//' << \SHAR_EOF > README
  48. XXPoor Man's Btree Library
  49. XX
  50. XXThis is a library that maintains a simple balanced btree index. Nothing
  51. XXmore is provided than routines to insert, set, find (specific, next,
  52. XXand previous), and delete keys. Each key, however, has a spare long
  53. XXvalue that can be used to contain an offset to a data file. A library
  54. XXto handle fixed-length records based on these pointers should be
  55. XXtrivial. (Can you say 'dBASEIII'?) Another failing of this library is
  56. XXits total inability to cope with having several programs modifying
  57. XXindices at the same time. (it *CAN*, but I won't vouch for the result)
  58. XXThe good solutions to that particular problem are OS dependent,
  59. XXunfortunately, and I am not a database guru anyhow.
  60. XX
  61. XXThe code originally came from a Public Domain package written by Ray
  62. XXSwartz in 1983. I have almost totally re-written it; a proverbial 'no
  63. XXline remains untouched' job that included removal of globals,
  64. XXrearranging most of the data structures, and use of read/write for file
  65. XXI/O instead of stdio.  I also made sure that return values are all
  66. XXchecked properly, so they can be properly ignored in the user code :-)
  67. XXAnother addition is a simple cache, which boosted performance a great
  68. XXdeal. The cache is maintained through a sort of a hash. I had a fairly
  69. XXnifty LRU cache set up, originally, but it turned out to be marginally
  70. XXslower, according to gprof, time, and anything else I could bring to
  71. XXbear on the problem.  If a real database guru takes a look at this,
  72. XXperhaps they can come up with a better way of doing things.
  73. XX
  74. XXSome aspects of this package are a bit primitive - mostly those that
  75. XXdeal with deleting nodes. Deleted nodes are simply flagged as such, and
  76. XXare ignored when searching for data. This effectively means that the
  77. XXindex will continue to grow. Fixing this is left as an exercise,
  78. XXetc...  :-)  (actually, keeping the stuff around has its uses, too.)
  79. XXThere is a hook in the super block structure designed to allow a
  80. XX'free-list' to be implemented, but no hooks in the btdelete() code for
  81. XXjoining nodes, etc, etc.
  82. XX
  83. XXThe original code was placed in the public domain. This is not, since I
  84. XXwish to retain some control over it. No restrictions are placed on
  85. XXmodification, or use of this code, as long as the copyrights are not
  86. XXremoved.  There are some areas that really could use improving (like
  87. XXhandling free nodes better) and I hope that if someone makes
  88. XXimprovements they will keep me up to date on them (e-mail please, I am
  89. XXnot on usenet).
  90. XX
  91. XXByte-order and portability: There are #ifdefs for BYTEORDER, which make
  92. XXthe program store data in network byte order (at least the data
  93. XXstructures that drive the library - user data is the user's problem.)
  94. XXThere are several unsolved problems with this approach. It works fine
  95. XXbetween my Sun and my VAX, but the way the structures are written to
  96. XXdisk is also going to depend on your compiler.  The BYTEORDER code is
  97. XXnot guaranteed to work, and if it doesn't, your best bet is to look at
  98. XXthe output of sizes.c and to check to see if your compiler assembles
  99. XXthe structures in the same ORDER.
  100. XX
  101. XX    Marcus J. Ranum, William Welch Medical Library, 1988
  102. XX    mjr@jhuigf.BITNET || uunet!mimsy!aplcen!osiris!welchvax!mjr
  103. SHAR_EOF
  104. if test 3153 -ne "`wc -c README`"
  105. then
  106. echo shar: error transmitting README '(should have been 3153 characters)'
  107. fi
  108. echo shar: extracting Makefile '(1880 characters)'
  109. sed 's/^XX//' << \SHAR_EOF > Makefile
  110. XX# Makefile for btree library 
  111. XX# Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
  112. XX# 
  113. XX# 
  114. XX# $Header: Makefile,v 1.1 88/06/01 21:36:05 mjr Rel $: Makefile 
  115. XX# 
  116. XX# $Log:    Makefile,v $
  117. XX# Revision 1.1  88/06/01  21:36:05  mjr
  118. XX# Initial revision
  119. XX# 
  120. XX# 
  121. XX# 
  122. XX
  123. XX# define SYSV or BSD (only for purposes of test code) - btree.c doesn't care.
  124. XX# 
  125. XX# define BYTEORDER to store the
  126. XX# data files in network byte order. On systems that are already in the
  127. XX# right byteorder, defining this will waste a few cycles here and there,
  128. XX# but the slowdown is I/O anyway.
  129. XXCFLAGS=-O -DBSD -DBYTEORDER
  130. XXLFLAGS=-s
  131. XXLINTFLAGS=-h -x -u -DBSD -DBYTEORDER
  132. XX
  133. XXLIB=    libbtree.a 
  134. XXLIBDIR=    /usr/local/lib
  135. XXHDR=    btree.h
  136. XXHDRDIR=    /usr/include/local
  137. XXMAN=    btree.3
  138. XXMANDIR=    /usr/man/manl
  139. XX
  140. XXall:    example loadtree treedump bench sizes
  141. XX
  142. XX$(LIB):    btree.o
  143. XX    ar rc $(LIB) btree.o
  144. XX    ranlib $(LIB)
  145. XX
  146. XXexample:    $(LIB) example.o
  147. XX    cc $(LFLAGS) -o example example.o $(LIB)
  148. XX
  149. XXloadtree:    $(LIB) loadtree.o
  150. XX    cc $(LFLAGS) -o loadtree loadtree.o $(LIB)
  151. XX
  152. XXtreedump:    $(LIB) treedump.o
  153. XX    cc $(LFLAGS) -o treedump treedump.o $(LIB)
  154. XX
  155. XXbench:        $(LIB) bench.o
  156. XX    cc $(LFLAGS) -o bench bench.o $(LIB)
  157. XX
  158. XXsizes:        sizes.o
  159. XX    cc $(LFLAGS) -o sizes sizes.o
  160. XX    @sizes
  161. XX
  162. XXbtree.o:    $(HDR) Makefile
  163. XXexample.o:    $(HDR) Makefile
  164. XXloadtree.o:    $(HDR) Makefile
  165. XXtreedump.o:    $(HDR) Makefile
  166. XXbench.o:    $(HDR) Makefile
  167. XXsizes.o:    $(HDR) Makefile
  168. XX
  169. XXinstall:    $(LIB) $(MAN)
  170. XX    cp $(LIB) $(LIBDIR)/$(LIB)
  171. XX    chmod 644 $(LIBDIR)/$(LIB)
  172. XX    cp $(HDR) $(HDRDIR)/$(HDR)
  173. XX    chmod 644 $(HDRDIR)/$(HDR)
  174. XX    ranlib $(LIBDIR)/$(LIB)
  175. XX    cp $(MAN) $(MANDIR)/$(MAN)
  176. XX    chmod 644 $(MANDIR)/$(MAN)
  177. XX
  178. XXclean:
  179. XX    rm -f $(LIB) *.o example bench loadtree treedump core mon.out \
  180. XX        sizes llib-lbtree.ln btr.shar
  181. XX
  182. XXlint:
  183. XX    lint $(LINTFLAGS) btree.c
  184. XX
  185. XXdiction:
  186. XX    style $(MAN)
  187. XX    diction $(MAN)
  188. XX
  189. XXlintlib:
  190. XX    lint -Cbtree btree.c
  191. XX
  192. XXshar:
  193. XX    shar -a README Makefile btree.c $(HDR) $(MAN) bench.c \
  194. XX        loadtree.c treedump.c sizes.c example.c > btr.shar
  195. SHAR_EOF
  196. if test 1880 -ne "`wc -c Makefile`"
  197. then
  198. echo shar: error transmitting Makefile '(should have been 1880 characters)'
  199. fi
  200. echo shar: extracting btree.c '(17883 characters)'
  201. sed 's/^XX//' << \SHAR_EOF > btree.c
  202. XX/*
  203. XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
  204. XX * $Author: mjr $
  205. XX */
  206. XX
  207. XX#ifndef lint
  208. XXstatic char *RCSid="$Header: btree.c,v 1.1 88/06/01 21:35:07 mjr Rel $: btree.c";
  209. XX#endif
  210. XX
  211. XX/*
  212. XX * $Log:    btree.c,v $
  213. XX * Revision 1.1  88/06/01  21:35:07  mjr
  214. XX * Initial revision
  215. XX * 
  216. XX */
  217. XX
  218. XX#include    <stdio.h>
  219. XX#include    "btree.h"
  220. XX
  221. XX/* if we wish to store our disk data in network byte order */
  222. XX#ifdef BYTEORDER
  223. XX#include    <sys/types.h>
  224. XX#include    <netinet/in.h>
  225. XX#endif
  226. XX
  227. XX#define    BT_NSIZ    (sizeof(struct btnode))
  228. XX#define    BT_SSIZ    (sizeof(struct btsuper))
  229. XX
  230. XX
  231. XX/* the errno for btree problems. we use negative # - */
  232. XX/* so btperror can use the real UNIX errno */
  233. XXint    bterrno = 0;
  234. XXchar    *bterrs[] = {
  235. XX    "No btree error",
  236. XX    "Bad index magic number",
  237. XX    "History stack overflow",
  238. XX    "Cannot delete node zero",
  239. XX    0
  240. XX};
  241. XX
  242. XX#ifdef vax
  243. XXextern    void    bcopy();
  244. XXextern    void    free();
  245. XXextern    void    exit();
  246. XXextern    void    perror();
  247. XX#endif
  248. XX
  249. XX
  250. XX/* write the btree superblock to disk */
  251. XXstatic int
  252. XXwsuper(bt)
  253. XXstruct    btree    *bt;
  254. XX{
  255. XX#ifdef BYTEORDER
  256. XX    struct    btsuper    boge;
  257. XX#endif
  258. XX    extern    long    lseek();
  259. XX
  260. XX    if (lseek(bt->fd, 0L, 0) < 0)
  261. XX        return (-1);
  262. XX
  263. XX#ifdef BYTEORDER
  264. XX    boge.magic = htonl(bt->sblk.magic);
  265. XX    boge.free = htonl(bt->sblk.free);
  266. XX    boge.root = htonl(bt->sblk.root);
  267. XX    boge.list = htonl(bt->sblk.list);
  268. XX
  269. XX    if (write(bt->fd, (char *) &boge, BT_SSIZ) != BT_SSIZ)
  270. XX        return (-1);
  271. XX#else
  272. XX    if (write(bt->fd, (char *) &bt->sblk, BT_SSIZ) != BT_SSIZ)
  273. XX        return (-1);
  274. XX#endif
  275. XX
  276. XX    return (0);
  277. XX}
  278. XX
  279. XX
  280. XX
  281. XX/* dynamically allocate a control structure for an open btree */
  282. XXstruct btree    *
  283. XXbtopen(path, flags, mode)
  284. XXchar    *path;
  285. XXint    flags;
  286. XXint    mode;
  287. XX{
  288. XX    struct    btree    *bt;
  289. XX    int    r;
  290. XX    extern    char    *malloc();
  291. XX
  292. XX    /* lets be dynamic, shall we ? */
  293. XX#ifndef lint
  294. XX    /* this to avoid the possible pointer alignment lint message */
  295. XX    if ((bt = (struct btree *) malloc(sizeof(struct btree))) == NULL)
  296. XX        return (NULL);
  297. XX#else
  298. XX    bt = (struct btree *)0;
  299. XX#endif
  300. XX
  301. XX    if ((bt->fd = open(path, flags, mode)) > -1) {
  302. XX
  303. XX        r = read(bt->fd, (char *) &bt->sblk, BT_SSIZ);
  304. XX
  305. XX        /* if read nothing, must be a new guy, right ? */
  306. XX        if (r == 0) {
  307. XX            bt->sblk.magic = BT_MAGIC;
  308. XX            bt->sblk.free = 1L;
  309. XX            bt->sblk.root = 0L;
  310. XX            bt->sblk.list = 0L;
  311. XX
  312. XX            if (wsuper(bt) == 0)
  313. XX                r = BT_SSIZ;
  314. XX        }
  315. XX#ifdef BYTEORDER
  316. XX        else {
  317. XX            /* read something, decode the numbers */
  318. XX            bt->sblk.magic = ntohl(bt->sblk.magic);
  319. XX            bt->sblk.free = ntohl(bt->sblk.free);
  320. XX            bt->sblk.root = ntohl(bt->sblk.root);
  321. XX            bt->sblk.list = ntohl(bt->sblk.list);
  322. XX        }
  323. XX#endif
  324. XX
  325. XX        /* cleverly check ret value from either read or write */
  326. XX        if (r != BT_SSIZ) {
  327. XX            (void) close(bt->fd);
  328. XX            (void) free((char *) bt);
  329. XX            return (NULL);
  330. XX        }
  331. XX
  332. XX        /* check that ole magic number */
  333. XX        if (bt->sblk.magic != BT_MAGIC) {
  334. XX            bterrno = BT_BAD_MAGIC;
  335. XX            (void) close(bt->fd);
  336. XX            (void) free((char *) bt);
  337. XX            return (NULL);
  338. XX        }
  339. XX    } else {
  340. XX        /* couldnt even open the bloody file */
  341. XX        (void) free((char *) bt);
  342. XX        return (NULL);
  343. XX    }
  344. XX
  345. XX    /* zero the cache - record numbers will never be -1, */
  346. XX    /* so the cache will load as activity takes place */
  347. XX    for(r = 0; r < BT_CSIZ; r++)
  348. XX        bt->cache[r].recno = -1L;
  349. XX
  350. XX    return (bt);
  351. XX}
  352. XX
  353. XX
  354. XX
  355. XX/* close and deallocate the control structure */
  356. XXbtclose(bt)
  357. XXstruct    btree    *bt;
  358. XX{
  359. XX    int    t;
  360. XX
  361. XX    t = wsuper(bt);
  362. XX    (void) close(bt->fd);
  363. XX    (void) free((char *) bt);
  364. XX    return (t);
  365. XX}
  366. XX
  367. XX
  368. XX
  369. XX/* write a node to disk */
  370. XXstatic    int
  371. XXwnode(nbr, npt, bt)
  372. XXlong    nbr;
  373. XXstruct    btnode    *npt;
  374. XXstruct    btree    *bt;
  375. XX{
  376. XX    extern    long    lseek();
  377. XX    extern    char    *strncpy();
  378. XX#ifdef    BYTEORDER
  379. XX    struct    btnode    boge;
  380. XX#endif
  381. XX
  382. XX    if (lseek(bt->fd, (long) ((nbr * BT_NSIZ) + BT_SSIZ), 0) == -1)
  383. XX        return (-1);
  384. XX
  385. XX
  386. XX#ifdef    BYTEORDER
  387. XX    boge.recno = htonl(npt->recno);
  388. XX    boge.lptr = htonl(npt->lptr);
  389. XX    boge.rptr = htonl(npt->rptr);
  390. XX    boge.deleted = htons(npt->deleted);
  391. XX    boge.balance = htons(npt->balance);
  392. XX    (void) strncpy(boge.key, npt->key, BT_KSIZ - 1);
  393. XX    if (write(bt->fd, (char *) &boge, BT_NSIZ) != BT_NSIZ)
  394. XX        return (-1);
  395. XX#else
  396. XX    if (write(bt->fd, (char *) npt, BT_NSIZ) != BT_NSIZ)
  397. XX        return (-1);
  398. XX#endif
  399. XX
  400. XX    /* update cache -  if the write succeeded */
  401. XX    (void)bcopy((char *)npt,(char *)&bt->cache[(int)nbr % BT_CSIZ],BT_NSIZ);
  402. XX    return (0);
  403. XX}
  404. XX
  405. XX
  406. XX
  407. XX/* read a node from disk */
  408. XXstatic    int
  409. XXrnode(nbr, npt, bt)
  410. XXlong    nbr;
  411. XXstruct    btnode    *npt;
  412. XXstruct    btree    *bt;
  413. XX{
  414. XX    extern    long    lseek();
  415. XX    extern    char    *strncpy();
  416. XX    int    hash;
  417. XX#ifdef    BYTEORDER
  418. XX    struct    btnode    boge;
  419. XX#endif
  420. XX    hash = (int)nbr % BT_CSIZ;
  421. XX
  422. XX    /* check for cache hit - simple hash - braindead, really */
  423. XX    if(bt->cache[hash].recno != nbr) {
  424. XX
  425. XX        /* if no cache hit, load from disk */
  426. XX        if (lseek(bt->fd, (long) ((nbr * BT_NSIZ) + BT_SSIZ), 0) == -1)
  427. XX            return (-1);
  428. XX#ifndef BYTEORDER
  429. XX        if (read(bt->fd, (char *) &bt->cache[hash], BT_NSIZ) != BT_NSIZ)
  430. XX            return (-1);
  431. XX#else
  432. XX        if (read(bt->fd, (char *) &boge, BT_NSIZ) != BT_NSIZ)
  433. XX            return (-1);
  434. XX
  435. XX        bt->cache[hash].recno = ntohl(boge.recno);
  436. XX        bt->cache[hash].lptr = ntohl(boge.lptr);
  437. XX        bt->cache[hash].rptr = ntohl(boge.rptr);
  438. XX        bt->cache[hash].deleted = ntohs(boge.deleted);
  439. XX        bt->cache[hash].balance = ntohs(boge.balance);
  440. XX        (void) strncpy(bt->cache[hash].key, boge.key, BT_KSIZ - 1);
  441. XX#endif
  442. XX    }
  443. XX
  444. XX    /* loaded OK, now copy the updated cached data to the target */
  445. XX    (void)bcopy((char *) &bt->cache[hash],(char *)npt,BT_NSIZ);
  446. XX
  447. XX    return (0);
  448. XX}
  449. XX
  450. XX
  451. XX
  452. XXstatic    int
  453. XXpushl(bt, nbr)
  454. XXstruct    btree    *bt;
  455. XXlong    nbr;
  456. XX{
  457. XX    if (++(bt->lstak.sptr) >= STACK_LENGTH) {
  458. XX        bterrno = BT_BAD_STACK;
  459. XX        exit(0);
  460. XX    }
  461. XX    bt->lstak.ele[bt->lstak.sptr] = nbr;
  462. XX    bt->lstak.lev[bt->lstak.sptr] = ++bt->slev;
  463. XX    return;
  464. XX}
  465. XX
  466. XX
  467. XXstatic    int
  468. XXpushr(bt, nbr)
  469. XXstruct    btree    *bt;
  470. XXlong    nbr;
  471. XX{
  472. XX    if (++(bt->rstak.sptr) >= STACK_LENGTH) {
  473. XX        bterrno = BT_BAD_STACK;
  474. XX        exit(0);
  475. XX    }
  476. XX    bt->rstak.ele[bt->rstak.sptr] = nbr;
  477. XX    bt->rstak.lev[bt->rstak.sptr] = ++bt->slev;
  478. XX    return;
  479. XX}
  480. XX
  481. XX
  482. XX
  483. XXstatic    long
  484. XXpopr(bt)
  485. XXstruct    btree    *bt;
  486. XX{
  487. XX
  488. XX    bt->slev = bt->rstak.lev[bt->rstak.sptr];
  489. XX
  490. XX    while (bt->lstak.lev[bt->lstak.sptr] > bt->slev)
  491. XX        (bt->lstak.sptr)--;
  492. XX
  493. XX    if (bt->rstak.sptr == 0)
  494. XX        return (0);
  495. XX
  496. XX    bt->slev--;
  497. XX    return (bt->rstak.ele[(bt->rstak.sptr)--]);
  498. XX}
  499. XX
  500. XX
  501. XX
  502. XXstatic    long
  503. XXpopl(bt)
  504. XXstruct    btree    *bt;
  505. XX{
  506. XX
  507. XX    bt->slev = bt->lstak.lev[bt->lstak.sptr];
  508. XX
  509. XX    while (bt->rstak.lev[bt->rstak.sptr] > bt->slev)
  510. XX        (bt->rstak.sptr)--;
  511. XX
  512. XX    if (bt->lstak.sptr == 0)
  513. XX        return (0);
  514. XX
  515. XX    bt->slev--;
  516. XX    return (bt->lstak.ele[(bt->lstak.sptr)--]);
  517. XX}
  518. XX
  519. XX
  520. XX
  521. XXstatic    void
  522. XXbt_link(alpha1, node1, alpha2, node2)
  523. XXint    alpha1;
  524. XXint    alpha2;
  525. XXstruct    btnode    *node1;
  526. XXstruct    btnode    *node2;
  527. XX{
  528. XX    if (alpha1 == -1 && alpha2 == -1)
  529. XX        node1->lptr = node2->lptr;
  530. XX    else if (alpha1 == -1 && alpha2 == 1)
  531. XX        node1->lptr = node2->rptr;
  532. XX    else if (alpha1 == 1 && alpha2 == -1)
  533. XX        node1->rptr = node2->lptr;
  534. XX    else
  535. XX        node1->rptr = node2->rptr;
  536. XX}
  537. XX
  538. XX
  539. XX
  540. XX/* number a link according to alpha */
  541. XXstatic    void
  542. XXnbr_link(nbr, alpha, node1)
  543. XXlong        *nbr;
  544. XXint        alpha;
  545. XXstruct    btnode    *node1;
  546. XX{
  547. XX    *nbr = (alpha == 1) ? node1->rptr : node1->lptr;
  548. XX}
  549. XX
  550. XX
  551. XX
  552. XX/* set a link according to alpha */
  553. XXstatic    void
  554. XXlink_nbr(alpha, node1, nbr)
  555. XXint        alpha;
  556. XXstruct    btnode    *node1;
  557. XXlong        nbr;
  558. XX{
  559. XX
  560. XX    if (alpha == 1)
  561. XX        node1->rptr = nbr;
  562. XX    else
  563. XX        node1->lptr = nbr;
  564. XX}
  565. XX
  566. XX
  567. XX
  568. XXstatic    void
  569. XXnode_bal(alpha, node1, node2, node3)
  570. XXint    alpha;
  571. XXstruct    btnode    *node1;
  572. XXstruct    btnode    *node2;
  573. XXstruct    btnode    *node3;
  574. XX{
  575. XX
  576. XX    if (node1->balance == alpha) {
  577. XX        node2->balance = -alpha;
  578. XX        node3->balance = 0;
  579. XX    } else if (node1->balance == 0)
  580. XX        node2->balance = node3->balance = 0;
  581. XX    else {
  582. XX        node2->balance = 0;
  583. XX        node3->balance = alpha;
  584. XX    }
  585. XX}
  586. XX
  587. XX
  588. XX
  589. XX/* change the record number in a node */
  590. XXbtsetrec(nbr, newrec, bt)
  591. XXlong    nbr;
  592. XXlong    newrec;
  593. XXstruct    btree    *bt;
  594. XX{
  595. XX    struct    btnode    tmpnode;
  596. XX
  597. XX    if(rnode(nbr, &tmpnode, bt) <0)
  598. XX        return(-1);
  599. XX
  600. XX    tmpnode.recno = newrec;
  601. XX
  602. XX    if(wnode(nbr, &tmpnode, bt) <0)
  603. XX        return(-1);
  604. XX
  605. XX
  606. XX    return(0);
  607. XX}
  608. XX
  609. XX
  610. XX
  611. XX/* insert the node into the tree */
  612. XXbtinsert(argkey, recnbr, bt)
  613. XXchar    *argkey;
  614. XXlong    recnbr;
  615. XXstruct    btree    *bt;
  616. XX{
  617. XX    long    top;
  618. XX    long    p_rec;
  619. XX    long    s_rec;
  620. XX    long    q_rec;
  621. XX    long    r_rec;
  622. XX    struct    btnode    q_node;
  623. XX    struct    btnode    s_node;
  624. XX    struct    btnode    r_node;
  625. XX    struct    btnode    p_node;
  626. XX    int    compare;
  627. XX    extern    char    *strncpy();
  628. XX
  629. XX
  630. XX    /* the very first node gets inserted specially */
  631. XX    if (bt->sblk.root == 0) {
  632. XX        bt->sblk.root = 1;
  633. XX        p_node.balance = p_node.rptr = p_node.lptr = 0;
  634. XX        p_node.deleted = BT_ACTIVE;
  635. XX        p_node.recno = recnbr;
  636. XX
  637. XX        (void) strncpy(p_node.key, argkey, BT_KSIZ - 1);
  638. XX        p_node.key[BT_KSIZ - 1] = '\0';
  639. XX        if(wnode(1L, &p_node, bt) < 0)
  640. XX            return(-1);
  641. XX
  642. XX        bt->sblk.free++;
  643. XX        bt->sblk.list++;
  644. XX        if(wsuper(bt) <0)
  645. XX            return(-1);
  646. XX        return (0);
  647. XX    }
  648. XX    top = -1;
  649. XX    p_rec = bt->sblk.root;
  650. XX    s_rec = bt->sblk.root;
  651. XX    while (1) {
  652. XX        if(rnode(p_rec, &p_node, bt) <0)
  653. XX            return(-1);
  654. XX        if ((compare = strcmp(argkey, p_node.key)) < 0) {
  655. XX
  656. XX            /* (move left) */
  657. XX            q_rec = p_node.lptr;
  658. XX
  659. XX            if (q_rec == 0) {
  660. XX                /* insert here */
  661. XX                q_rec = bt->sblk.free++;
  662. XX                p_node.lptr = q_rec;
  663. XX                break;    /* loop exit */
  664. XX            } else {
  665. XX                /* look again from this node */
  666. XX                if(rnode(q_rec, &q_node, bt) <0)
  667. XX                    return(-1);
  668. XX                if (q_node.balance != 0) {
  669. XX                    top = p_rec;
  670. XX                    s_rec = q_rec;
  671. XX                }
  672. XX            }
  673. XX            p_rec = q_rec;
  674. XX
  675. XX        } else {
  676. XX            /* (move right) */
  677. XX            q_rec = p_node.rptr;
  678. XX
  679. XX            if (q_rec == 0) {
  680. XX                /* insert here */
  681. XX                q_rec = bt->sblk.free++;
  682. XX                p_node.rptr = q_rec;
  683. XX                break;    /* loop exit */
  684. XX            } else {
  685. XX                /* look again from this node */
  686. XX                if(rnode(q_rec, &q_node, bt) <0)
  687. XX                    return(-1);
  688. XX                if (q_node.balance != 0) {
  689. XX                    top = p_rec;
  690. XX                    s_rec = q_rec;
  691. XX                }
  692. XX                p_rec = q_rec;
  693. XX            }
  694. XX        }
  695. XX    }
  696. XX
  697. XX    /* Step 5 (insert key at q_node) */
  698. XX    q_node.lptr = q_node.rptr = 0;
  699. XX    q_node.balance = 0;
  700. XX    q_node.deleted = BT_ACTIVE;
  701. XX    q_node.recno = recnbr;
  702. XX    (void) strncpy(q_node.key, argkey, BT_KSIZ);
  703. XX    q_node.key[BT_KSIZ - 1] = '\0';
  704. XX
  705. XX    if (wnode(q_rec, &q_node, bt) == -1)
  706. XX        return (-1);
  707. XX
  708. XX    if(wnode(p_rec, &p_node, bt) <0)
  709. XX        return(-1);
  710. XX    if(rnode(s_rec, &s_node, bt) <0)
  711. XX        return(-1);
  712. XX    if(wsuper(bt) <0)
  713. XX        return(-1);
  714. XX
  715. XX    /* (adjust balance factors) */
  716. XX    if (strcmp(argkey, s_node.key) < 0) {
  717. XX        r_rec = p_rec = s_node.lptr;
  718. XX    } else {
  719. XX        r_rec = p_rec = s_node.rptr;
  720. XX    }
  721. XX
  722. XX    while (p_rec != q_rec) {
  723. XX        if(rnode(p_rec, &p_node, bt) <0)
  724. XX            return(-1);
  725. XX        if (strcmp(argkey, p_node.key) < 0) {
  726. XX            p_node.balance = -1;
  727. XX            if(wnode(p_rec, &p_node, bt) < 0)
  728. XX                return(-1);
  729. XX            p_rec = p_node.lptr;
  730. XX        } else {
  731. XX            p_node.balance = 1;
  732. XX            if(wnode(p_rec, &p_node, bt) < 0)
  733. XX                return(-1);
  734. XX            p_rec = p_node.rptr;
  735. XX        }
  736. XX    }
  737. XX
  738. XX    compare = (strcmp(argkey, s_node.key) < 0) ? -1 : 1;
  739. XX    if (s_node.balance == 0) {
  740. XX        bt->sblk.list++;
  741. XX        s_node.balance = compare;
  742. XX        if(wnode(s_rec, &s_node, bt) < 0)
  743. XX            return(-1);
  744. XX        if(wsuper(bt) <0)
  745. XX            return(-1);
  746. XX        return (0);
  747. XX    } else if (s_node.balance == -compare) {
  748. XX        bt->sblk.list++;
  749. XX        s_node.balance = 0;
  750. XX        if(wnode(s_rec, &s_node, bt) < 0)
  751. XX            return(-1);
  752. XX        if(wsuper(bt) <0)
  753. XX            return(-1);
  754. XX        return (0);
  755. XX    } else {
  756. XX        /* (tree out of balance) */
  757. XX        bt->sblk.list++;
  758. XX        if(rnode(s_rec, &s_node, bt) <0)
  759. XX            return(-1);
  760. XX        if(rnode(r_rec, &r_node, bt) <0)
  761. XX            return(-1);
  762. XX        if (r_node.balance == compare) {
  763. XX            /* (single rotate) */
  764. XX            p_rec = r_rec;
  765. XX            bt_link(compare, &s_node, -compare, &r_node);
  766. XX            link_nbr(-compare, &r_node, s_rec);
  767. XX            s_node.balance = r_node.balance = 0;
  768. XX        } else {
  769. XX            /* (double rotate) */
  770. XX            nbr_link(&p_rec, -compare, &r_node);
  771. XX            if(rnode(p_rec, &p_node, bt) <0)
  772. XX                return(-1);
  773. XX            bt_link(-compare, &r_node, compare, &p_node);
  774. XX            link_nbr(compare, &p_node, r_rec);
  775. XX            bt_link(compare, &s_node, -compare, &p_node);
  776. XX            link_nbr(-compare, &p_node, s_rec);
  777. XX            node_bal(compare, &p_node, &s_node, &r_node);
  778. XX            p_node.balance = 0;
  779. XX            if(wnode(p_rec, &p_node, bt) <0)
  780. XX                return(-1);
  781. XX        }
  782. XX
  783. XX        if (top == -1) {
  784. XX            bt->sblk.root = p_rec;
  785. XX        } else {
  786. XX            /* balanced at top of a sub-tree */
  787. XX            if(rnode(top, &q_node, bt) < 0)
  788. XX                return(-1);
  789. XX            if (s_rec == q_node.rptr)
  790. XX                q_node.rptr = p_rec;
  791. XX            else
  792. XX                q_node.lptr = p_rec;
  793. XX            if(wnode(top, &q_node, bt) <0)
  794. XX                return(-1);
  795. XX        }
  796. XX        if(wnode(s_rec, &s_node, bt) <0)
  797. XX            return(-1);
  798. XX        if(wnode(r_rec, &r_node, bt) <0)
  799. XX            return(-1);
  800. XX        if(wsuper(bt) <0)
  801. XX            return(-1);
  802. XX        return (0);
  803. XX    }
  804. XX}
  805. XX
  806. XX
  807. XX
  808. XX/* drop a node */
  809. XXbtdelete(node_nbr, bt)
  810. XXlong    node_nbr;
  811. XXstruct    btree    *bt;
  812. XX{
  813. XX    struct    btnode    cno;
  814. XX
  815. XX    if (node_nbr == 0) {
  816. XX        bterrno = BT_BAD_ROOT;
  817. XX        return (-1);
  818. XX    } else {
  819. XX        if (rnode(node_nbr, &cno, bt) == -1) 
  820. XX            return(-1);
  821. XX        cno.deleted = BT_DELETED;
  822. XX        if (wnode(node_nbr, &cno, bt) == -1) {
  823. XX            return (-1);
  824. XX        } else {
  825. XX            bt->sblk.list--;
  826. XX            if(wsuper(bt) <0)
  827. XX                return(-1);
  828. XX        }
  829. XX    }
  830. XX    return (0);
  831. XX}
  832. XX
  833. XX
  834. XX
  835. XX/* find the next node */
  836. XXbtnext(node_nbr, cno, bt)
  837. XXlong    *node_nbr;
  838. XXstruct    btnode    *cno;
  839. XXstruct    btree    *bt;
  840. XX{
  841. XX    long    popl();
  842. XX    long    popr();
  843. XX    long    s_nod;
  844. XX
  845. XX    s_nod = *node_nbr;
  846. XX
  847. XX    if (*node_nbr == 0) {
  848. XX        /* undefined current node - wind to beginning of file */
  849. XX        return (bthead(node_nbr,cno,bt));
  850. XX    }
  851. XX    do {
  852. XX        if (cno->rptr == 0) {
  853. XX            /* can't move right */
  854. XX            if (bt->lstak.sptr == 0) {
  855. XX                /* none in stack */
  856. XX                if(rnode(*node_nbr, cno, bt) <0)
  857. XX                    return(-1);
  858. XX                return (BT_EOF);
  859. XX            } else {
  860. XX                /* can't go right & stack full (pop stack) */
  861. XX                s_nod = popl(bt);
  862. XX                if(rnode(s_nod, cno, bt) < 0)
  863. XX                    return(-1);
  864. XX            }
  865. XX        } else {
  866. XX            /* move right */
  867. XX            pushr(bt, s_nod);
  868. XX            s_nod = cno->rptr;
  869. XX            if(rnode(s_nod, cno, bt) <0 )
  870. XX                return(-1);
  871. XX
  872. XX            while (cno->lptr != 0) {
  873. XX                /* bottom left */
  874. XX                pushl(bt, s_nod);
  875. XX                /* of this sub-tree */
  876. XX                s_nod = cno->lptr;
  877. XX                if(rnode(s_nod, cno, bt) <0)
  878. XX                    return(-1);
  879. XX            }
  880. XX        }
  881. XX    } while (cno->deleted == BT_DELETED);
  882. XX
  883. XX    *node_nbr = s_nod;
  884. XX    return (0);
  885. XX}
  886. XX
  887. XX
  888. XX
  889. XX/* go to the tail of the file */
  890. XXbttail(node_nbr, cno, bt)
  891. XXstruct    btree    *bt;
  892. XXlong    *node_nbr;
  893. XXstruct    btnode    *cno;
  894. XX{
  895. XX    long    s_nod;
  896. XX
  897. XX    bt->rstak.sptr = 0;
  898. XX    bt->lstak.sptr = 0;
  899. XX    bt->rstak.ele[0] = 0;
  900. XX    bt->lstak.ele[0] = 0;
  901. XX
  902. XX    /* begin at list head */
  903. XX    s_nod = bt->sblk.root;
  904. XX
  905. XX    if(rnode(s_nod, cno, bt) <0)
  906. XX        return(-1);
  907. XX    while (1) {
  908. XX        /* search to right */
  909. XX        if (cno->rptr != 0) {
  910. XX            pushr(bt, s_nod);
  911. XX            s_nod = cno->rptr;
  912. XX            if(rnode(s_nod, cno, bt) <0)
  913. XX                return(-1);
  914. XX        } else {
  915. XX            if (cno->deleted == BT_DELETED) {
  916. XX                /* skip all deleted nodes */
  917. XX                while (cno->deleted == BT_DELETED) {
  918. XX                    if (btnext(&s_nod, cno, bt) == BT_EOF) {
  919. XX                        if(btprevious(&s_nod, cno, bt)<0)
  920. XX                            return(-1);
  921. XX                        *node_nbr = s_nod;
  922. XX                        return (0);
  923. XX                    }
  924. XX                }
  925. XX                *node_nbr = s_nod;
  926. XX                return (0);
  927. XX            } else {
  928. XX                /* at end of a branch */
  929. XX                *node_nbr = s_nod;
  930. XX                return (0);
  931. XX            }
  932. XX        }
  933. XX    }
  934. XX}
  935. XX
  936. XX
  937. XX/* go to the head of the file */
  938. XXbthead(node_nbr, cno, bt)
  939. XXstruct    btree    *bt;
  940. XXlong    *node_nbr;
  941. XXstruct    btnode    *cno;
  942. XX{
  943. XX    long    s_nod;
  944. XX
  945. XX    bt->rstak.sptr = 0;
  946. XX    bt->lstak.sptr = 0;
  947. XX    bt->rstak.ele[0] = 0;
  948. XX    bt->lstak.ele[0] = 0;
  949. XX
  950. XX    /* begin at list head */
  951. XX    s_nod = bt->sblk.root;
  952. XX
  953. XX    if(rnode(s_nod, cno, bt) <0)
  954. XX        return(-1);
  955. XX    while (1) {
  956. XX        /* search to left */
  957. XX        if (cno->lptr != 0) {
  958. XX            pushl(bt, s_nod);
  959. XX            s_nod = cno->lptr;
  960. XX            if(rnode(s_nod, cno, bt) <0)
  961. XX                return(-1);
  962. XX        } else {
  963. XX            if (cno->deleted == BT_DELETED) {
  964. XX                /* skip all deleted nodes */
  965. XX                while (cno->deleted == BT_DELETED) {
  966. XX                    if (btprevious(&s_nod, cno, bt) == BT_EOF) {
  967. XX                        if(btnext(&s_nod, cno, bt)<0)
  968. XX                            return(-1);
  969. XX                        *node_nbr = s_nod;
  970. XX                        return (0);
  971. XX                    }
  972. XX                }
  973. XX                *node_nbr = s_nod;
  974. XX                return (0);
  975. XX            } else {
  976. XX                /* at end of a branch */
  977. XX                *node_nbr = s_nod;
  978. XX                return (0);
  979. XX            }
  980. XX        }
  981. XX    }
  982. XX}
  983. XX
  984. XX
  985. XX
  986. XX/* find a key */
  987. XXbtfind(key1, node_nbr, cno, bt)
  988. XXchar    *key1;
  989. XXstruct    btree    *bt;
  990. XXlong    *node_nbr;
  991. XXstruct    btnode    *cno;
  992. XX{
  993. XX    int    direction;
  994. XX    long    s_nod;
  995. XX
  996. XX    bt->rstak.sptr = 0;
  997. XX    bt->lstak.sptr = 0;
  998. XX    bt->rstak.ele[0] = 0;
  999. XX    bt->lstak.ele[0] = 0;
  1000. XX
  1001. XX    bt->slev = 0;        /* tree level at start of search */
  1002. XX
  1003. XX    /* begin at list head */
  1004. XX    s_nod = bt->sblk.root;
  1005. XX
  1006. XX    if(rnode(s_nod, cno, bt) <0)
  1007. XX        return(-1);
  1008. XX    while ((direction = strcmp(key1, cno->key)) != 0 ||
  1009. XX        cno->deleted == BT_DELETED) {
  1010. XX
  1011. XX        if (direction > 0) {
  1012. XX            /* search to right */
  1013. XX            if (cno->rptr != 0) {
  1014. XX                pushr(bt, s_nod);
  1015. XX                s_nod = cno->rptr;
  1016. XX                if(rnode(s_nod, cno, bt) <0)
  1017. XX                    return(-1);
  1018. XX            } else if (cno->deleted == BT_DELETED) {
  1019. XX                /* skip all deleted nodes */
  1020. XX                while (cno->deleted == BT_DELETED) {
  1021. XX                    if (btnext(&s_nod, cno, bt) == BT_EOF) {
  1022. XX                        if(btprevious(&s_nod, cno, bt)<0)
  1023. XX                            return(-1);
  1024. XX                        *node_nbr = s_nod;
  1025. XX                        return (BT_NREC);
  1026. XX                    }
  1027. XX                }
  1028. XX                *node_nbr = s_nod;
  1029. XX                return (BT_NREC);
  1030. XX            } else {
  1031. XX                /* at end of a branch */
  1032. XX                *node_nbr = s_nod;
  1033. XX                return (BT_NREC);
  1034. XX            }
  1035. XX        } else {
  1036. XX            /* search to left */
  1037. XX            if (cno->lptr != 0) {
  1038. XX                pushl(bt, s_nod);
  1039. XX                s_nod = cno->lptr;
  1040. XX                if(rnode(s_nod, cno, bt) <0)
  1041. XX                    return(-1);
  1042. XX            } else if (cno->deleted == BT_DELETED) {
  1043. XX                while (cno->deleted == BT_DELETED) {
  1044. XX                    if (btnext(&s_nod, cno, bt) == BT_EOF) {
  1045. XX                        if(btprevious(&s_nod, cno, bt)< 0)
  1046. XX                            return(-1);
  1047. XX                        *node_nbr = s_nod;
  1048. XX                        return (BT_NREC);
  1049. XX                    }
  1050. XX                }
  1051. XX                *node_nbr = s_nod;
  1052. XX                return (BT_NREC);
  1053. XX            } else {
  1054. XX                *node_nbr = s_nod;
  1055. XX                return (BT_NREC);
  1056. XX            }
  1057. XX        }
  1058. XX    }
  1059. XX    *node_nbr = s_nod;
  1060. XX    return (0);
  1061. XX}
  1062. XX
  1063. XX
  1064. XX
  1065. XX/* get the previous node */
  1066. XXbtprevious(node_nbr, cno, bt)
  1067. XXlong    *node_nbr;
  1068. XXstruct    btnode    *cno;
  1069. XXstruct    btree    *bt;
  1070. XX{
  1071. XX    long    popr();
  1072. XX    long    popl();
  1073. XX    long    s_nod;
  1074. XX
  1075. XX    s_nod = *node_nbr;
  1076. XX
  1077. XX    /* if we are called without a node, wind to the end of file */
  1078. XX    if (*node_nbr == 0) {
  1079. XX        return (bttail(node_nbr,cno,bt));
  1080. XX    }
  1081. XX
  1082. XX
  1083. XX    do {
  1084. XX        if (cno->lptr == 0) {
  1085. XX            /* can't move left */
  1086. XX            if (bt->rstak.sptr == 0) {
  1087. XX                /* none in stack */
  1088. XX                if(rnode(*node_nbr, cno, bt) <0)
  1089. XX                    return(-1);
  1090. XX                return (BT_EOF);
  1091. XX                /* don't reset node_nbr */
  1092. XX            } else {
  1093. XX                /* can't go left & stack full (pop stack) */
  1094. XX                s_nod = popr(bt);
  1095. XX                if(rnode(s_nod, cno, bt) <0)
  1096. XX                    return(-1);
  1097. XX            }
  1098. XX        } else {
  1099. XX            /* left then to bottom right - is previous */
  1100. XX            pushl(bt, s_nod);
  1101. XX            s_nod = cno->lptr;
  1102. XX            if(rnode(s_nod, cno, bt) <0)
  1103. XX                return(-1);
  1104. XX            while (cno->rptr != 0) {
  1105. XX                /* bottom right */
  1106. XX                pushr(bt, s_nod);
  1107. XX                /* of this sub-tree */
  1108. XX                s_nod = cno->rptr;
  1109. XX                if(rnode(s_nod, cno, bt) <0)
  1110. XX                    return(-1);
  1111. XX            }
  1112. XX        }
  1113. XX    } while (cno->deleted == BT_DELETED);
  1114. XX
  1115. XX    *node_nbr = s_nod;
  1116. XX    return (0);
  1117. XX}
  1118. XX
  1119. XX
  1120. XX
  1121. XX/* print the btree error message */
  1122. XXvoid
  1123. XXbtperror(str)
  1124. XXchar    *str;
  1125. XX{
  1126. XX    extern    int    errno;
  1127. XX
  1128. XX    /* is it ours ?? */
  1129. XX    if (errno == 0) {
  1130. XX        if (str[strlen(str) - 1] != ':')
  1131. XX            (void) fprintf(stderr, "%s: %s\n", str, bterrs[bterrno]);
  1132. XX        else
  1133. XX            (void) fprintf(stderr, "%s %s\n", str, bterrs[bterrno]);
  1134. XX        bterrno = 0;
  1135. XX    } else {
  1136. XX        perror(str);
  1137. XX    }
  1138. XX}
  1139. SHAR_EOF
  1140. if test 17883 -ne "`wc -c btree.c`"
  1141. then
  1142. echo shar: error transmitting btree.c '(should have been 17883 characters)'
  1143. fi
  1144. echo shar: extracting btree.h '(2161 characters)'
  1145. sed 's/^XX//' << \SHAR_EOF > btree.h
  1146. XX/*
  1147. XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
  1148. XX * $Author: mjr $
  1149. XX *
  1150. XX * $Header: btree.h,v 1.1 88/06/01 21:35:55 mjr Rel $: btree.h
  1151. XX *
  1152. XX * $Log:    btree.h,v $
  1153. XX * Revision 1.1  88/06/01  21:35:55  mjr
  1154. XX * Initial revision
  1155. XX * 
  1156. XX */
  1157. XX
  1158. XX#ifndef _INCL_BTREE_H
  1159. XX
  1160. XX#define BT_NREC    1    /* no such record */
  1161. XX#define BT_EOF    2    /* end of the tree (either end) */
  1162. XX#define BT_ERR    -1    /* something went wrong */
  1163. XX
  1164. XX#define BT_KSIZ    40    /* size of keys to store (or trunc) */
  1165. XX#define BT_CSIZ    30    /* # of nodes to cache readonly */
  1166. XX            /* current cache alg gives ~59% hits */
  1167. XX
  1168. XX/* this indicates a node deleted */
  1169. XX#define    BT_DELETED    1
  1170. XX#define    BT_ACTIVE    0
  1171. XX
  1172. XX#define    BT_MAGIC    0x72251
  1173. XX
  1174. XX/* btree stack */
  1175. XX#define STACK_LENGTH 30        /* length of history stacks */
  1176. XX
  1177. XXstruct btstack {
  1178. XX    long    ele[STACK_LENGTH];    /* stack elements */
  1179. XX    int    lev[STACK_LENGTH];    /* stack levels */
  1180. XX    int    sptr;            /* stack pointer */
  1181. XX};
  1182. XX
  1183. XX/* a disk resident btree super block */
  1184. XXstruct    btsuper {
  1185. XX    long    magic;        /* generic magic number */
  1186. XX    long    free;        /* pointer to next free (basically, EOF) */
  1187. XX    long    root;        /* pointer to root node */
  1188. XX    long    list;        /* number of active records */
  1189. XX};
  1190. XX
  1191. XXstruct btnode {
  1192. XX    long    recno;        /* index to external file, or whatever */
  1193. XX    long    lptr;        /* left-pointer */
  1194. XX    long    rptr;        /* right-pointer */
  1195. XX    char    key[BT_KSIZ];    /* datum */
  1196. XX    short    deleted;    /* deleted flag */
  1197. XX    short    balance;    /* balance flag */
  1198. XX};
  1199. XX#define    BTNODE    struct    btnode
  1200. XX
  1201. XX/* a memory resident btree super block */
  1202. XX/* including room to hold a disk super block */
  1203. XXstruct btree {
  1204. XX    int    fd;        /* file descriptor */
  1205. XX    int    slev;        /* history stack level */
  1206. XX    struct    btsuper    sblk;    /* copy of superblock */
  1207. XX    struct    btstack    rstak;    /* history stack */
  1208. XX    struct    btstack    lstak;    /* history stack */
  1209. XX    struct    btnode    cache[BT_CSIZ];    /* read-only cache */
  1210. XX};
  1211. XX#define    BTREE    struct    btree
  1212. XX
  1213. XXBTREE    *btopen();
  1214. XXvoid    btperror();
  1215. XX
  1216. XXextern    int    bterrno;    /* btree error number/flag */
  1217. XXextern    char    *bterrs[];    /* error message list */
  1218. XX/* error codes - match bterrs */
  1219. XX#define    BT_BAD_MAGIC    1    /* bad index file magic number */
  1220. XX#define    BT_BAD_STACK    2    /* history stack overflow */
  1221. XX#define    BT_BAD_ROOT    3    /* failed attempt to delete node 0 */
  1222. XX
  1223. XX#define _INCL_BTREE_H
  1224. XX#endif
  1225. SHAR_EOF
  1226. if test 2161 -ne "`wc -c btree.h`"
  1227. then
  1228. echo shar: error transmitting btree.h '(should have been 2161 characters)'
  1229. fi
  1230. echo shar: extracting btree.3 '(7582 characters)'
  1231. sed 's/^XX//' << \SHAR_EOF > btree.3
  1232. XX.\" btree.3l (C)1988 Marcus J. Ranum, Welch Medical Library
  1233. XX.\" $Header: btree.3,v 1.1 88/06/01 21:36:01 mjr Rel $
  1234. XX.TH BTREE 3l
  1235. XX.SH NAME
  1236. XXbtopen, btclose, btfind, btinsert, btdelete, bthead, bttail,
  1237. XXbtnext, btprevious, btsetrec, btperror
  1238. XX.br
  1239. XX\- the poor man's b-tree index library 
  1240. XX.SH SYNTAX
  1241. XX.B #include <local/btree.h>
  1242. XX.PP
  1243. XX.B BTREE *btopen(path,flags,mode)
  1244. XX.br
  1245. XX.SM
  1246. XX.B char *path;
  1247. XX.br
  1248. XX.B int flags, mode;
  1249. XX.PP
  1250. XX.B int btclose(btree)
  1251. XX.br
  1252. XX.SM
  1253. XX.B BTREE *btree;
  1254. XX.PP
  1255. XX.B int btfind(key,node_num,nodebuf,btree)
  1256. XX.br
  1257. XX.SM
  1258. XX.B char *key;
  1259. XX.br
  1260. XX.B long *node_num;
  1261. XX.br
  1262. XX.B BTNODE *nodebuf;
  1263. XX.br
  1264. XX.B BTREE btree;
  1265. XX.PP
  1266. XX.B int btinsert(key,recno,btree)
  1267. XX.br
  1268. XX.SM
  1269. XX.B char *key;
  1270. XX.br
  1271. XX.B long recno;
  1272. XX.br
  1273. XX.B BTREE btree;
  1274. XX.PP
  1275. XX.B int btdelete(number,btree)
  1276. XX.br
  1277. XX.SM
  1278. XX.B long number;
  1279. XX.br
  1280. XX.B BTREE btree;
  1281. XX.PP
  1282. XX.B int bthead(node_num,nodebuf,btree)
  1283. XX.br
  1284. XX.SM
  1285. XX.B long *node_num;
  1286. XX.br
  1287. XX.B BTNODE *nodebuf;
  1288. XX.br
  1289. XX.B BTREE *btree;
  1290. XX.PP
  1291. XX.B int bttail(node_num,nodebuf,btree)
  1292. XX.br
  1293. XX.SM
  1294. XX.B long *node_num;
  1295. XX.br
  1296. XX.B BTNODE *nodebuf;
  1297. XX.br
  1298. XX.B BTREE *btree;
  1299. XX.PP
  1300. XX.B int btnext(node_num,nodebuf,btree)
  1301. XX.br
  1302. XX.SM
  1303. XX.B long *node_num;
  1304. XX.br
  1305. XX.B BTNODE *nodebuf;
  1306. XX.br
  1307. XX.B BTREE *btree;
  1308. XX.PP
  1309. XX.B int btprevious(node_num,nodebuf,btree)
  1310. XX.br
  1311. XX.SM
  1312. XX.B long *node_num;
  1313. XX.br
  1314. XX.B BTNODE *nodebuf;
  1315. XX.br
  1316. XX.B BTREE *btree;
  1317. XX.PP
  1318. XX.B int btsetrec(number,newrec,btree)
  1319. XX.br
  1320. XX.SM
  1321. XX.B long number, newrec;
  1322. XX.br
  1323. XX.B BTREE *btree;
  1324. XX.PP
  1325. XX.B void btperror(message)
  1326. XX.br
  1327. XX.SM
  1328. XX.B char *message;
  1329. XX.SH DESCRIPTION
  1330. XX.PP
  1331. XXThe poor man's btree library is a set of routines to manage a balanced
  1332. XXbtree index file. No provisions are made for storing any data other 
  1333. XXthan the key in the btree nodes, except for a single long int that
  1334. XXcan be used as a pointer to storage elsewhere. No provisions are made
  1335. XXfor multi-user access. Currently, deleted keys are not handled
  1336. XXelegantly. They are marked as deleted, but are not re-used, which will
  1337. XXcause an index file to grow constantly, which can waste 
  1338. XXdisk space if the data is frequently modified. A read cache is 
  1339. XXmaintained, but write requests are not cached. Multiple entries for
  1340. XXthe same key are permitted, so it is the user's responsibility to specify
  1341. XXthe node number to delete. Keys are fixed-length, defined
  1342. XXin
  1343. XX.B btree.h
  1344. XXand overlong keys are silently truncated during inserts.
  1345. XXAll functions return -1 on error, 0 for success, but occasionally
  1346. XXother codes defined in
  1347. XX.B btree.h
  1348. XXfor special conditions (no record found, end of tree, etc).
  1349. XX.PP
  1350. XXThe
  1351. XX.B btopen
  1352. XXsubroutine allocates a btree control structure, using the path name
  1353. XXprovided in
  1354. XX.B path.
  1355. XXThe
  1356. XX.B flags
  1357. XXand 
  1358. XX.B mode
  1359. XXarguments are passed to open(2) to control creation and permissions.
  1360. XXIf the data file is successfully opened with 0 size (either through
  1361. XXopen(2) flags O_TRUNC or O_CREAT on a nonexistent file) a new btree
  1362. XXis initialized automatically.
  1363. XX.B Btopen
  1364. XXchecks a magic number stored in the index superblock, and will fail
  1365. XXunless the magic number is correct, to prevent accidentally using a
  1366. XXdamaged file, or a non-index file. If
  1367. XX.B btopen
  1368. XXcannot open the requested file, or encounters other problems,
  1369. XXit returns NULL.
  1370. XX.PP
  1371. XXThe
  1372. XX.B btclose
  1373. XXsubroutine closes an opened btree, and deallocates the memory that
  1374. XXwas allocated in btopen.
  1375. XX.PP
  1376. XXThe 
  1377. XX.B btfind
  1378. XXsubroutine searches for a key within the index. The argument 
  1379. XX.B key
  1380. XXis
  1381. XXsearched for, and the results of the search are placed in 
  1382. XX.B nodebuf.
  1383. XXThe number of the "found" node is placed in 
  1384. XX.B node_num.
  1385. XX.B Btree 
  1386. XXis expected to be an open, valid, btree index.
  1387. XX.B Btfind
  1388. XXreturns 0 if the requested key is located, -1 for error, or BT_NREC if
  1389. XXthe requested key was not found. If the requested key is not found,
  1390. XXthe contents of
  1391. XX.B nodebuf
  1392. XXand 
  1393. XX.b node_num
  1394. XXwill be loaded with the node that held the place in the tree directly
  1395. XXbefore where the requested node would have been. This gives
  1396. XX.B btfind
  1397. XXa limited ability for finding the nearest "like" node (though it is a
  1398. XXtoss-up whether the preceding node is "closer" than the
  1399. XXfollowing one). 
  1400. XX.PP
  1401. XXThe
  1402. XX.B btinsert
  1403. XXsubroutine creates a new node for the given
  1404. XX.B key
  1405. XXand numbers it with the requested 
  1406. XX.B recno,
  1407. XXwhich can be used to link the index to additional data elsewhere.
  1408. XXIf
  1409. XX.B btinsert
  1410. XXfails, it returns -1, otherwise it returns 0.
  1411. XX.PP
  1412. XXThe
  1413. XX.B btdelete
  1414. XXsubroutine marks node number
  1415. XX.B number
  1416. XXas deleted, which causes it to become "invisible" during future searches.
  1417. XXThe disk space is not reclaimed.
  1418. XX.B Btdelete
  1419. XXreturns 0 on success, -1 on failure. Since the node to delete is
  1420. XXreferenced only by node number,
  1421. XX.B btdelete
  1422. XXis typically used with something like
  1423. XX.B btfind
  1424. XXthat provides the node number.
  1425. XX.PP
  1426. XXThe
  1427. XX.B bthead
  1428. XXsubroutine searches to the first entry in the btree, returning the entry's
  1429. XXnode number in
  1430. XX.B node_num
  1431. XXand its data in
  1432. XX.B nodebuf.
  1433. XX.B Bthead
  1434. XXreturns 0 on success, -1 on failure.
  1435. XX.PP
  1436. XXThe
  1437. XX.B bttail
  1438. XXsubroutine searches to the last entry in the btree, but is otherwise
  1439. XXexactly the same as 
  1440. XX.B bthead.
  1441. XX.PP
  1442. XXThe
  1443. XX.B btnext
  1444. XXsubroutine finds the next node in the tree after
  1445. XX.B node_nbr
  1446. XXand places its data in
  1447. XX.B nodebuf.
  1448. XX.B Btnext
  1449. XXreturns 0 on success, -1 on failure, ande
  1450. XX.B BT_EOF
  1451. XXif it cannot search any further because it has hit the end of the tree.
  1452. XXNote that
  1453. XX.B BT_EOF
  1454. XXis a positive value, so tests like:
  1455. XX.sp
  1456. XX.ti 1i
  1457. XXwhile(btnext(&node_nbr,&nodebuf,bt) >= 0);
  1458. XX.sp
  1459. XXwill loop forever. Something like:
  1460. XX.sp
  1461. XX.ti 1i
  1462. XXwhile(btnext(&node_nbr,&nodebuf,bt) == 0);
  1463. XX.sp
  1464. XXshould be used instead. If 
  1465. XX.B node_nbr 
  1466. XXis 0L (undefined)
  1467. XX.B btnext
  1468. XXwill automatically search to the beginning of the index file, rather
  1469. XXthan starting at a random location.
  1470. XX.PP
  1471. XXThe
  1472. XX.B btprevious
  1473. XXsubroutine finds the next node in the tree before 
  1474. XX.B node_nbr
  1475. XXbut is otherwise exactly the same as 
  1476. XX.B bthead. If invoked with
  1477. XX.B node_nbr
  1478. XX0, 
  1479. XX.B btprevious
  1480. XXautomatically searches to to the end of the index file.
  1481. XX.PP
  1482. XXThe 
  1483. XX.B btsetrec
  1484. XXsubroutine allows the user to modify node number
  1485. XX.B node_nbr
  1486. XXrecord number, for whatever reason. Typically
  1487. XX.B recno
  1488. XXis used for linking the index to additional data elsewhere.
  1489. XX.PP
  1490. XXThe
  1491. XX.B btperror
  1492. XXsubroutine will print any applicable btree error messages, similarly to 
  1493. XX.B perror.
  1494. XXIf the btree error number
  1495. XX.B bterrno
  1496. XXis 0, and the UNIX
  1497. XX.B errno
  1498. XXis set, perror is called instead, to print the UNIX error. The btree
  1499. XXerror messages are accessible to the user, as an array of strings
  1500. XX.B bterrs.
  1501. XXA call to 
  1502. XX.B btperror
  1503. XXresets 
  1504. XX.B bterrno
  1505. XXautomatically.
  1506. XX.SH EXAMPLES
  1507. XX.PP
  1508. XXThe following routine inputs strings into an index:
  1509. XX.nf
  1510. XX.na
  1511. XX.ft C
  1512. XX#include <local/btree.h>
  1513. XX
  1514. XXmain(ac,av)
  1515. XXint    ac;
  1516. XXchar    *av[];
  1517. XX{
  1518. XX    BTREE    *bt;
  1519. XX    char    buf[BUFSIZ];
  1520. XX    long    recno =0L;
  1521. XX
  1522. XX    if((bt = btopen(av[1],O_CREAT,0600)) ==NULL) {
  1523. XX        btperror(av[1]);
  1524. XX        exit(1);
  1525. XX    }
  1526. XX
  1527. XX    while(gets(buf)) {
  1528. XX        if(btinsert(buf,++recno,bt)< 0) {
  1529. XX            btperror("insert");
  1530. XX            (void)btclose(bt);
  1531. XX            exit(1);
  1532. XX        }
  1533. XX    }
  1534. XX    exit(btclose(bt));
  1535. XX}
  1536. XX.ft P
  1537. XX.sp
  1538. XX.PP
  1539. XXThe following example dumps an index:
  1540. XX.ft C
  1541. XX#include <local/btree.h>
  1542. XX
  1543. XXmain(ac,av)
  1544. XXint    ac;
  1545. XXchar    *av[];
  1546. XX{
  1547. XX
  1548. XX    BTREE    *bt;
  1549. XX    BTNODE    cnode;
  1550. XX    long    nbr =0L;
  1551. XX
  1552. XX    if((bt = btopen(av[1],O_RDWR,0600)) == NULL) {
  1553. XX        btperror(av[1]);
  1554. XX        exit(1);
  1555. XX    }
  1556. XX
  1557. XX    while((btnext(&nbr, &cnode, bt) == 0) {
  1558. XX        (void)printf("%s\\n",cnode.key);
  1559. XX    }
  1560. XX    exit(btclose(bt));
  1561. XX}
  1562. XX.ft P
  1563. XX.ad
  1564. XX.SH RESTRICTIONS
  1565. XX.PP
  1566. XXFiles can get large unless copied out occasionally.
  1567. XX.PP
  1568. XXIt is not permitted to delete node number 0.
  1569. XX.PP
  1570. XX.SH DIAGNOSTICS
  1571. XXThese functions return -1 on error, 0 on success, and occasionally other
  1572. XXvalues that can signal end of file or failure to find a record.
  1573. XX.SH AUTHOR
  1574. XX.PP
  1575. XXThe original code was from a PD library for IBM PCs written by Ray Swartz.
  1576. XX90% of the code was totally re-written and restructured to make it into
  1577. XXa usable library.
  1578. XX.PP
  1579. XXMarcus J. Ranum, Welch Medical Library.
  1580. XX.br
  1581. XX.ti 1i
  1582. XXuunet!aplcen!osiris!welchvax!mjr
  1583. XX.br
  1584. XX.ti 1i
  1585. XXmjr@jhuigf.BITNET
  1586. XX.SH SEE ALSO
  1587. SHAR_EOF
  1588. if test 7582 -ne "`wc -c btree.3`"
  1589. then
  1590. echo shar: error transmitting btree.3 '(should have been 7582 characters)'
  1591. fi
  1592. echo shar: extracting bench.c '(2003 characters)'
  1593. sed 's/^XX//' << \SHAR_EOF > bench.c
  1594. XX/*
  1595. XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
  1596. XX * $Author: mjr $
  1597. XX */
  1598. XX
  1599. XX#ifndef lint
  1600. XXstatic char *RCSid="$Header: bench.c,v 1.1 88/06/01 21:34:55 mjr Rel $: bench.c";
  1601. XX#endif
  1602. XX
  1603. XX/*
  1604. XX * $Log:    bench.c,v $
  1605. XX * Revision 1.1  88/06/01  21:34:55  mjr
  1606. XX * Initial revision
  1607. XX * 
  1608. XX */
  1609. XX
  1610. XX
  1611. XX/* grosso hack to load a database and perform a bunch of */
  1612. XX/* operations on it - a sort of benchmark, but not in any */
  1613. XX/* real sense of the word */
  1614. XX
  1615. XX#ifdef BSD
  1616. XX#include <sys/file.h>
  1617. XX#endif
  1618. XX#ifdef SYSV
  1619. XX#include <sys/fcntl.h>
  1620. XX#endif
  1621. XX#include <stdio.h>
  1622. XX#include "btree.h"
  1623. XX
  1624. XXmain(ac,av)
  1625. XXint    ac;
  1626. XXchar    *av[];
  1627. XX{
  1628. XX    BTREE    *bt;
  1629. XX    BTNODE    cnod;
  1630. XX    int    fo;
  1631. XX    int    xo;
  1632. XX    long    nbr;
  1633. XX    long    time();
  1634. XX    long    random();
  1635. XX    long    start;
  1636. XX    long    end;
  1637. XX    char    buf[120];
  1638. XX
  1639. XX    if(ac < 2) {
  1640. XX        (void)fprintf(stderr,"usage: %s <file>\n",av[0]);
  1641. XX        exit(1);
  1642. XX    }
  1643. XX
  1644. XX    (void)srandom(getpid());
  1645. XX    if((bt = btopen(av[1],O_CREAT|O_TRUNC,0600)) == NULL) {
  1646. XX        btperror(av[1]);
  1647. XX        exit(1);
  1648. XX    }
  1649. XX
  1650. XX    (void)time(&start);
  1651. XX
  1652. XX    (void)fprintf(stderr,"insert 5000\n");
  1653. XX    /* insert 5000 random records */
  1654. XX    for(fo = 0; fo < 5000; fo++) {
  1655. XX        for(xo = 0; xo < ((int)random()%15)+1; xo++)
  1656. XX            buf[xo] = (int)((random()%25)+97);
  1657. XX        buf[xo] = '\0';
  1658. XX        if(btinsert(buf, bt->sblk.free, bt)<0) {
  1659. XX            btperror("insert");
  1660. XX            exit(1);
  1661. XX        }
  1662. XX    }
  1663. XX
  1664. XX    (void)fprintf(stderr,"find 5000\n");
  1665. XX    /* find 5000 random records */
  1666. XX    for(fo = 0; fo < 5000; fo++) {
  1667. XX        for(xo = 0; xo < ((int)random()%15)+1; xo++)
  1668. XX            buf[xo] = (int)((random()%25)+97);
  1669. XX        buf[xo] = '\0';
  1670. XX        if(btfind(buf, &nbr, &cnod, bt)<0) {
  1671. XX            btperror("find");
  1672. XX            exit(1);
  1673. XX        }
  1674. XX    }
  1675. XX
  1676. XX    (void)fprintf(stderr,"delete 500\n");
  1677. XX    for(fo = 0; fo < 500; fo++) {
  1678. XX        for(xo = 0; xo < ((int)random()%15)+1; xo++)
  1679. XX            buf[xo] = (int)(random()%25)+97;
  1680. XX        buf[xo] = '\0';
  1681. XX        if(btfind(buf, &nbr, &cnod, bt)<0) {
  1682. XX            btperror("find");
  1683. XX            exit(1);
  1684. XX        }
  1685. XX        if(nbr != 0L && btdelete(nbr, bt)<0) {
  1686. XX            btperror("delete");
  1687. XX            (void)fprintf(stderr,"node=%d\n",nbr);
  1688. XX            exit(1);
  1689. XX        }
  1690. XX    }
  1691. XX
  1692. XX    (void)btclose(bt);
  1693. XX    (void)time(&end);
  1694. XX    (void)fprintf(stderr,"total secs:%ld\n",end-start);
  1695. XX    exit(0);
  1696. XX}
  1697. SHAR_EOF
  1698. if test 2003 -ne "`wc -c bench.c`"
  1699. then
  1700. echo shar: error transmitting bench.c '(should have been 2003 characters)'
  1701. fi
  1702. echo shar: extracting loadtree.c '(1264 characters)'
  1703. sed 's/^XX//' << \SHAR_EOF > loadtree.c
  1704. XX/*
  1705. XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
  1706. XX * $Author: mjr $
  1707. XX */
  1708. XX
  1709. XX#ifndef lint
  1710. XXstatic char *RCSid="$Header: loadtree.c,v 1.1 88/06/01 21:35:24 mjr Rel $: loadtree.c";
  1711. XX#endif
  1712. XX
  1713. XX/*
  1714. XX * $Log:    loadtree.c,v $
  1715. XX * Revision 1.1  88/06/01  21:35:24  mjr
  1716. XX * Initial revision
  1717. XX * 
  1718. XX */
  1719. XX
  1720. XX
  1721. XX/* used to load a tree with data from the standard input - */
  1722. XX/* primarily for testing purposes - to load a file with some */
  1723. XX/* "known" data, which can then be dumped and checked, etc */
  1724. XX
  1725. XX#ifdef BSD
  1726. XX#include <sys/file.h>
  1727. XX#endif
  1728. XX#ifdef SYSV
  1729. XX#include <sys/fcntl.h>
  1730. XX#endif
  1731. XX#include <stdio.h>
  1732. XX#include "btree.h"
  1733. XX
  1734. XXmain(ac,av)
  1735. XXint    ac;
  1736. XXchar    *av[];
  1737. XX{
  1738. XX    BTREE    *bt;
  1739. XX    long    time();
  1740. XX    long    start;
  1741. XX    long    end;
  1742. XX    long    lded = 0L;
  1743. XX    char    buf[BUFSIZ];
  1744. XX
  1745. XX    if(ac < 2) {
  1746. XX        (void)fprintf(stderr,"usage: %s <file>\n",av[0]);
  1747. XX        exit(1);
  1748. XX    }
  1749. XX
  1750. XX    (void)srandom(getpid());
  1751. XX
  1752. XX    if((bt = btopen(av[1],O_CREAT,0600)) ==NULL) {
  1753. XX        btperror(av[1]);
  1754. XX        exit(1);
  1755. XX    }
  1756. XX
  1757. XX    (void)time(&start);
  1758. XX
  1759. XX    while(gets(buf)) {
  1760. XX        /* note - btinsert() truncates overlong keys */
  1761. XX        if(btinsert(buf, bt->sblk.free, bt)< 0) {
  1762. XX            btperror("insert");
  1763. XX            (void)btclose(bt);
  1764. XX            exit(1);
  1765. XX        } else 
  1766. XX            lded++;
  1767. XX    }
  1768. XX    (void)btclose(bt);
  1769. XX    (void)time(&end);
  1770. XX    (void)fprintf(stderr,"total secs:%ld - %ld records\n",end-start,lded);
  1771. XX    exit(0);
  1772. XX}
  1773. SHAR_EOF
  1774. if test 1264 -ne "`wc -c loadtree.c`"
  1775. then
  1776. echo shar: error transmitting loadtree.c '(should have been 1264 characters)'
  1777. fi
  1778. echo shar: extracting treedump.c '(1064 characters)'
  1779. sed 's/^XX//' << \SHAR_EOF > treedump.c
  1780. XX/*
  1781. XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
  1782. XX * $Author: mjr $
  1783. XX */
  1784. XX
  1785. XX#ifndef lint
  1786. XXstatic char *RCSid="$Header: treedump.c,v 1.1 88/06/01 21:35:46 mjr Rel $: treedump.c";
  1787. XX#endif
  1788. XX
  1789. XX/*
  1790. XX * $Log:    treedump.c,v $
  1791. XX * Revision 1.1  88/06/01  21:35:46  mjr
  1792. XX * Initial revision
  1793. XX * 
  1794. XX */
  1795. XX
  1796. XX
  1797. XX/* dump a tree to the standard output */
  1798. XX
  1799. XX#ifdef BSD
  1800. XX#include <sys/file.h>
  1801. XX#endif
  1802. XX#ifdef SYSV
  1803. XX#include <sys/fcntl.h>
  1804. XX#endif
  1805. XX#include <stdio.h>
  1806. XX#include "btree.h"
  1807. XX
  1808. XXmain(ac,av)
  1809. XXint    ac;
  1810. XXchar    *av[];
  1811. XX{
  1812. XX
  1813. XX    BTREE    *bt;
  1814. XX    BTNODE    cnode;
  1815. XX    long    nbr =0L;
  1816. XX
  1817. XX    if(ac < 2) {
  1818. XX        (void)fprintf(stderr,"usage: %s <file>\n",av[0]);
  1819. XX        exit(1);
  1820. XX    }
  1821. XX
  1822. XX    if((bt = btopen(av[1],O_RDWR,0600)) == NULL) {
  1823. XX        btperror(av[1]);
  1824. XX        exit(1);
  1825. XX    }
  1826. XX
  1827. XX    /* if btnext is called with nbr = 0, it automatically winds to the */
  1828. XX    /* front of the file - as in this example */
  1829. XX    while (1) {
  1830. XX        switch (btnext(&nbr, &cnode, bt)) {
  1831. XX        case (-1):
  1832. XX            btperror("btnext");
  1833. XX            (void)btclose(bt);
  1834. XX            exit(1);
  1835. XX
  1836. XX        case (0):
  1837. XX            (void)printf("%s\n",cnode.key);
  1838. XX            break;
  1839. XX
  1840. XX        case (BT_EOF):
  1841. XX            (void)btclose(bt);
  1842. XX            exit(0);
  1843. XX        }
  1844. XX    }
  1845. XX}
  1846. SHAR_EOF
  1847. if test 1064 -ne "`wc -c treedump.c`"
  1848. then
  1849. echo shar: error transmitting treedump.c '(should have been 1064 characters)'
  1850. fi
  1851. echo shar: extracting sizes.c '(592 characters)'
  1852. sed 's/^XX//' << \SHAR_EOF > sizes.c
  1853. XX/*
  1854. XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
  1855. XX * $Author: mjr $
  1856. XX */
  1857. XX
  1858. XX#ifndef lint
  1859. XXstatic char *RCSid="$Header: sizes.c,v 1.1 88/06/01 21:35:34 mjr Rel $: sizes.c";
  1860. XX#endif
  1861. XX
  1862. XX/*
  1863. XX * $Log:    sizes.c,v $
  1864. XX * Revision 1.1  88/06/01  21:35:34  mjr
  1865. XX * Initial revision
  1866. XX * 
  1867. XX */
  1868. XX
  1869. XX
  1870. XX/* provides some minimally useful info about how big your */
  1871. XX/* data structures are */
  1872. XX
  1873. XX#include "btree.h"
  1874. XX
  1875. XXmain()
  1876. XX{
  1877. XX    (void)printf("a btree control structure is %d bytes",sizeof(BTREE));
  1878. XX    (void)printf(" (cache of %d nodes)\n",BT_CSIZ);
  1879. XX    (void)printf("a btree node is %d bytes\n",sizeof(BTNODE));
  1880. XX}
  1881. SHAR_EOF
  1882. if test 592 -ne "`wc -c sizes.c`"
  1883. then
  1884. echo shar: error transmitting sizes.c '(should have been 592 characters)'
  1885. fi
  1886. echo shar: extracting example.c '(3261 characters)'
  1887. sed 's/^XX//' << \SHAR_EOF > example.c
  1888. XX/*
  1889. XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
  1890. XX * $Author: mjr $
  1891. XX */
  1892. XX
  1893. XX#ifndef lint
  1894. XXstatic char *RCSid="$Header: example.c,v 1.1 88/06/01 21:35:15 mjr Rel $: example.c";
  1895. XX#endif
  1896. XX
  1897. XX/*
  1898. XX * $Log:    example.c,v $
  1899. XX * Revision 1.1  88/06/01  21:35:15  mjr
  1900. XX * Initial revision
  1901. XX * 
  1902. XX */
  1903. XX
  1904. XX
  1905. XX/* nobody ever writes nice test programs. in fact, this one is pretty gross */
  1906. XX/* basically, this allows exercising all the various functions of the btree */
  1907. XX/* library */
  1908. XX
  1909. XX#ifdef BSD
  1910. XX#include <sys/file.h>
  1911. XX#endif
  1912. XX#ifdef SYSV
  1913. XX#include <sys/fcntl.h>
  1914. XX#endif
  1915. XX#include <stdio.h>
  1916. XX#include "btree.h"
  1917. XX
  1918. XXextern    char    *strncpy();
  1919. XXextern    char    *strcpy();
  1920. XX
  1921. XXmain(ac,av)
  1922. XXint    ac;
  1923. XXchar    *av[];
  1924. XX{
  1925. XX    BTREE    *h1;
  1926. XX    BTNODE    cnode;
  1927. XX    char    instr[BUFSIZ];
  1928. XX    long    node_nbr;
  1929. XX
  1930. XX    if(ac < 2) {
  1931. XX        (void)fprintf(stderr,"usage: %s <file>\n",av[0]);
  1932. XX        exit(1);
  1933. XX    }
  1934. XX
  1935. XX    if((h1 = btopen(av[1],O_CREAT|O_RDWR,0600)) ==NULL) {
  1936. XX        btperror(av[1]);
  1937. XX        exit(1);
  1938. XX    }
  1939. XX
  1940. XX
  1941. XX    while (1) {
  1942. XX        (void)printf("Find  Next  Tail  Head  Prev  Insrt  Del  Quit:");
  1943. XX        if(gets(instr) == NULL)
  1944. XX            exit(btclose(h1));
  1945. XX
  1946. XX        switch (*instr) {
  1947. XX
  1948. XX        case 'f':
  1949. XX        case 'F':
  1950. XX            (void)printf("\nKey to Find: ");
  1951. XX            (void)gets(instr);
  1952. XX            (void)strncpy(instr, instr, BT_KSIZ - 1);
  1953. XX            instr[BT_KSIZ - 1] = '\0';
  1954. XX            switch(btfind(instr, &node_nbr, &cnode, h1)) {
  1955. XX            case BT_NREC:
  1956. XX                (void)printf("not found: closest before=%s\n",cnode.key);
  1957. XX                break;
  1958. XX            case -1:
  1959. XX                btperror("find");
  1960. XX                break;
  1961. XX            default:
  1962. XX                (void)printf("current=%s\n", cnode.key);
  1963. XX                break;
  1964. XX            }
  1965. XX            break;
  1966. XX
  1967. XX        case 'h':
  1968. XX        case 'H':
  1969. XX            switch(bthead(&node_nbr, &cnode, h1)) {
  1970. XX            case (-1):
  1971. XX                btperror("bthead() returns -1");
  1972. XX                continue;
  1973. XX                break;
  1974. XX            default:
  1975. XX                (void)printf("current=%s\n", cnode.key);
  1976. XX            }
  1977. XX            break;
  1978. XX
  1979. XX        case 't':
  1980. XX        case 'T':
  1981. XX            switch(bttail(&node_nbr, &cnode, h1)) {
  1982. XX            case (-1):
  1983. XX                btperror("bttail() returns -1");
  1984. XX                continue;
  1985. XX                break;
  1986. XX            default:
  1987. XX                (void)printf("current=%s\n", cnode.key);
  1988. XX            }
  1989. XX            break;
  1990. XX
  1991. XX        case 'd':
  1992. XX        case 'D':
  1993. XX            if(btdelete(node_nbr, h1) < 0) {
  1994. XX                btperror("delete failed");
  1995. XX            } else {
  1996. XX                (void)printf("...deleted\n");
  1997. XX            }
  1998. XX            break;
  1999. XX
  2000. XX        case 'n':
  2001. XX        case 'N':
  2002. XX            switch (btnext(&node_nbr, &cnode, h1)) {
  2003. XX            case (-1):
  2004. XX                btperror("btnext() returns -1");
  2005. XX                continue;
  2006. XX                break;
  2007. XX
  2008. XX            case (0):
  2009. XX                (void)printf("current=%s\n", cnode.key);
  2010. XX                break;
  2011. XX
  2012. XX            case (BT_EOF):
  2013. XX                (void)printf("end of file: current=%s\n",cnode.key);
  2014. XX                break;
  2015. XX            }
  2016. XX            break;
  2017. XX
  2018. XX        case 'p':
  2019. XX        case 'P':
  2020. XX            switch (btprevious(&node_nbr, &cnode, h1)) {
  2021. XX            case (-1):
  2022. XX                btperror("btprevious() returns -1");
  2023. XX                continue;
  2024. XX                break;
  2025. XX            case (0):
  2026. XX                (void)printf("current=%s\n", cnode.key);
  2027. XX                break;
  2028. XX            case (BT_EOF):
  2029. XX                (void)printf("start of file: current=%s\n",cnode.key);
  2030. XX            }
  2031. XX            break;
  2032. XX
  2033. XX        case 'i':
  2034. XX        case 'I':
  2035. XX            (void)printf("Enter a key: ");
  2036. XX            (void)gets(instr);
  2037. XX            (void)strncpy(cnode.key, instr, BT_KSIZ);
  2038. XX            cnode.key[BT_KSIZ - 1] = '\0';
  2039. XX
  2040. XX            /* h1->sblk.free is used here as arbitrary record # */
  2041. XX            /* typical use would be to set this to the recno */
  2042. XX            /* for whatever it is that is being indexed into */
  2043. XX            if(btinsert(cnode.key, h1->sblk.free, h1) < 0)
  2044. XX                btperror("insert failed");
  2045. XX            else
  2046. XX                (void)printf("...inserted\n");
  2047. XX            break;
  2048. XX
  2049. XX        case 'q':
  2050. XX        case 'Q':
  2051. XX            exit(btclose(h1));
  2052. XX
  2053. XX        default:
  2054. XX            (void)printf("huh?\n");
  2055. XX        }
  2056. XX    }
  2057. XX}
  2058. SHAR_EOF
  2059. if test 3261 -ne "`wc -c example.c`"
  2060. then
  2061. echo shar: error transmitting example.c '(should have been 3261 characters)'
  2062. fi
  2063. #    End of shell archive
  2064. exit 0
  2065.