hwloc/src/bitmap.c

/*
 * Copyright © 2009 CNRS
 * Copyright © 2009-2017 Inria.  All rights reserved.
 * Copyright © 2009-2011 Université Bordeaux
 * Copyright © 2009-2011 Cisco Systems, Inc.  All rights reserved.
 * See COPYING in top-level directory.
 */

#include <private/autogen/config.h>
#include <hwloc/autogen/config.h>
#include <hwloc.h>
#include <private/misc.h>
#include <private/private.h>
#include <hwloc/bitmap.h>

#include <stdarg.h>
#include <stdio.h>
#include <assert.h>
#include <errno.h>
#include <ctype.h>

/* TODO
 * - have a way to change the initial allocation size
 * - preallocate inside the bitmap structure (so that the whole structure is a cacheline for instance)
 *   and allocate a dedicated array only later when reallocating larger
 */

/* magic number */
#define HWLOC_BITMAP_MAGIC 0x20091007

/* actual opaque type internals */
struct hwloc_bitmap_s {
  unsigned ulongs_count; /* how many ulong bitmasks are valid, >= 1 */
  unsigned ulongs_allocated; /* how many ulong bitmasks are allocated, >= ulongs_count */
  unsigned long *ulongs;
  int infinite; /* set to 1 if all bits beyond ulongs are set */
#ifdef HWLOC_DEBUG
  int magic;
#endif
};

/* overzealous check in debug-mode, not as powerful as valgrind but still useful */
#ifdef HWLOC_DEBUG
#define HWLOC__BITMAP_CHECK(set) do {                           \
  assert((set)->magic == HWLOC_BITMAP_MAGIC);                   \
  assert((set)->ulongs_count >= 1);                             \
  assert((set)->ulongs_allocated >= (set)->ulongs_count);       \
} while (0)
#else
#define HWLOC__BITMAP_CHECK(set)
#endif

/* extract a subset from a set using an index or a cpu */
#define HWLOC_SUBBITMAP_INDEX(cpu)              ((cpu)/(HWLOC_BITS_PER_LONG))
#define HWLOC_SUBBITMAP_CPU_ULBIT(cpu)          ((cpu)%(HWLOC_BITS_PER_LONG))
/* Read from a bitmap ulong without knowing whether x is valid.
 * Writers should make sure that x is valid and modify set->ulongs[x] directly.
 */
#define HWLOC_SUBBITMAP_READULONG(set,x)        ((x) < (set)->ulongs_count ? (set)->ulongs[x] : (set)->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO)

/* predefined subset values */
#define HWLOC_SUBBITMAP_ZERO                    0UL
#define HWLOC_SUBBITMAP_FULL                    (~0UL)
#define HWLOC_SUBBITMAP_ULBIT(bit)              (1UL<<(bit))
#define HWLOC_SUBBITMAP_CPU(cpu)                HWLOC_SUBBITMAP_ULBIT(HWLOC_SUBBITMAP_CPU_ULBIT(cpu))
#define HWLOC_SUBBITMAP_ULBIT_TO(bit)           (HWLOC_SUBBITMAP_FULL>>(HWLOC_BITS_PER_LONG-1-(bit)))
#define HWLOC_SUBBITMAP_ULBIT_FROM(bit)         (HWLOC_SUBBITMAP_FULL<<(bit))
#define HWLOC_SUBBITMAP_ULBIT_FROMTO(begin,end) (HWLOC_SUBBITMAP_ULBIT_TO(end) & HWLOC_SUBBITMAP_ULBIT_FROM(begin))

struct hwloc_bitmap_s * hwloc_bitmap_alloc(void)
{
  struct hwloc_bitmap_s * set;

  set = malloc(sizeof(struct hwloc_bitmap_s));
  if (!set)
    return NULL;

  set->ulongs_count = 1;
  set->ulongs_allocated = 64/sizeof(unsigned long);
  set->ulongs = malloc(64);
  if (!set->ulongs) {
    free(set);
    return NULL;
  }

  set->ulongs[0] = HWLOC_SUBBITMAP_ZERO;
  set->infinite = 0;
#ifdef HWLOC_DEBUG
  set->magic = HWLOC_BITMAP_MAGIC;
#endif
  return set;
}

struct hwloc_bitmap_s * hwloc_bitmap_alloc_full(void)
{
  struct hwloc_bitmap_s * set = hwloc_bitmap_alloc();
  if (set) {
    set->infinite = 1;
    set->ulongs[0] = HWLOC_SUBBITMAP_FULL;
  }
  return set;
}

void hwloc_bitmap_free(struct hwloc_bitmap_s * set)
{
  if (!set)
    return;

  HWLOC__BITMAP_CHECK(set);
#ifdef HWLOC_DEBUG
  set->magic = 0;
#endif

  free(set->ulongs);
  free(set);
}

/* enlarge until it contains at least needed_count ulongs.
 */
static void
hwloc_bitmap_enlarge_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count)
{
  unsigned tmp = 1 << hwloc_flsl((unsigned long) needed_count - 1);
  if (tmp > set->ulongs_allocated) {
    set->ulongs = realloc(set->ulongs, tmp * sizeof(unsigned long));
    assert(set->ulongs);
    set->ulongs_allocated = tmp;
  }
}

/* enlarge until it contains at least needed_count ulongs,
 * and update new ulongs according to the infinite field.
 */
static void
hwloc_bitmap_realloc_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count)
{
  unsigned i;

  HWLOC__BITMAP_CHECK(set);

  if (needed_count <= set->ulongs_count)
    return;

  /* realloc larger if needed */
  hwloc_bitmap_enlarge_by_ulongs(set, needed_count);

  /* fill the newly allocated subset depending on the infinite flag */
  for(i=set->ulongs_count; i<needed_count; i++)
    set->ulongs[i] = set->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
  set->ulongs_count = needed_count;
}

/* realloc until it contains at least cpu+1 bits */
#define hwloc_bitmap_realloc_by_cpu_index(set, cpu) hwloc_bitmap_realloc_by_ulongs(set, ((cpu)/HWLOC_BITS_PER_LONG)+1)

/* reset a bitmap to exactely the needed size.
 * the caller must reinitialize all ulongs and the infinite flag later.
 */
