1 /* $NetBSD: graph3.h,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 /* 35 * Implementation of common 3-graph routines: 36 * - build a 3-graph with hash-triple as edges 37 * - check a 3-graph for acyclicness and compute an output order 38 */ 39 40 struct vertex3 { 41 uint32_t l_edge, m_edge, r_edge; 42 }; 43 44 struct edge3 { 45 uint32_t left, middle, right; 46 uint32_t l_prev, m_prev, l_next; 47 uint32_t r_prev, m_next, r_next; 48 }; 49 50 struct graph3 { 51 struct vertex3 *verts; 52 struct edge3 *edges; 53 uint32_t output_index; 54 uint32_t *output_order; 55 uint32_t e, v; 56 }; 57 58 void graph3_setup(struct graph3 *, uint32_t, uint32_t); 59 void graph3_free(struct graph3 *); 60 61 int graph3_hash(struct nbperf *, struct graph3 *); 62 int graph3_output_order(struct graph3 *); 63