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 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 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 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 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 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 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 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 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 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
Indexes created Sun Sep 21 19:09:51 GMT 2025