static void
hwloc_bitmap_reset_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count)
{
  hwloc_bitmap_enlarge_by_ulongs(set, needed_count);
  set->ulongs_count = needed_count;
}

/* reset until it contains exactly cpu+1 bits (roundup to a ulong).
 * the caller must reinitialize all ulongs and the infinite flag later.
 */
#define hwloc_bitmap_reset_by_cpu_index(set, cpu) hwloc_bitmap_reset_by_ulongs(set, ((cpu)/HWLOC_BITS_PER_LONG)+1)

struct hwloc_bitmap_s * hwloc_bitmap_dup(const struct hwloc_bitmap_s * old)
{
  struct hwloc_bitmap_s * new;

  if (!old)
    return NULL;

  HWLOC__BITMAP_CHECK(old);

  new = malloc(sizeof(struct hwloc_bitmap_s));
  if (!new)
    return NULL;

  new->ulongs = malloc(old->ulongs_allocated * sizeof(unsigned long));
  if (!new->ulongs) {
    free(new);
    return NULL;
  }
  new->ulongs_allocated = old->ulongs_allocated;
  new->ulongs_count = old->ulongs_count;
  memcpy(new->ulongs, old->ulongs, new->ulongs_count * sizeof(unsigned long));
  new->infinite = old->infinite;
#ifdef HWLOC_DEBUG
  new->magic = HWLOC_BITMAP_MAGIC;
#endif
  return new;
}

void hwloc_bitmap_copy(struct hwloc_bitmap_s * dst, const struct hwloc_bitmap_s * src)
{
  HWLOC__BITMAP_CHECK(dst);
  HWLOC__BITMAP_CHECK(src);

  hwloc_bitmap_reset_by_ulongs(dst, src->ulongs_count);

  memcpy(dst->ulongs, src->ulongs, src->ulongs_count * sizeof(unsigned long));
  dst->infinite = src->infinite;
}

/* Strings always use 32bit groups */
#define HWLOC_PRIxSUBBITMAP             "%08lx"
#define HWLOC_BITMAP_SUBSTRING_SIZE     32
#define HWLOC_BITMAP_SUBSTRING_LENGTH   (HWLOC_BITMAP_SUBSTRING_SIZE/4)
#define HWLOC_BITMAP_STRING_PER_LONG    (HWLOC_BITS_PER_LONG/HWLOC_BITMAP_SUBSTRING_SIZE)

int hwloc_bitmap_snprintf(char * __hwloc_restrict buf, size_t buflen, const struct hwloc_bitmap_s * __hwloc_restrict set)
{
  ssize_t size = buflen;
  char *tmp = buf;
  int res, ret = 0;
  int needcomma = 0;
  int i;
  unsigned long accum = 0;
  int accumed = 0;
#if HWLOC_BITS_PER_LONG == HWLOC_BITMAP_SUBSTRING_SIZE
  const unsigned long accum_mask = ~0UL;
#else /* HWLOC_BITS_PER_LONG != HWLOC_BITMAP_SUBSTRING_SIZE */
  const unsigned long accum_mask = ((1UL << HWLOC_BITMAP_SUBSTRING_SIZE) - 1) << (HWLOC_BITS_PER_LONG - HWLOC_BITMAP_SUBSTRING_SIZE);
#endif /* HWLOC_BITS_PER_LONG != HWLOC_BITMAP_SUBSTRING_SIZE */

  HWLOC__BITMAP_CHECK(set);

  /* mark the end in case we do nothing later */
  if (buflen > 0)
    tmp[0] = '\0';

  if (set->infinite) {
    res = hwloc_snprintf(tmp, size, "0xf...f");
    needcomma = 1;
    if (res < 0)
      return -1;
    ret += res;
    if (res >= size)
      res = size>0 ? (int)size - 1 : 0;
    tmp += res;
    size -= res;
  }

  i=set->ulongs_count-1;

  if (set->infinite) {
    /* ignore starting FULL since we have 0xf...f already */
    while (i>=0 && set->ulongs[i] == HWLOC_SUBBITMAP_FULL)
      i--;
  } else {
    /* ignore starting ZERO except the last one */
    while (i>=0 && set->ulongs[i] == HWLOC_SUBBITMAP_ZERO)
      i--;
  }

  while (i>=0 || accumed) {
    /* Refill accumulator */
    if (!accumed) {
      accum = set->ulongs[i--];
      accumed = HWLOC_BITS_PER_LONG;
    }

    if (accum & accum_mask) {
      /* print the whole subset if not empty */
        res = hwloc_snprintf(tmp, size, needcomma ? ",0x" HWLOC_PRIxSUBBITMAP : "0x" HWLOC_PRIxSUBBITMAP,
                     (accum & accum_mask) >> (HWLOC_BITS_PER_LONG - HWLOC_BITMAP_SUBSTRING_SIZE));
      needcomma = 1;
    } else if (i == -1 && accumed == HWLOC_BITMAP_SUBSTRING_SIZE) {
      /* print a single 0 to mark the last subset */
      res = hwloc_snprintf(tmp, size, needcomma ? ",0x0" : "0x0");
    } else if (needcomma) {
      res = hwloc_snprintf(tmp, size, ",");
    } else {
      res = 0;
    }
    if (res < 0)
      return -1;
    ret += res;

#if HWLOC_BITS_PER_LONG == HWLOC_BITMAP_SUBSTRING_SIZE
    accum = 0;
    accumed = 0;
#else
    accum <<= HWLOC_BITMAP_SUBSTRING_SIZE;
    accumed -= HWLOC_BITMAP_SUBSTRING_SIZE;
#endif

    if (res >= size)
      res = size>0 ? (int)size - 1 : 0;

    tmp += res;
    size -= res;
  }

  /* if didn't display anything, display 0x0 */
  if (!ret) {
    res = hwloc_snprintf(tmp, size, "0x0");
    if (res < 0)
      return -1;
    ret += res;
  }

  return ret;
}

int hwloc_bitmap_asprintf(char ** strp, const struct hwloc_bitmap_s * __hwloc_restrict set)
{
  int len;
  char *buf;

  HWLOC__BITMAP_CHECK(set);

  len = hwloc_bitmap_snprintf(NULL, 0, set);
  buf = malloc(len+1);
  *strp = buf;
  return hwloc_bitmap_snprintf(buf, len+1, set);
}

