Changeset View
Changeset View
Standalone View
Standalone View
contrib/mg/graph2.h
- This file was added.
/* $NetBSD: graph2.h,v 1.1 2009/08/15 16:21:05 joerg Exp $ */ | |||||
/*- | |||||
* Copyright (c) 2009 The NetBSD Foundation, Inc. | |||||
* All rights reserved. | |||||
* | |||||
* This code is derived from software contributed to The NetBSD Foundation | |||||
* by Joerg Sonnenberger. | |||||
* | |||||
* Redistribution and use in source and binary forms, with or without | |||||
* modification, are permitted provided that the following conditions | |||||
* are met: | |||||
* | |||||
* 1. Redistributions of source code must retain the above copyright | |||||
* notice, this list of conditions and the following disclaimer. | |||||
* 2. Redistributions in binary form must reproduce the above copyright | |||||
* notice, this list of conditions and the following disclaimer in | |||||
* the documentation and/or other materials provided with the | |||||
* distribution. | |||||
* | |||||
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |||||
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |||||
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS | |||||
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE | |||||
* COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, | |||||
* INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, | |||||
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |||||
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED | |||||
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, | |||||
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT | |||||
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |||||
* SUCH DAMAGE. | |||||
*/ | |||||
/* | |||||
* Implementation of common 2-graph routines: | |||||
* - build a 2-graph with hash-pairs as edges | |||||
* - check a 2-graph for acyclicness and compute an output order | |||||
*/ | |||||
struct vertex2 { | |||||
uint32_t l_edge, r_edge; | |||||
}; | |||||
struct edge2 { | |||||
uint32_t left, right; | |||||
uint32_t l_prev, l_next; | |||||
uint32_t r_prev, r_next; | |||||
}; | |||||
struct graph2 { | |||||
struct vertex2 *verts; | |||||
struct edge2 *edges; | |||||
uint32_t output_index; | |||||
uint32_t *output_order; | |||||
uint8_t *visited; | |||||
uint32_t e, v; | |||||
}; | |||||
void graph2_setup(struct graph2 *, uint32_t, uint32_t); | |||||
void graph2_free(struct graph2 *); | |||||
int graph2_hash(struct nbperf *, struct graph2 *); | |||||
int graph2_output_order(struct graph2 *graph); |