usr.bin/nbperf/graph3.c

   1 /*      $NetBSD: graph3.c,v 1.1 2009/08/15 16:21:05 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.1 2009/08/15 16:21:05 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 }