logo

utils-std

Collection of commonly available Unix tools git clone https://anongit.hacktivis.me/git/utils-std.git

join.c (14726B)

    

  1. /*-
  2.  * SPDX-License-Identifier: BSD-3-Clause
  3.  *
  4.  * Copyright (c) 1991, 1993, 1994
  5.  *	The Regents of the University of California.  All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Steve Hayman of the Computer Science Department, Indiana University,
  9.  * Michiro Hikida and David Goodenough.
  10.  *
  11.  * Redistribution and use in source and binary forms, with or without
  12.  * modification, are permitted provided that the following conditions
  13.  * are met:
  14.  * 1. Redistributions of source code must retain the above copyright
  15.  *    notice, this list of conditions and the following disclaimer.
  16.  * 2. Redistributions in binary form must reproduce the above copyright
  17.  *    notice, this list of conditions and the following disclaimer in the
  18.  *    documentation and/or other materials provided with the distribution.
  19.  * 3. Neither the name of the University nor the names of its contributors
  20.  *    may be used to endorse or promote products derived from this software
  21.  *    without specific prior written permission.
  22.  *
  23.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33.  * SUCH DAMAGE.
  34.  */
  36. #define _BSD_SOURCE
  38. #include <err.h>
  39. #include <errno.h>
  40. #include <limits.h>
  41. #include <locale.h>
  42. #include <stdio.h>
  43. #include <stdlib.h>
  44. #include <string.h>
  45. #include <sys/param.h>
  46. #include <unistd.h>
  47. #include <wchar.h>
  49. /*
  50.  * There's a structure per input file which encapsulates the state of the
  51.  * file.  We repeatedly read lines from each file until we've read in all
  52.  * the consecutive lines from the file with a common join field.  Then we
  53.  * compare the set of lines with an equivalent set from the other file.
  54.  */
  55. typedef struct
  56. {
  57. 	char *line;               /* line */
  58. 	unsigned long linealloc;  /* line allocated count */
  59. 	char **fields;            /* line field(s) */
  60. 	unsigned long fieldcnt;   /* line field(s) count */
  61. 	unsigned long fieldalloc; /* line field(s) allocated count */
  62. } LINE;
  64. typedef struct
  65. {
  66. 	FILE *fp;             /* file descriptor */
  67. 	unsigned long joinf;  /* join field (-1, -2, -j) */
  68. 	int unpair;           /* output unpairable lines (-a) */
  69. 	unsigned long number; /* 1 for file 1, 2 for file 2 */
  71. 	LINE *set;              /* set of lines with same field */
  72. 	int pushbool;           /* if pushback is set */
  73. 	unsigned long pushback; /* line on the stack */
  74. 	unsigned long setcnt;   /* set count */
  75. 	unsigned long setalloc; /* set allocated count */
  76. } INPUT;
  77. static INPUT input1 = {NULL, 0, 0, 1, NULL, 0, 0, 0, 0}, input2 = {NULL, 0, 0, 2, NULL, 0, 0, 0, 0};
  79. typedef struct
  80. {
  81. 	unsigned long filenum; /* file number */
  82. 	unsigned long fieldno; /* field number */
  83. } OLIST;
  84. static OLIST *olist;             /* output field list */
  85. static unsigned long olistcnt;   /* output field list count */
  86. static unsigned long olistalloc; /* output field allocated count */
  88. static int joinout = 1; /* show lines with matched join fields (-v) */
  89. static int needsep;     /* need separator character */
  90. static int spans = 1;   /* span multiple delimiters (-t) */
  91. static char *empty;     /* empty field replacement string (-e) */
  92. static wchar_t default_tabchar[] = L" \t";
  93. static wchar_t *tabchar = default_tabchar; /* delimiter characters (-t) */
  95. static int cmp(LINE *, unsigned long, LINE *, unsigned long);
  96. static void fieldarg(char *);
  97. static void joinlines(INPUT *, INPUT *);
  98. static int mbscoll(const char *, const char *);
  99. static char *mbssep(char **, const wchar_t *);
  100. static void outfield(LINE *, unsigned long, int);
  101. static void outoneline(INPUT *, LINE *);
  102. static void outtwoline(INPUT *, LINE *, INPUT *, LINE *);
  103. static void slurp(INPUT *);
  104. static wchar_t *towcs(const char *);
  105. static void usage(void);
  107. int
  108. main(int argc, char *argv[])
  109. {
  110. 	INPUT *F1, *F2;
  111. 	int aflag, ch, cval, vflag;
  112. 	char *end;
  114. 	setlocale(LC_ALL, "");
  116. 	F1 = &input1;
  117. 	F2 = &input2;
  119. 	aflag = vflag = 0;
  120. 	while((ch = getopt(argc, argv, "a:e:j:1:2:o:t:v:")) != -1)
  121. 	{
  122. 		switch(ch)
  123. 		{
  124. 		case '1':
  125. 			if((F1->joinf = strtol(optarg, &end, 10)) < 1) errx(1, "-1 option field number less than 1");
  126. 			if(*end) errx(1, "illegal field number -- %s", optarg);
  127. 			--F1->joinf;
  128. 			break;
  129. 		case '2':
  130. 			if((F2->joinf = strtol(optarg, &end, 10)) < 1) errx(1, "-2 option field number less than 1");
  131. 			if(*end) errx(1, "illegal field number -- %s", optarg);
  132. 			--F2->joinf;
  133. 			break;
  134. 		case 'a':
  135. 			aflag = 1;
  136. 			switch(strtol(optarg, &end, 10))
  137. 			{
  138. 			case 1:
  139. 				F1->unpair = 1;
  140. 				break;
  141. 			case 2:
  142. 				F2->unpair = 1;
  143. 				break;
  144. 			default:
  145. 				errx(1, "-a option file number not 1 or 2");
  146. 				break;
  147. 			}
  148. 			if(*end) errx(1, "illegal file number -- %s", optarg);
  149. 			break;
  150. 		case 'e':
  151. 			empty = optarg;
  152. 			break;
  153. 		case 'j':
  154. 			if((F1->joinf = F2->joinf = strtol(optarg, &end, 10)) < 1)
  155. 				errx(1, "-j option field number less than 1");
  156. 			if(*end) errx(1, "illegal field number -- %s", optarg);
  157. 			--F1->joinf;
  158. 			--F2->joinf;
  159. 			break;
  160. 		case 'o':
  161. 			fieldarg(optarg);
  162. 			break;
  163. 		case 't':
  164. 			spans = 0;
  165. 			if(mbrtowc(&tabchar[0], optarg, MB_LEN_MAX, NULL) != strlen(optarg))
  166. 				errx(1, "illegal tab character specification");
  167. 			tabchar[1] = L'\0';
  168. 			break;
  169. 		case 'v':
  170. 			vflag = 1;
  171. 			joinout = 0;
  172. 			switch(strtol(optarg, &end, 10))
  173. 			{
  174. 			case 1:
  175. 				F1->unpair = 1;
  176. 				break;
  177. 			case 2:
  178. 				F2->unpair = 1;
  179. 				break;
  180. 			default:
  181. 				errx(1, "-v option file number not 1 or 2");
  182. 				break;
  183. 			}
  184. 			if(*end) errx(1, "illegal file number -- %s", optarg);
  185. 			break;
  186. 		case '?':
  187. 		default:
  188. 			usage();
  189. 		}
  190. 	}
  191. 	argc -= optind;
  192. 	argv += optind;
  194. 	if(aflag && vflag) errx(1, "the -a and -v options are mutually exclusive");
  196. 	if(argc != 2) usage();
  198. 	/* Open the files; "-" means stdin. */
  199. 	if(!strcmp(*argv, "-"))
  200. 		F1->fp = stdin;
  201. 	else if((F1->fp = fopen(*argv, "r")) == NULL)
  202. 		err(1, "%s", *argv);
  203. 	++argv;
  204. 	if(!strcmp(*argv, "-"))
  205. 		F2->fp = stdin;
  206. 	else if((F2->fp = fopen(*argv, "r")) == NULL)
  207. 		err(1, "%s", *argv);
  208. 	if(F1->fp == stdin && F2->fp == stdin) errx(1, "only one input file may be stdin");
  210. 	slurp(F1);
  211. 	slurp(F2);
  212. 	while(F1->setcnt && F2->setcnt)
  213. 	{
  214. 		cval = cmp(F1->set, F1->joinf, F2->set, F2->joinf);
  215. 		if(cval == 0)
  216. 		{
  217. 			/* Oh joy, oh rapture, oh beauty divine! */
  218. 			if(joinout) joinlines(F1, F2);
  219. 			slurp(F1);
  220. 			slurp(F2);
  221. 		}
  222. 		else if(cval < 0)
  223. 		{
  224. 			/* File 1 takes the lead... */
  225. 			if(F1->unpair) joinlines(F1, NULL);
  226. 			slurp(F1);
  227. 		}
  228. 		else
  229. 		{
  230. 			/* File 2 takes the lead... */
  231. 			if(F2->unpair) joinlines(F2, NULL);
  232. 			slurp(F2);
  233. 		}
  234. 	}
  236. 	/*
  237. 	 * Now that one of the files is used up, optionally output any
  238. 	 * remaining lines from the other file.
  239. 	 */
  240. 	if(F1->unpair)
  241. 		while(F1->setcnt)
  242. 		{
  243. 			joinlines(F1, NULL);
  244. 			slurp(F1);
  245. 		}
  246. 	if(F2->unpair)
  247. 		while(F2->setcnt)
  248. 		{
  249. 			joinlines(F2, NULL);
  250. 			slurp(F2);
  251. 		}
  252. 	exit(0);
  253. }
  255. static void
  256. slurp(INPUT *F)
  257. {
  258. 	LINE *lp, *lastlp, tmp;
  259. 	size_t len;
  260. 	int cnt;
  261. 	char *bp, *fieldp;
  263. 	/*
  264. 	 * Read all of the lines from an input file that have the same
  265. 	 * join field.
  266. 	 */
  267. 	F->setcnt = 0;
  268. 	for(lastlp = NULL;; ++F->setcnt)
  269. 	{
  270. 		/*
  271. 		 * If we're out of space to hold line structures, allocate
  272. 		 * more.  Initialize the structure so that we know that this
  273. 		 * is new space.
  274. 		 */
  275. 		if(F->setcnt == F->setalloc)
  276. 		{
  277. 			cnt = F->setalloc;
  278. 			F->setalloc += 50;
  279. 			if((F->set = realloc(F->set, F->setalloc * sizeof(LINE))) == NULL) err(1, NULL);
  280. 			memset(F->set + cnt, 0, 50 * sizeof(LINE));
  282. 			/* re-set lastlp in case it moved */
  283. 			if(lastlp != NULL) lastlp = &F->set[F->setcnt - 1];
  284. 		}
  286. 		/*
  287. 		 * Get any pushed back line, else get the next line.  Allocate
  288. 		 * space as necessary.  If taking the line from the stack swap
  289. 		 * the two structures so that we don't lose space allocated to
  290. 		 * either structure.  This could be avoided by doing another
  291. 		 * level of indirection, but it's probably okay as is.
  292. 		 */
  293. 		lp = &F->set[F->setcnt];
  294. 		if(F->setcnt) lastlp = &F->set[F->setcnt - 1];
  295. 		if(F->pushbool)
  296. 		{
  297. 			tmp = F->set[F->setcnt];
  298. 			F->set[F->setcnt] = F->set[F->pushback];
  299. 			F->set[F->pushback] = tmp;
  300. 			F->pushbool = 0;
  301. 			continue;
  302. 		}
  303. 		if((bp = fgetln(F->fp, &len)) == NULL) return;
  304. 		if(lp->linealloc <= len + 1)
  305. 		{
  306. 			lp->linealloc += MAX(100, len + 1 - lp->linealloc);
  307. 			if((lp->line = realloc(lp->line, lp->linealloc)) == NULL) err(1, NULL);
  308. 		}
  309. 		memmove(lp->line, bp, len);
  311. 		/* Replace trailing newline, if it exists. */
  312. 		if(bp[len - 1] == '\n')
  313. 			lp->line[len - 1] = '\0';
  314. 		else
  315. 			lp->line[len] = '\0';
  316. 		bp = lp->line;
  318. 		/* Split the line into fields, allocate space as necessary. */
  319. 		lp->fieldcnt = 0;
  320. 		while((fieldp = mbssep(&bp, tabchar)) != NULL)
  321. 		{
  322. 			if(spans && *fieldp == '\0') continue;
  323. 			if(lp->fieldcnt == lp->fieldalloc)
  324. 			{
  325. 				lp->fieldalloc += 50;
  326. 				if((lp->fields = realloc(lp->fields, lp->fieldalloc * sizeof(char *))) == NULL)
  327. 					err(1, NULL);
  328. 			}
  329. 			lp->fields[lp->fieldcnt++] = fieldp;
  330. 		}
  332. 		/* See if the join field value has changed. */
  333. 		if(lastlp != NULL && cmp(lp, F->joinf, lastlp, F->joinf))
  334. 		{
  335. 			F->pushbool = 1;
  336. 			F->pushback = F->setcnt;
  337. 			break;
  338. 		}
  339. 	}
  340. }
  342. static char *
  343. mbssep(char **stringp, const wchar_t *delim)
  344. {
  345. 	char *s, *tok;
  346. 	const wchar_t *spanp;
  347. 	wchar_t c, sc;
  348. 	size_t n;
  350. 	if((s = *stringp) == NULL) return (NULL);
  351. 	for(tok = s;;)
  352. 	{
  353. 		n = mbrtowc(&c, s, MB_LEN_MAX, NULL);
  354. 		if(n == (size_t)-1 || n == (size_t)-2)
  355. 		{
  356. 			fprintf(stderr, "join: mbrtowc: Illegal byte sequence\n");
  357. 			exit(1);
  358. 		}
  359. 		s += n;
  360. 		spanp = delim;
  361. 		do
  362. 		{
  363. 			if((sc = *spanp++) == c)
  364. 			{
  365. 				if(c == 0)
  366. 					s = NULL;
  367. 				else
  368. 					s[-n] = '\0';
  369. 				*stringp = s;
  370. 				return (tok);
  371. 			}
  372. 		} while(sc != 0);
  373. 	}
  374. }
  376. static int
  377. cmp(LINE *lp1, unsigned long fieldno1, LINE *lp2, unsigned long fieldno2)
  378. {
  379. 	if(lp1->fieldcnt <= fieldno1) return (lp2->fieldcnt <= fieldno2 ? 0 : 1);
  380. 	if(lp2->fieldcnt <= fieldno2) return (-1);
  381. 	return (mbscoll(lp1->fields[fieldno1], lp2->fields[fieldno2]));
  382. }
  384. static int
  385. mbscoll(const char *s1, const char *s2)
  386. {
  387. 	wchar_t *w1, *w2;
  388. 	int ret;
  390. 	if(MB_CUR_MAX == 1) return (strcoll(s1, s2));
  391. 	if((w1 = towcs(s1)) == NULL || (w2 = towcs(s2)) == NULL) err(1, NULL); /* XXX */
  392. 	ret = wcscoll(w1, w2);
  393. 	free(w1);
  394. 	free(w2);
  395. 	return (ret);
  396. }
  398. static wchar_t *
  399. towcs(const char *s)
  400. {
  401. 	wchar_t *wcs;
  402. 	size_t n;
  404. 	if((n = mbsrtowcs(NULL, &s, 0, NULL)) == (size_t)-1) return (NULL);
  405. 	if((wcs = calloc((n + 1), sizeof(*wcs))) == NULL) return (NULL);
  406. 	mbsrtowcs(wcs, &s, n + 1, NULL);
  407. 	return (wcs);
  408. }
  410. static void
  411. joinlines(INPUT *F1, INPUT *F2)
  412. {
  413. 	unsigned long cnt1, cnt2;
  415. 	/*
  416. 	 * Output the results of a join comparison.  The output may be from
  417. 	 * either file 1 or file 2 (in which case the first argument is the
  418. 	 * file from which to output) or from both.
  419. 	 */
  420. 	if(F2 == NULL)
  421. 	{
  422. 		for(cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
  423. 			outoneline(F1, &F1->set[cnt1]);
  424. 		return;
  425. 	}
  426. 	for(cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
  427. 		for(cnt2 = 0; cnt2 < F2->setcnt; ++cnt2)
  428. 			outtwoline(F1, &F1->set[cnt1], F2, &F2->set[cnt2]);
  429. }
  431. static void
  432. outoneline(INPUT *F, LINE *lp)
  433. {
  434. 	unsigned long cnt;
  436. 	/*
  437. 	 * Output a single line from one of the files, according to the
  438. 	 * join rules.  This happens when we are writing unmatched single
  439. 	 * lines.  Output empty fields in the right places.
  440. 	 */
  441. 	if(olist)
  442. 		for(cnt = 0; cnt < olistcnt; ++cnt)
  443. 		{
  444. 			if(olist[cnt].filenum == (unsigned)F->number)
  445. 				outfield(lp, olist[cnt].fieldno, 0);
  446. 			else if(olist[cnt].filenum == 0)
  447. 				outfield(lp, F->joinf, 0);
  448. 			else
  449. 				outfield(lp, 0, 1);
  450. 		}
  451. 	else
  452. 	{
  453. 		/*
  454. 		 * Output the join field, then the remaining fields.
  455. 		 */
  456. 		outfield(lp, F->joinf, 0);
  457. 		for(cnt = 0; cnt < lp->fieldcnt; ++cnt)
  458. 			if(F->joinf != cnt) outfield(lp, cnt, 0);
  459. 	}
  460. 	(void)printf("\n");
  461. 	if(ferror(stdout)) err(1, "stdout");
  462. 	needsep = 0;
  463. }
  465. static void
  466. outtwoline(INPUT *F1, LINE *lp1, INPUT *F2, LINE *lp2)
  467. {
  468. 	unsigned long cnt;
  470. 	/* Output a pair of lines according to the join list (if any). */
  471. 	if(olist)
  472. 		for(cnt = 0; cnt < olistcnt; ++cnt)
  473. 			if(olist[cnt].filenum == 0)
  474. 			{
  475. 				if(lp1->fieldcnt >= F1->joinf)
  476. 					outfield(lp1, F1->joinf, 0);
  477. 				else
  478. 					outfield(lp2, F2->joinf, 0);
  479. 			}
  480. 			else if(olist[cnt].filenum == 1)
  481. 				outfield(lp1, olist[cnt].fieldno, 0);
  482. 			else /* if (olist[cnt].filenum == 2) */
  483. 				outfield(lp2, olist[cnt].fieldno, 0);
  484. 	else
  485. 	{
  486. 		/*
  487. 		 * Output the join field, then the remaining fields from F1
  488. 		 * and F2.
  489. 		 */
  490. 		outfield(lp1, F1->joinf, 0);
  491. 		for(cnt = 0; cnt < lp1->fieldcnt; ++cnt)
  492. 			if(F1->joinf != cnt) outfield(lp1, cnt, 0);
  493. 		for(cnt = 0; cnt < lp2->fieldcnt; ++cnt)
  494. 			if(F2->joinf != cnt) outfield(lp2, cnt, 0);
  495. 	}
  496. 	(void)printf("\n");
  497. 	if(ferror(stdout)) err(1, "stdout");
  498. 	needsep = 0;
  499. }
  501. static void
  502. outfield(LINE *lp, unsigned long fieldno, int out_empty)
  503. {
  504. 	if(needsep++) (void)printf("%lc", (wint_t)*tabchar);
  505. 	if(!ferror(stdout))
  506. 	{
  507. 		if(lp->fieldcnt <= fieldno || out_empty)
  508. 		{
  509. 			if(empty != NULL) (void)printf("%s", empty);
  510. 		}
  511. 		else
  512. 		{
  513. 			if(*lp->fields[fieldno] == '\0') return;
  514. 			(void)printf("%s", lp->fields[fieldno]);
  515. 		}
  516. 	}
  517. 	if(ferror(stdout)) err(1, "stdout");
  518. }
  520. /*
  521.  * Convert an output list argument "2.1, 1.3, 2.4" into an array of output
  522.  * fields.
  523.  */
  524. static void
  525. fieldarg(char *option)
  526. {
  527. 	unsigned long fieldno, filenum;
  528. 	char *end, *token;
  530. 	while((token = strsep(&option, ", \t")) != NULL)
  531. 	{
  532. 		if(*token == '\0') continue;
  533. 		if(token[0] == '0')
  534. 			filenum = fieldno = 0;
  535. 		else if((token[0] == '1' || token[0] == '2') && token[1] == '.')
  536. 		{
  537. 			filenum = token[0] - '0';
  538. 			fieldno = strtol(token + 2, &end, 10);
  539. 			if(*end) errx(1, "malformed -o option field");
  540. 			if(fieldno == 0) errx(1, "field numbers are 1 based");
  541. 			--fieldno;
  542. 		}
  543. 		else
  544. 			errx(1, "malformed -o option field");
  545. 		if(olistcnt == olistalloc)
  546. 		{
  547. 			olistalloc += 50;
  548. 			if((olist = realloc(olist, olistalloc * sizeof(OLIST))) == NULL) err(1, NULL);
  549. 		}
  550. 		olist[olistcnt].filenum = filenum;
  551. 		olist[olistcnt].fieldno = fieldno;
  552. 		++olistcnt;
  553. 	}
  554. }
  556. static void
  557. usage(void)
  558. {
  559. 	(void)fprintf(stderr,
  560. 	              "%s %s\n%s\n",
  561. 	              "usage: join [-a fileno | -v fileno ] [-e string] [-1 field]",
  562. 	              "[-2 field]",
  563. 	              "            [-o list] [-t char] file1 file2");
  564. 	exit(1);
  565. }