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