opal/mca/hwloc/hwloc201/hwloc/hwloc/bitmap.c

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
hwloc_bitmap_alloc
hwloc_bitmap_alloc_full
hwloc_bitmap_free
hwloc_bitmap_enlarge_by_ulongs
hwloc_bitmap_realloc_by_ulongs
hwloc_bitmap_reset_by_ulongs
hwloc_bitmap_tma_dup
hwloc_bitmap_dup
hwloc_bitmap_copy
hwloc_bitmap_snprintf
hwloc_bitmap_asprintf
hwloc_bitmap_sscanf
hwloc_bitmap_list_snprintf
hwloc_bitmap_list_asprintf
hwloc_bitmap_list_sscanf
hwloc_bitmap_taskset_snprintf
hwloc_bitmap_taskset_asprintf
hwloc_bitmap_taskset_sscanf
hwloc_bitmap__zero
hwloc_bitmap_zero
hwloc_bitmap__fill
hwloc_bitmap_fill
hwloc_bitmap_from_ulong
hwloc_bitmap_from_ith_ulong
hwloc_bitmap_to_ulong
hwloc_bitmap_to_ith_ulong
hwloc_bitmap_only
hwloc_bitmap_allbut
hwloc_bitmap_set
hwloc_bitmap_set_range
hwloc_bitmap_set_ith_ulong
hwloc_bitmap_clr
hwloc_bitmap_clr_range
hwloc_bitmap_isset
hwloc_bitmap_iszero
hwloc_bitmap_isfull
hwloc_bitmap_isequal
hwloc_bitmap_intersects
hwloc_bitmap_isincluded
hwloc_bitmap_or
hwloc_bitmap_and
hwloc_bitmap_andnot
hwloc_bitmap_xor
hwloc_bitmap_not
hwloc_bitmap_first
hwloc_bitmap_first_unset
hwloc_bitmap_last
hwloc_bitmap_last_unset
hwloc_bitmap_next
hwloc_bitmap_next_unset
hwloc_bitmap_singlify
hwloc_bitmap_compare_first
hwloc_bitmap_compare
hwloc_bitmap_weight
hwloc_bitmap_compare_inclusion
   1 /*
   2  * Copyright © 2009 CNRS
   3  * Copyright © 2009-2017 Inria.  All rights reserved.
   4  * Copyright © 2009-2011 Université Bordeaux
   5  * Copyright © 2009-2011 Cisco Systems, Inc.  All rights reserved.
   6  * See COPYING in top-level directory.
   7  */
   8 
   9 #include <private/autogen/config.h>
  10 #include <hwloc/autogen/config.h>
  11 #include <hwloc.h>
  12 #include <private/misc.h>
  13 #include <private/private.h>
  14 #include <private/debug.h>
  15 #include <hwloc/bitmap.h>
  16 
  17 #include <stdarg.h>
  18 #include <stdio.h>
  19 #include <assert.h>
  20 #include <errno.h>
  21 #include <ctype.h>
  22 
  23 /*
  24  * possible improvements:
  25  * - have a way to change the initial allocation size:
  26  *   add hwloc_bitmap_set_foo() to changes a global here,
  27  *   and make the hwloc core call based on the early number of PUs
  28  * - make HWLOC_BITMAP_PREALLOC_BITS configurable, and detectable
  29  *   by parsing /proc/cpuinfo during configure on Linux.
  30  * - preallocate inside the bitmap structure (so that the whole structure is a cacheline for instance)
  31  *   and allocate a dedicated array only later when reallocating larger
  32  * - add a bitmap->ulongs_empty_first which guarantees that some first ulongs are empty,
  33  *   making tests much faster for big bitmaps since there's no need to look at first ulongs.
  34  *   no need for ulongs_empty_first to be exactly the max number of empty ulongs,
  35  *   clearing bits that were set earlier isn't very common.
  36  */
  37 
  38 /* magic number */
  39 #define HWLOC_BITMAP_MAGIC 0x20091007
  40 
  41 /* preallocated bits in every bitmap */
  42 #define HWLOC_BITMAP_PREALLOC_BITS 512
  43 #define HWLOC_BITMAP_PREALLOC_ULONGS (HWLOC_BITMAP_PREALLOC_BITS/HWLOC_BITS_PER_LONG)
  44 
  45 /* actual opaque type internals */
  46 struct hwloc_bitmap_s {
  47   unsigned ulongs_count; /* how many ulong bitmasks are valid, >= 1 */
  48   unsigned ulongs_allocated; /* how many ulong bitmasks are allocated, >= ulongs_count */
  49   unsigned long *ulongs;
  50   int infinite; /* set to 1 if all bits beyond ulongs are set */
  51 #ifdef HWLOC_DEBUG
  52   int magic;
  53 #endif
  54 };
  55 
  56 /* overzealous check in debug-mode, not as powerful as valgrind but still useful */
  57 #ifdef HWLOC_DEBUG
  58 #define HWLOC__BITMAP_CHECK(set) do {                           \
  59   assert((set)->magic == HWLOC_BITMAP_MAGIC);                   \
  60   assert((set)->ulongs_count >= 1);                             \
  61   assert((set)->ulongs_allocated >= (set)->ulongs_count);       \
  62 } while (0)
  63 #else
  64 #define HWLOC__BITMAP_CHECK(set)
  65 #endif
  66 
  67 /* extract a subset from a set using an index or a cpu */
  68 #define HWLOC_SUBBITMAP_INDEX(cpu)              ((cpu)/(HWLOC_BITS_PER_LONG))
  69 #define HWLOC_SUBBITMAP_CPU_ULBIT(cpu)          ((cpu)%(HWLOC_BITS_PER_LONG))
  70 /* Read from a bitmap ulong without knowing whether x is valid.
  71  * Writers should make sure that x is valid and modify set->ulongs[x] directly.
  72  */
  73 #define HWLOC_SUBBITMAP_READULONG(set,x)        ((x) < (set)->ulongs_count ? (set)->ulongs[x] : (set)->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO)
  74 
  75 /* predefined subset values */
  76 #define HWLOC_SUBBITMAP_ZERO                    0UL
  77 #define HWLOC_SUBBITMAP_FULL                    (~0UL)
  78 #define HWLOC_SUBBITMAP_ULBIT(bit)              (1UL<<(bit))
  79 #define HWLOC_SUBBITMAP_CPU(cpu)                HWLOC_SUBBITMAP_ULBIT(HWLOC_SUBBITMAP_CPU_ULBIT(cpu))
  80 #define HWLOC_SUBBITMAP_ULBIT_TO(bit)           (HWLOC_SUBBITMAP_FULL>>(HWLOC_BITS_PER_LONG-1-(bit)))
  81 #define HWLOC_SUBBITMAP_ULBIT_FROM(bit)         (HWLOC_SUBBITMAP_FULL<<(bit))
  82 #define HWLOC_SUBBITMAP_ULBIT_FROMTO(begin,end) (HWLOC_SUBBITMAP_ULBIT_TO(end) & HWLOC_SUBBITMAP_ULBIT_FROM(begin))
  83 
  84 struct hwloc_bitmap_s * hwloc_bitmap_alloc(void)
  85 {
  86   struct hwloc_bitmap_s * set;
  87 
  88   set = malloc(sizeof(struct hwloc_bitmap_s));
  89   if (!set)
  90     return NULL;
  91 
  92   set->ulongs_count = 1;
  93   set->ulongs_allocated = HWLOC_BITMAP_PREALLOC_ULONGS;
  94   set->ulongs = malloc(HWLOC_BITMAP_PREALLOC_ULONGS * sizeof(unsigned long));
  95   if (!set->ulongs) {
  96     free(set);
  97     return NULL;
  98   }
  99 
 100   set->ulongs[0] = HWLOC_SUBBITMAP_ZERO;
 101   set->infinite = 0;
 102 #ifdef HWLOC_DEBUG
 103   set->magic = HWLOC_BITMAP_MAGIC;
 104 #endif
 105   return set;
 106 }
 107 
 108 struct hwloc_bitmap_s * hwloc_bitmap_alloc_full(void)
 109 {
 110   struct hwloc_bitmap_s * set = hwloc_bitmap_alloc();
 111   if (set) {
 112     set->infinite = 1;
 113     set->ulongs[0] = HWLOC_SUBBITMAP_FULL;
 114   }
 115   return set;
 116 }
 117 
 118 void hwloc_bitmap_free(struct hwloc_bitmap_s * set)
 119 {
 120   if (!set)
 121     return;
 122 
 123   HWLOC__BITMAP_CHECK(set);
 124 #ifdef HWLOC_DEBUG
 125   set->magic = 0;
 126 #endif
 127 
 128   free(set->ulongs);
 129   free(set);
 130 }
 131 
 132 /* enlarge until it contains at least needed_count ulongs.
 133  */
 134 static int
 135 hwloc_bitmap_enlarge_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count) __hwloc_attribute_warn_unused_result;
 136 static int
 137 hwloc_bitmap_enlarge_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count)
 138 {
 139   unsigned tmp = 1U << hwloc_flsl((unsigned long) needed_count - 1);
 140   if (tmp > set->ulongs_allocated) {
 141     unsigned long *tmpulongs;
 142     tmpulongs = realloc(set->ulongs, tmp * sizeof(unsigned long));
 143     if (!tmpulongs)
 144       return -1;
 145     set->ulongs = tmpulongs;
 146     set->ulongs_allocated = tmp;
 147   }
 148   return 0;
 149 }
 150 
 151 /* enlarge until it contains at least needed_count ulongs,
 152  * and update new ulongs according to the infinite field.
 153  */
 154 static int
 155 hwloc_bitmap_realloc_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count) __hwloc_attribute_warn_unused_result;
 156 static int
 157 hwloc_bitmap_realloc_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count)
 158 {
 159   unsigned i;
 160 
 161   HWLOC__BITMAP_CHECK(set);
 162 
 163   if (needed_count <= set->ulongs_count)
 164     return 0;
 165 
 166   /* realloc larger if needed */
 167   if (hwloc_bitmap_enlarge_by_ulongs(set, needed_count) < 0)
 168     return -1;
 169 
 170   /* fill the newly allocated subset depending on the infinite flag */
 171   for(i=set->ulongs_count; i<needed_count; i++)
 172     set->ulongs[i] = set->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
 173   set->ulongs_count = needed_count;
 174   return 0;
 175 }
 176 
 177 /* realloc until it contains at least cpu+1 bits */
 178 #define hwloc_bitmap_realloc_by_cpu_index(set, cpu) hwloc_bitmap_realloc_by_ulongs(set, ((cpu)/HWLOC_BITS_PER_LONG)+1)
 179 
 180 /* reset a bitmap to exactely the needed size.
 181  * the caller must reinitialize all ulongs and the infinite flag later.
 182  */
 183 static int
 184 hwloc_bitmap_reset_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count) __hwloc_attribute_warn_unused_result;
 185 static int
 186 hwloc_bitmap_reset_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count)
 187 {
 188   if (hwloc_bitmap_enlarge_by_ulongs(set, needed_count))
 189     return -1;
 190   set->ulongs_count = needed_count;
 191   return 0;
 192 }
 193 
 194 /* reset until it contains exactly cpu+1 bits (roundup to a ulong).
 195  * the caller must reinitialize all ulongs and the infinite flag later.
 196  */
 197 #define hwloc_bitmap_reset_by_cpu_index(set, cpu) hwloc_bitmap_reset_by_ulongs(set, ((cpu)/HWLOC_BITS_PER_LONG)+1)
 198 
 199 struct hwloc_bitmap_s * hwloc_bitmap_tma_dup(struct hwloc_tma *tma, const struct hwloc_bitmap_s * old)
 200 {
 201   struct hwloc_bitmap_s * new;
 202 
 203   if (!old)
 204     return NULL;
 205 
 206   HWLOC__BITMAP_CHECK(old);
 207 
 208   new = hwloc_tma_malloc(tma, sizeof(struct hwloc_bitmap_s));
 209   if (!new)
 210     return NULL;
 211 
 212   new->ulongs = hwloc_tma_malloc(tma, old->ulongs_allocated * sizeof(unsigned long));
 213   if (!new->ulongs) {
 214     free(new);
 215     return NULL;
 216   }
 217   new->ulongs_allocated = old->ulongs_allocated;
 218   new->ulongs_count = old->ulongs_count;
 219   memcpy(new->ulongs, old->ulongs, new->ulongs_count * sizeof(unsigned long));
 220   new->infinite = old->infinite;
 221 #ifdef HWLOC_DEBUG
 222   new->magic = HWLOC_BITMAP_MAGIC;
 223 #endif
 224   return new;
 225 }
 226 
 227 struct hwloc_bitmap_s * hwloc_bitmap_dup(const struct hwloc_bitmap_s * old)
 228 {
 229   return hwloc_bitmap_tma_dup(NULL, old);
 230 }
 231 
 232 int hwloc_bitmap_copy(struct hwloc_bitmap_s * dst, const struct hwloc_bitmap_s * src)
 233 {
 234   HWLOC__BITMAP_CHECK(dst);
 235   HWLOC__BITMAP_CHECK(src);
 236 
 237   if (hwloc_bitmap_reset_by_ulongs(dst, src->ulongs_count) < 0)
 238     return -1;
 239 
 240   memcpy(dst->ulongs, src->ulongs, src->ulongs_count * sizeof(unsigned long));
 241   dst->infinite = src->infinite;
 242   return 0;
 243 }
 244 
 245 /* Strings always use 32bit groups */
 246 #define HWLOC_PRIxSUBBITMAP             "%08lx"
 247 #define HWLOC_BITMAP_SUBSTRING_SIZE     32
 248 #define HWLOC_BITMAP_SUBSTRING_LENGTH   (HWLOC_BITMAP_SUBSTRING_SIZE/4)
 249 #define HWLOC_BITMAP_STRING_PER_LONG    (HWLOC_BITS_PER_LONG/HWLOC_BITMAP_SUBSTRING_SIZE)
 250 
 251 int hwloc_bitmap_snprintf(char * __hwloc_restrict buf, size_t buflen, const struct hwloc_bitmap_s * __hwloc_restrict set)
 252 {
 253   ssize_t size = buflen;
 254   char *tmp = buf;
 255   int res, ret = 0;
 256   int needcomma = 0;
 257   int i;
 258   unsigned long accum = 0;
 259   int accumed = 0;
 260 #if HWLOC_BITS_PER_LONG == HWLOC_BITMAP_SUBSTRING_SIZE
 261   const unsigned long accum_mask = ~0UL;
 262 #else /* HWLOC_BITS_PER_LONG != HWLOC_BITMAP_SUBSTRING_SIZE */
 263   const unsigned long accum_mask = ((1UL << HWLOC_BITMAP_SUBSTRING_SIZE) - 1) << (HWLOC_BITS_PER_LONG - HWLOC_BITMAP_SUBSTRING_SIZE);
 264 #endif /* HWLOC_BITS_PER_LONG != HWLOC_BITMAP_SUBSTRING_SIZE */
 265 
 266   HWLOC__BITMAP_CHECK(set);
 267 
 268   /* mark the end in case we do nothing later */
 269   if (buflen > 0)
 270     tmp[0] = '\0';
 271 
 272   if (set->infinite) {
 273     res = hwloc_snprintf(tmp, size, "0xf...f");
 274     needcomma = 1;
 275     if (res < 0)
 276       return -1;
 277     ret += res;
 278     if (res >= size)
 279       res = size>0 ? (int)size - 1 : 0;
 280     tmp += res;
 281     size -= res;
 282   }
 283 
 284   i=(int) set->ulongs_count-1;
 285 
 286   if (set->infinite) {
 287     /* ignore starting FULL since we have 0xf...f already */
 288     while (i>=0 && set->ulongs[i] == HWLOC_SUBBITMAP_FULL)
 289       i--;
 290   } else {
 291     /* ignore starting ZERO except the last one */
 292     while (i>=0 && set->ulongs[i] == HWLOC_SUBBITMAP_ZERO)
 293       i--;
 294   }
 295 
 296   while (i>=0 || accumed) {
 297     /* Refill accumulator */
 298     if (!accumed) {
 299       accum = set->ulongs[i--];
 300       accumed = HWLOC_BITS_PER_LONG;
 301     }
 302 
 303     if (accum & accum_mask) {
 304       /* print the whole subset if not empty */
 305         res = hwloc_snprintf(tmp, size, needcomma ? ",0x" HWLOC_PRIxSUBBITMAP : "0x" HWLOC_PRIxSUBBITMAP,
 306                      (accum & accum_mask) >> (HWLOC_BITS_PER_LONG - HWLOC_BITMAP_SUBSTRING_SIZE));
 307       needcomma = 1;
 308     } else if (i == -1 && accumed == HWLOC_BITMAP_SUBSTRING_SIZE) {
 309       /* print a single 0 to mark the last subset */
 310       res = hwloc_snprintf(tmp, size, needcomma ? ",0x0" : "0x0");
 311     } else if (needcomma) {
 312       res = hwloc_snprintf(tmp, size, ",");
 313     } else {
 314       res = 0;
 315     }
 316     if (res < 0)
 317       return -1;
 318     ret += res;
 319 
 320 #if HWLOC_BITS_PER_LONG == HWLOC_BITMAP_SUBSTRING_SIZE
 321     accum = 0;
 322     accumed = 0;
 323 #else
 324     accum <<= HWLOC_BITMAP_SUBSTRING_SIZE;
 325     accumed -= HWLOC_BITMAP_SUBSTRING_SIZE;
 326 #endif
 327 
 328     if (res >= size)
 329       res = size>0 ? (int)size - 1 : 0;
 330 
 331     tmp += res;
 332     size -= res;
 333   }
 334 
 335   /* if didn't display anything, display 0x0 */
 336   if (!ret) {
 337     res = hwloc_snprintf(tmp, size, "0x0");
 338     if (res < 0)
 339       return -1;
 340     ret += res;
 341   }
 342 
 343   return ret;
 344 }
 345 
 346 int hwloc_bitmap_asprintf(char ** strp, const struct hwloc_bitmap_s * __hwloc_restrict set)
 347 {
 348   int len;
 349   char *buf;
 350 
 351   HWLOC__BITMAP_CHECK(set);
 352 
 353   len = hwloc_bitmap_snprintf(NULL, 0, set);
 354   buf = malloc(len+1);
 355   if (!buf)
 356     return -1;
 357   *strp = buf;
 358   return hwloc_bitmap_snprintf(buf, len+1, set);
 359 }
 360 
 361 int hwloc_bitmap_sscanf(struct hwloc_bitmap_s *set, const char * __hwloc_restrict string)
 362 {
 363   const char * current = string;
 364   unsigned long accum = 0;
 365   int count=0;
 366   int infinite = 0;
 367 
 368   /* count how many substrings there are */
 369   count++;
 370   while ((current = strchr(current+1, ',')) != NULL)
 371     count++;
 372 
 373   current = string;
 374   if (!strncmp("0xf...f", current, 7)) {
 375     current += 7;
 376     if (*current != ',') {
 377       /* special case for infinite/full bitmap */
 378       hwloc_bitmap_fill(set);
 379       return 0;
 380     }
 381     current++;
 382     infinite = 1;
 383     count--;
 384   }
 385 
 386   if (hwloc_bitmap_reset_by_ulongs(set, (count + HWLOC_BITMAP_STRING_PER_LONG - 1) / HWLOC_BITMAP_STRING_PER_LONG) < 0)
 387     return -1;
 388   set->infinite = 0;
 389 
 390   while (*current != '\0') {
 391     unsigned long val;
 392     char *next;
 393     val = strtoul(current, &next, 16);
 394 
 395     assert(count > 0);
 396     count--;
 397 
 398     accum |= (val << ((count * HWLOC_BITMAP_SUBSTRING_SIZE) % HWLOC_BITS_PER_LONG));
 399     if (!(count % HWLOC_BITMAP_STRING_PER_LONG)) {
 400       set->ulongs[count / HWLOC_BITMAP_STRING_PER_LONG] = accum;
 401       accum = 0;
 402     }
 403 
 404     if (*next != ',') {
 405       if (*next || count > 0)
 406         goto failed;
 407       else
 408         break;
 409     }
 410     current = (const char*) next+1;
 411   }
 412 
 413   set->infinite = infinite; /* set at the end, to avoid spurious realloc with filled new ulongs */
 414 
 415   return 0;
 416 
 417  failed:
 418   /* failure to parse */
 419   hwloc_bitmap_zero(set);
 420   return -1;
 421 }
 422 
 423 int hwloc_bitmap_list_snprintf(char * __hwloc_restrict buf, size_t buflen, const struct hwloc_bitmap_s * __hwloc_restrict set)
 424 {
 425   int prev = -1;
 426   ssize_t size = buflen;
 427   char *tmp = buf;
 428   int res, ret = 0;
 429   int needcomma = 0;
 430 
 431   HWLOC__BITMAP_CHECK(set);
 432 
 433   /* mark the end in case we do nothing later */
 434   if (buflen > 0)
 435     tmp[0] = '\0';
 436 
 437   while (1) {
 438     int begin, end;
 439 
 440     begin = hwloc_bitmap_next(set, prev);
 441     if (begin == -1)
 442       break;
 443     end = hwloc_bitmap_next_unset(set, begin);
 444 
 445     if (end == begin+1) {
 446       res = hwloc_snprintf(tmp, size, needcomma ? ",%d" : "%d", begin);
 447     } else if (end == -1) {
 448       res = hwloc_snprintf(tmp, size, needcomma ? ",%d-" : "%d-", begin);
 449     } else {
 450       res = hwloc_snprintf(tmp, size, needcomma ? ",%d-%d" : "%d-%d", begin, end-1);
 451     }
 452     if (res < 0)
 453       return -1;
 454     ret += res;
 455 
 456     if (res >= size)
 457       res = size>0 ? (int)size - 1 : 0;
 458 
 459     tmp += res;
 460     size -= res;
 461     needcomma = 1;
 462 
 463     if (end == -1)
 464       break;
 465     else
 466       prev = end - 1;
 467   }
 468 
 469   return ret;
 470 }
 471 
 472 int hwloc_bitmap_list_asprintf(char ** strp, const struct hwloc_bitmap_s * __hwloc_restrict set)
 473 {
 474   int len;
 475   char *buf;
 476 
 477   HWLOC__BITMAP_CHECK(set);
 478 
 479   len = hwloc_bitmap_list_snprintf(NULL, 0, set);
 480   buf = malloc(len+1);
 481   if (!buf)
 482     return -1;
 483   *strp = buf;
 484   return hwloc_bitmap_list_snprintf(buf, len+1, set);
 485 }
 486 
 487 int hwloc_bitmap_list_sscanf(struct hwloc_bitmap_s *set, const char * __hwloc_restrict string)
 488 {
 489   const char * current = string;
 490   char *next;
 491   long begin = -1, val;
 492 
 493   hwloc_bitmap_zero(set);
 494 
 495   while (*current != '\0') {
 496 
 497     /* ignore empty ranges */
 498     while (*current == ',' || *current == ' ')
 499       current++;
 500 
 501     val = strtoul(current, &next, 0);
 502     /* make sure we got at least one digit */
 503     if (next == current)
 504       goto failed;
 505 
 506     if (begin != -1) {
 507       /* finishing a range */
 508       hwloc_bitmap_set_range(set, begin, val);
 509       begin = -1;
 510 
 511     } else if (*next == '-') {
 512       /* starting a new range */
 513       if (*(next+1) == '\0') {
 514         /* infinite range */
 515         hwloc_bitmap_set_range(set, val, -1);
 516         break;
 517       } else {
 518         /* normal range */
 519         begin = val;
 520       }
 521 
 522     } else if (*next == ',' || *next == ' ' || *next == '\0') {
 523       /* single digit */
 524       hwloc_bitmap_set(set, val);
 525     }
 526 
 527     if (*next == '\0')
 528       break;
 529     current = next+1;
 530   }
 531 
 532   return 0;
 533 
 534  failed:
 535   /* failure to parse */
 536   hwloc_bitmap_zero(set);
 537   return -1;
 538 }
 539 
 540 int hwloc_bitmap_taskset_snprintf(char * __hwloc_restrict buf, size_t buflen, const struct hwloc_bitmap_s * __hwloc_restrict set)
 541 {
 542   ssize_t size = buflen;
 543   char *tmp = buf;
 544   int res, ret = 0;
 545   int started = 0;
 546   int i;
 547 
 548   HWLOC__BITMAP_CHECK(set);
 549 
 550   /* mark the end in case we do nothing later */
 551   if (buflen > 0)
 552     tmp[0] = '\0';
 553 
 554   if (set->infinite) {
 555     res = hwloc_snprintf(tmp, size, "0xf...f");
 556     started = 1;
 557     if (res < 0)
 558       return -1;
 559     ret += res;
 560     if (res >= size)
 561       res = size>0 ? (int)size - 1 : 0;
 562     tmp += res;
 563     size -= res;
 564   }
 565 
 566   i=set->ulongs_count-1;
 567 
 568   if (set->infinite) {
 569     /* ignore starting FULL since we have 0xf...f already */
 570     while (i>=0 && set->ulongs[i] == HWLOC_SUBBITMAP_FULL)
 571       i--;
 572   } else {
 573     /* ignore starting ZERO except the last one */
 574     while (i>=1 && set->ulongs[i] == HWLOC_SUBBITMAP_ZERO)
 575       i--;
 576   }
 577 
 578   while (i>=0) {
 579     unsigned long val = set->ulongs[i--];
 580     if (started) {
 581       /* print the whole subset */
 582 #if HWLOC_BITS_PER_LONG == 64
 583       res = hwloc_snprintf(tmp, size, "%016lx", val);
 584 #else
 585       res = hwloc_snprintf(tmp, size, "%08lx", val);
 586 #endif
 587     } else if (val || i == -1) {
 588       res = hwloc_snprintf(tmp, size, "0x%lx", val);
 589       started = 1;
 590     } else {
 591       res = 0;
 592     }
 593     if (res < 0)
 594       return -1;
 595     ret += res;
 596     if (res >= size)
 597       res = size>0 ? (int)size - 1 : 0;
 598     tmp += res;
 599     size -= res;
 600   }
 601 
 602   /* if didn't display anything, display 0x0 */
 603   if (!ret) {
 604     res = hwloc_snprintf(tmp, size, "0x0");
 605     if (res < 0)
 606       return -1;
 607     ret += res;
 608   }
 609 
 610   return ret;
 611 }
 612 
 613 int hwloc_bitmap_taskset_asprintf(char ** strp, const struct hwloc_bitmap_s * __hwloc_restrict set)
 614 {
 615   int len;
 616   char *buf;
 617 
 618   HWLOC__BITMAP_CHECK(set);
 619 
 620   len = hwloc_bitmap_taskset_snprintf(NULL, 0, set);
 621   buf = malloc(len+1);
 622   if (!buf)
 623     return -1;
 624   *strp = buf;
 625   return hwloc_bitmap_taskset_snprintf(buf, len+1, set);
 626 }
 627 
 628 int hwloc_bitmap_taskset_sscanf(struct hwloc_bitmap_s *set, const char * __hwloc_restrict string)
 629 {
 630   const char * current = string;
 631   int chars;
 632   int count;
 633   int infinite = 0;
 634 
 635   if (!strncmp("0xf...f", current, 7)) {
 636     /* infinite bitmap */
 637     infinite = 1;
 638     current += 7;
 639     if (*current == '\0') {
 640       /* special case for infinite/full bitmap */
 641       hwloc_bitmap_fill(set);
 642       return 0;
 643     }
 644   } else {
 645     /* finite bitmap */
 646     if (!strncmp("0x", current, 2))
 647       current += 2;
 648     if (*current == '\0') {
 649       /* special case for empty bitmap */
 650       hwloc_bitmap_zero(set);
 651       return 0;
 652     }
 653   }
 654   /* we know there are other characters now */
 655 
 656   chars = (int)strlen(current);
 657   count = (chars * 4 + HWLOC_BITS_PER_LONG - 1) / HWLOC_BITS_PER_LONG;
 658 
 659   if (hwloc_bitmap_reset_by_ulongs(set, count) < 0)
 660     return -1;
 661   set->infinite = 0;
 662 
 663   while (*current != '\0') {
 664     int tmpchars;
 665     char ustr[17];
 666     unsigned long val;
 667     char *next;
 668 
 669     tmpchars = chars % (HWLOC_BITS_PER_LONG/4);
 670     if (!tmpchars)
 671       tmpchars = (HWLOC_BITS_PER_LONG/4);
 672 
 673     memcpy(ustr, current, tmpchars);
 674     ustr[tmpchars] = '\0';
 675     val = strtoul(ustr, &next, 16);
 676     if (*next != '\0')
 677       goto failed;
 678 
 679     set->ulongs[count-1] = val;
 680 
 681     current += tmpchars;
 682     chars -= tmpchars;
 683     count--;
 684   }
 685 
 686   set->infinite = infinite; /* set at the end, to avoid spurious realloc with filled new ulongs */
 687 
 688   return 0;
 689 
 690  failed:
 691   /* failure to parse */
 692   hwloc_bitmap_zero(set);
 693   return -1;
 694 }
 695 
 696 static void hwloc_bitmap__zero(struct hwloc_bitmap_s *set)
 697 {
 698         unsigned i;
 699         for(i=0; i<set->ulongs_count; i++)
 700                 set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
 701         set->infinite = 0;
 702 }
 703 
 704 void hwloc_bitmap_zero(struct hwloc_bitmap_s * set)
 705 {
 706         HWLOC__BITMAP_CHECK(set);
 707 
 708         HWLOC_BUILD_ASSERT(HWLOC_BITMAP_PREALLOC_ULONGS >= 1);
 709         if (hwloc_bitmap_reset_by_ulongs(set, 1) < 0) {
 710                 /* cannot fail since we preallocate some ulongs.
 711                  * if we ever preallocate nothing, we'll reset to 0 ulongs.
 712                  */
 713         }
 714         hwloc_bitmap__zero(set);
 715 }
 716 
 717 static void hwloc_bitmap__fill(struct hwloc_bitmap_s * set)
 718 {
 719         unsigned i;
 720         for(i=0; i<set->ulongs_count; i++)
 721                 set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
 722         set->infinite = 1;
 723 }
 724 
 725 void hwloc_bitmap_fill(struct hwloc_bitmap_s * set)
 726 {
 727         HWLOC__BITMAP_CHECK(set);
 728 
 729         HWLOC_BUILD_ASSERT(HWLOC_BITMAP_PREALLOC_ULONGS >= 1);
 730         if (hwloc_bitmap_reset_by_ulongs(set, 1) < 0) {
 731                 /* cannot fail since we pre-allocate some ulongs.
 732                  * if we ever pre-allocate nothing, we'll reset to 0 ulongs.
 733                  */
 734         }
 735         hwloc_bitmap__fill(set);
 736 }
 737 
 738 int hwloc_bitmap_from_ulong(struct hwloc_bitmap_s *set, unsigned long mask)
 739 {
 740         HWLOC__BITMAP_CHECK(set);
 741 
 742         HWLOC_BUILD_ASSERT(HWLOC_BITMAP_PREALLOC_ULONGS >= 1);
 743         if (hwloc_bitmap_reset_by_ulongs(set, 1) < 0) {
 744                 /* cannot fail since we pre-allocate some ulongs.
 745                  * if ever pre-allocate nothing, we may have to return a failure.
 746                  */
 747         }
 748         set->ulongs[0] = mask; /* there's always at least one ulong allocated */
 749         set->infinite = 0;
 750         return 0;
 751 }
 752 
 753 int hwloc_bitmap_from_ith_ulong(struct hwloc_bitmap_s *set, unsigned i, unsigned long mask)
 754 {
 755         unsigned j;
 756 
 757         HWLOC__BITMAP_CHECK(set);
 758 
 759         if (hwloc_bitmap_reset_by_ulongs(set, i+1) < 0)
 760                 return -1;
 761 
 762         set->ulongs[i] = mask;
 763         for(j=0; j<i; j++)
 764                 set->ulongs[j] = HWLOC_SUBBITMAP_ZERO;
 765         set->infinite = 0;
 766         return 0;
 767 }
 768 
 769 unsigned long hwloc_bitmap_to_ulong(const struct hwloc_bitmap_s *set)
 770 {
 771         HWLOC__BITMAP_CHECK(set);
 772 
 773         return set->ulongs[0]; /* there's always at least one ulong allocated */
 774 }
 775 
 776 unsigned long hwloc_bitmap_to_ith_ulong(const struct hwloc_bitmap_s *set, unsigned i)
 777 {
 778         HWLOC__BITMAP_CHECK(set);
 779 
 780         return HWLOC_SUBBITMAP_READULONG(set, i);
 781 }
 782 
 783 int hwloc_bitmap_only(struct hwloc_bitmap_s * set, unsigned cpu)
 784 {
 785         unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
 786 
 787         HWLOC__BITMAP_CHECK(set);
 788 
 789         if (hwloc_bitmap_reset_by_cpu_index(set, cpu) < 0)
 790                 return -1;
 791 
 792         hwloc_bitmap__zero(set);
 793         set->ulongs[index_] |= HWLOC_SUBBITMAP_CPU(cpu);
 794         return 0;
 795 }
 796 
 797 int hwloc_bitmap_allbut(struct hwloc_bitmap_s * set, unsigned cpu)
 798 {
 799         unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
 800 
 801         HWLOC__BITMAP_CHECK(set);
 802 
 803         if (hwloc_bitmap_reset_by_cpu_index(set, cpu) < 0)
 804                 return -1;
 805 
 806         hwloc_bitmap__fill(set);
 807         set->ulongs[index_] &= ~HWLOC_SUBBITMAP_CPU(cpu);
 808         return 0;
 809 }
 810 
 811 int hwloc_bitmap_set(struct hwloc_bitmap_s * set, unsigned cpu)
 812 {
 813         unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
 814 
 815         HWLOC__BITMAP_CHECK(set);
 816 
 817         /* nothing to do if setting inside the infinite part of the bitmap */
 818         if (set->infinite && cpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
 819                 return 0;
 820 
 821         if (hwloc_bitmap_realloc_by_cpu_index(set, cpu) < 0)
 822                 return -1;
 823 
 824         set->ulongs[index_] |= HWLOC_SUBBITMAP_CPU(cpu);
 825         return 0;
 826 }
 827 
 828 int hwloc_bitmap_set_range(struct hwloc_bitmap_s * set, unsigned begincpu, int _endcpu)
 829 {
 830         unsigned i;
 831         unsigned beginset,endset;
 832         unsigned endcpu = (unsigned) _endcpu;
 833 
 834         HWLOC__BITMAP_CHECK(set);
 835 
 836         if (endcpu < begincpu)
 837                 return 0;
 838         if (set->infinite && begincpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
 839                 /* setting only in the already-set infinite part, nothing to do */
 840                 return 0;
 841 
 842         if (_endcpu == -1) {
 843                 /* infinite range */
 844 
 845                 /* make sure we can play with the ulong that contains begincpu */
 846                 if (hwloc_bitmap_realloc_by_cpu_index(set, begincpu) < 0)
 847                         return -1;
 848 
 849                 /* update the ulong that contains begincpu */
 850                 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
 851                 set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
 852                 /* set ulongs after begincpu if any already allocated */
 853                 for(i=beginset+1; i<set->ulongs_count; i++)
 854                         set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
 855                 /* mark the infinity as set */
 856                 set->infinite = 1;
 857         } else {
 858                 /* finite range */
 859 
 860                 /* ignore the part of the range that overlaps with the already-set infinite part */
 861                 if (set->infinite && endcpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
 862                         endcpu = set->ulongs_count * HWLOC_BITS_PER_LONG - 1;
 863                 /* make sure we can play with the ulongs that contain begincpu and endcpu */
 864                 if (hwloc_bitmap_realloc_by_cpu_index(set, endcpu) < 0)
 865                         return -1;
 866 
 867                 /* update first and last ulongs */
 868                 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
 869                 endset = HWLOC_SUBBITMAP_INDEX(endcpu);
 870                 if (beginset == endset) {
 871                         set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROMTO(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu), HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
 872                 } else {
 873                         set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
 874                         set->ulongs[endset] |= HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
 875                 }
 876                 /* set ulongs in the middle of the range */
 877                 for(i=beginset+1; i<endset; i++)
 878                         set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
 879         }
 880 
 881         return 0;
 882 }
 883 
 884 int hwloc_bitmap_set_ith_ulong(struct hwloc_bitmap_s *set, unsigned i, unsigned long mask)
 885 {
 886         HWLOC__BITMAP_CHECK(set);
 887 
 888         if (hwloc_bitmap_realloc_by_ulongs(set, i+1) < 0)
 889                 return -1;
 890 
 891         set->ulongs[i] = mask;
 892         return 0;
 893 }
 894 
 895 int hwloc_bitmap_clr(struct hwloc_bitmap_s * set, unsigned cpu)
 896 {
 897         unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
 898 
 899         HWLOC__BITMAP_CHECK(set);
 900 
 901         /* nothing to do if clearing inside the infinitely-unset part of the bitmap */
 902         if (!set->infinite && cpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
 903                 return 0;
 904 
 905         if (hwloc_bitmap_realloc_by_cpu_index(set, cpu) < 0)
 906                 return -1;
 907 
 908         set->ulongs[index_] &= ~HWLOC_SUBBITMAP_CPU(cpu);
 909         return 0;
 910 }
 911 
 912 int hwloc_bitmap_clr_range(struct hwloc_bitmap_s * set, unsigned begincpu, int _endcpu)
 913 {
 914         unsigned i;
 915         unsigned beginset,endset;
 916         unsigned endcpu = (unsigned) _endcpu;
 917 
 918         HWLOC__BITMAP_CHECK(set);
 919 
 920         if (endcpu < begincpu)
 921                 return 0;
 922 
 923         if (!set->infinite && begincpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
 924                 /* clearing only in the already-unset infinite part, nothing to do */
 925                 return 0;
 926 
 927         if (_endcpu == -1) {
 928                 /* infinite range */
 929 
 930                 /* make sure we can play with the ulong that contains begincpu */
 931                 if (hwloc_bitmap_realloc_by_cpu_index(set, begincpu) < 0)
 932                         return -1;
 933 
 934                 /* update the ulong that contains begincpu */
 935                 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
 936                 set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
 937                 /* clear ulong after begincpu if any already allocated */
 938                 for(i=beginset+1; i<set->ulongs_count; i++)
 939                         set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
 940                 /* mark the infinity as unset */
 941                 set->infinite = 0;
 942         } else {
 943                 /* finite range */
 944 
 945                 /* ignore the part of the range that overlaps with the already-unset infinite part */
 946                 if (!set->infinite && endcpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
 947                         endcpu = set->ulongs_count * HWLOC_BITS_PER_LONG - 1;
 948                 /* make sure we can play with the ulongs that contain begincpu and endcpu */
 949                 if (hwloc_bitmap_realloc_by_cpu_index(set, endcpu) < 0)
 950                         return -1;
 951 
 952                 /* update first and last ulongs */
 953                 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
 954                 endset = HWLOC_SUBBITMAP_INDEX(endcpu);
 955                 if (beginset == endset) {
 956                         set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROMTO(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu), HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
 957                 } else {
 958                         set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
 959                         set->ulongs[endset] &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
 960                 }
 961                 /* clear ulongs in the middle of the range */
 962                 for(i=beginset+1; i<endset; i++)
 963                         set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
 964         }
 965 
 966         return 0;
 967 }
 968 
 969 int hwloc_bitmap_isset(const struct hwloc_bitmap_s * set, unsigned cpu)
 970 {
 971         unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
 972 
 973         HWLOC__BITMAP_CHECK(set);
 974 
 975         return (HWLOC_SUBBITMAP_READULONG(set, index_) & HWLOC_SUBBITMAP_CPU(cpu)) != 0;
 976 }
 977 
 978 int hwloc_bitmap_iszero(const struct hwloc_bitmap_s *set)
 979 {
 980         unsigned i;
 981 
 982         HWLOC__BITMAP_CHECK(set);
 983 
 984         if (set->infinite)
 985                 return 0;
 986         for(i=0; i<set->ulongs_count; i++)
 987                 if (set->ulongs[i] != HWLOC_SUBBITMAP_ZERO)
 988                         return 0;
 989         return 1;
 990 }
 991 
 992 int hwloc_bitmap_isfull(const struct hwloc_bitmap_s *set)
 993 {
 994         unsigned i;
 995 
 996         HWLOC__BITMAP_CHECK(set);
 997 
 998         if (!set->infinite)
 999                 return 0;
1000         for(i=0; i<set->ulongs_count; i++)
1001                 if (set->ulongs[i] != HWLOC_SUBBITMAP_FULL)
1002                         return 0;
1003         return 1;
1004 }
1005 
1006 int hwloc_bitmap_isequal (const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1007 {
1008         unsigned count1 = set1->ulongs_count;
1009         unsigned count2 = set2->ulongs_count;
1010         unsigned min_count = count1 < count2 ? count1 : count2;
1011         unsigned i;
1012 
1013         HWLOC__BITMAP_CHECK(set1);
1014         HWLOC__BITMAP_CHECK(set2);
1015 
1016         for(i=0; i<min_count; i++)
1017                 if (set1->ulongs[i] != set2->ulongs[i])
1018                         return 0;
1019 
1020         if (count1 != count2) {
1021                 unsigned long w1 = set1->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1022                 unsigned long w2 = set2->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1023                 for(i=min_count; i<count1; i++) {
1024                         if (set1->ulongs[i] != w2)
1025                                 return 0;
1026                 }
1027                 for(i=min_count; i<count2; i++) {
1028                         if (set2->ulongs[i] != w1)
1029                                 return 0;
1030                 }
1031         }
1032 
1033         if (set1->infinite != set2->infinite)
1034                 return 0;
1035 
1036         return 1;
1037 }
1038 
1039 int hwloc_bitmap_intersects (const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1040 {
1041         unsigned count1 = set1->ulongs_count;
1042         unsigned count2 = set2->ulongs_count;
1043         unsigned min_count = count1 < count2 ? count1 : count2;
1044         unsigned i;
1045 
1046         HWLOC__BITMAP_CHECK(set1);
1047         HWLOC__BITMAP_CHECK(set2);
1048 
1049         for(i=0; i<min_count; i++)
1050                 if (set1->ulongs[i] & set2->ulongs[i])
1051                         return 1;
1052 
1053         if (count1 != count2) {
1054                 if (set2->infinite) {
1055                         for(i=min_count; i<set1->ulongs_count; i++)
1056                                 if (set1->ulongs[i])
1057                                         return 1;
1058                 }
1059                 if (set1->infinite) {
1060                         for(i=min_count; i<set2->ulongs_count; i++)
1061                                 if (set2->ulongs[i])
1062                                         return 1;
1063                 }
1064         }
1065 
1066         if (set1->infinite && set2->infinite)
1067                 return 1;
1068 
1069         return 0;
1070 }
1071 
1072 int hwloc_bitmap_isincluded (const struct hwloc_bitmap_s *sub_set, const struct hwloc_bitmap_s *super_set)
1073 {
1074         unsigned super_count = super_set->ulongs_count;
1075         unsigned sub_count = sub_set->ulongs_count;
1076         unsigned min_count = super_count < sub_count ? super_count : sub_count;
1077         unsigned i;
1078 
1079         HWLOC__BITMAP_CHECK(sub_set);
1080         HWLOC__BITMAP_CHECK(super_set);
1081 
1082         for(i=0; i<min_count; i++)
1083                 if (super_set->ulongs[i] != (super_set->ulongs[i] | sub_set->ulongs[i]))
1084                         return 0;
1085 
1086         if (super_count != sub_count) {
1087                 if (!super_set->infinite)
1088                         for(i=min_count; i<sub_count; i++)
1089                                 if (sub_set->ulongs[i])
1090                                         return 0;
1091                 if (sub_set->infinite)
1092                         for(i=min_count; i<super_count; i++)
1093                                 if (super_set->ulongs[i] != HWLOC_SUBBITMAP_FULL)
1094                                         return 0;
1095         }
1096 
1097         if (sub_set->infinite && !super_set->infinite)
1098                 return 0;
1099 
1100         return 1;
1101 }
1102 
1103 int hwloc_bitmap_or (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1104 {
1105         /* cache counts so that we can reset res even if it's also set1 or set2 */
1106         unsigned count1 = set1->ulongs_count;
1107         unsigned count2 = set2->ulongs_count;
1108         unsigned max_count = count1 > count2 ? count1 : count2;
1109         unsigned min_count = count1 + count2 - max_count;
1110         unsigned i;
1111 
1112         HWLOC__BITMAP_CHECK(res);
1113         HWLOC__BITMAP_CHECK(set1);
1114         HWLOC__BITMAP_CHECK(set2);
1115 
1116         if (hwloc_bitmap_reset_by_ulongs(res, max_count) < 0)
1117                 return -1;
1118 
1119         for(i=0; i<min_count; i++)
1120                 res->ulongs[i] = set1->ulongs[i] | set2->ulongs[i];
1121 
1122         if (count1 != count2) {
1123                 if (min_count < count1) {
1124                         if (set2->infinite) {
1125                                 res->ulongs_count = min_count;
1126                         } else {
1127                                 for(i=min_count; i<max_count; i++)
1128                                         res->ulongs[i] = set1->ulongs[i];
1129                         }
1130                 } else {
1131                         if (set1->infinite) {
1132                                 res->ulongs_count = min_count;
1133                         } else {
1134                                 for(i=min_count; i<max_count; i++)
1135                                         res->ulongs[i] = set2->ulongs[i];
1136                         }
1137                 }
1138         }
1139 
1140         res->infinite = set1->infinite || set2->infinite;
1141         return 0;
1142 }
1143 
1144 int hwloc_bitmap_and (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1145 {
1146         /* cache counts so that we can reset res even if it's also set1 or set2 */
1147         unsigned count1 = set1->ulongs_count;
1148         unsigned count2 = set2->ulongs_count;
1149         unsigned max_count = count1 > count2 ? count1 : count2;
1150         unsigned min_count = count1 + count2 - max_count;
1151         unsigned i;
1152 
1153         HWLOC__BITMAP_CHECK(res);
1154         HWLOC__BITMAP_CHECK(set1);
1155         HWLOC__BITMAP_CHECK(set2);
1156 
1157         if (hwloc_bitmap_reset_by_ulongs(res, max_count) < 0)
1158                 return -1;
1159 
1160         for(i=0; i<min_count; i++)
1161                 res->ulongs[i] = set1->ulongs[i] & set2->ulongs[i];
1162 
1163         if (count1 != count2) {
1164                 if (min_count < count1) {
1165                         if (set2->infinite) {
1166                                 for(i=min_count; i<max_count; i++)
1167                                         res->ulongs[i] = set1->ulongs[i];
1168                         } else {
1169                                 res->ulongs_count = min_count;
1170                         }
1171                 } else {
1172                         if (set1->infinite) {
1173                                 for(i=min_count; i<max_count; i++)
1174                                         res->ulongs[i] = set2->ulongs[i];
1175                         } else {
1176                                 res->ulongs_count = min_count;
1177                         }
1178                 }
1179         }
1180 
1181         res->infinite = set1->infinite && set2->infinite;
1182         return 0;
1183 }
1184 
1185 int hwloc_bitmap_andnot (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1186 {
1187         /* cache counts so that we can reset res even if it's also set1 or set2 */
1188         unsigned count1 = set1->ulongs_count;
1189         unsigned count2 = set2->ulongs_count;
1190         unsigned max_count = count1 > count2 ? count1 : count2;
1191         unsigned min_count = count1 + count2 - max_count;
1192         unsigned i;
1193 
1194         HWLOC__BITMAP_CHECK(res);
1195         HWLOC__BITMAP_CHECK(set1);
1196         HWLOC__BITMAP_CHECK(set2);
1197 
1198         if (hwloc_bitmap_reset_by_ulongs(res, max_count) < 0)
1199                 return -1;
1200 
1201         for(i=0; i<min_count; i++)
1202                 res->ulongs[i] = set1->ulongs[i] & ~set2->ulongs[i];
1203 
1204         if (count1 != count2) {
1205                 if (min_count < count1) {
1206                         if (!set2->infinite) {
1207                                 for(i=min_count; i<max_count; i++)
1208                                         res->ulongs[i] = set1->ulongs[i];
1209                         } else {
1210                                 res->ulongs_count = min_count;
1211                         }
1212                 } else {
1213                         if (set1->infinite) {
1214                                 for(i=min_count; i<max_count; i++)
1215                                         res->ulongs[i] = ~set2->ulongs[i];
1216                         } else {
1217                                 res->ulongs_count = min_count;
1218                         }
1219                 }
1220         }
1221 
1222         res->infinite = set1->infinite && !set2->infinite;
1223         return 0;
1224 }
1225 
1226 int hwloc_bitmap_xor (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1227 {
1228         /* cache counts so that we can reset res even if it's also set1 or set2 */
1229         unsigned count1 = set1->ulongs_count;
1230         unsigned count2 = set2->ulongs_count;
1231         unsigned max_count = count1 > count2 ? count1 : count2;
1232         unsigned min_count = count1 + count2 - max_count;
1233         unsigned i;
1234 
1235         HWLOC__BITMAP_CHECK(res);
1236         HWLOC__BITMAP_CHECK(set1);
1237         HWLOC__BITMAP_CHECK(set2);
1238 
1239         if (hwloc_bitmap_reset_by_ulongs(res, max_count) < 0)
1240                 return -1;
1241 
1242         for(i=0; i<min_count; i++)
1243                 res->ulongs[i] = set1->ulongs[i] ^ set2->ulongs[i];
1244 
1245         if (count1 != count2) {
1246                 if (min_count < count1) {
1247                         unsigned long w2 = set2->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1248                         for(i=min_count; i<max_count; i++)
1249                                 res->ulongs[i] = set1->ulongs[i] ^ w2;
1250                 } else {
1251                         unsigned long w1 = set1->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1252                         for(i=min_count; i<max_count; i++)
1253                                 res->ulongs[i] = set2->ulongs[i] ^ w1;
1254                 }
1255         }
1256 
1257         res->infinite = (!set1->infinite) != (!set2->infinite);
1258         return 0;
1259 }
1260 
1261 int hwloc_bitmap_not (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set)
1262 {
1263         unsigned count = set->ulongs_count;
1264         unsigned i;
1265 
1266         HWLOC__BITMAP_CHECK(res);
1267         HWLOC__BITMAP_CHECK(set);
1268 
1269         if (hwloc_bitmap_reset_by_ulongs(res, count) < 0)
1270                 return -1;
1271 
1272         for(i=0; i<count; i++)
1273                 res->ulongs[i] = ~set->ulongs[i];
1274 
1275         res->infinite = !set->infinite;
1276         return 0;
1277 }
1278 
1279 int hwloc_bitmap_first(const struct hwloc_bitmap_s * set)
1280 {
1281         unsigned i;
1282 
1283         HWLOC__BITMAP_CHECK(set);
1284 
1285         for(i=0; i<set->ulongs_count; i++) {
1286                 /* subsets are unsigned longs, use ffsl */
1287                 unsigned long w = set->ulongs[i];
1288                 if (w)
1289                         return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1290         }
1291 
1292         if (set->infinite)
1293                 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1294 
1295         return -1;
1296 }
1297 
1298 int hwloc_bitmap_first_unset(const struct hwloc_bitmap_s * set)
1299 {
1300         unsigned i;
1301 
1302         HWLOC__BITMAP_CHECK(set);
1303 
1304         for(i=0; i<set->ulongs_count; i++) {
1305                 /* subsets are unsigned longs, use ffsl */
1306                 unsigned long w = ~set->ulongs[i];
1307                 if (w)
1308                         return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1309         }
1310 
1311         if (!set->infinite)
1312                 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1313 
1314         return -1;
1315 }
1316 
1317 int hwloc_bitmap_last(const struct hwloc_bitmap_s * set)
1318 {
1319         int i;
1320 
1321         HWLOC__BITMAP_CHECK(set);
1322 
1323         if (set->infinite)
1324                 return -1;
1325 
1326         for(i=(int)set->ulongs_count-1; i>=0; i--) {
1327                 /* subsets are unsigned longs, use flsl */
1328                 unsigned long w = set->ulongs[i];
1329                 if (w)
1330                         return hwloc_flsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1331         }
1332 
1333         return -1;
1334 }
1335 
1336 int hwloc_bitmap_last_unset(const struct hwloc_bitmap_s * set)
1337 {
1338         int i;
1339 
1340         HWLOC__BITMAP_CHECK(set);
1341 
1342         if (!set->infinite)
1343                 return -1;
1344 
1345         for(i=(int)set->ulongs_count-1; i>=0; i--) {
1346                 /* subsets are unsigned longs, use flsl */
1347                 unsigned long w = ~set->ulongs[i];
1348                 if (w)
1349                         return hwloc_flsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1350         }
1351 
1352         return -1;
1353 }
1354 
1355 int hwloc_bitmap_next(const struct hwloc_bitmap_s * set, int prev_cpu)
1356 {
1357         unsigned i = HWLOC_SUBBITMAP_INDEX(prev_cpu + 1);
1358 
1359         HWLOC__BITMAP_CHECK(set);
1360 
1361         if (i >= set->ulongs_count) {
1362                 if (set->infinite)
1363                         return prev_cpu + 1;
1364                 else
1365                         return -1;
1366         }
1367 
1368         for(; i<set->ulongs_count; i++) {
1369                 /* subsets are unsigned longs, use ffsl */
1370                 unsigned long w = set->ulongs[i];
1371 
1372                 /* if the prev cpu is in the same word as the possible next one,
1373                    we need to mask out previous cpus */
1374                 if (prev_cpu >= 0 && HWLOC_SUBBITMAP_INDEX((unsigned) prev_cpu) == i)
1375                         w &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(prev_cpu));
1376 
1377                 if (w)
1378                         return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1379         }
1380 
1381         if (set->infinite)
1382                 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1383 
1384         return -1;
1385 }
1386 
1387 int hwloc_bitmap_next_unset(const struct hwloc_bitmap_s * set, int prev_cpu)
1388 {
1389         unsigned i = HWLOC_SUBBITMAP_INDEX(prev_cpu + 1);
1390 
1391         HWLOC__BITMAP_CHECK(set);
1392 
1393         if (i >= set->ulongs_count) {
1394                 if (!set->infinite)
1395                         return prev_cpu + 1;
1396                 else
1397                         return -1;
1398         }
1399 
1400         for(; i<set->ulongs_count; i++) {
1401                 /* subsets are unsigned longs, use ffsl */
1402                 unsigned long w = ~set->ulongs[i];
1403 
1404                 /* if the prev cpu is in the same word as the possible next one,
1405                    we need to mask out previous cpus */
1406                 if (prev_cpu >= 0 && HWLOC_SUBBITMAP_INDEX((unsigned) prev_cpu) == i)
1407                         w &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(prev_cpu));
1408 
1409                 if (w)
1410                         return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1411         }
1412 
1413         if (!set->infinite)
1414                 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1415 
1416         return -1;
1417 }
1418 
1419 int hwloc_bitmap_singlify(struct hwloc_bitmap_s * set)
1420 {
1421         unsigned i;
1422         int found = 0;
1423 
1424         HWLOC__BITMAP_CHECK(set);
1425 
1426         for(i=0; i<set->ulongs_count; i++) {
1427                 if (found) {
1428                         set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
1429                         continue;
1430                 } else {
1431                         /* subsets are unsigned longs, use ffsl */
1432                         unsigned long w = set->ulongs[i];
1433                         if (w) {
1434                                 int _ffs = hwloc_ffsl(w);
1435                                 set->ulongs[i] = HWLOC_SUBBITMAP_CPU(_ffs-1);
1436                                 found = 1;
1437                         }
1438                 }
1439         }
1440 
1441         if (set->infinite) {
1442                 if (found) {
1443                         set->infinite = 0;
1444                 } else {
1445                         /* set the first non allocated bit */
1446                         unsigned first = set->ulongs_count * HWLOC_BITS_PER_LONG;
1447                         set->infinite = 0; /* do not let realloc fill the newly allocated sets */
1448                         return hwloc_bitmap_set(set, first);
1449                 }
1450         }
1451 
1452         return 0;
1453 }
1454 
1455 int hwloc_bitmap_compare_first(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
1456 {
1457         unsigned count1 = set1->ulongs_count;
1458         unsigned count2 = set2->ulongs_count;
1459         unsigned max_count = count1 > count2 ? count1 : count2;
1460         unsigned min_count = count1 + count2 - max_count;
1461         unsigned i;
1462 
1463         HWLOC__BITMAP_CHECK(set1);
1464         HWLOC__BITMAP_CHECK(set2);
1465 
1466         for(i=0; i<min_count; i++) {
1467                 unsigned long w1 = set1->ulongs[i];
1468                 unsigned long w2 = set2->ulongs[i];
1469                 if (w1 || w2) {
1470                         int _ffs1 = hwloc_ffsl(w1);
1471                         int _ffs2 = hwloc_ffsl(w2);
1472                         /* if both have a bit set, compare for real */
1473                         if (_ffs1 && _ffs2)
1474                                 return _ffs1-_ffs2;
1475                         /* one is empty, and it is considered higher, so reverse-compare them */
1476                         return _ffs2-_ffs1;
1477                 }
1478         }
1479 
1480         if (count1 != count2) {
1481                 if (min_count < count2) {
1482                         for(i=min_count; i<count2; i++) {
1483                                 unsigned long w2 = set2->ulongs[i];
1484                                 if (set1->infinite)
1485                                         return -!(w2 & 1);
1486                                 else if (w2)
1487                                         return 1;
1488                         }
1489                 } else {
1490                         for(i=min_count; i<count1; i++) {
1491                                 unsigned long w1 = set1->ulongs[i];
1492                                 if (set2->infinite)
1493                                         return !(w1 & 1);
1494                                 else if (w1)
1495                                         return -1;
1496                         }
1497                 }
1498         }
1499 
1500         return !!set1->infinite - !!set2->infinite;
1501 }
1502 
1503 int hwloc_bitmap_compare(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
1504 {
1505         unsigned count1 = set1->ulongs_count;
1506         unsigned count2 = set2->ulongs_count;
1507         unsigned max_count = count1 > count2 ? count1 : count2;
1508         unsigned min_count = count1 + count2 - max_count;
1509         int i;
1510 
1511         HWLOC__BITMAP_CHECK(set1);
1512         HWLOC__BITMAP_CHECK(set2);
1513 
1514         if ((!set1->infinite) != (!set2->infinite))
1515                 return !!set1->infinite - !!set2->infinite;
1516 
1517         if (count1 != count2) {
1518                 if (min_count < count2) {
1519                         unsigned long val1 = set1->infinite ? HWLOC_SUBBITMAP_FULL :  HWLOC_SUBBITMAP_ZERO;
1520                         for(i=(int)max_count-1; i>=(int) min_count; i--) {
1521                                 unsigned long val2 = set2->ulongs[i];
1522                                 if (val1 == val2)
1523                                         continue;
1524                                 return val1 < val2 ? -1 : 1;
1525                         }
1526                 } else {
1527                         unsigned long val2 = set2->infinite ? HWLOC_SUBBITMAP_FULL :  HWLOC_SUBBITMAP_ZERO;
1528                         for(i=(int)max_count-1; i>=(int) min_count; i--) {
1529                                 unsigned long val1 = set1->ulongs[i];
1530                                 if (val1 == val2)
1531                                         continue;
1532                                 return val1 < val2 ? -1 : 1;
1533                         }
1534                 }
1535         }
1536 
1537         for(i=(int)min_count-1; i>=0; i--) {
1538                 unsigned long val1 = set1->ulongs[i];
1539                 unsigned long val2 = set2->ulongs[i];
1540                 if (val1 == val2)
1541                         continue;
1542                 return val1 < val2 ? -1 : 1;
1543         }
1544 
1545         return 0;
1546 }
1547 
1548 int hwloc_bitmap_weight(const struct hwloc_bitmap_s * set)
1549 {
1550         int weight = 0;
1551         unsigned i;
1552 
1553         HWLOC__BITMAP_CHECK(set);
1554 
1555         if (set->infinite)
1556                 return -1;
1557 
1558         for(i=0; i<set->ulongs_count; i++)
1559                 weight += hwloc_weight_long(set->ulongs[i]);
1560         return weight;
1561 }
1562 
1563 int hwloc_bitmap_compare_inclusion(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
1564 {
1565         unsigned max_count = set1->ulongs_count > set2->ulongs_count ? set1->ulongs_count : set2->ulongs_count;
1566         int result = HWLOC_BITMAP_EQUAL; /* means empty sets return equal */
1567         int empty1 = 1;
1568         int empty2 = 1;
1569         unsigned i;
1570 
1571         HWLOC__BITMAP_CHECK(set1);
1572         HWLOC__BITMAP_CHECK(set2);
1573 
1574         for(i=0; i<max_count; i++) {
1575           unsigned long val1 = HWLOC_SUBBITMAP_READULONG(set1, (unsigned) i);
1576           unsigned long val2 = HWLOC_SUBBITMAP_READULONG(set2, (unsigned) i);
1577 
1578           if (!val1) {
1579             if (!val2)
1580               /* both empty, no change */
1581               continue;
1582 
1583             /* val1 empty, val2 not */
1584             if (result == HWLOC_BITMAP_CONTAINS) {
1585               if (!empty2)
1586                 return HWLOC_BITMAP_INTERSECTS;
1587               result = HWLOC_BITMAP_DIFFERENT;
1588             } else if (result == HWLOC_BITMAP_EQUAL) {
1589               result = HWLOC_BITMAP_INCLUDED;
1590             }
1591             /* no change otherwise */
1592 
1593           } else if (!val2) {
1594             /* val2 empty, val1 not */
1595             if (result == HWLOC_BITMAP_INCLUDED) {
1596               if (!empty1)
1597                 return HWLOC_BITMAP_INTERSECTS;
1598               result = HWLOC_BITMAP_DIFFERENT;
1599             } else if (result == HWLOC_BITMAP_EQUAL) {
1600               result = HWLOC_BITMAP_CONTAINS;
1601             }
1602             /* no change otherwise */
1603 
1604           } else if (val1 == val2) {
1605             /* equal and not empty */
1606             if (result == HWLOC_BITMAP_DIFFERENT)
1607               return HWLOC_BITMAP_INTERSECTS;
1608             /* equal/contains/included unchanged */
1609 
1610           } else if ((val1 & val2) == val1) {
1611             /* included and not empty */
1612             if (result == HWLOC_BITMAP_CONTAINS || result == HWLOC_BITMAP_DIFFERENT)
1613               return HWLOC_BITMAP_INTERSECTS;
1614             /* equal/included unchanged */
1615             result = HWLOC_BITMAP_INCLUDED;
1616 
1617           } else if ((val1 & val2) == val2) {
1618             /* contains and not empty */
1619             if (result == HWLOC_BITMAP_INCLUDED || result == HWLOC_BITMAP_DIFFERENT)
1620               return HWLOC_BITMAP_INTERSECTS;
1621             /* equal/contains unchanged */
1622             result = HWLOC_BITMAP_CONTAINS;
1623 
1624           } else if ((val1 & val2) != 0) {
1625             /* intersects and not empty */
1626             return HWLOC_BITMAP_INTERSECTS;
1627 
1628           } else {
1629             /* different and not empty */
1630 
1631             /* equal/included/contains with non-empty sets means intersects */
1632             if (result == HWLOC_BITMAP_EQUAL && !empty1 /* implies !empty2 */)
1633               return HWLOC_BITMAP_INTERSECTS;
1634             if (result == HWLOC_BITMAP_INCLUDED && !empty1)
1635               return HWLOC_BITMAP_INTERSECTS;
1636             if (result == HWLOC_BITMAP_CONTAINS && !empty2)
1637               return HWLOC_BITMAP_INTERSECTS;
1638             /* otherwise means different */
1639             result = HWLOC_BITMAP_DIFFERENT;
1640           }
1641 
1642           empty1 &= !val1;
1643           empty2 &= !val2;
1644         }
1645 
1646         if (!set1->infinite) {
1647           if (set2->infinite) {
1648             /* set2 infinite only */
1649             if (result == HWLOC_BITMAP_CONTAINS) {
1650               if (!empty2)
1651                 return HWLOC_BITMAP_INTERSECTS;
1652               result = HWLOC_BITMAP_DIFFERENT;
1653             } else if (result == HWLOC_BITMAP_EQUAL) {
1654               result = HWLOC_BITMAP_INCLUDED;
1655             }
1656             /* no change otherwise */
1657           }
1658         } else if (!set2->infinite) {
1659           /* set1 infinite only */
1660           if (result == HWLOC_BITMAP_INCLUDED) {
1661             if (!empty1)
1662               return HWLOC_BITMAP_INTERSECTS;
1663             result = HWLOC_BITMAP_DIFFERENT;
1664           } else if (result == HWLOC_BITMAP_EQUAL) {
1665             result = HWLOC_BITMAP_CONTAINS;
1666           }
1667           /* no change otherwise */
1668         } else {
1669           /* both infinite */
1670           if (result == HWLOC_BITMAP_DIFFERENT)
1671             return HWLOC_BITMAP_INTERSECTS;
1672           /* equal/contains/included unchanged */
1673         }
1674 
1675         return result;
1676 }
/* [<][>][^][v][top][bottom][index][help] */
root/opal/mca/hwloc/hwloc201/hwloc/hwloc/bitmap.c

DEFINITIONS
