p99_uf.h

Go to the documentation of this file.

/* This may look like nonsense, but it really is -*- mode: C; coding: utf-8 -*- */
/*                                                                              */
/* Except for parts copied from previous work and as explicitly stated below,   */
/* the author and copyright holder for this work is                             */
/* (C) copyright  2016 Jens Gustedt, INRIA, France                              */
/*                                                                              */
/* This file is free software; it is part of the P99 project.                   */
/*                                                                              */
/* Licensed under the Apache License, Version 2.0 (the "License");              */
/* you may not use this file except in compliance with the License.             */
/* You may obtain a copy of the License at                                      */
/*                                                                              */
/*     http://www.apache.org/licenses/LICENSE-2.0                               */
/*                                                                              */
/* Unless required by applicable law or agreed to in writing, software          */
/* distributed under the License is distributed on an "AS IS" BASIS,            */
/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.     */
/* See the License for the specific language governing permissions and          */
/* limitations under the License.                                               */
/*                                                                              */
#ifndef P99_UF_H
#define P99_UF_H
 
#include "p99_compiler.h"
#include "p99_type.h"
#include "p99_c99.h"
 
P99_DECLARE_STRUCT(p99_uf);
 
struct p99_uf {
  uint64_t size;
  int64_t tab[];
};
 
p99_inline
p99_uf* p99_uf_init(p99_uf* uf, uint64_t size) {
  if (uf) {
    *uf = (p99_uf) { .size = size, };
    memset(uf->tab, UCHAR_MAX, sizeof(int64_t[size]));
  }
  return uf;
}
 
p99_inline
void p99_uf_destroy(p99_uf const volatile* uf) {
  // empty
}
 
p99_inline
p99_uf* p99_uf_alloc(uint64_t size) {
  return p99_uf_init(malloc(sizeof(int64_t[size])+offsetof(p99_uf, tab)), size);
}
 
p99_inline
void p99_uf_free(p99_uf const volatile* uf) {
  p99_uf_destroy(uf);
  free((void*)uf);
}
 
p99_inline
bool p00_uf_root(int64_t pos, int64_t const tab[static pos+1]) {
  return tab[pos] < 0;
}
 
p99_inline
uint64_t p00_uf_size(int64_t pos, int64_t const tab[static pos+1]) {
  return p00_uf_root(pos, tab) ? -tab[pos] : 0;
}
 
p99_inline
int64_t p00_uf_find(int64_t pos, int64_t const tab[static pos+1]) {
  while (!p00_uf_root(pos, tab)) pos = tab[pos];
  return pos;
}
 
p99_inline
int64_t p99_uf_find(p99_uf const* uf, uint64_t pos) {
  if (!uf || (uf->size <= pos)) return -1;
  else return p00_uf_find(pos, uf->tab);
}
 
p99_inline
int64_t p00_uf_exchange(int64_t pos, int64_t tab[static pos+1], int64_t val) {
  int64_t ret = tab[pos];
  tab[pos] = val;
  return ret;
}
 
p99_inline
void p00_uf_compress(uint64_t pos, int64_t tab[static pos+1], uint64_t root) {
  while (!p00_uf_root(pos, tab)) {
    pos = p00_uf_exchange(pos, tab, root);
  }
}
 
p99_inline
int64_t p00_uf_findCompress(int64_t pos, int64_t tab[static pos+1]) {
  int64_t root = p00_uf_find(pos, tab);
  p00_uf_compress(pos, tab, root);
  return root;
}
 
p99_inline
int64_t p99_uf_findCompress(p99_uf* uf, uint64_t pos) {
  if (!uf || (uf->size <= pos)) return -1;
  return p00_uf_findCompress(pos, uf->tab);
}
 
p99_inline
uint64_t p99_uf_size(p99_uf* uf, uint64_t pos) {
  if (uf || (uf->size > pos)) {
    int64_t root = p00_uf_findCompress(pos, uf->tab);
    if (root >= 0 && p00_uf_root(root, uf->tab))
      return -uf->tab[root];
  }
  return 0;
}
 
p99_inline
void p00_uf_union(int64_t left, int64_t right, int64_t tab[static (left < right ? right : left)+1]) {
  tab[left] += p00_uf_exchange(right, tab, left);
}
 
p99_inline
int64_t p99_uf_union(p99_uf* uf, uint64_t left, uint64_t right) {
  int64_t root = -1;
  if (uf && (uf->size > left) && (uf->size > right)) {
    root = p00_uf_findCompress(left, uf->tab);
    if (root >= 0) {
      int64_t rright = p00_uf_find(right, uf->tab);
      if (rright >= 0) {
        // use the new root to mark all elements of the right
        p00_uf_compress(right, uf->tab, root);
        // now also link the old root on the right to the new one
        p00_uf_union(root, rright, uf->tab);
      } else
        root = rright;
    }
  }
  return root;
}
 
p99_inline
void p99_uf_flatten(p99_uf* uf, uint64_t pos, uint64_t length) {
  if (uf && (uf->size > pos) && ((uf->size-pos) >= length)) {
    for (uint64_t stop = pos+length; pos < stop; ++pos) {
      p00_uf_findCompress(pos, uf->tab);
    }
  }
}
 
#endif