int hwloc_bitmap_sscanf(struct hwloc_bitmap_s *set, const char * __hwloc_restrict string)
{
  const char * current = string;
  unsigned long accum = 0;
  int count=0;
  int infinite = 0;

  /* count how many substrings there are */
  count++;
  while ((current = strchr(current+1, ',')) != NULL)
    count++;

  current = string;
  if (!strncmp("0xf...f", current, 7)) {
    current += 7;
    if (*current != ',') {
      /* special case for infinite/full bitmap */
      hwloc_bitmap_fill(set);
      return 0;
    }
    current++;
    infinite = 1;
    count--;
  }

  hwloc_bitmap_reset_by_ulongs(set, (count + HWLOC_BITMAP_STRING_PER_LONG - 1) / HWLOC_BITMAP_STRING_PER_LONG);
  set->infinite = 0;

  while (*current != '\0') {
    unsigned long val;
    char *next;
    val = strtoul(current, &next, 16);

    assert(count > 0);
    count--;

    accum |= (val << ((count * HWLOC_BITMAP_SUBSTRING_SIZE) % HWLOC_BITS_PER_LONG));
    if (!(count % HWLOC_BITMAP_STRING_PER_LONG)) {
      set->ulongs[count / HWLOC_BITMAP_STRING_PER_LONG] = accum;
      accum = 0;
    }

    if (*next != ',') {
      if (*next || count > 0)
        goto failed;
      else
        break;
    }
    current = (const char*) next+1;
  }

  set->infinite = infinite; /* set at the end, to avoid spurious realloc with filled new ulongs */

  return 0;

 failed:
  /* failure to parse */
  hwloc_bitmap_zero(set);
  return -1;
}

int hwloc_bitmap_list_snprintf(char * __hwloc_restrict buf, size_t buflen, const struct hwloc_bitmap_s * __hwloc_restrict set)
{
  int prev = -1;
  hwloc_bitmap_t reverse;
  ssize_t size = buflen;
  char *tmp = buf;
  int res, ret = 0;
  int needcomma = 0;

  HWLOC__BITMAP_CHECK(set);

  reverse = hwloc_bitmap_alloc(); /* FIXME: add hwloc_bitmap_alloc_size() + hwloc_bitmap_init_allocated() to avoid malloc? */
  hwloc_bitmap_not(reverse, set);

  /* mark the end in case we do nothing later */
  if (buflen > 0)
    tmp[0] = '\0';

  while (1) {
    int begin, end;

    begin = hwloc_bitmap_next(set, prev);
    if (begin == -1)
      break;
    end = hwloc_bitmap_next(reverse, begin);

    if (end == begin+1) {
      res = hwloc_snprintf(tmp, size, needcomma ? ",%d" : "%d", begin);
    } else if (end == -1) {
      res = hwloc_snprintf(tmp, size, needcomma ? ",%d-" : "%d-", begin);
    } else {
      res = hwloc_snprintf(tmp, size, needcomma ? ",%d-%d" : "%d-%d", begin, end-1);
    }
    if (res < 0) {
      hwloc_bitmap_free(reverse);
      return -1;
    }
    ret += res;

    if (res >= size)
      res = size>0 ? (int)size - 1 : 0;

    tmp += res;
    size -= res;
    needcomma = 1;

    if (end == -1)
      break;
    else
      prev = end - 1;
  }

  hwloc_bitmap_free(reverse);

  return ret;
}

int hwloc_bitmap_list_asprintf(char ** strp, const struct hwloc_bitmap_s * __hwloc_restrict set)
{
  int len;
  char *buf;

  HWLOC__BITMAP_CHECK(set);

  len = hwloc_bitmap_list_snprintf(NULL, 0, set);
  buf = malloc(len+1);
  *strp = buf;
  return hwloc_bitmap_list_snprintf(buf, len+1, set);
}

int hwloc_bitmap_list_sscanf(struct hwloc_bitmap_s *set, const char * __hwloc_restrict string)
{
  const char * current = string;
  char *next;
  long begin = -1, val;

  hwloc_bitmap_zero(set);

  while (*current != '\0') {

    /* ignore empty ranges */
    while (*current == ',')
      current++;

    val = strtoul(current, &next, 0);
    /* make sure we got at least one digit */
    if (next == current)
      goto failed;

    if (begin != -1) {
      /* finishing a range */
      hwloc_bitmap_set_range(set, begin, val);
      begin = -1;

    } else if (*next == '-') {
      /* starting a new range */
      if (*(next+1) == '\0') {
        /* infinite range */
        hwloc_bitmap_set_range(set, val, -1);
        break;
      } else {
        /* normal range */
        begin = val;
      }

    } else if (*next == ',' || *next == '\0') {
      /* single digit */
      hwloc_bitmap_set(set, val);
    }

    if (*next == '\0')
      break;
    current = next+1;
  }

  return 0;

 failed:
  /* failure to parse */
  hwloc_bitmap_zero(set);
  return -1;
}

int hwloc_bitmap_taskset_snprintf(char * __hwloc_restrict buf, size_t buflen, const struct hwloc_bitmap_s * __hwloc_restrict set)
{
  ssize_t size = buflen;
  char *tmp = buf;
  int res, ret = 0;
  int started = 0;
  int i;

  HWLOC__BITMAP_CHECK(set);

  /* mark the end in case we do nothing later */
  if (buflen > 0)
    tmp[0] = '\0';

  if (set->infinite) {
    res = hwloc_snprintf(tmp, size, "0xf...f");
    started = 1;
    if (res < 0)
      return -1;
    ret += res;
    if (res >= size)
      res = size>0 ? (int)size - 1 : 0;
    tmp += res;
    size -= res;
  }

  i=set->ulongs_count-1;

  if (set->infinite) {
    /* ignore starting FULL since we have 0xf...f already */
    while (i>=0 && set->ulongs[i] == HWLOC_SUBBITMAP_FULL)
      i--;
  } else {
    /* ignore starting ZERO except the last one */
    while (i>=1 && set->ulongs[i] == HWLOC_SUBBITMAP_ZERO)
      i--;
  }

  while (i>=0) {
    unsigned long val = set->ulongs[i--];
    if (started) {
      /* print the whole subset */
#if HWLOC_BITS_PER_LONG == 64
      res = hwloc_snprintf(tmp, size, "%016lx", val);
#else
      res = hwloc_snprintf(tmp, size, "%08lx", val);
#endif
    } else if (val || i == -1) {
      res = hwloc_snprintf(tmp, size, "0x%lx", val);
      started = 1;
    } else {
      res = 0;
    }
    if (res < 0)
      return -1;
    ret += res;
    if (res >= size)
      res = size>0 ? (int)size - 1 : 0;
    tmp += res;
    size -= res;
  }

  /* if didn't display anything, display 0x0 */
  if (!ret) {
    res = hwloc_snprintf(tmp, size, "0x0");
    if (res < 0)
      return -1;
    ret += res;
  }

  return ret;
}

