coloring.h

Go to the documentation of this file.

// Copyright 2024 Markus Anders
// This file is part of dejavu 2.0.
// See LICENSE for extended copyright information.
 
#ifndef DEJAVU_COLORING_H
#define DEJAVU_COLORING_H
 
#include <vector>
#include <cassert>
#include <cstring>
#include "utility.h"
 
namespace dejavu { namespace ds {
    // (need to nest namespaces due to C++ 14)
 
    class coloring {
    public:
        int *lab = nullptr;            
        int *ptn = nullptr;            
        int *vertex_to_col = nullptr;  
        int *vertex_to_lab = nullptr;  
        int cells       = 1;           
        int domain_size = 0;           
    private:
        int *alloc_pt = nullptr;
 
        void alloc(int sz) {
            dej_assert(sz >= 0);
 
            if (alloc_pt) dealloc();
            alloc_pt = (int *) malloc(sz * 4 * sizeof(int));
            dej_assert(alloc_pt != nullptr);
 
            lab = alloc_pt;
            ptn = lab + sz;
            vertex_to_col = lab + sz * 2;
            vertex_to_lab = lab + sz * 3;
 
            domain_size = sz;
        }
 
        void dealloc() {
            if (alloc_pt) free(alloc_pt);
            lab = nullptr;
            ptn = nullptr;
            vertex_to_col = nullptr;
            vertex_to_lab = nullptr;
 
            domain_size = 0;
        };
 
    public:
        ~coloring() {
            if (alloc_pt) {
                dealloc();
            }
        }
 
        void copy_ptn(coloring *c) const {
            dej_assert(alloc_pt);
            dej_assert(c->alloc_pt);
            dej_assert(domain_size == c->domain_size);
            memcpy(ptn, c->ptn, c->domain_size * sizeof(int));
        }
 
        void copy_from_ir_ancestor(coloring *c) {
            if (alloc_pt) {
                if (domain_size != c->domain_size) {
                    dealloc();
                } else {
                    cells = c->cells;
                    memcpy(vertex_to_col, c->vertex_to_col, c->domain_size * sizeof(int));
                    return;
                }
            }
 
            if (!alloc_pt) alloc(c->domain_size);
 
            memcpy(ptn, c->ptn, c->domain_size * sizeof(int));
            memcpy(lab, c->lab, c->domain_size * sizeof(int));
            memcpy(vertex_to_col, c->vertex_to_col, c->domain_size * sizeof(int));
            memcpy(vertex_to_lab, c->vertex_to_lab, c->domain_size * sizeof(int));
 
            domain_size = c->domain_size;
            cells = c->cells;
        }
 
        void copy_any(coloring *c) {
            if (alloc_pt) {
                if (domain_size != c->domain_size) dealloc();
            }
 
            if (!alloc_pt) {
                alloc(c->domain_size);
            }
 
            memcpy(ptn, c->ptn, c->domain_size * sizeof(int));
            memcpy(lab, c->lab, c->domain_size * sizeof(int));
            memcpy(vertex_to_col, c->vertex_to_col, c->domain_size * sizeof(int));
            memcpy(vertex_to_lab, c->vertex_to_lab, c->domain_size * sizeof(int));
 
            domain_size = c->domain_size;
            cells = c->cells;
        }
 
        void initialize(int new_domain_size) {
            alloc(new_domain_size);
        }
 
        void check() const {
            bool comp = true;
 
            for (int i = 0; i < domain_size; ++i) {
                comp = comp && (lab[i] >= 0 && lab[i] < domain_size);
                comp = comp && (lab[vertex_to_lab[i]] == i);
            }
 
            int counter = 1;
            for (int i = 0; i < domain_size; ++i) {
                --counter;
                if (counter == 0) {
                    counter = ptn[i] + 1;
                    dej_assert(ptn[i] >= 0 && ptn[i] < domain_size);
                }
            }
 
            for (int i = 0; i < domain_size;) {
                dej_assert(vertex_to_col[lab[i]] == i);
                i += ptn[i] + 1;
            }
            dej_assert(comp);
        }
    };
}}
 
#endif //DEJAVU_COLORING_H