xref: /netbsd-src/usr.bin/nbperf/graph2.c (revision 4fdf57e855859123287734ac3552d5ab20a4231a)
1*4fdf57e8Sjoerg /*	$NetBSD: graph2.c,v 1.6 2021/01/28 18:52:43 joerg Exp $	*/
203c8ba1cSjoerg /*-
303c8ba1cSjoerg  * Copyright (c) 2009 The NetBSD Foundation, Inc.
403c8ba1cSjoerg  * All rights reserved.
503c8ba1cSjoerg  *
603c8ba1cSjoerg  * This code is derived from software contributed to The NetBSD Foundation
703c8ba1cSjoerg  * by Joerg Sonnenberger.
803c8ba1cSjoerg  *
903c8ba1cSjoerg  * Redistribution and use in source and binary forms, with or without
1003c8ba1cSjoerg  * modification, are permitted provided that the following conditions
1103c8ba1cSjoerg  * are met:
1203c8ba1cSjoerg  *
1303c8ba1cSjoerg  * 1. Redistributions of source code must retain the above copyright
1403c8ba1cSjoerg  *    notice, this list of conditions and the following disclaimer.
1503c8ba1cSjoerg  * 2. Redistributions in binary form must reproduce the above copyright
1603c8ba1cSjoerg  *    notice, this list of conditions and the following disclaimer in
1703c8ba1cSjoerg  *    the documentation and/or other materials provided with the
1803c8ba1cSjoerg  *    distribution.
1903c8ba1cSjoerg  *
2003c8ba1cSjoerg  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2103c8ba1cSjoerg  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2203c8ba1cSjoerg  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
2303c8ba1cSjoerg  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
2403c8ba1cSjoerg  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
2503c8ba1cSjoerg  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
2603c8ba1cSjoerg  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
2703c8ba1cSjoerg  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
2803c8ba1cSjoerg  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
2903c8ba1cSjoerg  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
3003c8ba1cSjoerg  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
3103c8ba1cSjoerg  * SUCH DAMAGE.
3203c8ba1cSjoerg  */
3303c8ba1cSjoerg 
3410769988Sjoerg #if HAVE_NBTOOL_CONFIG_H
3510769988Sjoerg #include "nbtool_config.h"
3610769988Sjoerg #endif
3710769988Sjoerg 
3803c8ba1cSjoerg #include <sys/cdefs.h>
39*4fdf57e8Sjoerg __RCSID("$NetBSD: graph2.c,v 1.6 2021/01/28 18:52:43 joerg Exp $");
4003c8ba1cSjoerg 
4103c8ba1cSjoerg #include <err.h>
4203c8ba1cSjoerg #include <inttypes.h>
4303c8ba1cSjoerg #include <stdio.h>
4403c8ba1cSjoerg #include <stdlib.h>
45f9c779deSjoerg #include <string.h>
4603c8ba1cSjoerg 
4703c8ba1cSjoerg #include "nbperf.h"
4803c8ba1cSjoerg #include "graph2.h"
4903c8ba1cSjoerg 
5003c8ba1cSjoerg void
SIZED2(_setup)517c219dd6Sjoerg SIZED2(_setup)(struct SIZED(graph) *graph, uint32_t v, uint32_t e)
5203c8ba1cSjoerg {
5303c8ba1cSjoerg 	graph->v = v;
5403c8ba1cSjoerg 	graph->e = e;
5503c8ba1cSjoerg 
567c219dd6Sjoerg 	graph->verts = calloc(sizeof(*graph->verts), v);
577c219dd6Sjoerg 	graph->edges = calloc(sizeof(*graph->edges), e);
5803c8ba1cSjoerg 	graph->output_order = calloc(sizeof(uint32_t), e);
5903c8ba1cSjoerg 
6003c8ba1cSjoerg 	if (graph->verts == NULL || graph->edges == NULL ||
6103c8ba1cSjoerg 	    graph->output_order == NULL)
6203c8ba1cSjoerg 		err(1, "malloc failed");
6303c8ba1cSjoerg }
6403c8ba1cSjoerg 
6503c8ba1cSjoerg void
SIZED2(_free)667c219dd6Sjoerg SIZED2(_free)(struct SIZED(graph) *graph)
6703c8ba1cSjoerg {
6803c8ba1cSjoerg 	free(graph->verts);
6903c8ba1cSjoerg 	free(graph->edges);
7003c8ba1cSjoerg 	free(graph->output_order);
7103c8ba1cSjoerg 
7203c8ba1cSjoerg 	graph->verts = NULL;
7303c8ba1cSjoerg 	graph->edges = NULL;
7403c8ba1cSjoerg 	graph->output_order = NULL;
7503c8ba1cSjoerg }
7603c8ba1cSjoerg 
777c219dd6Sjoerg static struct nbperf *sorting_nbperf;
787c219dd6Sjoerg static struct SIZED(graph) *sorting_graph;
797c219dd6Sjoerg static int sorting_found;
80f9c779deSjoerg 
sorting_cmp(const void * a_,const void * b_)817c219dd6Sjoerg static int sorting_cmp(const void *a_, const void *b_)
827c219dd6Sjoerg {
837c219dd6Sjoerg 	const uint32_t *a = a_, *b = b_;
847c219dd6Sjoerg 	int i;
857c219dd6Sjoerg 	const struct SIZED(edge) *ea = &sorting_graph->edges[*a],
867c219dd6Sjoerg 	    *eb = &sorting_graph->edges[*b];
877c219dd6Sjoerg 	for (i = 0; i < GRAPH_SIZE; ++i) {
887c219dd6Sjoerg 		if (ea->vertices[i] < eb->vertices[i])
897c219dd6Sjoerg 			return -1;
907c219dd6Sjoerg 		if (ea->vertices[i] > eb->vertices[i])
917c219dd6Sjoerg 			return 1;
927c219dd6Sjoerg 	}
937c219dd6Sjoerg 	if (sorting_nbperf->keylens[*a] < sorting_nbperf->keylens[*b])
947c219dd6Sjoerg 		return -1;
957c219dd6Sjoerg 	if (sorting_nbperf->keylens[*a] > sorting_nbperf->keylens[*b])
967c219dd6Sjoerg 		return 1;
977c219dd6Sjoerg 	i = memcmp(sorting_nbperf->keys[*a], sorting_nbperf->keys[*b],
987c219dd6Sjoerg 	    sorting_nbperf->keylens[*a]);
997c219dd6Sjoerg 	if (i == 0)
1007c219dd6Sjoerg 		sorting_found = 1;
1017c219dd6Sjoerg 	return i;
1027c219dd6Sjoerg }
1037c219dd6Sjoerg 
1047c219dd6Sjoerg static int
SIZED2(_check_duplicates)1057c219dd6Sjoerg SIZED2(_check_duplicates)(struct nbperf *nbperf, struct SIZED(graph) *graph)
1067c219dd6Sjoerg {
1077c219dd6Sjoerg 	size_t i;
1087c219dd6Sjoerg 	uint32_t *key_index = calloc(sizeof(*key_index), graph->e);
1097c219dd6Sjoerg 
1107c219dd6Sjoerg 	if (key_index == NULL)
1117c219dd6Sjoerg 		err(1, "malloc failed");
1127c219dd6Sjoerg 	for (i = 0; i < graph->e; ++i)
1137c219dd6Sjoerg 		key_index[i] = i;
1147c219dd6Sjoerg 
1157c219dd6Sjoerg 	sorting_nbperf = nbperf;
1167c219dd6Sjoerg 	sorting_graph = graph;
1177c219dd6Sjoerg 	sorting_found = 0;
1187c219dd6Sjoerg 	qsort(key_index, graph->e, sizeof(*key_index), sorting_cmp);
1197c219dd6Sjoerg 	if (sorting_found)
1207c219dd6Sjoerg 		goto found_dups;
1217c219dd6Sjoerg 	/*
1227c219dd6Sjoerg 	 * Any duplicate must have been found as part of the qsort,
1237c219dd6Sjoerg 	 * as it can't sort consecutive elements in the output without
1247c219dd6Sjoerg 	 * comparing them at least once.
1257c219dd6Sjoerg 	 */
1267c219dd6Sjoerg 
1277c219dd6Sjoerg 	free(key_index);
1287c219dd6Sjoerg 	return 0;
1297c219dd6Sjoerg  found_dups:
130f9c779deSjoerg 	nbperf->has_duplicates = 1;
131f9c779deSjoerg 	return -1;
132f9c779deSjoerg }
1337c219dd6Sjoerg 
1347c219dd6Sjoerg static inline void
SIZED2(_add_edge)1357c219dd6Sjoerg SIZED2(_add_edge)(struct SIZED(graph) *graph, uint32_t edge)
1367c219dd6Sjoerg {
1377c219dd6Sjoerg 	struct SIZED(edge) *e = graph->edges + edge;
1387c219dd6Sjoerg 	struct SIZED(vertex) *v;
1397c219dd6Sjoerg 	size_t i;
1407c219dd6Sjoerg 
1417c219dd6Sjoerg 	for (i = 0; i < GRAPH_SIZE; ++i) {
1427c219dd6Sjoerg 		v = graph->verts + e->vertices[i];
1437c219dd6Sjoerg 		v->edges ^= edge;
1447c219dd6Sjoerg 		++v->degree;
145f9c779deSjoerg 	}
146f9c779deSjoerg }
1477c219dd6Sjoerg 
1487c219dd6Sjoerg static inline void
SIZED2(_remove_edge)1497c219dd6Sjoerg SIZED2(_remove_edge)(struct SIZED(graph) *graph, uint32_t edge)
1507c219dd6Sjoerg {
1517c219dd6Sjoerg 	struct SIZED(edge) *e = graph->edges + edge;
1527c219dd6Sjoerg 	struct SIZED(vertex) *v;
1537c219dd6Sjoerg 	size_t i;
1547c219dd6Sjoerg 
1557c219dd6Sjoerg 	for (i = 0; i < GRAPH_SIZE; ++i) {
1567c219dd6Sjoerg 		v = graph->verts + e->vertices[i];
1577c219dd6Sjoerg 		v->edges ^= edge;
1587c219dd6Sjoerg 		--v->degree;
1597c219dd6Sjoerg 	}
1607c219dd6Sjoerg }
1617c219dd6Sjoerg 
1627c219dd6Sjoerg static inline void
SIZED2(_remove_vertex)1637c219dd6Sjoerg SIZED2(_remove_vertex)(struct SIZED(graph) *graph, uint32_t vertex)
1647c219dd6Sjoerg {
1657c219dd6Sjoerg 	struct SIZED(vertex) *v = graph->verts + vertex;
1667c219dd6Sjoerg 	uint32_t e;
1677c219dd6Sjoerg 
1687c219dd6Sjoerg 	if (v->degree == 1) {
1697c219dd6Sjoerg 		e = v->edges;
1707c219dd6Sjoerg 		graph->output_order[--graph->output_index] = e;
1717c219dd6Sjoerg 		SIZED2(_remove_edge)(graph, e);
1727c219dd6Sjoerg 	}
173f9c779deSjoerg }
174f9c779deSjoerg 
17503c8ba1cSjoerg int
SIZED2(_hash)1767c219dd6Sjoerg SIZED2(_hash)(struct nbperf *nbperf, struct SIZED(graph) *graph)
17703c8ba1cSjoerg {
1787c219dd6Sjoerg 	struct SIZED(edge) *e;
179976b948dSjoerg 	uint32_t hashes[NBPERF_MAX_HASH_SIZE];
1807c219dd6Sjoerg 	size_t i, j;
1817c219dd6Sjoerg 
1827c219dd6Sjoerg #if GRAPH_SIZE == 2
183*4fdf57e8Sjoerg 	if (nbperf->allow_hash_fudging && (graph->v & 1) != 0)
184*4fdf57e8Sjoerg 		errx(1, "vertex count must have lowest bit clear");
1857c219dd6Sjoerg #else
186*4fdf57e8Sjoerg 	if (nbperf->allow_hash_fudging && (graph->v & 3) != 0)
187*4fdf57e8Sjoerg 		errx(1, "vertex count must have lowest 2 bits clear");
1887c219dd6Sjoerg #endif
1897c219dd6Sjoerg 
1907c219dd6Sjoerg 
1917c219dd6Sjoerg 	memset(graph->verts, 0, sizeof(*graph->verts) * graph->v);
1927c219dd6Sjoerg 	graph->hash_fudge = 0;
19303c8ba1cSjoerg 
19403c8ba1cSjoerg 	for (i = 0; i < graph->e; ++i) {
19503c8ba1cSjoerg 		(*nbperf->compute_hash)(nbperf,
19603c8ba1cSjoerg 		    nbperf->keys[i], nbperf->keylens[i], hashes);
1977c219dd6Sjoerg 		e = graph->edges + i;
1987c219dd6Sjoerg 		for (j = 0; j < GRAPH_SIZE; ++j) {
1997c219dd6Sjoerg 			e->vertices[j] = hashes[j] % graph->v;
2007c219dd6Sjoerg 			if (j == 1 && e->vertices[0] == e->vertices[1]) {
2017c219dd6Sjoerg 				if (!nbperf->allow_hash_fudging)
20203c8ba1cSjoerg 					return -1;
2037c219dd6Sjoerg 				e->vertices[1] ^= 1; /* toogle bit to differ */
2047c219dd6Sjoerg 				graph->hash_fudge |= 1;
2057c219dd6Sjoerg 			}
2067c219dd6Sjoerg #if GRAPH_SIZE == 3
2077c219dd6Sjoerg 			if (j == 2 && (e->vertices[0] == e->vertices[2] ||
2087c219dd6Sjoerg 			    e->vertices[1] == e->vertices[2])) {
2097c219dd6Sjoerg 				if (!nbperf->allow_hash_fudging)
2107c219dd6Sjoerg 					return -1;
2117c219dd6Sjoerg 				graph->hash_fudge |= 2;
2127c219dd6Sjoerg 				e->vertices[2] ^= 1;
2137c219dd6Sjoerg 				e->vertices[2] ^= 2 * (e->vertices[0] == e->vertices[2] ||
2147c219dd6Sjoerg 				    e->vertices[1] == e->vertices[2]);
2157c219dd6Sjoerg 			}
2167c219dd6Sjoerg #endif
2177c219dd6Sjoerg 		}
21803c8ba1cSjoerg 	}
21903c8ba1cSjoerg 
2207c219dd6Sjoerg 	for (i = 0; i < graph->e; ++i)
2217c219dd6Sjoerg 		SIZED2(_add_edge)(graph, i);
22203c8ba1cSjoerg 
2237c219dd6Sjoerg 	if (nbperf->check_duplicates) {
2247c219dd6Sjoerg 		nbperf->check_duplicates = 0;
2257c219dd6Sjoerg 		return SIZED2(_check_duplicates)(nbperf, graph);
226f9c779deSjoerg 	}
227f9c779deSjoerg 
22803c8ba1cSjoerg 	return 0;
22903c8ba1cSjoerg }
23003c8ba1cSjoerg 
23103c8ba1cSjoerg int
SIZED2(_output_order)2327c219dd6Sjoerg SIZED2(_output_order)(struct SIZED(graph) *graph)
23303c8ba1cSjoerg {
2347c219dd6Sjoerg 	size_t i, j;
2357c219dd6Sjoerg 	struct SIZED(edge) *e2;
23603c8ba1cSjoerg 
23703c8ba1cSjoerg 	graph->output_index = graph->e;
23803c8ba1cSjoerg 
23903c8ba1cSjoerg 	for (i = 0; i < graph->v; ++i)
2407c219dd6Sjoerg 		SIZED2(_remove_vertex)(graph, i);
24103c8ba1cSjoerg 
2427c219dd6Sjoerg 	for (i = graph->e; graph->output_index > 0 && i > graph->output_index;) {
2437c219dd6Sjoerg 		e2 = graph->edges + graph->output_order[--i];
2447c219dd6Sjoerg 		for (j = 0; j < GRAPH_SIZE; ++j)
2457c219dd6Sjoerg 			SIZED2(_remove_vertex)(graph, e2->vertices[j]);
2467c219dd6Sjoerg 	}
2477c219dd6Sjoerg 
2487c219dd6Sjoerg 	if (graph->output_index != 0) {
24903c8ba1cSjoerg 		return -1;
2507c219dd6Sjoerg 	}
25103c8ba1cSjoerg 
25203c8ba1cSjoerg 	return 0;
25303c8ba1cSjoerg }
254