int hwloc_bitmap_taskset_asprintf(char ** strp, const struct hwloc_bitmap_s * __hwloc_restrict set)
{
  int len;
  char *buf;

  HWLOC__BITMAP_CHECK(set);

  len = hwloc_bitmap_taskset_snprintf(NULL, 0, set);
  buf = malloc(len+1);
  *strp = buf;
  return hwloc_bitmap_taskset_snprintf(buf, len+1, set);
}

int hwloc_bitmap_taskset_sscanf(struct hwloc_bitmap_s *set, const char * __hwloc_restrict string)
{
  const char * current = string;
  int chars;
  int count;
  int infinite = 0;

  if (!strncmp("0xf...f", current, 7)) {
    /* infinite bitmap */
    infinite = 1;
    current += 7;
    if (*current == '\0') {
      /* special case for infinite/full bitmap */
      hwloc_bitmap_fill(set);
      return 0;
    }
  } else {
    /* finite bitmap */
    if (!strncmp("0x", current, 2))
      current += 2;
    if (*current == '\0') {
      /* special case for empty bitmap */
      hwloc_bitmap_zero(set);
      return 0;
    }
  }
  /* we know there are other characters now */

  chars = (int)strlen(current);
  count = (chars * 4 + HWLOC_BITS_PER_LONG - 1) / HWLOC_BITS_PER_LONG;

  hwloc_bitmap_reset_by_ulongs(set, count);
  set->infinite = 0;

  while (*current != '\0') {
    int tmpchars;
    char ustr[17];
    unsigned long val;
    char *next;

    tmpchars = chars % (HWLOC_BITS_PER_LONG/4);
    if (!tmpchars)
      tmpchars = (HWLOC_BITS_PER_LONG/4);

    memcpy(ustr, current, tmpchars);
    ustr[tmpchars] = '\0';
    val = strtoul(ustr, &next, 16);
    if (*next != '\0')
      goto failed;

    set->ulongs[count-1] = val;

    current += tmpchars;
    chars -= tmpchars;
    count--;
  }

  set->infinite = infinite; /* set at the end, to avoid spurious realloc with filled new ulongs */

  return 0;

 failed:
  /* failure to parse */
  hwloc_bitmap_zero(set);
  return -1;
}

static void hwloc_bitmap__zero(struct hwloc_bitmap_s *set)
{
        unsigned i;
        for(i=0; i<set->ulongs_count; i++)
                set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
        set->infinite = 0;
}

void hwloc_bitmap_zero(struct hwloc_bitmap_s * set)
{
        HWLOC__BITMAP_CHECK(set);

        hwloc_bitmap_reset_by_ulongs(set, 1);
        hwloc_bitmap__zero(set);
}

static void hwloc_bitmap__fill(struct hwloc_bitmap_s * set)
{
        unsigned i;
        for(i=0; i<set->ulongs_count; i++)
                set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
        set->infinite = 1;
}

void hwloc_bitmap_fill(struct hwloc_bitmap_s * set)
{
        HWLOC__BITMAP_CHECK(set);

        hwloc_bitmap_reset_by_ulongs(set, 1);
        hwloc_bitmap__fill(set);
}

void hwloc_bitmap_from_ulong(struct hwloc_bitmap_s *set, unsigned long mask)
{
        HWLOC__BITMAP_CHECK(set);

        hwloc_bitmap_reset_by_ulongs(set, 1);
        set->ulongs[0] = mask; /* there's always at least one ulong allocated */
        set->infinite = 0;
}

void hwloc_bitmap_from_ith_ulong(struct hwloc_bitmap_s *set, unsigned i, unsigned long mask)
{
        unsigned j;

        HWLOC__BITMAP_CHECK(set);

        hwloc_bitmap_reset_by_ulongs(set, i+1);
        set->ulongs[i] = mask;
        for(j=0; j<i; j++)
                set->ulongs[j] = HWLOC_SUBBITMAP_ZERO;
        set->infinite = 0;
}

unsigned long hwloc_bitmap_to_ulong(const struct hwloc_bitmap_s *set)
{
        HWLOC__BITMAP_CHECK(set);

        return set->ulongs[0]; /* there's always at least one ulong allocated */
}

unsigned long hwloc_bitmap_to_ith_ulong(const struct hwloc_bitmap_s *set, unsigned i)
{
        HWLOC__BITMAP_CHECK(set);

        return HWLOC_SUBBITMAP_READULONG(set, i);
}

void hwloc_bitmap_only(struct hwloc_bitmap_s * set, unsigned cpu)
{
        unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);

        HWLOC__BITMAP_CHECK(set);

        hwloc_bitmap_reset_by_cpu_index(set, cpu);
        hwloc_bitmap__zero(set);
        set->ulongs[index_] |= HWLOC_SUBBITMAP_CPU(cpu);
}

void hwloc_bitmap_allbut(struct hwloc_bitmap_s * set, unsigned cpu)
{
        unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);

        HWLOC__BITMAP_CHECK(set);

        hwloc_bitmap_reset_by_cpu_index(set, cpu);
        hwloc_bitmap__fill(set);
        set->ulongs[index_] &= ~HWLOC_SUBBITMAP_CPU(cpu);
}

