1 /* $NetBSD: graph2.h,v 1.2 2021/01/07 16:03:08 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 2/3-graph routines: 36 * - build a 2/3-graph with hash-pairs as edges 37 * - check a 2/3-graph for acyclicness and compute an output order 38 * 39 * For each vertex in the 2/3-graph, the incidence lists need to kept. 40 * Avoid storing the full list by just XORing the indices of the still 41 * incident edges and the number of such edges as that's all the peeling 42 * computation needs. This is inspired by: 43 * Cache-Oblivious Peeling of Random Hypergraphs by Djamal Belazzougui, 44 * Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano 45 * Vigna. https://arxiv.org/abs/1312.0526 46 * 47 * Unlike in the paper, we don't care about external storage and have 48 * the edge list at hand all the time. As such, no ordering is necessary 49 * and the vertices of the edge don't have to be copied. 50 * 51 * The core observation of the paper above is that for a degree of one, 52 * the incident edge can be obtained directly. 53 */ 54 55 #ifndef GRAPH_SIZE 56 #define GRAPH_SIZE 2 57 #endif 58 59 #define SIZED__(n, i) n ## i 60 #define SIZED_(n, i) SIZED__(n, i) 61 #define SIZED(n) SIZED_(n, GRAPH_SIZE) 62 #define SIZED2__(n, i, m) n ## i ## m 63 #define SIZED2_(n, i, m) SIZED2__(n, i, m) 64 #define SIZED2(n) SIZED2_(graph, GRAPH_SIZE, n) 65 66 struct SIZED(vertex) { 67 uint32_t degree, edges; 68 }; 69 70 struct SIZED(edge) { 71 uint32_t vertices[GRAPH_SIZE]; 72 }; 73 74 struct SIZED(graph) { 75 struct SIZED(vertex) *verts; 76 struct SIZED(edge) *edges; 77 uint32_t output_index; 78 uint32_t *output_order; 79 uint8_t *visited; 80 uint32_t e, v; 81 int hash_fudge; 82 }; 83 84 void SIZED2(_setup)(struct SIZED(graph) *, uint32_t, uint32_t); 85 void SIZED2(_free)(struct SIZED(graph) *); 86 87 int SIZED2(_hash)(struct nbperf *, struct SIZED(graph) *); 88 int SIZED2(_output_order)(struct SIZED(graph) *graph); 89