logo

utils-std

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

join.c (15552B)

    

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