logo

utils-std

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

join.c (15280B)

    

  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 // fgetln, strsep
  38. #include "../lib/err.h"
  40. #include <limits.h>
  41. #include <locale.h>
  42. #include <stdio.h> // fgetln
  43. #include <stdlib.h>
  44. #include <string.h> // strsep
  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. const char *argv0 = "join";
  109. int
  110. main(int argc, char *argv[])
  111. {
  112. 	INPUT *F1, *F2;
  113. 	int aflag, ch, cval, vflag;
  114. 	char *end;
  116. 	setlocale(LC_ALL, "");
  118. 	F1 = &input1;
  119. 	F2 = &input2;
  121. 	aflag = vflag = 0;
  122. 	while((ch = getopt(argc, argv, ":a:e:j:1:2:o:t:v:")) != -1)
  123. 	{
  124. 		switch(ch)
  125. 		{
  126. 		case '1':
  127. 			if((F1->joinf = strtol(optarg, &end, 10)) < 1)
  128. 				utils_errx(1, "-1 option field number less than 1");
  129. 			if(*end) utils_errx(1, "illegal field number -- %s", optarg);
  130. 			--F1->joinf;
  131. 			break;
  132. 		case '2':
  133. 			if((F2->joinf = strtol(optarg, &end, 10)) < 1)
  134. 				utils_errx(1, "-2 option field number less than 1");
  135. 			if(*end) utils_errx(1, "illegal field number -- %s", optarg);
  136. 			--F2->joinf;
  137. 			break;
  138. 		case 'a':
  139. 			aflag = 1;
  140. 			switch(strtol(optarg, &end, 10))
  141. 			{
  142. 			case 1:
  143. 				F1->unpair = 1;
  144. 				break;
  145. 			case 2:
  146. 				F2->unpair = 1;
  147. 				break;
  148. 			default:
  149. 				utils_errx(1, "-a option file number not 1 or 2");
  150. 				break;
  151. 			}
  152. 			if(*end) utils_errx(1, "illegal file number -- %s", optarg);
  153. 			break;
  154. 		case 'e':
  155. 			empty = optarg;
  156. 			break;
  157. 		case 'j':
  158. 			if((F1->joinf = F2->joinf = strtol(optarg, &end, 10)) < 1)
  159. 				utils_errx(1, "-j option field number less than 1");
  160. 			if(*end) utils_errx(1, "illegal field number -- %s", optarg);
  161. 			--F1->joinf;
  162. 			--F2->joinf;
  163. 			break;
  164. 		case 'o':
  165. 			fieldarg(optarg);
  166. 			break;
  167. 		case 't':
  168. 			spans = 0;
  169. 			if(mbrtowc(&tabchar[0], optarg, MB_LEN_MAX, NULL) != strlen(optarg))
  170. 				utils_errx(1, "illegal tab character specification");
  171. 			tabchar[1] = L'\0';
  172. 			break;
  173. 		case 'v':
  174. 			vflag = 1;
  175. 			joinout = 0;
  176. 			switch(strtol(optarg, &end, 10))
  177. 			{
  178. 			case 1:
  179. 				F1->unpair = 1;
  180. 				break;
  181. 			case 2:
  182. 				F2->unpair = 1;
  183. 				break;
  184. 			default:
  185. 				utils_errx(1, "-v option file number not 1 or 2");
  186. 				break;
  187. 			}
  188. 			if(*end) utils_errx(1, "illegal file number -- %s", optarg);
  189. 			break;
  190. 		case ':':
  191. 			fprintf(stderr, "%s: error: Missing operand for option: '-%c'\n", argv0, optopt);
  192. 			usage();
  193. 			return 1;
  194. 		case '?':
  195. 			fprintf(stderr, "%s: error: Unrecognised option: '-%c'\n", argv0, optopt);
  196. 			usage();
  197. 			return 1;
  198. 		default:
  199. 			abort();
  200. 		}
  201. 	}
  202. 	argc -= optind;
  203. 	argv += optind;
  205. 	if(aflag && vflag) utils_errx(1, "the -a and -v options are mutually exclusive");
  207. 	if(argc != 2)
  208. 	{
  209. 		fprintf(stderr, "%s: error: Need exactly 2 file operands, got %d instead\n", argv0, argc);
  210. 		usage();
  211. 	}
  213. 	/* Open the files; "-" means stdin. */
  214. 	if(!strcmp(*argv, "-"))
  215. 		F1->fp = stdin;
  216. 	else if((F1->fp = fopen(*argv, "r")) == NULL)
  217. 		utils_err(1, "%s", *argv);
  218. 	++argv;
  219. 	if(!strcmp(*argv, "-"))
  220. 		F2->fp = stdin;
  221. 	else if((F2->fp = fopen(*argv, "r")) == NULL)
  222. 		utils_err(1, "%s", *argv);
  223. 	if(F1->fp == stdin && F2->fp == stdin) utils_errx(1, "only one input file may be stdin");
  225. 	slurp(F1);
  226. 	slurp(F2);
  227. 	while(F1->setcnt && F2->setcnt)
  228. 	{
  229. 		cval = cmp(F1->set, F1->joinf, F2->set, F2->joinf);
  230. 		if(cval == 0)
  231. 		{
  232. 			/* Oh joy, oh rapture, oh beauty divine! */
  233. 			if(joinout) joinlines(F1, F2);
  234. 			slurp(F1);
  235. 			slurp(F2);
  236. 		}
  237. 		else if(cval < 0)
  238. 		{
  239. 			/* File 1 takes the lead... */
  240. 			if(F1->unpair) joinlines(F1, NULL);
  241. 			slurp(F1);
  242. 		}
  243. 		else
  244. 		{
  245. 			/* File 2 takes the lead... */
  246. 			if(F2->unpair) joinlines(F2, NULL);
  247. 			slurp(F2);
  248. 		}
  249. 	}
  251. 	/*
  252. 	 * Now that one of the files is used up, optionally output any
  253. 	 * remaining lines from the other file.
  254. 	 */
  255. 	if(F1->unpair)
  256. 		while(F1->setcnt)
  257. 		{
  258. 			joinlines(F1, NULL);
  259. 			slurp(F1);
  260. 		}
  261. 	if(F2->unpair)
  262. 		while(F2->setcnt)
  263. 		{
  264. 			joinlines(F2, NULL);
  265. 			slurp(F2);
  266. 		}
  267. 	exit(0);
  268. }
  270. static void
  271. slurp(INPUT *F)
  272. {
  273. 	LINE *lp, *lastlp, tmp;
  274. 	size_t len;
  275. 	int cnt;
  276. 	char *bp, *fieldp;
  278. 	/*
  279. 	 * Read all of the lines from an input file that have the same
  280. 	 * join field.
  281. 	 */
  282. 	F->setcnt = 0;
  283. 	for(lastlp = NULL;; ++F->setcnt)
  284. 	{
  285. 		/*
  286. 		 * If we're out of space to hold line structures, allocate
  287. 		 * more.  Initialize the structure so that we know that this
  288. 		 * is new space.
  289. 		 */
  290. 		if(F->setcnt == F->setalloc)
  291. 		{
  292. 			cnt = F->setalloc;
  293. 			F->setalloc += 50;
  294. 			if((F->set = realloc(F->set, F->setalloc * sizeof(LINE))) == NULL) utils_err(1, NULL);
  295. 			memset(F->set + cnt, 0, 50 * sizeof(LINE));
  297. 			/* re-set lastlp in case it moved */
  298. 			if(lastlp != NULL) lastlp = &F->set[F->setcnt - 1];
  299. 		}
  301. 		/*
  302. 		 * Get any pushed back line, else get the next line.  Allocate
  303. 		 * space as necessary.  If taking the line from the stack swap
  304. 		 * the two structures so that we don't lose space allocated to
  305. 		 * either structure.  This could be avoided by doing another
  306. 		 * level of indirection, but it's probably okay as is.
  307. 		 */
  308. 		lp = &F->set[F->setcnt];
  309. 		if(F->setcnt) lastlp = &F->set[F->setcnt - 1];
  310. 		if(F->pushbool)
  311. 		{
  312. 			tmp = F->set[F->setcnt];
  313. 			F->set[F->setcnt] = F->set[F->pushback];
  314. 			F->set[F->pushback] = tmp;
  315. 			F->pushbool = 0;
  316. 			continue;
  317. 		}
  318. 		if((bp = fgetln(F->fp, &len)) == NULL) return;
  319. 		if(lp->linealloc <= len + 1)
  320. 		{
  321. 			lp->linealloc += MAX(100, len + 1 - lp->linealloc);
  322. 			if((lp->line = realloc(lp->line, lp->linealloc)) == NULL) utils_err(1, NULL);
  323. 		}
  324. 		memmove(lp->line, bp, len);
  326. 		/* Replace trailing newline, if it exists. */
  327. 		if(bp[len - 1] == '\n')
  328. 			lp->line[len - 1] = '\0';
  329. 		else
  330. 			lp->line[len] = '\0';
  331. 		bp = lp->line;
  333. 		/* Split the line into fields, allocate space as necessary. */
  334. 		lp->fieldcnt = 0;
  335. 		while((fieldp = mbssep(&bp, tabchar)) != NULL)
  336. 		{
  337. 			if(spans && *fieldp == '\0') continue;
  338. 			if(lp->fieldcnt == lp->fieldalloc)
  339. 			{
  340. 				lp->fieldalloc += 50;
  341. 				if((lp->fields = realloc(lp->fields, lp->fieldalloc * sizeof(char *))) == NULL)
  342. 					utils_err(1, NULL);
  343. 			}
  344. 			lp->fields[lp->fieldcnt++] = fieldp;
  345. 		}
  347. 		/* See if the join field value has changed. */
  348. 		if(lastlp != NULL && cmp(lp, F->joinf, lastlp, F->joinf))
  349. 		{
  350. 			F->pushbool = 1;
  351. 			F->pushback = F->setcnt;
  352. 			break;
  353. 		}
  354. 	}
  355. }
  357. static char *
  358. mbssep(char **stringp, const wchar_t *delim)
  359. {
  360. 	char *s, *tok;
  361. 	const wchar_t *spanp;
  362. 	wchar_t c, sc;
  363. 	size_t n;
  365. 	if((s = *stringp) == NULL) return (NULL);
  366. 	for(tok = s;;)
  367. 	{
  368. 		n = mbrtowc(&c, s, MB_LEN_MAX, NULL);
  369. 		if(n == (size_t)-1 || n == (size_t)-2)
  370. 		{
  371. 			fprintf(stderr, "join: error: mbrtowc: Illegal byte sequence\n");
  372. 			exit(1);
  373. 		}
  374. 		s += n;
  375. 		spanp = delim;
  376. 		do
  377. 		{
  378. 			if((sc = *spanp++) == c)
  379. 			{
  380. 				if(c == 0)
  381. 					s = NULL;
  382. 				else
  383. 					s[-n] = '\0';
  384. 				*stringp = s;
  385. 				return (tok);
  386. 			}
  387. 		} while(sc != 0);
  388. 	}
  389. }
  391. static int
  392. cmp(LINE *lp1, unsigned long fieldno1, LINE *lp2, unsigned long fieldno2)
  393. {
  394. 	if(lp1->fieldcnt <= fieldno1) return (lp2->fieldcnt <= fieldno2 ? 0 : 1);
  395. 	if(lp2->fieldcnt <= fieldno2) return (-1);
  396. 	return (mbscoll(lp1->fields[fieldno1], lp2->fields[fieldno2]));
  397. }
  399. static int
  400. mbscoll(const char *s1, const char *s2)
  401. {
  402. 	wchar_t *w1, *w2;
  403. 	int ret;
  405. 	if(MB_CUR_MAX == 1) return (strcoll(s1, s2));
  406. 	if((w1 = towcs(s1)) == NULL || (w2 = towcs(s2)) == NULL) utils_err(1, NULL); /* XXX */
  407. 	ret = wcscoll(w1, w2);
  408. 	free(w1);
  409. 	free(w2);
  410. 	return (ret);
  411. }
  413. static wchar_t *
  414. towcs(const char *s)
  415. {
  416. 	wchar_t *wcs;
  417. 	size_t n;
  419. 	if((n = mbsrtowcs(NULL, &s, 0, NULL)) == (size_t)-1) return (NULL);
  420. 	if((wcs = calloc((n + 1), sizeof(*wcs))) == NULL) return (NULL);
  421. 	mbsrtowcs(wcs, &s, n + 1, NULL);
  422. 	return (wcs);
  423. }
  425. static void
  426. joinlines(INPUT *F1, INPUT *F2)
  427. {
  428. 	unsigned long cnt1, cnt2;
  430. 	/*
  431. 	 * Output the results of a join comparison.  The output may be from
  432. 	 * either file 1 or file 2 (in which case the first argument is the
  433. 	 * file from which to output) or from both.
  434. 	 */
  435. 	if(F2 == NULL)
  436. 	{
  437. 		for(cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
  438. 			outoneline(F1, &F1->set[cnt1]);
  439. 		return;
  440. 	}
  441. 	for(cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
  442. 		for(cnt2 = 0; cnt2 < F2->setcnt; ++cnt2)
  443. 			outtwoline(F1, &F1->set[cnt1], F2, &F2->set[cnt2]);
  444. }
  446. static void
  447. outoneline(INPUT *F, LINE *lp)
  448. {
  449. 	unsigned long cnt;
  451. 	/*
  452. 	 * Output a single line from one of the files, according to the
  453. 	 * join rules.  This happens when we are writing unmatched single
  454. 	 * lines.  Output empty fields in the right places.
  455. 	 */
  456. 	if(olist)
  457. 		for(cnt = 0; cnt < olistcnt; ++cnt)
  458. 		{
  459. 			if(olist[cnt].filenum == (unsigned)F->number)
  460. 				outfield(lp, olist[cnt].fieldno, 0);
  461. 			else if(olist[cnt].filenum == 0)
  462. 				outfield(lp, F->joinf, 0);
  463. 			else
  464. 				outfield(lp, 0, 1);
  465. 		}
  466. 	else
  467. 	{
  468. 		/*
  469. 		 * Output the join field, then the remaining fields.
  470. 		 */
  471. 		outfield(lp, F->joinf, 0);
  472. 		for(cnt = 0; cnt < lp->fieldcnt; ++cnt)
  473. 			if(F->joinf != cnt) outfield(lp, cnt, 0);
  474. 	}
  475. 	(void)printf("\n");
  476. 	if(ferror(stdout)) utils_err(1, "stdout");
  477. 	needsep = 0;
  478. }
  480. static void
  481. outtwoline(INPUT *F1, LINE *lp1, INPUT *F2, LINE *lp2)
  482. {
  483. 	unsigned long cnt;
  485. 	/* Output a pair of lines according to the join list (if any). */
  486. 	if(olist)
  487. 		for(cnt = 0; cnt < olistcnt; ++cnt)
  488. 			if(olist[cnt].filenum == 0)
  489. 			{
  490. 				if(lp1->fieldcnt >= F1->joinf)
  491. 					outfield(lp1, F1->joinf, 0);
  492. 				else
  493. 					outfield(lp2, F2->joinf, 0);
  494. 			}
  495. 			else if(olist[cnt].filenum == 1)
  496. 				outfield(lp1, olist[cnt].fieldno, 0);
  497. 			else /* if (olist[cnt].filenum == 2) */
  498. 				outfield(lp2, olist[cnt].fieldno, 0);
  499. 	else
  500. 	{
  501. 		/*
  502. 		 * Output the join field, then the remaining fields from F1
  503. 		 * and F2.
  504. 		 */
  505. 		outfield(lp1, F1->joinf, 0);
  506. 		for(cnt = 0; cnt < lp1->fieldcnt; ++cnt)
  507. 			if(F1->joinf != cnt) outfield(lp1, cnt, 0);
  508. 		for(cnt = 0; cnt < lp2->fieldcnt; ++cnt)
  509. 			if(F2->joinf != cnt) outfield(lp2, cnt, 0);
  510. 	}
  511. 	(void)printf("\n");
  512. 	if(ferror(stdout)) utils_err(1, "stdout");
  513. 	needsep = 0;
  514. }
  516. static void
  517. outfield(LINE *lp, unsigned long fieldno, int out_empty)
  518. {
  519. 	if(needsep++) (void)printf("%lc", (wint_t)*tabchar);
  520. 	if(!ferror(stdout))
  521. 	{
  522. 		if(lp->fieldcnt <= fieldno || out_empty)
  523. 		{
  524. 			if(empty != NULL) (void)printf("%s", empty);
  525. 		}
  526. 		else
  527. 		{
  528. 			if(*lp->fields[fieldno] == '\0') return;
  529. 			(void)printf("%s", lp->fields[fieldno]);
  530. 		}
  531. 	}
  532. 	if(ferror(stdout)) utils_err(1, "stdout");
  533. }
  535. /*
  536.  * Convert an output list argument "2.1, 1.3, 2.4" into an array of output
  537.  * fields.
  538.  */
  539. static void
  540. fieldarg(char *option)
  541. {
  542. 	unsigned long fieldno, filenum;
  543. 	char *end, *token;
  545. 	while((token = strsep(&option, ", \t")) != NULL)
  546. 	{
  547. 		if(*token == '\0') continue;
  548. 		if(token[0] == '0')
  549. 			filenum = fieldno = 0;
  550. 		else if((token[0] == '1' || token[0] == '2') && token[1] == '.')
  551. 		{
  552. 			filenum = token[0] - '0';
  553. 			fieldno = strtol(token + 2, &end, 10);
  554. 			if(*end) utils_errx(1, "malformed -o option field");
  555. 			if(fieldno == 0) utils_errx(1, "field numbers are 1 based");
  556. 			--fieldno;
  557. 		}
  558. 		else
  559. 			utils_errx(1, "malformed -o option field");
  560. 		if(olistcnt == olistalloc)
  561. 		{
  562. 			olistalloc += 50;
  563. 			if((olist = realloc(olist, olistalloc * sizeof(OLIST))) == NULL) utils_err(1, NULL);
  564. 		}
  565. 		olist[olistcnt].filenum = filenum;
  566. 		olist[olistcnt].fieldno = fieldno;
  567. 		++olistcnt;
  568. 	}
  569. }
  571. static void
  572. usage(void)
  573. {
  574. 	(void)fprintf(stderr,
  575. 	              "%s %s\n%s\n",
  576. 	              "usage: join [-a fileno | -v fileno ] [-e string] [-1 field]",
  577. 	              "[-2 field]",
  578. 	              "            [-o list] [-t char] file1 file2");
  579. 	exit(1);
  580. }