usr.bin/nbperf/graph2.c

   1 /*      $NetBSD: graph2.c,v 1.1 2009/08/15 16:21: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: graph2.c,v 1.1 2009/08/15 16:21:04 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 "graph2.h"
  44
  45 static const uint32_t unused = 0xffffffffU;
  46
  47 void
  48 graph2_setup(struct graph2 *graph, uint32_t v, uint32_t e)
  49 {
  50         graph->v = v;
  51         graph->e = e;
  52
  53         graph->verts = calloc(sizeof(struct vertex2), v);
  54         graph->edges = calloc(sizeof(struct edge2), 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 graph2_free(struct graph2 *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 graph2_hash(struct nbperf *nbperf, struct graph2 *graph)
  76 {
  77         struct vertex2 *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].right = hashes[1] % graph->v;
  86                 if (graph->edges[i].left == graph->edges[i].right)
  87                         return -1;
  88         }
  89
  90         for (i = 0; i < graph->v; ++i) {
  91                 graph->verts[i].l_edge = unused;
  92                 graph->verts[i].r_edge = unused;
  93         }
  94
  95         for (i = 0; i < graph->e; ++i) {
  96                 v = &graph->verts[graph->edges[i].left];
  97                 if (v->l_edge != unused)
  98                         graph->edges[v->l_edge].l_prev = i;
  99                 graph->edges[i].l_next = v->l_edge;
 100                 graph->edges[i].l_prev = unused;
 101                 v->l_edge = i;
 102
 103                 v = &graph->verts[graph->edges[i].right];
 104                 if (v->r_edge != unused)
 105                         graph->edges[v->r_edge].r_prev = i;
 106                 graph->edges[i].r_next = v->r_edge;
 107                 graph->edges[i].r_prev = unused;
 108                 v->r_edge = i;
 109         }
 110
 111         return 0;
 112 }
 113
 114 static void
 115 graph2_remove_vertex(struct graph2 *graph, struct vertex2 *v)
 116 {
 117         struct edge2 *e;
 118         struct vertex2 *v2;
 119
 120         for (;;) {
 121                 if (v->l_edge != unused && v->r_edge != unused)
 122                         break;
 123                 if (v->l_edge == unused && v->r_edge == unused)
 124                         break;
 125
 126                 if (v->l_edge != unused) {
 127                         e = &graph->edges[v->l_edge];
 128                         if (e->l_next != unused)
 129                                 break;
 130                         v->l_edge = unused; /* No other elements possible! */
 131                         v2 = &graph->verts[e->right];
 132                         if (e->r_prev == unused)
 133                                 v2->r_edge = e->r_next;
 134                         else
 135                                 graph->edges[e->r_prev].r_next = e->r_next;
 136                         if (e->r_next != unused)
 137                                 graph->edges[e->r_next].r_prev = e->r_prev;
 138                         v = v2;
 139                 } else {
 140                         e = &graph->edges[v->r_edge];
 141                         if (e->r_next != unused)
 142                                 break;
 143                         v->r_edge = unused; /* No other elements possible! */
 144                         v2 = &graph->verts[e->left];
 145                         if (e->l_prev == unused)
 146                                 v2->l_edge = e->l_next;
 147                         else
 148                                 graph->edges[e->l_prev].l_next = e->l_next;
 149                         if (e->l_next != unused)
 150                                 graph->edges[e->l_next].l_prev = e->l_prev;
 151                         v = v2;
 152                 }
 153
 154                 graph->output_order[--graph->output_index] = e - graph->edges;
 155         }
 156 }
 157
 158 int
 159 graph2_output_order(struct graph2 *graph)
 160 {
 161         size_t i;
 162
 163         graph->output_index = graph->e;
 164
 165         for (i = 0; i < graph->v; ++i)
 166                 graph2_remove_vertex(graph, &graph->verts[i]);
 167
 168         if (graph->output_index != 0)
 169                 return -1;
 170
 171         return 0;
 172 }