1 /* $NetBSD: graph3.c,v 1.3 2010/03/03 01:55:04 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 #include <sys/cdefs.h> 35 __RCSID("$NetBSD: graph3.c,v 1.3 2010/03/03 01:55:04 joerg Exp $"); 36 37 #include <err.h> 38 #include <inttypes.h> 39 #include <stdio.h> 40 #include <stdlib.h> 41 #include <string.h> 42 43 #include "nbperf.h" 44 #include "graph3.h" 45 46 static const uint32_t unused = 0xffffffffU; 47 48 void 49 graph3_setup(struct graph3 *graph, uint32_t v, uint32_t e) 50 { 51 graph->v = v; 52 graph->e = e; 53 54 graph->verts = calloc(sizeof(struct vertex3), v); 55 graph->edges = calloc(sizeof(struct edge3), e); 56 graph->output_order = calloc(sizeof(uint32_t), e); 57 58 if (graph->verts == NULL || graph->edges == NULL || 59 graph->output_order == NULL) 60 err(1, "malloc failed"); 61 } 62 63 void 64 graph3_free(struct graph3 *graph) 65 { 66 free(graph->verts); 67 free(graph->edges); 68 free(graph->output_order); 69 70 graph->verts = NULL; 71 graph->edges = NULL; 72 graph->output_order = NULL; 73 } 74 75 static int 76 graph3_check_duplicates(struct nbperf *nbperf, struct graph3 *graph) 77 { 78 struct vertex3 *v; 79 struct edge3 *e, *e2; 80 uint32_t i, j; 81 82 for (i = 0; i < graph->e; ++i) { 83 e = &graph->edges[i]; 84 v = &graph->verts[e->left]; 85 j = v->l_edge; 86 e2 = &graph->edges[j]; 87 for (;;) { 88 if (i < j && e->middle == e2->middle && 89 e->right == e2->right && 90 nbperf->keylens[i] == nbperf->keylens[j] && 91 memcmp(nbperf->keys[i], nbperf->keys[j], 92 nbperf->keylens[i]) == 0) { 93 nbperf->has_duplicates = 1; 94 return -1; 95 } 96 if (e2->l_next == unused) 97 break; 98 j = e2->l_next; 99 e2 = &graph->edges[j]; 100 } 101 } 102 return 0; 103 } 104 105 int 106 graph3_hash(struct nbperf *nbperf, struct graph3 *graph) 107 { 108 struct vertex3 *v; 109 uint32_t hashes[NBPERF_MAX_HASH_SIZE]; 110 size_t i; 111 112 for (i = 0; i < graph->e; ++i) { 113 (*nbperf->compute_hash)(nbperf, 114 nbperf->keys[i], nbperf->keylens[i], hashes); 115 graph->edges[i].left = hashes[0] % graph->v; 116 graph->edges[i].middle = hashes[1] % graph->v; 117 graph->edges[i].right = hashes[2] % graph->v; 118 if (graph->edges[i].left == graph->edges[i].middle) 119 return -1; 120 if (graph->edges[i].left == graph->edges[i].right) 121 return -1; 122 if (graph->edges[i].middle == graph->edges[i].right) 123 return -1; 124 } 125 126 for (i = 0; i < graph->v; ++i) { 127 graph->verts[i].l_edge = unused; 128 graph->verts[i].m_edge = unused; 129 graph->verts[i].r_edge = unused; 130 } 131 132 for (i = 0; i < graph->e; ++i) { 133 v = &graph->verts[graph->edges[i].left]; 134 if (v->l_edge != unused) 135 graph->edges[v->l_edge].l_prev = i; 136 graph->edges[i].l_next = v->l_edge; 137 graph->edges[i].l_prev = unused; 138 v->l_edge = i; 139 140 v = &graph->verts[graph->edges[i].middle]; 141 if (v->m_edge != unused) 142 graph->edges[v->m_edge].m_prev = i; 143 graph->edges[i].m_next = v->m_edge; 144 graph->edges[i].m_prev = unused; 145 v->m_edge = i; 146 147 v = &graph->verts[graph->edges[i].right]; 148 if (v->r_edge != unused) 149 graph->edges[v->r_edge].r_prev = i; 150 graph->edges[i].r_next = v->r_edge; 151 graph->edges[i].r_prev = unused; 152 v->r_edge = i; 153 } 154 155 if (nbperf->first_round) { 156 nbperf->first_round = 0; 157 return graph3_check_duplicates(nbperf, graph); 158 } 159 160 return 0; 161 } 162 163 static void 164 graph3_remove_vertex(struct graph3 *graph, struct vertex3 *v) 165 { 166 struct edge3 *e; 167 struct vertex3 *vl, *vm, *vr; 168 169 if (v->l_edge != unused && v->m_edge != unused) 170 return; 171 if (v->l_edge != unused && v->r_edge != unused) 172 return; 173 if (v->m_edge != unused && v->r_edge != unused) 174 return; 175 if (v->l_edge == unused && v->m_edge == unused && v->r_edge == unused) 176 return; 177 178 if (v->l_edge != unused) { 179 e = &graph->edges[v->l_edge]; 180 if (e->l_next != unused) 181 return; 182 } else if (v->m_edge != unused) { 183 e = &graph->edges[v->m_edge]; 184 if (e->m_next != unused) 185 return; 186 } else { 187 if (v->r_edge == unused) 188 abort(); 189 e = &graph->edges[v->r_edge]; 190 if (e->r_next != unused) 191 return; 192 } 193 194 graph->output_order[--graph->output_index] = e - graph->edges; 195 196 vl = &graph->verts[e->left]; 197 vm = &graph->verts[e->middle]; 198 vr = &graph->verts[e->right]; 199 200 if (e->l_prev == unused) 201 vl->l_edge = e->l_next; 202 else 203 graph->edges[e->l_prev].l_next = e->l_next; 204 if (e->l_next != unused) 205 graph->edges[e->l_next].l_prev = e->l_prev; 206 207 if (e->m_prev == unused) 208 vm->m_edge = e->m_next; 209 else 210 graph->edges[e->m_prev].m_next = e->m_next; 211 if (e->m_next != unused) 212 graph->edges[e->m_next].m_prev = e->m_prev; 213 214 if (e->r_prev == unused) 215 vr->r_edge = e->r_next; 216 else 217 graph->edges[e->r_prev].r_next = e->r_next; 218 if (e->r_next != unused) 219 graph->edges[e->r_next].r_prev = e->r_prev; 220 } 221 222 int 223 graph3_output_order(struct graph3 *graph) 224 { 225 struct edge3 *e; 226 size_t i; 227 228 graph->output_index = graph->e; 229 230 for (i = 0; i < graph->v; ++i) 231 graph3_remove_vertex(graph, &graph->verts[i]); 232 233 for (i = graph->e; i > 0 && i > graph->output_index;) { 234 --i; 235 e = &graph->edges[graph->output_order[i]]; 236 237 graph3_remove_vertex(graph, &graph->verts[e->left]); 238 graph3_remove_vertex(graph, &graph->verts[e->middle]); 239 graph3_remove_vertex(graph, &graph->verts[e->right]); 240 } 241 242 if (graph->output_index != 0) 243 return -1; 244 245 return 0; 246 } 247