GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/yacc/warshall.c Lines: 25 25 100.0 %
Date: 2017-11-13 Branches: 14 14 100.0 %

Line Branch Exec Source
1
/* $OpenBSD: warshall.c,v 1.11 2014/03/13 01:18:22 tedu Exp $	 */
2
/* $NetBSD: warshall.c,v 1.4 1996/03/19 03:21:51 jtc Exp $	 */
3
4
/*
5
 * Copyright (c) 1989 The Regents of the University of California.
6
 * All rights reserved.
7
 *
8
 * This code is derived from software contributed to Berkeley by
9
 * Robert Paul Corbett.
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
 */
35
36
#include "defs.h"
37
38
void transitive_closure(unsigned int *, int);
39
40
void
41
transitive_closure(unsigned int *R, int n)
42
{
43
	int rowsize;
44
	unsigned int i;
45
	unsigned int *rowj, *rp, *rend, *ccol, *relend, *cword, *rowi;
46
47
18
	rowsize = WORDSIZE(n);
48
9
	relend = R + n * rowsize;
49
50
	cword = R;
51
	i = 0;
52
	rowi = R;
53
498
	while (rowi < relend) {
54
		ccol = cword;
55
		rowj = R;
56
57
14288
		while (rowj < relend) {
58
6904
			if (*ccol & (1 << i)) {
59
				rp = rowi;
60
255
				rend = rowj + rowsize;
61
1500
				while (rowj < rend)
62
495
					*rowj++ |= *rp++;
63
			} else {
64
6649
				rowj += rowsize;
65
			}
66
67
6904
			ccol += rowsize;
68
		}
69
70
240
		if (++i >= BITS_PER_WORD) {
71
			i = 0;
72
4
			cword++;
73
4
		}
74
240
		rowi += rowsize;
75
	}
76
9
}
77
78
void
79
reflexive_transitive_closure(unsigned int *R, int n)
80
{
81
	int rowsize;
82
	unsigned int i;
83
	unsigned int *rp, *relend;
84
85
18
	transitive_closure(R, n);
86
87
9
	rowsize = WORDSIZE(n);
88
9
	relend = R + n * rowsize;
89
90
	i = 0;
91
	rp = R;
92
498
	while (rp < relend) {
93
240
		*rp |= (1 << i);
94
240
		if (++i >= BITS_PER_WORD) {
95
			i = 0;
96
4
			rp++;
97
4
		}
98
240
		rp += rowsize;
99
	}
100
9
}