usr.bin/nbperf/graph3.c

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