home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume9 / umdb / part01 next >
Encoding:
Text File  |  1989-12-12  |  35.0 KB  |  1,422 lines
  1. Newsgroups: comp.sources.misc
  2. subject: v09i063: umdb - UUCP Map Database - part 01/02
  3. from: allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc)
  4. Reply-To: wht%n4hgf@gatech.edu (Warren Tucker)
  5.  
  6. Posting-number: Volume 9, Issue 63
  7. Submitted-by: wht%n4hgf@gatech.edu (Warren Tucker)
  8. Archive-name: umdb/part01
  9.  
  10. This gaggle of programs uses a btree database to play around with masses
  11. of UUCP maps.  The stuff is not so much a finished product as a toolbox
  12. for development of map-grokking tools.  They are not efficient, but
  13. might be useful.  For more details, see the README
  14.  
  15. UMDBUILD builds the database.
  16.  
  17. UMDBDUP prints duplicate system names.
  18.  
  19. UMDBPATH prints expanded path information.  IT CURRENTLY WORKS ONLY IF
  20. YOU HAVE SMAIL (by 'smail -A').
  21.  
  22. ---- Cut Here and unpack ----
  23. #!/bin/sh
  24. # This is umdb, a shell archive (shar 3.04)
  25. # made 12/11/1989 01:41 UTC by gatech!kd4nc!n4hgf!wht (wht%n4hgf@gatech.edu)
  26. # Source directory /u4/src/umdb
  27. #
  28. # existing files WILL be overwritten
  29. #
  30. # This is part 1 of a multipart archive                                    
  31. # do not concatenate these parts, unpack them in order with /bin/sh        
  32. #
  33. # This shar contains:
  34. #    README
  35. #    Makefile
  36. #    btree.h
  37. #    funcdefs.h
  38. #    umdb.h
  39. #    btree.c
  40. #    diagnose.c
  41. #    umdbdup.c
  42. #    umdbpath.c
  43. #    umdbuild.c
  44. #    umdbutil.c
  45. #
  46. touch 2>&1 | fgrep '[-amc]' > /tmp/s3_touch$$
  47. if [ -s /tmp/s3_touch$$ ]
  48. then
  49.     TOUCH=can
  50. else
  51.     TOUCH=cannot
  52. fi
  53. rm -f /tmp/s3_touch$$
  54. if test -r s3_seq_.tmp
  55. then echo "Must unpack archives in sequence!"
  56.      next=`cat s3_seq_.tmp`; echo "Please unpack part $next next"
  57.      exit 1; fi
  58. echo "x - extracting README (Text)"
  59. sed 's/^X//' << 'SHAR_EOF' > README &&
  60. XUMDB Release x1.00 - Sun Dec 10 20:37:46 EST 1989
  61. X
  62. XThis gaggle of programs uses a btree database to play around with masses
  63. Xof UUCP maps.  The stuff is not so much a finished product as a toolbox
  64. Xfor development of map-grokking tools.  They are not efficient, but
  65. Xmight be useful.
  66. X
  67. XTO MAKE:
  68. X---------------------------------------------------------------------
  69. XEdit the Makefile if you are not running on SCO UNIX or XENIX 386 or
  70. Xa Pyramid in the BSD universe.  Note that I have only tested the 
  71. Xprograms on SCO UNIX/XENIX and a Pyramid. It hasn't been tested, but
  72. Xsome #defines are in the code for Sun.
  73. X
  74. XAdd to CFLAGS:
  75. X-DBSD4 for a BSD or Sun system.
  76. X-M2l for a XENIX 286 system.  M_SYS5 provided by the compiler will do
  77. Xthe rest.
  78. XPyramid from the att universe, 'ucb make' :-).
  79. X
  80. XUMDBUILD
  81. X---------------------------------------------------------------------
  82. XUMDBUILD builds the database.  To do it:
  83. Xsu root
  84. Xcd /.../.../map_directory
  85. Xumdbbuild /.../.../map_directory/[du].*
  86. XThis places the output database into /usr/lib/uucp/umdb.
  87. XA name index is placed in /usr/lib/uucp/umdb.in.
  88. XCode is present in the program to build a location index in
  89. X/usr/lib/uucp/umdb.il, but since no programs use it, production
  90. Xis turned off (to turn on, use -DBUILD_LOC_INDEX).
  91. X
  92. XUMDBDUP
  93. X---------------------------------------------------------------------
  94. XUMDBDUP prints duplicate system names.  Example output:
  95. Xpei (pei) in /u3/lib/pathalias/u.usa.ca.5
  96. Xpei (pei) in /u3/lib/pathalias/u.usa.ca.8
  97. Xpepper (pepper) in /u3/lib/pathalias/u.fin.1
  98. Xpepper (pepper) in /u3/lib/pathalias/u.usa.co.1
  99. Xpporta (pporta) in /u3/lib/pathalias/u.usa.az.1
  100. Xpporta (pporta) in /u3/lib/pathalias/u.usa.ok.1
  101. Xsoft (softcon) in /u3/lib/pathalias/u.deu.2
  102. Xsoft (intra) in /u3/lib/pathalias/u.grc.1
  103. Xsssphx (sssphx) in /u3/lib/pathalias/u.usa.az.1
  104. Xsssphx (sssphx) in /u3/lib/pathalias/u.usa.ca.5
  105. X
  106. XUMDBPATH
  107. X---------------------------------------------------------------------
  108. XUMDBPATH prints expanded path information.  IT CURRENTLY WORKS ONLY IF
  109. XYOU HAVE SMAIL (by 'smail -A').  I would love to receive patches
  110. Xfrom folks who get it working with other path generators.
  111. XExample output (from n4hgf perspective):
  112. X
  113. X% umdbpath sco
  114. Xpath: kd4nc!gatech!ames!sun!sco
  115. Xkd4nc                     33.7500 N  82.3833 W city (u.usa.ga.1)
  116. X.gatech.edu               33.7753 N  84.3947 W      (u.usa.ga.1)
  117. Xames                      37.4172 N 122.0575 W      (u.usa.ca.2)
  118. Xsun                       37.4289 N 122.0969 W      (u.usa.ca.8)
  119. Xsco                       36.9667 N 122.0500 W city (u.usa.ca.8)
  120. X
  121. X% umdbpath proxima
  122. Xpath: kd4nc!gatech!ames!lll-winken!ddsw1!olsa99!tabbs!proxima
  123. Xkd4nc                     33.7500 N  82.3833 W city (u.usa.ga.1)
  124. X.gatech.edu               33.7753 N  84.3947 W      (u.usa.ga.1)
  125. Xames                      37.4172 N 122.0575 W      (u.usa.ca.2)
  126. Xlll-winken                37.6839 N 121.7106 W      (u.usa.ca.6)
  127. Xddsw1                     42.2833 N  87.9667 W city (u.usa.il.1)
  128. Xolsa99                    26.0000 S  27.0000 E      (u.zaf.1)
  129. Xtabbs                     26.0000 S  27.0000 E      (u.zaf.1)
  130. Xproxima                    0.0000 N   0.0000 W ??   (u.zaf.1)
  131. X
  132. X% umdbpath oz
  133. Xpath: kd4nc!gatech!mailrus!uunet!munnari
  134. Xkd4nc                     33.7500 N  82.3833 W city (u.usa.ga.1)
  135. X.gatech.edu               33.7753 N  84.3947 W      (u.usa.ga.1)
  136. Xmailrus                   42.2889 N  83.7144 W      (u.usa.mi.2)
  137. X.uu.net                   38.8833 N  77.0667 W      (u.usa.va.2)
  138. Xmunnari not found: munnari.oz.au seems to match
  139. Xmunnari.oz.au             37.8086 S 144.9617 E      (u.aus.vic.1)
  140. X
  141. X^^^^^^^^^^^^^^^^^^^^^^^  ^^^^^^^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^
  142. X1st name on #N line       latitude, latitude         basename of map
  143. X
  144. X-N SWITCH
  145. X---------------------------------------------------------------------
  146. XAll of the above programs accept an optional -n <umdb> to specify
  147. Xa database other than /u3/lib/uucp/umdb.
  148. X
  149. Xumdbbuild -n foo u.*
  150. X
  151. Xbuilds the databse in ./foo and the index in ./foo.in.
  152. X
  153. XDIAGNOSE
  154. X---------------------------------------------------------------------
  155. XDIAGNOSE is not made by default, but is included for those who want
  156. Xto hack on or debug the btree.  Thanks for the btree source to Marcus
  157. XJ. Ranum, William Welch Medical Library (mjr@jhuigf.BITNET).  Much
  158. Xhacking was done on btree.c and btree.h to improve efficiency and to
  159. Xtune it for this "large" an application.  It also seemed not to work
  160. Xreal great when I first got it, and I'm still not sure it won't
  161. Xbreak, but it works fine on an SCO UNIX or XENIX 386 box and on a
  162. XPyramid.
  163. X
  164. X---------------------------------------------------------------------
  165. XWarren Tucker,  Mountain Park, Georgia     ...!gatech!kd4nc!n4hgf!wht 
  166. SHAR_EOF
  167. chmod 0644 README || echo "restore of README fails"
  168. if [ $TOUCH = can ]
  169. then
  170.     touch -m 1210204189 README
  171. fi
  172. echo "x - extracting Makefile (Text)"
  173. sed 's/^X//' << 'SHAR_EOF' > Makefile &&
  174. X#------------------------------------------------------------------
  175. X#  Makefile for umdb - UUCP Map Database programs
  176. X#    ...!gatech!emory!tridom!wht
  177. X#------------------------------------------------------------------
  178. X#+:EDITS:
  179. X#:12-09-1989-20:30-wht-creation
  180. X
  181. XSHELL = /bin/sh
  182. XCFLAGS = -Ox -DLINT_ARGS
  183. XLIB=
  184. X
  185. XSRC = \
  186. X    btree.c \
  187. X    umdbuild.c \
  188. X    umdbdup.c \
  189. X    umdbutil.c
  190. X
  191. XUMDBUILD_OBJ = \
  192. X    btree.o \
  193. X    umdbuild.o \
  194. X    umdbutil.o
  195. X
  196. XUMDBDUP_OBJ = \
  197. X    btree.o \
  198. X    umdbdup.o \
  199. X    umdbutil.o
  200. X
  201. XUMDBPATH_OBJ = \
  202. X    btree.o \
  203. X    umdbpath.o \
  204. X    umdbutil.o
  205. X
  206. XDIAGNOSE_OBJ = \
  207. X    btree.o \
  208. X    diagnose.o
  209. X
  210. Xall: umdbuild umdbdup umdbpath
  211. X
  212. Xumdbuild: $(UMDBUILD_OBJ)
  213. X    cc -o $@ $(UMDBUILD_OBJ) $(LIB)
  214. X
  215. Xumdbdup: $(UMDBDUP_OBJ)
  216. X    cc -o $@ $(UMDBDUP_OBJ) $(LIB)
  217. X
  218. Xumdbpath: $(UMDBPATH_OBJ)
  219. X    cc -o $@ $(UMDBPATH_OBJ) $(LIB)
  220. X
  221. Xdiagnose: $(DIAGNOSE_OBJ)
  222. X    cc -o $@ $(DIAGNOSE_OBJ) $(LIB)
  223. X
  224. X# using this method, can only build with MSC compiler
  225. Xlint:
  226. X    ls $(SRC) > src.fls
  227. X    echo ' '> funcdefs.h
  228. X    csh ./zgcc src.fls funcdefs.h
  229. X
  230. Xshar:
  231. X    shar -c -numdb -o/tmp/umdb. -l36 README Makefile *.h *.c
  232. SHAR_EOF
  233. chmod 0644 Makefile || echo "restore of Makefile fails"
  234. if [ $TOUCH = can ]
  235. then
  236.     touch -m 1210202889 Makefile
  237. fi
  238. echo "x - extracting btree.h (Text)"
  239. sed 's/^X//' << 'SHAR_EOF' > btree.h &&
  240. X/*+-------------------------------------------------------------------------
  241. X    btree.h
  242. X    hacked by ...!gatech!kd4nc!n4hgf!wht
  243. X
  244. XCopyright (C) 1988, Marcus J.  Ranum, William Welch Medical Library
  245. X$Author: mjr $ $Log: btree.c,v $ Revision 1.1 88/06/01 21:35:07 mjr
  246. XInitial revision
  247. XThe original code was placed in the public domain.  This is not, since I
  248. Xwish to retain some control over it.  No restrictions are placed on
  249. Xmodification, or use of this code, as long as the copyrights are not
  250. Xremoved.  There are some areas that really could use improving (like
  251. Xhandling free nodes better) and I hope that if someone makes
  252. Ximprovements they will keep me up to date on them (e-mail please, I am
  253. Xnot on usenet).
  254. XMarcus J. Ranum, William Welch Medical Library, 1988
  255. Xmjr@jhuigf.BITNET || uunet!mimsy!aplcen!osiris!welchvax!mjr
  256. X--------------------------------------------------------------------------*/
  257. X/*+:EDITS:*/
  258. X/*:12-10-1989-18:03-wht-make cache much larger */
  259. X/*:12-17-1988-19:52-wht-released 1.20  */
  260. X/*:12-16-1988-20:38-wht-variable max key length */
  261. X/*:12-16-1988-18:22-afterlint-creation */
  262. X
  263. X#ifndef _INCL_BTREE_H
  264. X#define _INCL_BTREE_H 1
  265. X
  266. X#define BT_NREC    1    /* no such record */
  267. X#define BT_EOF    2    /* end of the tree (either end) */
  268. X#define BT_ERR    -1    /* something went wrong */
  269. X
  270. X#define BT_KSIZ    60    /* size of keys to store (or trunc) */
  271. X#define BT_CSIZ    4096    /* # of nodes to cache (power of two) */
  272. X
  273. X/* this indicates a node deleted */
  274. X#define    BT_DELETED    1
  275. X#define    BT_ACTIVE    0
  276. X
  277. X#define    BT_MAGIC    0x0BB1
  278. X
  279. X/* btree stack */
  280. X#define STACK_LENGTH 30        /* length of history stacks */
  281. X
  282. Xstruct btstack {
  283. X    short    ele[STACK_LENGTH];    /* stack elements */
  284. X    short    lev[STACK_LENGTH];    /* stack levels */
  285. X    short    sptr;                /* stack pointer */
  286. X};
  287. X
  288. X/* a disk resident btree super block */
  289. Xstruct    btsuper {
  290. X    short    magic;        /* magic number */
  291. X    short    keysize;    /* maximum length of key */
  292. X    short    root;        /* pointer to root node */
  293. X    short    free;        /* pointer to next free (basically, EOF) */
  294. X    short    list;        /* number of active records */
  295. X};
  296. X
  297. Xstruct btnode {
  298. X    long    recno;        /* index to external file, or whatever */
  299. X    short    lptr;        /* left-pointer */
  300. X    short    rptr;        /* right-pointer */
  301. X    char    deleted;    /* deleted flag */
  302. X    char    balance;    /* balance flag */
  303. X};
  304. X#define    BTNODE    struct    btnode
  305. X
  306. Xstruct btnode_m
  307. X{
  308. X    struct btnode n;        /* keep these two ... */
  309. X    char key[BT_KSIZ];        /* ... fields FIRST !!! */
  310. X    short node_num;            /* disk node number */
  311. X    short dirty;            /* if true, cache item needs writing to disk */
  312. X};
  313. X
  314. X/* a memory resident btree super block */
  315. X/* including room to hold a disk super block */
  316. Xstruct btree
  317. X{
  318. X    int        fd;                /* file descriptor */
  319. X    struct    btsuper    sblk;    /* copy of superblock */
  320. X    struct    btstack    rstak;    /* history stack */
  321. X    struct    btstack    lstak;    /* history stack */
  322. X    struct    btnode_m *cache[BT_CSIZ];    /* read-only cache */
  323. X    short    rdonly;            /* true if file opened read-only */
  324. X    short    slev;            /* history stack level */
  325. X};
  326. X#define    BTREE    struct    btree
  327. X
  328. XBTREE    *btopen();
  329. Xvoid    btperror();
  330. X
  331. Xextern    int    bterrno;    /* btree error number/flag */
  332. Xextern    char    *bterrs[];    /* error message list */
  333. X/* error codes - match bterrs */
  334. X#define    BT_BAD_MAGIC    1    /* bad index file magic number */
  335. X#define    BT_BAD_STACK    2    /* history stack overflow */
  336. X#define    BT_BAD_ROOT    3    /* failed attempt to delete node 0 */
  337. X#define BT_BAD_KSIZ    4    /* keysize at open does not match index keysize */
  338. X#define BT_BAD_MEMORY    5    /* memory allocation failed */
  339. X#define BT_BAD_SBLK    6    /* bad superblock */
  340. X#define BT_BAD_WSUPER    7    /* error writing superblock */
  341. X#define BT_BAD_WNODE    8    /* error writing node */
  342. X#define BT_BAD_RNODE    9    /* error reading node */
  343. X#define BT_BAD_FLUSH    10    /* error flushing node */
  344. X
  345. X#endif /*_INCL_BTREE_H */
  346. X/* vi: set tabstop=4 shiftwidth=4: */
  347. X/* end of btree.h */
  348. SHAR_EOF
  349. chmod 0644 btree.h || echo "restore of btree.h fails"
  350. if [ $TOUCH = can ]
  351. then
  352.     touch -m 1210180489 btree.h
  353. fi
  354. echo "x - extracting funcdefs.h (Text)"
  355. sed 's/^X//' << 'SHAR_EOF' > funcdefs.h &&
  356. X/*+-----------------------------------------------------------------------
  357. X    funcdefs.h
  358. X------------------------------------------------------------------------*/
  359. X/*+:EDITS:*/
  360. X/*:12-10-1989-15:27-afterlint-creation */
  361. X
  362. X#ifndef BUILDING_LINT_ARGS
  363. X#ifdef LINT_ARGS
  364. X
  365. X/* btree.c */
  366. Xint _bthead(short *,struct btnode_m *,struct btree *);
  367. Xint _btnext(short *,struct btnode_m *,struct btree *);
  368. Xint _btprevious(short *,struct btnode_m *,struct btree *);
  369. Xint _bttail(short *,struct btnode_m *,struct btree *);
  370. Xint _flush_cache_node(struct btree *,struct btnode_m *);
  371. Xint _pushl(struct btree *,short );
  372. Xint _pushr(struct btree *,short );
  373. Xint _rnode(short ,struct btnode_m *,struct btree *);
  374. Xint _wnode(short ,struct btnode_m *,struct btree *);
  375. Xint _wsuper(struct btree *);
  376. Xint btclose(struct btree *);
  377. Xint btdelete(short ,struct btree *);
  378. Xint btfind(char *,short *,char **,long *,struct btree *);
  379. Xint btflush(struct btree *);
  380. Xint bthead(short *,char **,long *,struct btree *);
  381. Xint btinsert(char *,long ,struct btree *);
  382. Xint btnext(short *,char **,long *,struct btree *);
  383. Xint btprevious(short *,char **,long *,struct btree *);
  384. Xint btsetrec(short ,long ,struct btree *);
  385. Xint bttail(short *,char **,long *,struct btree *);
  386. Xshort _popl(struct btree *);
  387. Xshort _popr(struct btree *);
  388. Xstruct btree *btopen(char *,int ,int ,int );
  389. Xvoid _btlink(int ,struct btnode *,int ,struct btnode *);
  390. Xvoid _linknbr(int ,struct btnode *,short );
  391. Xvoid _nbrlink(short *,int ,struct btnode *);
  392. Xvoid _nodebal(int ,struct btnode *,struct btnode *,struct btnode *);
  393. Xvoid btperror(char *);
  394. X/* umdbdup.c */
  395. Xint main(int ,char **,char **);
  396. Xvoid print_dup_umdb_rec(long );
  397. X/* umdbuild.c */
  398. Xint main(int ,char **,char **);
  399. Xvoid mapfile_to_mapdb(char *);
  400. X/* umdbutil.c */
  401. Xchar *arg_token(char *,char *);
  402. Xchar *normalize_location(char *);
  403. Xchar *normalized_loc_to_str(char *);
  404. Xint array_to_angle(char **,int ,double *);
  405. Xvoid build_arg_array(char *,char **,int ,int *,char *);
  406. Xvoid build_dbfld_array(char *,char **,int ,int *);
  407. Xvoid build_normalized_locfld(char *,double ,double ,int );
  408. Xvoid build_sitename_array(char *,char **,int ,int *);
  409. X
  410. X#else        /* compiler doesn't know about prototyping */
  411. X
  412. X/* btree.c */
  413. Xshort _popl();
  414. Xshort _popr();
  415. Xstruct btree *btopen();
  416. Xvoid _btlink();
  417. Xvoid _linknbr();
  418. Xvoid _nbrlink();
  419. Xvoid _nodebal();
  420. Xvoid btperror();
  421. X/* umdbdup.c */
  422. Xvoid print_dup_umdb_rec();
  423. X/* umdbuild.c */
  424. Xvoid mapfile_to_mapdb();
  425. X/* umdbutil.c */
  426. Xchar *arg_token();
  427. Xchar *normalize_location();
  428. Xchar *normalized_loc_to_str();
  429. Xvoid build_arg_array();
  430. Xvoid build_dbfld_array();
  431. Xvoid build_normalized_locfld();
  432. Xvoid build_sitename_array();
  433. X
  434. X#endif /* LINT_ARGS */
  435. X#endif /* BUILDING_LINT_ARGS */
  436. X
  437. X/* end of funcdefs.h */
  438. SHAR_EOF
  439. chmod 0644 funcdefs.h || echo "restore of funcdefs.h fails"
  440. if [ $TOUCH = can ]
  441. then
  442.     touch -m 1210180489 funcdefs.h
  443. fi
  444. echo "x - extracting umdb.h (Text)"
  445. sed 's/^X//' << 'SHAR_EOF' > umdb.h &&
  446. X/*+-------------------------------------------------------------------------
  447. X    umdb.h - uucp map database definitions
  448. X    ...!gatech!emory!tridom!wht
  449. X--------------------------------------------------------------------------*/
  450. X/*+:EDITS:*/
  451. X/*:12-09-1989-18:18-wht-creation */
  452. X
  453. X#include "funcdefs.h"
  454. X
  455. X/* maximum length of system name (remember .dom.dom.ad.nauseam) */
  456. X#define SYSNAME_MAXLEN    40
  457. X
  458. X/* length of normailed location (latitude/logitude) field */
  459. X#define LOC_LEN            24    /* don't change w/o studying code */
  460. X
  461. X/* max sitenames per #N or other text line */
  462. X#define MAX_SITENAMES_PER_LINE    20    /* plenty! - avoid overflow tomorrow */
  463. X
  464. X/* max systems in a path */
  465. X#define MAX_SYSTEMS_PER_PATH    50    /* plenty! - avoid overflow tomorrow */
  466. X
  467. X/* count of fields in umdb main db record */
  468. X#define DBFLD_NLOC        0    /* normalized location */
  469. X#define DBFLD_SNAME        1    /* site name */
  470. X#define DBFLD_MNAME        2    /* map file name */
  471. X#define DBFLD_MPOS        3    /* map file position of #N line */
  472. X#define DBFLD_COUNT        4
  473. X
  474. X/* angle type definitions */
  475. X#define ANGLE_LATITUDE        1
  476. X#define ANGLE_LONGITUDE        2
  477. X#define ANGLE_BAD            -1
  478. X
  479. X/* vi: set tabstop=4 shiftwidth=4: */
  480. X/* end of umdb.h */
  481. SHAR_EOF
  482. chmod 0644 umdb.h || echo "restore of umdb.h fails"
  483. if [ $TOUCH = can ]
  484. then
  485.     touch -m 1210180489 umdb.h
  486. fi
  487. echo "x - extracting btree.c (Text)"
  488. sed 's/^X//' << 'SHAR_EOF' > btree.c &&
  489. X/*#define DEBUG*/
  490. X/*+-------------------------------------------------------------------------
  491. X    btree.c
  492. X    hacked by ...!gatech!kd4nc!n4hgf!wht
  493. X
  494. XCopyright (C) 1988, Marcus J.  Ranum, William Welch Medical Library
  495. X$Author: mjr $ $Log: btree.c,v $ Revision 1.1 88/06/01 21:35:07 mjr
  496. XInitial revision
  497. XThe original code was placed in the public domain.  This is not, since I
  498. Xwish to retain some control over it.  No restrictions are placed on
  499. Xmodification, or use of this code, as long as the copyrights are not
  500. Xremoved.  There are some areas that really could use improving (like
  501. Xhandling free nodes better) and I hope that if someone makes
  502. Ximprovements they will keep me up to date on them (e-mail please, I am
  503. Xnot on usenet).
  504. XMarcus J. Ranum, William Welch Medical Library, 1988
  505. Xmjr@jhuigf.BITNET || uunet!mimsy!aplcen!osiris!welchvax!mjr
  506. X
  507. X  Defined functions:
  508. X    _bthead(node_num,node,bt)
  509. X    _btlink(alpha1,node1,alpha2,node2)
  510. X    _btnext(node_num,node,bt)
  511. X    _btprevious(node_num,node,bt)
  512. X    _bttail(node_num,node,bt)
  513. X    _flush_cache_node(bt,cache_node)
  514. X    _linknbr(alpha,node1,node_num)
  515. X    _nbrlink(node_num,alpha,node1)
  516. X    _nodebal(alpha,node1,node2,node3)
  517. X    _popl(bt)
  518. X    _popr(bt)
  519. X    _pushl(bt,node_num)
  520. X    _pushr(bt,node_num)
  521. X    _rnode(node_num,npt,bt)
  522. X    _wnode(node_num,npt,bt)
  523. X    _wsuper(bt)
  524. X    btclose(bt)
  525. X    btdelete(node_num,bt)
  526. X    btfind(key,node_num,reckey,recno,bt)
  527. X    btflush(bt)
  528. X    bthead(node_num,key,recno,bt)
  529. X    btinsert(argkey,recno,bt)
  530. X    btnext(node_num,key,recno,bt)
  531. X    btopen(path,flags,mode,keysize)
  532. X    btperror(str)
  533. X    btprevious(node_num,key,recno,bt)
  534. X    btsetrec(node_num,newrec,bt)
  535. X    bttail(node_num,key,recno,bt)
  536. X
  537. X--------------------------------------------------------------------------*/
  538. X/*+:EDITS:*/
  539. X/*:12-09-1989-17:29-wht-get working on SCO UNIX -- just #defines */
  540. X/*:12-17-1988-17:51-wht-write sblk only at close-writes were inefficient */
  541. X/*:12-17-1988-17:51-wht-cache now read-write... writes were inefficient */
  542. X/*:12-17-1988-12:09-wht-allow open of existing index to specify zero keysize */
  543. X/*:12-16-1988-20:38-wht-variable max key length */
  544. X/*:12-16-1988-17:15-wht-static procs no longer static, but with '_' prefix */
  545. X
  546. X
  547. X#include <stdio.h>
  548. X#include <errno.h>
  549. X#include "funcdefs.h"
  550. X
  551. X#define ff fprintf
  552. X#define se stderr
  553. X
  554. X#if defined(pyr) || defined(sun) || defined(BSD4)
  555. X#include <sys/file.h>
  556. X#endif
  557. X
  558. X#if defined(M_SYS5) || defined(SYS5)
  559. X#include <sys/fcntl.h>
  560. X#define bcopy(dest,src,len) memcpy(src,dest,len)
  561. X#define bzero(dest,len) memset(dest,0,len)
  562. X#endif
  563. X
  564. X#include "btree.h"
  565. X
  566. Xlong cache_hits = 0;
  567. Xlong cache_no_hits = 0;
  568. X
  569. X#define    BT_NSIZ        (sizeof(struct btnode) + bt->sblk.keysize)
  570. X#define    BT_SSIZ        (sizeof(struct btsuper))
  571. Xlong lseek();
  572. X
  573. X/* the errno for btree problems. we use negative # - */
  574. X/* so btperror can use the real UNIX errno */
  575. Xint bterrno = 0;
  576. Xchar *bterrs[] = 
  577. X{
  578. X    "No btree error",
  579. X    "Bad index magic number (is this an index file?)",
  580. X    "History stack overflow",
  581. X    "Cannot delete node zero",
  582. X    "Open keysize does not match index keysize",
  583. X    "Memory allocation failure",
  584. X    "Bad superblock (is this an index file?)",
  585. X    "error writing superblock",
  586. X    "error writing node",
  587. X    "error reading node",
  588. X    "error flushing node",
  589. X    0
  590. X};
  591. X
  592. X/* write the btree superblock to disk */
  593. Xint
  594. X_wsuper(bt)
  595. Xstruct btree *bt;
  596. X{
  597. Xregister int save_bterrno = bterrno;
  598. X
  599. X    if(bt->rdonly)
  600. X        return(0);
  601. X
  602. X#ifdef DEBUG
  603. X    ff(se,"-------> write superblock fd=%d\n",bt->fd);
  604. X#endif
  605. X
  606. X    bterrno = BT_BAD_WSUPER;
  607. X    if(lseek(bt->fd,0L,0) < 0)
  608. X        return(BT_ERR);
  609. X
  610. X    if(write(bt->fd,(char *)&bt->sblk,BT_SSIZ) != BT_SSIZ)
  611. X        return(BT_ERR);
  612. X
  613. X    bterrno = save_bterrno;
  614. X    return(0);
  615. X}
  616. X
  617. X
  618. X
  619. X/* dynamically allocate a control structure for an open btree */
  620. Xstruct btree *
  621. Xbtopen(path,flags,mode,keysize)
  622. Xchar *path;
  623. Xregister int flags;
  624. Xregister int mode;
  625. Xregister int keysize;
  626. X{
  627. X    struct btree *bt;
  628. X    register int r;
  629. X    extern    char *malloc();
  630. X
  631. X    if(keysize)
  632. X    {
  633. X        keysize++;        /* allow for null at end of record */
  634. X        if(keysize & 1)
  635. X            keysize++;    /* keep even */
  636. X    }
  637. X    if(keysize > BT_KSIZ)
  638. X    {
  639. X        fprintf(stderr,"key size specified for %s (%d) exceeds max of %d\n",
  640. X            path,keysize,BT_KSIZ);
  641. X        exit(1);
  642. X    }
  643. X        
  644. X
  645. X    /* lets be dynamic, shall we ? */
  646. X    if((bt = (struct btree *) malloc(sizeof(struct btree))) == (BTREE *)0)
  647. X    {
  648. X        bterrno = BT_BAD_MEMORY;
  649. X        return((BTREE *)0);
  650. X    }
  651. X
  652. X    if((bt->fd = open(path,flags,mode)) > -1)
  653. X    {
  654. X#ifdef DEBUG
  655. X        ff(se,"----------> open '%s' fd=%d\n",path,bt->fd);
  656. X#endif
  657. X        r = read(bt->fd,(char *) &bt->sblk,BT_SSIZ);
  658. X
  659. X        /* if read nothing, must be a new guy, right ? */
  660. X        if(r == 0)
  661. X        {
  662. X            bt->sblk.magic = BT_MAGIC;
  663. X            bt->sblk.free = 1;
  664. X            bt->sblk.root = 0;
  665. X            bt->sblk.list = 0;
  666. X            if(keysize)
  667. X                bt->sblk.keysize = keysize;
  668. X            else
  669. X            {
  670. X                printf("cannot create new index with max keysize == 0\n");
  671. X                exit(1);
  672. X            }
  673. X
  674. X            if(_wsuper(bt) == 0)
  675. X                r = BT_SSIZ;
  676. X        }
  677. X        else if(r == BT_SSIZ)
  678. X        {
  679. X            bterrno = 0;
  680. X            if(bt->sblk.magic != BT_MAGIC)
  681. X                bterrno = BT_BAD_MAGIC;
  682. X            else if(keysize && (keysize != bt->sblk.keysize))
  683. X                bterrno = BT_BAD_KSIZ;
  684. X            if(bterrno)
  685. X            {
  686. X                close(bt->fd);
  687. X                free((char *) bt);
  688. X                return((BTREE *)0);
  689. X            }
  690. X        }
  691. X
  692. X        /* cleverly check ret value from either read or write */
  693. X        if(r != BT_SSIZ)
  694. X        {
  695. X            bterrno = BT_BAD_SBLK;
  696. X            close(bt->fd);
  697. X            free((char *) bt);
  698. X            return((BTREE *)0);
  699. X        }
  700. X    }
  701. X    else 
  702. X    {
  703. X        /* couldnt even open the bloody file */
  704. X        free((char *) bt);
  705. X        return((BTREE *)0);
  706. X    }
  707. X
  708. X    /* zero the cache -- will fail at 65535 records :-) */
  709. X    for(r = 0; r < BT_CSIZ; r++)
  710. X    {
  711. X        if((bt->cache[r] = (struct btnode_m *)malloc(sizeof(struct btnode_m)))
  712. X            == (struct btnode_m *)0)
  713. X        {
  714. X            ff(se,"no memory for cache\n");
  715. X            exit(1);
  716. X        }
  717. X        bt->cache[r]->node_num = -1;
  718. X        bt->cache[r]->dirty = 0;
  719. X    }
  720. X    bt->rdonly = ((flags & (O_WRONLY | O_RDWR)) == O_RDONLY);
  721. X
  722. X    return(bt);
  723. X}
  724. X
  725. X/* close and deallocate the control structure */
  726. Xbtclose(bt)
  727. Xstruct btree *bt;
  728. X{
  729. X    register int err = 0;
  730. X    register int icache;
  731. X
  732. X    if(!bt->rdonly)
  733. X    {
  734. X        if(err = btflush(bt))
  735. X            printf("======== ERROR WRITING TO DISK ON CLOSE ==========\n");
  736. X    }
  737. X    close(bt->fd);
  738. X    for(icache = 0; icache < BT_CSIZ; icache++)
  739. X        free((char *)bt->cache[icache]);
  740. X    free((char *) bt);
  741. X    return(err);
  742. X}
  743. X
  744. Xint
  745. X_flush_cache_node(bt,cache_node)
  746. Xstruct btree *bt;
  747. Xregister struct btnode_m *cache_node;
  748. X{
  749. Xregister int save_bterrno = bterrno;
  750. X
  751. X    if((cache_node->node_num == -1) || (!cache_node->dirty))
  752. X        return(0);
  753. X    bterrno = BT_BAD_FLUSH;
  754. X    if(lseek(bt->fd,(((long)cache_node->node_num * BT_NSIZ) + BT_SSIZ),0) < 0)
  755. X        return(BT_ERR);
  756. X    if(write(bt->fd,(char *)&cache_node->n,BT_NSIZ) != BT_NSIZ)
  757. X        return(BT_ERR);
  758. X    cache_node->dirty = 0;
  759. X    bterrno = save_bterrno;
  760. X    return(0);
  761. X}
  762. X
  763. Xint
  764. Xbtflush(bt)
  765. Xstruct btree *bt;
  766. X{
  767. X    register int icache;
  768. X    register struct btnode_m *cache_node;
  769. X
  770. X    for(icache = 0; icache < BT_CSIZ; icache++)
  771. X    {
  772. X        cache_node = bt->cache[icache];
  773. X        if(_flush_cache_node(bt,cache_node))
  774. X            return(BT_ERR);
  775. X    }
  776. X    if(_wsuper(bt))
  777. X        return(BT_ERR);
  778. X    return(0);
  779. X}
  780. X
  781. X/* write a node to cache */
  782. Xint
  783. X_wnode(node_num,npt,bt)
  784. Xregister short node_num;
  785. Xstruct btnode_m *npt;
  786. Xregister struct btree *bt;
  787. X{
  788. X    unsigned int hash = (unsigned int)node_num & (BT_CSIZ - 1);
  789. X    register struct btnode_m *cache_node = bt->cache[hash];
  790. X    extern int errno;
  791. X
  792. X#ifdef DEBUG
  793. X    ff(se,"_wnode(node_num=%d,fd=%d)\n",node_num,bt->fd);
  794. X    ff(se,"       cache node_num=%d\n",cache_node->node_num);
  795. X#endif
  796. X
  797. X    if(!node_num)
  798. X        return(0);
  799. X
  800. X    errno = 0;
  801. X    if(bt->rdonly)
  802. X    {
  803. X        errno = EPERM;    /* would be reported later */
  804. X        return(BT_ERR);
  805. X    }
  806. X    bterrno = BT_BAD_WNODE;
  807. X    if(cache_node->node_num != node_num)
  808. X    {
  809. X        if(_flush_cache_node(bt,cache_node))
  810. X            return(BT_ERR);
  811. X    }
  812. X
  813. X    /* update cache -  if the write succeeded */
  814. X    (void)bcopy((char *)npt,(char *)cache_node,sizeof(struct btnode_m));
  815. X    cache_node->node_num = node_num;
  816. X    cache_node->dirty = 1;
  817. X    bterrno = 0;
  818. X    return(0);
  819. X}
  820. X
  821. X/* read a node from disk */
  822. Xint
  823. X_rnode(node_num,npt,bt)
  824. Xregister short node_num;
  825. Xregister struct btnode_m *npt;
  826. Xregister struct btree *bt;
  827. X{
  828. X    register rdcount;
  829. X    register long readpos;
  830. X    unsigned int hash = (unsigned int)node_num & (BT_CSIZ - 1);
  831. X    register struct btnode_m *cache_node = bt->cache[hash];
  832. X    extern int errno;
  833. X
  834. X#ifdef DEBUG
  835. X    ff(se,"_rnode(node_num=%d,fd=%d)\n",node_num,bt->fd);
  836. X    ff(se,"       cache node_num=%d\n",cache_node->node_num);
  837. X#endif
  838. X
  839. X    if(!node_num)
  840. X    {
  841. X        (void)bzero((char *)npt,sizeof(struct btnode_m));
  842. X        return(0);
  843. X    }
  844. X
  845. X    errno = 0;
  846. X    bterrno = BT_BAD_RNODE;
  847. X    if(cache_node->node_num != node_num)
  848. X    {
  849. X        /* if no cache hit, load from disk */
  850. X        cache_no_hits++;
  851. X        if(!bt->rdonly)
  852. X        {
  853. X            if(_flush_cache_node(bt,cache_node))
  854. X                return(BT_ERR);
  855. X        }
  856. X        if(lseek(bt->fd,(readpos = ((long)node_num * BT_NSIZ) + BT_SSIZ),0) < 0)
  857. X            return(BT_ERR);
  858. X        if((rdcount = read(bt->fd,(char *)&cache_node->n,BT_NSIZ)) != BT_NSIZ)
  859. X        {
  860. X#ifdef DEBUG
  861. X            if(rdcount >= 0)
  862. X                ff(se,"rdcount for node %u was % (should be %d) @ %ld\n",
  863. X                    node_num,rdcount,BT_NSIZ,readpos);
  864. X#endif
  865. X            return(BT_ERR);
  866. X        }
  867. X        cache_node->node_num = node_num;
  868. X        cache_node->dirty = 0;
  869. X    }
  870. X    else
  871. X        cache_hits++;
  872. X
  873. X    (void)bcopy((char *)cache_node,(char *)npt,sizeof(struct btnode_m));
  874. X
  875. X    bterrno = 0;
  876. X    return(0);
  877. X}
  878. X
  879. Xint
  880. X_pushl(bt,node_num)
  881. Xstruct btree *bt;
  882. Xregister short node_num;
  883. X{
  884. X    if(++ (bt->lstak.sptr) >= STACK_LENGTH)
  885. X    {
  886. X        bterrno = BT_BAD_STACK;
  887. X        exit(0);
  888. X    }
  889. X    bt->lstak.ele[bt->lstak.sptr] = node_num;
  890. X    bt->lstak.lev[bt->lstak.sptr] = ++bt->slev;
  891. X    return;
  892. X}
  893. X
  894. X
  895. Xint
  896. X_pushr(bt,node_num)
  897. Xstruct btree *bt;
  898. Xregister short node_num;
  899. X{
  900. X    if(++ (bt->rstak.sptr) >= STACK_LENGTH)
  901. X    {
  902. X        bterrno = BT_BAD_STACK;
  903. X        exit(0);
  904. X    }
  905. X    bt->rstak.ele[bt->rstak.sptr] = node_num;
  906. X    bt->rstak.lev[bt->rstak.sptr] = ++bt->slev;
  907. X    return;
  908. X}
  909. X
  910. X
  911. X
  912. Xshort
  913. X_popr(bt)
  914. Xstruct btree *bt;
  915. X{
  916. X
  917. X    bt->slev = bt->rstak.lev[bt->rstak.sptr];
  918. X
  919. X    while(bt->lstak.lev[bt->lstak.sptr] > bt->slev)
  920. X        (bt->lstak.sptr)--;
  921. X
  922. X    if(bt->rstak.sptr == 0)
  923. X        return(0);
  924. X
  925. X    bt->slev--;
  926. X    return(bt->rstak.ele[(bt->rstak.sptr)--]);
  927. X}
  928. X
  929. X
  930. X
  931. Xshort
  932. X_popl(bt)
  933. Xstruct btree *bt;
  934. X{
  935. X
  936. X    bt->slev = bt->lstak.lev[bt->lstak.sptr];
  937. X
  938. X    while(bt->rstak.lev[bt->rstak.sptr] > bt->slev)
  939. X        (bt->rstak.sptr)--;
  940. X
  941. X    if(bt->lstak.sptr == 0)
  942. X        return(0);
  943. X
  944. X    bt->slev--;
  945. X    return(bt->lstak.ele[(bt->lstak.sptr)--]);
  946. X}
  947. X
  948. Xvoid
  949. X_btlink(alpha1,node1,alpha2,node2)
  950. Xregister int alpha1;
  951. Xregister int alpha2;
  952. Xstruct btnode *node1;
  953. Xstruct btnode *node2;
  954. X{
  955. X    if(alpha1 == -1 && alpha2 == -1)
  956. X        node1->lptr = node2->lptr;
  957. X    else if(alpha1 == -1 && alpha2 == 1)
  958. X        node1->lptr = node2->rptr;
  959. X    else if(alpha1 == 1 && alpha2 == -1)
  960. X        node1->rptr = node2->lptr;
  961. X    else
  962. X        node1->rptr = node2->rptr;
  963. X}
  964. X
  965. X
  966. X
  967. X/* number a link according to alpha */
  968. Xvoid
  969. X_nbrlink(node_num,alpha,node1)
  970. Xshort *node_num;
  971. Xregister int alpha;
  972. Xstruct btnode *node1;
  973. X{
  974. X    *node_num = (alpha == 1) ? node1->rptr : node1->lptr;
  975. X}
  976. X
  977. X
  978. X
  979. X/* set a link according to alpha */
  980. Xvoid
  981. X_linknbr(alpha,node1,node_num)
  982. Xregister int alpha;
  983. Xstruct btnode *node1;
  984. Xregister short node_num;
  985. X{
  986. X
  987. X    if(alpha == 1)
  988. X        node1->rptr = node_num;
  989. X    else
  990. X        node1->lptr = node_num;
  991. X}
  992. X
  993. X
  994. X
  995. Xvoid
  996. X_nodebal(alpha,node1,node2,node3)
  997. Xregister int alpha;
  998. Xstruct btnode *node1;
  999. Xstruct btnode *node2;
  1000. Xstruct btnode *node3;
  1001. X{
  1002. X
  1003. X    if(node1->balance == alpha)
  1004. X    {
  1005. X        node2->balance = -alpha;
  1006. X        node3->balance = 0;
  1007. X    }
  1008. X    else if(node1->balance == 0)
  1009. X        node2->balance = node3->balance = 0;
  1010. X    else 
  1011. X    {
  1012. X        node2->balance = 0;
  1013. X        node3->balance = alpha;
  1014. X    }
  1015. X}
  1016. X
  1017. X
  1018. X
  1019. X/* change the record number in a node */
  1020. Xbtsetrec(node_num,newrec,bt)
  1021. Xregister short node_num;
  1022. Xlong newrec;
  1023. Xstruct btree *bt;
  1024. X{
  1025. X    struct btnode_m tnode;
  1026. X
  1027. X    if(_rnode(node_num,&tnode,bt))
  1028. X        return(BT_ERR);
  1029. X
  1030. X    tnode.n.recno = newrec;
  1031. X
  1032. X    if(_wnode(node_num,&tnode,bt))
  1033. X        return(BT_ERR);
  1034. X
  1035. X    return(0);
  1036. X}
  1037. X
  1038. X/* insert the node into the tree */
  1039. Xbtinsert(argkey,recno,bt)
  1040. Xchar *argkey;
  1041. Xlong recno;
  1042. Xstruct btree *bt;
  1043. X{
  1044. X    register int compare;
  1045. X    short trec1;
  1046. X    short trec2;
  1047. X    short trec3;
  1048. X    short trec4;
  1049. X    short top;
  1050. X    struct btnode_m tnode1;
  1051. X    struct btnode_m tnode2;
  1052. X    struct btnode_m tnode3;
  1053. X    struct btnode_m tnode4;
  1054. X
  1055. X
  1056. X    /* the very first node gets inserted specially */
  1057. X    if(bt->sblk.root == 0)
  1058. X    {
  1059. X        bt->sblk.root = 1;
  1060. X        tnode1.n.balance = tnode1.n.rptr = tnode1.n.lptr = 0;
  1061. X        tnode1.n.deleted = BT_ACTIVE;
  1062. X        tnode1.n.recno = recno;
  1063. X
  1064. X        strncpy(tnode1.key,argkey,bt->sblk.keysize - 1);
  1065. X        tnode1.key[bt->sblk.keysize - 1] = '\0';
  1066. X        if(_wnode(1,&tnode1,bt) < 0)
  1067. X            return(BT_ERR);
  1068. X
  1069. X        bt->sblk.free++;
  1070. X        bt->sblk.list++;
  1071. X        return(0);
  1072. X    }
  1073. X    top = -1;
  1074. X    trec1 = bt->sblk.root;
  1075. X    trec4 = bt->sblk.root;
  1076. X    while(1)
  1077. X    {
  1078. X        if(_rnode(trec1,&tnode1,bt))
  1079. X        {
  1080. X#ifdef DEBUG
  1081. X            ff(se,"btinsert: trec1(1) read error\n");
  1082. X#endif
  1083. X            return(BT_ERR);
  1084. X        }
  1085. X        if((compare = strcmp(argkey,tnode1.key)) < 0)
  1086. X        {
  1087. X            /* (move left) */
  1088. X            trec2 = tnode1.n.lptr;
  1089. X
  1090. X            if(trec2 == 0)
  1091. X            {
  1092. X                /* insert here */
  1093. X                trec2 = bt->sblk.free++;
  1094. X                tnode1.n.lptr = trec2;
  1095. X                break;    /* loop exit */
  1096. X            }
  1097. X            else 
  1098. X            {
  1099. X                /* look again from this node */
  1100. X                if(_rnode(trec2,&tnode2,bt))
  1101. X                {
  1102. X#ifdef DEBUG
  1103. X                    ff(se,"btinsert: trec2(1) read error\n");
  1104. X#endif
  1105. X                    return(BT_ERR);
  1106. X                }
  1107. X                if(tnode2.n.balance != 0)
  1108. X                {
  1109. X                    top = trec1;
  1110. X                    trec4 = trec2;
  1111. X                }
  1112. X            }
  1113. X            trec1 = trec2;
  1114. X        }
  1115. X        else 
  1116. X        {
  1117. X            /* (move right) */
  1118. X            trec2 = tnode1.n.rptr;
  1119. X
  1120. X            if(trec2 == 0)
  1121. X            {
  1122. X                /* insert here */
  1123. X                trec2 = bt->sblk.free++;
  1124. X                tnode1.n.rptr = trec2;
  1125. X                break;    /* loop exit */
  1126. X            }
  1127. X            else 
  1128. X            {
  1129. X                /* look again from this node */
  1130. X                if(_rnode(trec2,&tnode2,bt))
  1131. X                {
  1132. X#ifdef DEBUG
  1133. X                    ff(se,"btinsert: trec2(2) read error\n");
  1134. X#endif
  1135. X                    return(BT_ERR);
  1136. X                }
  1137. X                if(tnode2.n.balance != 0)
  1138. X                {
  1139. X                    top = trec1;
  1140. X                    trec4 = trec2;
  1141. X                }
  1142. X                trec1 = trec2;
  1143. X            }
  1144. X        }
  1145. X    }
  1146. X
  1147. X    /* Step 5 (insert key at tnode2) */
  1148. X    tnode2.n.lptr = tnode2.n.rptr = 0;
  1149. X    tnode2.n.balance = 0;
  1150. X    tnode2.n.deleted = BT_ACTIVE;
  1151. X    tnode2.n.recno = recno;
  1152. X    strncpy(tnode2.key,argkey,bt->sblk.keysize - 1);
  1153. X    tnode2.key[bt->sblk.keysize - 1] = '\0';
  1154. X
  1155. X    if(_wnode(trec2,&tnode2,bt))
  1156. X        return(BT_ERR);
  1157. X    if(_wnode(trec1,&tnode1,bt))
  1158. X        return(BT_ERR);
  1159. X    if(_rnode(trec4,&tnode4,bt))
  1160. X    {
  1161. X#ifdef DEBUG
  1162. X        ff(se,"btinsert: trec4(1) read error\n");
  1163. X#endif
  1164. X        return(BT_ERR);
  1165. X    }
  1166. X
  1167. X    /* (adjust balance factors) */
  1168. X    if(strcmp(argkey,tnode4.key) < 0)
  1169. X        trec3 = trec1 = tnode4.n.lptr;
  1170. X    else 
  1171. X        trec3 = trec1 = tnode4.n.rptr;
  1172. X
  1173. X    while(trec1 != trec2)
  1174. X    {
  1175. X        if(_rnode(trec1,&tnode1,bt))
  1176. X        {
  1177. X#ifdef DEBUG
  1178. X            ff(se,"btinsert: trec1(2) read error\n");
  1179. X#endif
  1180. X            return(BT_ERR);
  1181. X        }
  1182. X        if(strcmp(argkey,tnode1.key) < 0)
  1183. X        {
  1184. X            tnode1.n.balance = -1;
  1185. X            if(_wnode(trec1,&tnode1,bt) < 0)
  1186. X                return(BT_ERR);
  1187. X            trec1 = tnode1.n.lptr;
  1188. X        }
  1189. X        else 
  1190. X        {
  1191. X            tnode1.n.balance = 1;
  1192. X            if(_wnode(trec1,&tnode1,bt) < 0)
  1193. X                return(BT_ERR);
  1194. X            trec1 = tnode1.n.rptr;
  1195. X        }
  1196. X    }
  1197. X
  1198. X    compare = (strcmp(argkey,tnode4.key) < 0) ? -1 : 1;
  1199. X    if(tnode4.n.balance == 0)
  1200. X    {
  1201. X        bt->sblk.list++;
  1202. X        tnode4.n.balance = compare;
  1203. X        if(_wnode(trec4,&tnode4,bt) < 0)
  1204. X            return(BT_ERR);
  1205. X        return(0);
  1206. X    }
  1207. X    else if(tnode4.n.balance == -compare)
  1208. X    {
  1209. X        bt->sblk.list++;
  1210. X        tnode4.n.balance = 0;
  1211. X        if(_wnode(trec4,&tnode4,bt) < 0)
  1212. X            return(BT_ERR);
  1213. X        return(0);
  1214. X    }
  1215. X    else 
  1216. X    {
  1217. X        /* (tree out of balance) */
  1218. X        bt->sblk.list++;
  1219. X        if(_rnode(trec4,&tnode4,bt))
  1220. X        {
  1221. X#ifdef DEBUG
  1222. X            ff(se,"btinsert: trec4(2) read error\n");
  1223. X#endif
  1224. X            return(BT_ERR);
  1225. X        }
  1226. X        if(_rnode(trec3,&tnode3,bt))
  1227. X        {
  1228. X#ifdef DEBUG
  1229. X            ff(se,"btinsert: trec3(1) read error\n");
  1230. X#endif
  1231. X            return(BT_ERR);
  1232. X        }
  1233. X        if(tnode3.n.balance == compare)
  1234. X        {
  1235. X            /* (single rotate) */
  1236. X            trec1 = trec3;
  1237. X            _btlink(compare,(BTNODE *) &tnode4,-compare,(BTNODE *) &tnode3);
  1238. X            _linknbr(-compare,(BTNODE *) &tnode3,trec4);
  1239. X            tnode4.n.balance = tnode3.n.balance = 0;
  1240. X        }
  1241. X        else 
  1242. X        {
  1243. X            /* (double rotate) */
  1244. X            _nbrlink(&trec1,-compare,(BTNODE *) &tnode3);
  1245. X            if(_rnode(trec1,&tnode1,bt))
  1246. X            {
  1247. X#ifdef DEBUG
  1248. X                ff(se,"btinsert: trec1(3) read error\n");
  1249. X#endif
  1250. X                return(BT_ERR);
  1251. X            }
  1252. X            _btlink(-compare,(BTNODE *) &tnode3,compare,(BTNODE *) &tnode1);
  1253. X            _linknbr(compare,(BTNODE *) &tnode1,trec3);
  1254. X            _btlink(compare,(BTNODE *) &tnode4,-compare,(BTNODE *) &tnode1);
  1255. X            _linknbr(-compare,(BTNODE *) &tnode1,trec4);
  1256. X            _nodebal(compare,(BTNODE *) &tnode1,(BTNODE *) &tnode4,(BTNODE *) &tnode3);
  1257. X            tnode1.n.balance = 0;
  1258. X            if(_wnode(trec1,&tnode1,bt))
  1259. X                return(BT_ERR);
  1260. X        }
  1261. X
  1262. X        if(top == -1)
  1263. X            bt->sblk.root = trec1;
  1264. X        else 
  1265. X        {
  1266. X            /* balanced at top of a sub-tree */
  1267. X            if(_rnode(top,&tnode2,bt) < 0)
  1268. X            {
  1269. X#ifdef DEBUG
  1270. X                ff(se,"btinsert: top(1) read error\n");
  1271. X#endif
  1272. X                return(BT_ERR);
  1273. X            }
  1274. X            if(trec4 == tnode2.n.rptr)
  1275. X                tnode2.n.rptr = trec1;
  1276. X            else
  1277. X                tnode2.n.lptr = trec1;
  1278. X            if(_wnode(top,&tnode2,bt))
  1279. X                return(BT_ERR);
  1280. X        }
  1281. X        if(_wnode(trec4,&tnode4,bt))
  1282. X            return(BT_ERR);
  1283. X        if(_wnode(trec3,&tnode3,bt))
  1284. X            return(BT_ERR);
  1285. X        return(0);
  1286. X    }
  1287. X}
  1288. X
  1289. X/* drop a node */
  1290. Xbtdelete(node_num,bt)
  1291. Xregister short node_num;
  1292. Xstruct btree *bt;
  1293. X{
  1294. X    struct btnode_m node;
  1295. X
  1296. X    if(node_num == 0)
  1297. X    {
  1298. X        bterrno = BT_BAD_ROOT;
  1299. X        return(BT_ERR);
  1300. X    }
  1301. X    else 
  1302. X    {
  1303. X        if(_rnode(node_num,&node,bt))
  1304. X            return(BT_ERR);
  1305. X        node.n.deleted = BT_DELETED;
  1306. X        if(_wnode(node_num,&node,bt))
  1307. X            return(BT_ERR);
  1308. X        else 
  1309. X            bt->sblk.list--;
  1310. X    }
  1311. X    return(0);
  1312. X}
  1313. X
  1314. X/* find the next node */
  1315. Xbtnext(node_num,key,recno,bt)
  1316. Xshort *node_num;
  1317. Xchar **key;
  1318. Xlong *recno;
  1319. Xstruct btree *bt;
  1320. X{
  1321. X    static struct btnode_m node;
  1322. X    register int retn;
  1323. X    if(_rnode(*node_num,&node,bt))
  1324. X        return(BT_ERR);
  1325. X    retn = _btnext(node_num,&node,bt);
  1326. X    *key = node.key;
  1327. X    *recno = node.n.recno;
  1328. X    return(retn);
  1329. X}
  1330. X
  1331. X
  1332. X/* find the next node */
  1333. X_btnext(node_num,node,bt)
  1334. Xshort *node_num;
  1335. Xregister struct btnode_m *node;
  1336. Xstruct btree *bt;
  1337. X{
  1338. X    short _popl();
  1339. X    short _popr();
  1340. X    short s_nod;
  1341. X
  1342. X    s_nod = *node_num;
  1343. X
  1344. X    if(*node_num == 0)
  1345. X    {
  1346. X        /* undefined current node - wind to beginning of file */
  1347. X        return(_bthead(node_num,node,bt));
  1348. X    }
  1349. X    do 
  1350. X    {
  1351. X        if(node->n.rptr == 0)
  1352. X        {
  1353. X            /* can't move right */
  1354. X            if(bt->lstak.sptr == 0)
  1355. X            {
  1356. X                /* none in stack */
  1357. X                if(_rnode(*node_num,node,bt))
  1358. X                    return(BT_ERR);
  1359. X                return(BT_EOF);
  1360. X            }
  1361. X            else 
  1362. X            {
  1363. X                /* can't go right & stack full (pop stack) */
  1364. X                s_nod = _popl(bt);
  1365. X                if(_rnode(s_nod,node,bt) < 0)
  1366. X                    return(BT_ERR);
  1367. X            }
  1368. X        }
  1369. X        else 
  1370. X        {
  1371. X            /* move right */
  1372. X            _pushr(bt,s_nod);
  1373. X            s_nod = node->n.rptr;
  1374. X            if(_rnode(s_nod,node,bt) )
  1375. X                return(BT_ERR);
  1376. X
  1377. X            while(node->n.lptr != 0)
  1378. X            {
  1379. X                /* bottom left */
  1380. X                _pushl(bt,s_nod);
  1381. X                /* of this sub-tree */
  1382. X                s_nod = node->n.lptr;
  1383. X                if(_rnode(s_nod,node,bt))
  1384. X                    return(BT_ERR);
  1385. X            }
  1386. X        }
  1387. X    } while(node->n.deleted == BT_DELETED);
  1388. X
  1389. X    *node_num = s_nod;
  1390. X    return(0);
  1391. X}
  1392. X
  1393. X/* go to the tail of the file */
  1394. Xbttail(node_num,key,recno,bt)
  1395. Xshort *node_num;
  1396. Xchar **key;
  1397. Xlong *recno;
  1398. Xstruct btree *bt;
  1399. X{
  1400. X    static struct btnode_m node;
  1401. X    register int retn = _bttail(node_num,&node,bt);
  1402. X    *key = node.key;
  1403. X    *recno = node.n.recno;
  1404. X    return(retn);
  1405. X}
  1406. X
  1407. X/* go to the tail of the file */
  1408. X_bttail(node_num,node,bt)
  1409. Xshort *node_num;
  1410. Xregister struct btnode_m *node;
  1411. Xstruct btree *bt;
  1412. X{
  1413. X    short s_nod;
  1414. X
  1415. X    bt->rstak.sptr = 0;
  1416. SHAR_EOF
  1417. echo "End of umdb part 1"
  1418. echo "File btree.c is continued in part 2"
  1419. echo "2" > s3_seq_.tmp
  1420. exit 0
  1421.  
  1422.