1 /* $NetBSD: graph2.c,v 1.6 2021/01/28 18:52:43 joerg Exp $ */
2 /*-
3 * Copyright (c) 2009 The NetBSD Foundation, Inc.
4 * All rights reserved.
5 *
6 * This code is derived from software contributed to The NetBSD Foundation
7 * by Joerg Sonnenberger.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
28 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
30 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34 #if HAVE_NBTOOL_CONFIG_H
35 #include "nbtool_config.h"
36 #endif
37
38 #include <sys/cdefs.h>
39 __RCSID("$NetBSD: graph2.c,v 1.6 2021/01/28 18:52:43 joerg Exp $");
40
41 #include <err.h>
42 #include <inttypes.h>
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <string.h>
46
47 #include "nbperf.h"
48 #include "graph2.h"
49
50 void
SIZED2(_setup)51 SIZED2(_setup)(struct SIZED(graph) *graph, uint32_t v, uint32_t e)
52 {
53 graph->v = v;
54 graph->e = e;
55
56 graph->verts = calloc(sizeof(*graph->verts), v);
57 graph->edges = calloc(sizeof(*graph->edges), e);
58 graph->output_order = calloc(sizeof(uint32_t), e);
59
60 if (graph->verts == NULL || graph->edges == NULL ||
61 graph->output_order == NULL)
62 err(1, "malloc failed");
63 }
64
65 void
SIZED2(_free)66 SIZED2(_free)(struct SIZED(graph) *graph)
67 {
68 free(graph->verts);
69 free(graph->edges);
70 free(graph->output_order);
71
72 graph->verts = NULL;
73 graph->edges = NULL;
74 graph->output_order = NULL;
75 }
76
77 static struct nbperf *sorting_nbperf;
78 static struct SIZED(graph) *sorting_graph;
79 static int sorting_found;
80
sorting_cmp(const void * a_,const void * b_)81 static int sorting_cmp(const void *a_, const void *b_)
82 {
83 const uint32_t *a = a_, *b = b_;
84 int i;
85 const struct SIZED(edge) *ea = &sorting_graph->edges[*a],
86 *eb = &sorting_graph->edges[*b];
87 for (i = 0; i < GRAPH_SIZE; ++i) {
88 if (ea->vertices[i] < eb->vertices[i])
89 return -1;
90 if (ea->vertices[i] > eb->vertices[i])
91 return 1;
92 }
93 if (sorting_nbperf->keylens[*a] < sorting_nbperf->keylens[*b])
94 return -1;
95 if (sorting_nbperf->keylens[*a] > sorting_nbperf->keylens[*b])
96 return 1;
97 i = memcmp(sorting_nbperf->keys[*a], sorting_nbperf->keys[*b],
98 sorting_nbperf->keylens[*a]);
99 if (i == 0)
100 sorting_found = 1;
101 return i;
102 }
103
104 static int
SIZED2(_check_duplicates)105 SIZED2(_check_duplicates)(struct nbperf *nbperf, struct SIZED(graph) *graph)
106 {
107 size_t i;
108 uint32_t *key_index = calloc(sizeof(*key_index), graph->e);
109
110 if (key_index == NULL)
111 err(1, "malloc failed");
112 for (i = 0; i < graph->e; ++i)
113 key_index[i] = i;
114
115 sorting_nbperf = nbperf;
116 sorting_graph = graph;
117 sorting_found = 0;
118 qsort(key_index, graph->e, sizeof(*key_index), sorting_cmp);
119 if (sorting_found)
120 goto found_dups;
121 /*
122 * Any duplicate must have been found as part of the qsort,
123 * as it can't sort consecutive elements in the output without
124 * comparing them at least once.
125 */
126
127 free(key_index);
128 return 0;
129 found_dups:
130 nbperf->has_duplicates = 1;
131 return -1;
132 }
133
134 static inline void
SIZED2(_add_edge)135 SIZED2(_add_edge)(struct SIZED(graph) *graph, uint32_t edge)
136 {
137 struct SIZED(edge) *e = graph->edges + edge;
138 struct SIZED(vertex) *v;
139 size_t i;
140
141 for (i = 0; i < GRAPH_SIZE; ++i) {
142 v = graph->verts + e->vertices[i];
143 v->edges ^= edge;
144 ++v->degree;
145 }
146 }
147
148 static inline void
SIZED2(_remove_edge)149 SIZED2(_remove_edge)(struct SIZED(graph) *graph, uint32_t edge)
150 {
151 struct SIZED(edge) *e = graph->edges + edge;
152 struct SIZED(vertex) *v;
153 size_t i;
154
155 for (i = 0; i < GRAPH_SIZE; ++i) {
156 v = graph->verts + e->vertices[i];
157 v->edges ^= edge;
158 --v->degree;
159 }
160 }
161
162 static inline void
SIZED2(_remove_vertex)163 SIZED2(_remove_vertex)(struct SIZED(graph) *graph, uint32_t vertex)
164 {
165 struct SIZED(vertex) *v = graph->verts + vertex;
166 uint32_t e;
167
168 if (v->degree == 1) {
169 e = v->edges;
170 graph->output_order[--graph->output_index] = e;
171 SIZED2(_remove_edge)(graph, e);
172 }
173 }
174
175 int
SIZED2(_hash)176 SIZED2(_hash)(struct nbperf *nbperf, struct SIZED(graph) *graph)
177 {
178 struct SIZED(edge) *e;
179 uint32_t hashes[NBPERF_MAX_HASH_SIZE];
180 size_t i, j;
181
182 #if GRAPH_SIZE == 2
183 if (nbperf->allow_hash_fudging && (graph->v & 1) != 0)
184 errx(1, "vertex count must have lowest bit clear");
185 #else
186 if (nbperf->allow_hash_fudging && (graph->v & 3) != 0)
187 errx(1, "vertex count must have lowest 2 bits clear");
188 #endif
189
190
191 memset(graph->verts, 0, sizeof(*graph->verts) * graph->v);
192 graph->hash_fudge = 0;
193
194 for (i = 0; i < graph->e; ++i) {
195 (*nbperf->compute_hash)(nbperf,
196 nbperf->keys[i], nbperf->keylens[i], hashes);
197 e = graph->edges + i;
198 for (j = 0; j < GRAPH_SIZE; ++j) {
199 e->vertices[j] = hashes[j] % graph->v;
200 if (j == 1 && e->vertices[0] == e->vertices[1]) {
201 if (!nbperf->allow_hash_fudging)
202 return -1;
203 e->vertices[1] ^= 1; /* toogle bit to differ */
204 graph->hash_fudge |= 1;
205 }
206 #if GRAPH_SIZE == 3
207 if (j == 2 && (e->vertices[0] == e->vertices[2] ||
208 e->vertices[1] == e->vertices[2])) {
209 if (!nbperf->allow_hash_fudging)
210 return -1;
211 graph->hash_fudge |= 2;
212 e->vertices[2] ^= 1;
213 e->vertices[2] ^= 2 * (e->vertices[0] == e->vertices[2] ||
214 e->vertices[1] == e->vertices[2]);
215 }
216 #endif
217 }
218 }
219
220 for (i = 0; i < graph->e; ++i)
221 SIZED2(_add_edge)(graph, i);
222
223 if (nbperf->check_duplicates) {
224 nbperf->check_duplicates = 0;
225 return SIZED2(_check_duplicates)(nbperf, graph);
226 }
227
228 return 0;
229 }
230
231 int
SIZED2(_output_order)232 SIZED2(_output_order)(struct SIZED(graph) *graph)
233 {
234 size_t i, j;
235 struct SIZED(edge) *e2;
236
237 graph->output_index = graph->e;
238
239 for (i = 0; i < graph->v; ++i)
240 SIZED2(_remove_vertex)(graph, i);
241
242 for (i = graph->e; graph->output_index > 0 && i > graph->output_index;) {
243 e2 = graph->edges + graph->output_order[--i];
244 for (j = 0; j < GRAPH_SIZE; ++j)
245 SIZED2(_remove_vertex)(graph, e2->vertices[j]);
246 }
247
248 if (graph->output_index != 0) {
249 return -1;
250 }
251
252 return 0;
253 }
254