void hwloc_bitmap_set(struct hwloc_bitmap_s * set, unsigned cpu)
{
        unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);

        HWLOC__BITMAP_CHECK(set);

        /* nothing to do if setting inside the infinite part of the bitmap */
        if (set->infinite && cpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
                return;

        hwloc_bitmap_realloc_by_cpu_index(set, cpu);
        set->ulongs[index_] |= HWLOC_SUBBITMAP_CPU(cpu);
}

void hwloc_bitmap_set_range(struct hwloc_bitmap_s * set, unsigned begincpu, int _endcpu)
{
        unsigned i;
        unsigned beginset,endset;
        unsigned endcpu = (unsigned) _endcpu;

        HWLOC__BITMAP_CHECK(set);

        if (endcpu < begincpu)
                return;
        if (set->infinite && begincpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
                /* setting only in the already-set infinite part, nothing to do */
                return;

        if (_endcpu == -1) {
                /* infinite range */

                /* make sure we can play with the ulong that contains begincpu */
                hwloc_bitmap_realloc_by_cpu_index(set, begincpu);
                /* update the ulong that contains begincpu */
                beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
                set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
                /* set ulongs after begincpu if any already allocated */
                for(i=beginset+1; i<set->ulongs_count; i++)
                        set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
                /* mark the infinity as set */
                set->infinite = 1;
        } else {
                /* finite range */

                /* ignore the part of the range that overlaps with the already-set infinite part */
                if (set->infinite && endcpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
                        endcpu = set->ulongs_count * HWLOC_BITS_PER_LONG - 1;
                /* make sure we can play with the ulongs that contain begincpu and endcpu */
                hwloc_bitmap_realloc_by_cpu_index(set, endcpu);
                /* update first and last ulongs */
                beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
                endset = HWLOC_SUBBITMAP_INDEX(endcpu);
                if (beginset == endset) {
                        set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROMTO(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu), HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
                } else {
                        set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
                        set->ulongs[endset] |= HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
                }
                /* set ulongs in the middle of the range */
                for(i=beginset+1; i<endset; i++)
                        set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
        }
}

void hwloc_bitmap_set_ith_ulong(struct hwloc_bitmap_s *set, unsigned i, unsigned long mask)
{
        HWLOC__BITMAP_CHECK(set);

        hwloc_bitmap_realloc_by_ulongs(set, i+1);
        set->ulongs[i] = mask;
}

void hwloc_bitmap_clr(struct hwloc_bitmap_s * set, unsigned cpu)
{
        unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);

        HWLOC__BITMAP_CHECK(set);

        /* nothing to do if clearing inside the infinitely-unset part of the bitmap */
        if (!set->infinite && cpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
                return;

        hwloc_bitmap_realloc_by_cpu_index(set, cpu);
        set->ulongs[index_] &= ~HWLOC_SUBBITMAP_CPU(cpu);
}

void hwloc_bitmap_clr_range(struct hwloc_bitmap_s * set, unsigned begincpu, int _endcpu)
{
        unsigned i;
        unsigned beginset,endset;
        unsigned endcpu = (unsigned) _endcpu;

        HWLOC__BITMAP_CHECK(set);

        if (endcpu < begincpu)
                return;

        if (!set->infinite && begincpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
                /* clearing only in the already-unset infinite part, nothing to do */
                return;

        if (_endcpu == -1) {
                /* infinite range */

                /* make sure we can play with the ulong that contains begincpu */
                hwloc_bitmap_realloc_by_cpu_index(set, begincpu);
                /* update the ulong that contains begincpu */
                beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
                set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
                /* clear ulong after begincpu if any already allocated */
                for(i=beginset+1; i<set->ulongs_count; i++)
                        set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
                /* mark the infinity as unset */
                set->infinite = 0;
        } else {
                /* finite range */

                /* ignore the part of the range that overlaps with the already-unset infinite part */
                if (!set->infinite && endcpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
                        endcpu = set->ulongs_count * HWLOC_BITS_PER_LONG - 1;
                /* make sure we can play with the ulongs that contain begincpu and endcpu */
                hwloc_bitmap_realloc_by_cpu_index(set, endcpu);
                /* update first and last ulongs */
                beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
                endset = HWLOC_SUBBITMAP_INDEX(endcpu);
                if (beginset == endset) {
                        set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROMTO(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu), HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
                } else {
                        set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
                        set->ulongs[endset] &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
                }
                /* clear ulongs in the middle of the range */
                for(i=beginset+1; i<endset; i++)
                        set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
        }
}

int hwloc_bitmap_isset(const struct hwloc_bitmap_s * set, unsigned cpu)
{
        unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);

        HWLOC__BITMAP_CHECK(set);

        return (HWLOC_SUBBITMAP_READULONG(set, index_) & HWLOC_SUBBITMAP_CPU(cpu)) != 0;
}

int hwloc_bitmap_iszero(const struct hwloc_bitmap_s *set)
{
        unsigned i;

        HWLOC__BITMAP_CHECK(set);

        if (set->infinite)
                return 0;
        for(i=0; i<set->ulongs_count; i++)
                if (set->ulongs[i] != HWLOC_SUBBITMAP_ZERO)
                        return 0;
        return 1;
}

int hwloc_bitmap_isfull(const struct hwloc_bitmap_s *set)
{
        unsigned i;

        HWLOC__BITMAP_CHECK(set);

        if (!set->infinite)
                return 0;
        for(i=0; i<set->ulongs_count; i++)
                if (set->ulongs[i] != HWLOC_SUBBITMAP_FULL)
                        return 0;
        return 1;
}

int hwloc_bitmap_isequal (const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
{
        unsigned count1 = set1->ulongs_count;
        unsigned count2 = set2->ulongs_count;
        unsigned min_count = count1 < count2 ? count1 : count2;
        unsigned i;

        HWLOC__BITMAP_CHECK(set1);
        HWLOC__BITMAP_CHECK(set2);

        for(i=0; i<min_count; i++)
                if (set1->ulongs[i] != set2->ulongs[i])
                        return 0;

        if (count1 != count2) {
                unsigned long w1 = set1->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
                unsigned long w2 = set2->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
                for(i=min_count; i<count1; i++) {
                        if (set1->ulongs[i] != w2)
                                return 0;
                }
                for(i=min_count; i<count2; i++) {
                        if (set2->ulongs[i] != w1)
                                return 0;
                }
        }

        if (set1->infinite != set2->infinite)
                return 0;

        return 1;
}

int hwloc_bitmap_intersects (const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
{
        unsigned count1 = set1->ulongs_count;
        unsigned count2 = set2->ulongs_count;
        unsigned min_count = count1 < count2 ? count1 : count2;
        unsigned i;

        HWLOC__BITMAP_CHECK(set1);
        HWLOC__BITMAP_CHECK(set2);

        for(i=0; i<min_count; i++)
                if (set1->ulongs[i] & set2->ulongs[i])
                        return 1;

        if (count1 != count2) {
                if (set2->infinite) {
                        for(i=min_count; i<set1->ulongs_count; i++)
                                if (set1->ulongs[i])
                                        return 1;
                }
                if (set1->infinite) {
                        for(i=min_count; i<set2->ulongs_count; i++)
                                if (set2->ulongs[i])
                                        return 1;
                }
        }

        if (set1->infinite && set2->infinite)
                return 1;

        return 0;
}

int hwloc_bitmap_isincluded (const struct hwloc_bitmap_s *sub_set, const struct hwloc_bitmap_s *super_set)
{
        unsigned super_count = super_set->ulongs_count;
        unsigned sub_count = sub_set->ulongs_count;
        unsigned min_count = super_count < sub_count ? super_count : sub_count;
        unsigned i;

        HWLOC__BITMAP_CHECK(sub_set);
        HWLOC__BITMAP_CHECK(super_set);

        for(i=0; i<min_count; i++)
                if (super_set->ulongs[i] != (super_set->ulongs[i] | sub_set->ulongs[i]))
                        return 0;

        if (super_count != sub_count) {
                if (!super_set->infinite)
                        for(i=min_count; i<sub_count; i++)
                                if (sub_set->ulongs[i])
                                        return 0;
                if (sub_set->infinite)
                        for(i=min_count; i<super_count; i++)
                                if (super_set->ulongs[i] != HWLOC_SUBBITMAP_FULL)
                                        return 0;
        }

        if (sub_set->infinite && !super_set->infinite)
                return 0;

        return 1;
}

void hwloc_bitmap_or (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
{
        /* cache counts so that we can reset res even if it's also set1 or set2 */
        unsigned count1 = set1->ulongs_count;
        unsigned count2 = set2->ulongs_count;
        unsigned max_count = count1 > count2 ? count1 : count2;
        unsigned min_count = count1 + count2 - max_count;
        unsigned i;

        HWLOC__BITMAP_CHECK(res);
        HWLOC__BITMAP_CHECK(set1);
        HWLOC__BITMAP_CHECK(set2);

        hwloc_bitmap_reset_by_ulongs(res, max_count);

        for(i=0; i<min_count; i++)
                res->ulongs[i] = set1->ulongs[i] | set2->ulongs[i];

        if (count1 != count2) {
                if (min_count < count1) {
                        if (set2->infinite) {
                                res->ulongs_count = min_count;
                        } else {
                                for(i=min_count; i<max_count; i++)
                                        res->ulongs[i] = set1->ulongs[i];
                        }
                } else {
                        if (set1->infinite) {
                                res->ulongs_count = min_count;
                        } else {
                                for(i=min_count; i<max_count; i++)
                                        res->ulongs[i] = set2->ulongs[i];
                        }
                }
        }

        res->infinite = set1->infinite || set2->infinite;
}

void hwloc_bitmap_and (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
{
        /* cache counts so that we can reset res even if it's also set1 or set2 */
        unsigned count1 = set1->ulongs_count;
        unsigned count2 = set2->ulongs_count;
        unsigned max_count = count1 > count2 ? count1 : count2;
        unsigned min_count = count1 + count2 - max_count;
        unsigned i;

        HWLOC__BITMAP_CHECK(res);
        HWLOC__BITMAP_CHECK(set1);
        HWLOC__BITMAP_CHECK(set2);

        hwloc_bitmap_reset_by_ulongs(res, max_count);

        for(i=0; i<min_count; i++)
                res->ulongs[i] = set1->ulongs[i] & set2->ulongs[i];

        if (count1 != count2) {
                if (min_count < count1) {
                        if (set2->infinite) {
                                for(i=min_count; i<max_count; i++)
                                        res->ulongs[i] = set1->ulongs[i];
                        } else {
                                res->ulongs_count = min_count;
                        }
                } else {
                        if (set1->infinite) {
                                for(i=min_count; i<max_count; i++)
                                        res->ulongs[i] = set2->ulongs[i];
                        } else {
                                res->ulongs_count = min_count;
                        }
                }
        }

        res->infinite = set1->infinite && set2->infinite;
}

void hwloc_bitmap_andnot (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
{
        /* cache counts so that we can reset res even if it's also set1 or set2 */
        unsigned count1 = set1->ulongs_count;
        unsigned count2 = set2->ulongs_count;
        unsigned max_count = count1 > count2 ? count1 : count2;
        unsigned min_count = count1 + count2 - max_count;
        unsigned i;

        HWLOC__BITMAP_CHECK(res);
        HWLOC__BITMAP_CHECK(set1);
        HWLOC__BITMAP_CHECK(set2);

        hwloc_bitmap_reset_by_ulongs(res, max_count);

        for(i=0; i<min_count; i++)
                res->ulongs[i] = set1->ulongs[i] & ~set2->ulongs[i];

        if (count1 != count2) {
                if (min_count < count1) {
                        if (!set2->infinite) {
                                for(i=min_count; i<max_count; i++)
                                        res->ulongs[i] = set1->ulongs[i];
                        } else {
                                res->ulongs_count = min_count;
                        }
                } else {
                        if (set1->infinite) {
                                for(i=min_count; i<max_count; i++)
                                        res->ulongs[i] = ~set2->ulongs[i];
                        } else {
                                res->ulongs_count = min_count;
                        }
                }
        }

        res->infinite = set1->infinite && !set2->infinite;
}

void hwloc_bitmap_xor (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
{
        /* cache counts so that we can reset res even if it's also set1 or set2 */
        unsigned count1 = set1->ulongs_count;
        unsigned count2 = set2->ulongs_count;
        unsigned max_count = count1 > count2 ? count1 : count2;
        unsigned min_count = count1 + count2 - max_count;
        unsigned i;

        HWLOC__BITMAP_CHECK(res);
        HWLOC__BITMAP_CHECK(set1);
        HWLOC__BITMAP_CHECK(set2);

        hwloc_bitmap_reset_by_ulongs(res, max_count);

        for(i=0; i<min_count; i++)
                res->ulongs[i] = set1->ulongs[i] ^ set2->ulongs[i];

        if (count1 != count2) {
                if (min_count < count1) {
                        unsigned long w2 = set2->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
                        for(i=min_count; i<max_count; i++)
                                res->ulongs[i] = set1->ulongs[i] ^ w2;
                } else {
                        unsigned long w1 = set1->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
                        for(i=min_count; i<max_count; i++)
                                res->ulongs[i] = set2->ulongs[i] ^ w1;
                }
        }

        res->infinite = (!set1->infinite) != (!set2->infinite);
}

void hwloc_bitmap_not (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set)
{
        unsigned count = set->ulongs_count;
        unsigned i;

        HWLOC__BITMAP_CHECK(res);
        HWLOC__BITMAP_CHECK(set);

        hwloc_bitmap_reset_by_ulongs(res, count);

        for(i=0; i<count; i++)
                res->ulongs[i] = ~set->ulongs[i];

        res->infinite = !set->infinite;
}

int hwloc_bitmap_first(const struct hwloc_bitmap_s * set)
{
        unsigned i;

        HWLOC__BITMAP_CHECK(set);

        for(i=0; i<set->ulongs_count; i++) {
                /* subsets are unsigned longs, use ffsl */
                unsigned long w = set->ulongs[i];
                if (w)
                        return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
        }

        if (set->infinite)
                return set->ulongs_count * HWLOC_BITS_PER_LONG;

        return -1;
}

int hwloc_bitmap_last(const struct hwloc_bitmap_s * set)
{
        int i;

        HWLOC__BITMAP_CHECK(set);

        if (set->infinite)
                return -1;

        for(i=set->ulongs_count-1; i>=0; i--) {
                /* subsets are unsigned longs, use flsl */
                unsigned long w = set->ulongs[i];
                if (w)
                        return hwloc_flsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
        }

        return -1;
}

int hwloc_bitmap_next(const struct hwloc_bitmap_s * set, int prev_cpu)
{
        unsigned i = HWLOC_SUBBITMAP_INDEX(prev_cpu + 1);

        HWLOC__BITMAP_CHECK(set);

        if (i >= set->ulongs_count) {
                if (set->infinite)
                        return prev_cpu + 1;
                else
                        return -1;
        }

        for(; i<set->ulongs_count; i++) {
                /* subsets are unsigned longs, use ffsl */
                unsigned long w = set->ulongs[i];

                /* if the prev cpu is in the same word as the possible next one,
                   we need to mask out previous cpus */
                if (prev_cpu >= 0 && HWLOC_SUBBITMAP_INDEX((unsigned) prev_cpu) == i)
                        w &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(prev_cpu));

                if (w)
                        return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
        }

        if (set->infinite)
                return set->ulongs_count * HWLOC_BITS_PER_LONG;

        return -1;
}

void hwloc_bitmap_singlify(struct hwloc_bitmap_s * set)
{
        unsigned i;
        int found = 0;

        HWLOC__BITMAP_CHECK(set);

        for(i=0; i<set->ulongs_count; i++) {
                if (found) {
                        set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
                        continue;
                } else {
                        /* subsets are unsigned longs, use ffsl */
                        unsigned long w = set->ulongs[i];
                        if (w) {
                                int _ffs = hwloc_ffsl(w);
                                set->ulongs[i] = HWLOC_SUBBITMAP_CPU(_ffs-1);
                                found = 1;
                        }
                }
        }

        if (set->infinite) {
                if (found) {
                        set->infinite = 0;
                } else {
                        /* set the first non allocated bit */
                        unsigned first = set->ulongs_count * HWLOC_BITS_PER_LONG;
                        set->infinite = 0; /* do not let realloc fill the newly allocated sets */
                        hwloc_bitmap_set(set, first);
                }
        }
}

int hwloc_bitmap_compare_first(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
{
        unsigned count1 = set1->ulongs_count;
        unsigned count2 = set2->ulongs_count;
        unsigned max_count = count1 > count2 ? count1 : count2;
        unsigned min_count = count1 + count2 - max_count;
        unsigned i;

        HWLOC__BITMAP_CHECK(set1);
        HWLOC__BITMAP_CHECK(set2);

        for(i=0; i<min_count; i++) {
                unsigned long w1 = set1->ulongs[i];
                unsigned long w2 = set2->ulongs[i];
                if (w1 || w2) {
                        int _ffs1 = hwloc_ffsl(w1);
                        int _ffs2 = hwloc_ffsl(w2);
                        /* if both have a bit set, compare for real */
                        if (_ffs1 && _ffs2)
                                return _ffs1-_ffs2;
                        /* one is empty, and it is considered higher, so reverse-compare them */
                        return _ffs2-_ffs1;
                }
        }

        if (count1 != count2) {
                if (min_count < count2) {
                        for(i=min_count; i<count2; i++) {
                                unsigned long w2 = set2->ulongs[i];
                                if (set1->infinite)
                                        return -!(w2 & 1);
                                else if (w2)
                                        return 1;
                        }
                } else {
                        for(i=min_count; i<count1; i++) {
                                unsigned long w1 = set1->ulongs[i];
                                if (set2->infinite)
                                        return !(w1 & 1);
                                else if (w1)
                                        return -1;
                        }
                }
        }

        return !!set1->infinite - !!set2->infinite;
}

int hwloc_bitmap_compare(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
{
        unsigned count1 = set1->ulongs_count;
        unsigned count2 = set2->ulongs_count;
        unsigned max_count = count1 > count2 ? count1 : count2;
        unsigned min_count = count1 + count2 - max_count;
        int i;

        HWLOC__BITMAP_CHECK(set1);
        HWLOC__BITMAP_CHECK(set2);

        if ((!set1->infinite) != (!set2->infinite))
                return !!set1->infinite - !!set2->infinite;

        if (count1 != count2) {
                if (min_count < count2) {
                        unsigned long val1 = set1->infinite ? HWLOC_SUBBITMAP_FULL :  HWLOC_SUBBITMAP_ZERO;
                        for(i=max_count-1; i>=(signed) min_count; i--) {
                                unsigned long val2 = set2->ulongs[i];
                                if (val1 == val2)
                                        continue;
                                return val1 < val2 ? -1 : 1;
                        }
                } else {
                        unsigned long val2 = set2->infinite ? HWLOC_SUBBITMAP_FULL :  HWLOC_SUBBITMAP_ZERO;
                        for(i=max_count-1; i>=(signed) min_count; i--) {
                                unsigned long val1 = set1->ulongs[i];
                                if (val1 == val2)
                                        continue;
                                return val1 < val2 ? -1 : 1;
                        }
                }
        }

        for(i=min_count-1; i>=0; i--) {
                unsigned long val1 = set1->ulongs[i];
                unsigned long val2 = set2->ulongs[i];
                if (val1 == val2)
                        continue;
                return val1 < val2 ? -1 : 1;
        }

        return 0;
}

int hwloc_bitmap_weight(const struct hwloc_bitmap_s * set)
{
        int weight = 0;
        unsigned i;

        HWLOC__BITMAP_CHECK(set);

        if (set->infinite)
                return -1;

        for(i=0; i<set->ulongs_count; i++)
                weight += hwloc_weight_long(set->ulongs[i]);
        return weight;
}

int hwloc_bitmap_compare_inclusion(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
{
        unsigned max_count = set1->ulongs_count > set2->ulongs_count ? set1->ulongs_count : set2->ulongs_count;
        int result = HWLOC_BITMAP_EQUAL; /* means empty sets return equal */
        int empty1 = 1;
        int empty2 = 1;
        unsigned i;

        HWLOC__BITMAP_CHECK(set1);
        HWLOC__BITMAP_CHECK(set2);

        for(i=0; i<max_count; i++) {
          unsigned long val1 = HWLOC_SUBBITMAP_READULONG(set1, (unsigned) i);
          unsigned long val2 = HWLOC_SUBBITMAP_READULONG(set2, (unsigned) i);

          if (!val1) {
            if (!val2)
              /* both empty, no change */
              continue;

            /* val1 empty, val2 not */
            if (result == HWLOC_BITMAP_CONTAINS) {
              if (!empty2)
                return HWLOC_BITMAP_INTERSECTS;
              result = HWLOC_BITMAP_DIFFERENT;
            } else if (result == HWLOC_BITMAP_EQUAL) {
              result = HWLOC_BITMAP_INCLUDED;
            }
            /* no change otherwise */

          } else if (!val2) {
            /* val2 empty, val1 not */
            if (result == HWLOC_BITMAP_INCLUDED) {
              if (!empty1)
                return HWLOC_BITMAP_INTERSECTS;
              result = HWLOC_BITMAP_DIFFERENT;
            } else if (result == HWLOC_BITMAP_EQUAL) {
              result = HWLOC_BITMAP_CONTAINS;
            }
            /* no change otherwise */

          } else if (val1 == val2) {
            /* equal and not empty */
            if (result == HWLOC_BITMAP_DIFFERENT)
              return HWLOC_BITMAP_INTERSECTS;
            /* equal/contains/included unchanged */

          } else if ((val1 & val2) == val1) {
            /* included and not empty */
            if (result == HWLOC_BITMAP_CONTAINS || result == HWLOC_BITMAP_DIFFERENT)
              return HWLOC_BITMAP_INTERSECTS;
            /* equal/included unchanged */
            result = HWLOC_BITMAP_INCLUDED;

          } else if ((val1 & val2) == val2) {
            /* contains and not empty */
            if (result == HWLOC_BITMAP_INCLUDED || result == HWLOC_BITMAP_DIFFERENT)
              return HWLOC_BITMAP_INTERSECTS;
            /* equal/contains unchanged */
            result = HWLOC_BITMAP_CONTAINS;

          } else if ((val1 & val2) != 0) {
            /* intersects and not empty */
            return HWLOC_BITMAP_INTERSECTS;

          } else {
            /* different and not empty */

            /* equal/included/contains with non-empty sets means intersects */
            if (result == HWLOC_BITMAP_EQUAL && !empty1 /* implies !empty2 */)
              return HWLOC_BITMAP_INTERSECTS;
            if (result == HWLOC_BITMAP_INCLUDED && !empty1)
              return HWLOC_BITMAP_INTERSECTS;
            if (result == HWLOC_BITMAP_CONTAINS && !empty2)
              return HWLOC_BITMAP_INTERSECTS;
            /* otherwise means different */
            result = HWLOC_BITMAP_DIFFERENT;
          }

          empty1 &= !val1;
          empty2 &= !val2;
        }

        if (!set1->infinite) {
          if (set2->infinite) {
            /* set2 infinite only */
            if (result == HWLOC_BITMAP_CONTAINS) {
              if (!empty2)
                return HWLOC_BITMAP_INTERSECTS;
              result = HWLOC_BITMAP_DIFFERENT;
            } else if (result == HWLOC_BITMAP_EQUAL) {
              result = HWLOC_BITMAP_INCLUDED;
            }
            /* no change otherwise */
          }
        } else if (!set2->infinite) {
          /* set1 infinite only */
          if (result == HWLOC_BITMAP_INCLUDED) {
            if (!empty1)
              return HWLOC_BITMAP_INTERSECTS;
            result = HWLOC_BITMAP_DIFFERENT;
          } else if (result == HWLOC_BITMAP_EQUAL) {
            result = HWLOC_BITMAP_CONTAINS;
          }
          /* no change otherwise */
        } else {
          /* both infinite */
          if (result == HWLOC_BITMAP_DIFFERENT)
            return HWLOC_BITMAP_INTERSECTS;
          /* equal/contains/included unchanged */
        }

        return result;
}