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