Home | History | Annotate | Line # | Download | only in nbperf
graph2.c revision 1.1 
      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->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 }
    173