lustre/utils/hostlist.c

   1 /*****************************************************************************\
   2  *  $Id: hostlist.c,v 1.1.10.2 2008/12/18 18:02:13 johann Exp $
   3  *****************************************************************************
   4  *  Copyright (C) 2002 The Regents of the University of California.
   5  *  Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
   6  *  Written by Mark Grondona <mgrondona@llnl.gov>
   7  *  UCRL-CODE-2002-040.
   8  *
   9  *  This file is part of SLURM, a resource management program.
  10  *  For details, see <http://www.llnl.gov/linux/slurm/>.
  11  *
  12  *  SLURM is free software; you can redistribute it and/or modify it under
  13  *  the terms of the GNU General Public License as published by the Free
  14  *  Software Foundation; either version 2 of the License, or (at your option)
  15  *  any later version.
  16  *
  17  *  SLURM is distributed in the hope that it will be useful, but WITHOUT ANY
  18  *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  19  *  FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  20  *  details.
  21  *
  22  *  You should have received a copy of the GNU General Public License along
  23  *  with SLURM; if not, write to the Free Software Foundation, Inc.,
  24  *  59 Temple Place, Suite 330, Boston, MA  02111-1307  USA.
  25 \*****************************************************************************/
  26
  27 #ifdef HAVE_CONFIG_H
  28 #  include "config.h"
  29 #  if HAVE_STRING_H
  30 #    include <string.h>
  31 #  endif
  32 #  if HAVE_PTHREAD_H
  33 #    include <pthread.h>
  34 #  endif
  35 #else                /* !HAVE_CONFIG_H */
  36 #  include <string.h>
  37 #  include <pthread.h>
  38 #endif                /* HAVE_CONFIG_H */
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <stdarg.h>
  43 #include <assert.h>
  44 #include <errno.h>
  45 #include <ctype.h>
  46 #include <sys/param.h>
  47 #include <unistd.h>
  48
  49 #include "hostlist.h"
  50
  51 /*
  52  * lsd_fatal_error : fatal error macro
  53  */
  54 #ifdef WITH_LSD_FATAL_ERROR_FUNC
  55 #  undef lsd_fatal_error
  56    extern void lsd_fatal_error(char *file, int line, char *mesg);
  57 #else /* !WITH_LSD_FATAL_ERROR_FUNC */
  58 #  ifndef lsd_fatal_error
  59 #    define lsd_fatal_error(file, line, mesg)                                \
  60        do {                                                                  \
  61            fprintf(stderr, "ERROR: [%s:%d] %s: %s\n",                        \
  62            file, line, mesg, strerror(errno));                               \
  63        } while (0)
  64 #  endif /* !lsd_fatal_error */
  65 #endif /* !WITH_LSD_FATAL_ERROR_FUNC */
  66
  67 /*
  68  * lsd_nonmem_error
  69  */
  70 #ifdef WITH_LSD_NOMEM_ERROR_FUNC
  71 #  undef lsd_nomem_error
  72    extern void * lsd_nomem_error(char *file, int line, char *mesg);
  73 #else /* !WITH_LSD_NOMEM_ERROR_FUNC */
  74 #  ifndef lsd_nomem_error
  75 #    define lsd_nomem_error(file, line, mesg) (NULL)
  76 #  endif /* !lsd_nomem_error */
  77 #endif /* !WITH_LSD_NOMEM_ERROR_FUNC */
  78
  79 /*
  80  * OOM helper function
  81  *  Automatically call lsd_nomem_error with appropriate args
  82  *  and set errno to ENOMEM
  83  */
  84 #define out_of_memory(mesg)                                                  \
  85     do {                                                                     \
  86         errno = ENOMEM;                                                      \
  87         return(lsd_nomem_error(__FILE__, __LINE__, mesg));                   \
  88     } while (0)
  89
  90 /*
  91  * Some constants and tunables:
  92  */
  93
  94 /* number of elements to allocate when extending the hostlist array */
  95 #define HOSTLIST_CHUNK    16
  96
  97 /* max host range: anything larger will be assumed to be an error */
  98 #define MAX_RANGE    16384    /* 16K Hosts */
  99
 100 /* max host suffix value */
 101 #define MAX_HOST_SUFFIX 1<<25
 102
 103 /* max number of ranges that will be processed between brackets */
 104 #define MAX_RANGES    10240    /* 10K Ranges */
 105
 106 /* size of internal hostname buffer (+ some slop), hostnames will probably
 107  * be truncated if longer than MAXHOSTNAMELEN */
 108 #ifndef MAXHOSTNAMELEN
 109 #define MAXHOSTNAMELEN    64
 110 #endif
 111
 112 /* max size of internal hostrange buffer */
 113 #define MAXHOSTRANGELEN 1024
 114
 115 /* ----[ Internal Data Structures ]---- */
 116
 117 /* hostname type: A convenience structure used in parsing single hostnames */
 118 struct hostname_components {
 119     char *hostname;         /* cache of initialized hostname        */
 120     char *prefix;           /* hostname prefix                      */
 121     unsigned long num;      /* numeric suffix                       */
 122
 123     /* string representation of numeric suffix
 124      * points into `hostname'                                       */
 125     char *suffix;
 126 };
 127
 128 typedef struct hostname_components *hostname_t;
 129
 130 /* hostrange type: A single prefix with `hi' and `lo' numeric suffix values */
 131 struct hostrange_components {
 132     char *prefix;        /* alphanumeric prefix: */
 133
 134     /* beginning (lo) and end (hi) of suffix range */
 135     unsigned long lo, hi;
 136
 137     /* width of numeric output format
 138      * (pad with zeros up to this width) */
 139     int width;
 140
 141     /* If singlehost is 1, `lo' and `hi' are invalid */
 142     unsigned singlehost:1;
 143 };
 144
 145 typedef struct hostrange_components *hostrange_t;
 146
 147 /* The hostlist type: An array based list of hostrange_t's */
 148 struct hostlist {
 149 #ifndef NDEBUG
 150 #define HOSTLIST_MAGIC    57005
 151     int magic;
 152 #endif
 153 #if    WITH_PTHREADS
 154     pthread_mutex_t mutex;
 155 #endif                /* WITH_PTHREADS */
 156
 157     /* current number of elements available in array */
 158     int size;
 159
 160     /* current number of ranges stored in array */
 161     int nranges;
 162
 163     /* current number of hosts stored in hostlist */
 164     int nhosts;
 165
 166     /* pointer to hostrange array */
 167     hostrange_t *hr;
 168
 169     /* list of iterators */
 170     struct hostlist_iterator *ilist;
 171
 172 };
 173
 174
 175 /* a hostset is a wrapper around a hostlist */
 176 struct hostset {
 177     hostlist_t hl;
 178 };
 179
 180 struct hostlist_iterator {
 181 #ifndef NDEBUG
 182     int magic;
 183 #endif
 184     /* hostlist we are traversing */
 185     hostlist_t hl;
 186
 187     /* current index of iterator in hl->hr[] */
 188     int idx;
 189
 190     /* current hostrange object in list hl, i.e. hl->hr[idx] */
 191     hostrange_t hr;
 192
 193     /* current depth we've traversed into range hr */
 194     int depth;
 195
 196     /* next ptr for lists of iterators */
 197     struct hostlist_iterator *next;
 198 };
 199
 200
 201 /* ---- ---- */
 202
 203 /* ------[ static function prototypes ]------ */
 204
 205 static void _error(char *file, int line, char *mesg, ...);
 206 static char * _next_tok(char *, char **);
 207 static int    _zero_padded(unsigned long, int);
 208 static int    _width_equiv(unsigned long, int *, unsigned long, int *);
 209
 210 static int           host_prefix_end(const char *);
 211 static hostname_t    hostname_create(const char *);
 212 static void          hostname_destroy(hostname_t);
 213 static int           hostname_suffix_is_valid(hostname_t);
 214 static int           hostname_suffix_width(hostname_t);
 215
 216 static hostrange_t   hostrange_new(void);
 217 static hostrange_t   hostrange_create_single(const char *);
 218 static hostrange_t   hostrange_create(char *, unsigned long, unsigned long, int);
 219 static unsigned long hostrange_count(hostrange_t);
 220 static hostrange_t   hostrange_copy(hostrange_t);
 221 static void          hostrange_destroy(hostrange_t);
 222 static hostrange_t   hostrange_delete_host(hostrange_t, unsigned long);
 223 static int           hostrange_cmp(hostrange_t, hostrange_t);
 224 static int           hostrange_prefix_cmp(hostrange_t, hostrange_t);
 225 static int           hostrange_within_range(hostrange_t, hostrange_t);
 226 static int           hostrange_width_combine(hostrange_t, hostrange_t);
 227 static int           hostrange_empty(hostrange_t);
 228 static char *        hostrange_pop(hostrange_t);
 229 static char *        hostrange_shift(hostrange_t);
 230 static int           hostrange_join(hostrange_t, hostrange_t);
 231 static hostrange_t   hostrange_intersect(hostrange_t, hostrange_t);
 232 static int           hostrange_hn_within(hostrange_t, hostname_t);
 233 static size_t        hostrange_to_string(hostrange_t hr, size_t, char *, char *);
 234 static size_t        hostrange_numstr(hostrange_t, size_t, char *);
 235
 236 static hostlist_t  hostlist_new(void);
 237 static hostlist_t _hostlist_create_bracketed(const char *, char *, char *);
 238 static int         hostlist_resize(hostlist_t, size_t);
 239 static int         hostlist_expand(hostlist_t);
 240 static int         hostlist_push_range(hostlist_t, hostrange_t);
 241 static int         hostlist_push_hr(hostlist_t, char *, unsigned long,
 242                                     unsigned long, int);
 243 static int         hostlist_insert_range(hostlist_t, hostrange_t, int);
 244 static void        hostlist_delete_range(hostlist_t, int n);
 245 static void        hostlist_coalesce(hostlist_t hl);
 246 static void        hostlist_collapse(hostlist_t hl);
 247 static hostlist_t _hostlist_create(const char *, char *, char *);
 248 static void        hostlist_shift_iterators(hostlist_t, int, int, int);
 249 static int        _attempt_range_join(hostlist_t, int);
 250 static int        _is_bracket_needed(hostlist_t, int);
 251
 252 static hostlist_iterator_t hostlist_iterator_new(void);
 253 static void               _iterator_advance(hostlist_iterator_t);
 254 static void               _iterator_advance_range(hostlist_iterator_t);
 255
 256 static int hostset_find_host(hostset_t, const char *);
 257
 258 /* ------[ macros ]------ */
 259
 260 #ifdef WITH_PTHREADS
 261 #  define mutex_init(mutex)                                                  \
 262      do {                                                                    \
 263         int e = pthread_mutex_init(mutex, NULL);                             \
 264         if (e) {                                                             \
 265             errno = e;                                                       \
 266             lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex init:");     \
 267             abort();                                                         \
 268         }                                                                    \
 269      } while (0)
 270
 271 #  define mutex_lock(mutex)                                                  \
 272      do {                                                                    \
 273         int e = pthread_mutex_lock(mutex);                                   \
 274         if (e) {                                                             \
 275            errno = e;                                                        \
 276            lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex lock:");      \
 277            abort();                                                          \
 278         }                                                                    \
 279      } while (0)
 280
 281 #  define mutex_unlock(mutex)                                                \
 282      do {                                                                    \
 283         int e = pthread_mutex_unlock(mutex);                                 \
 284         if (e) {                                                             \
 285             errno = e;                                                       \
 286             lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex unlock:");   \
 287             abort();                                                         \
 288         }                                                                    \
 289      } while (0)
 290
 291 #  define mutex_destroy(mutex)                                               \
 292      do {                                                                    \
 293         int e = pthread_mutex_destroy(mutex);                                \
 294         if (e) {                                                             \
 295             errno = e;                                                       \
 296             lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex destroy:");  \
 297             abort();                                                         \
 298         }                                                                    \
 299      } while (0)
 300
 301 #else                /* !WITH_PTHREADS */
 302
 303 #  define mutex_init(mutex)
 304 #  define mutex_lock(mutex)
 305 #  define mutex_unlock(mutex)
 306 #  define mutex_destroy(mutex)
 307
 308 #endif                /* WITH_PTHREADS */
 309
 310 #define LOCK_HOSTLIST(_hl)                                                   \
 311       do {                                                                   \
 312           assert(_hl != NULL);                                               \
 313           mutex_lock(&(_hl)->mutex);                                         \
 314           assert((_hl)->magic == HOSTLIST_MAGIC);                            \
 315       } while (0)
 316
 317 #define UNLOCK_HOSTLIST(_hl)                                                 \
 318       do {                                                                   \
 319           mutex_unlock(&(_hl)->mutex);                                       \
 320       } while (0)
 321
 322 #define seterrno_ret(_errno, _rc)                                            \
 323       do {                                                                   \
 324           errno = _errno;                                                    \
 325           return _rc;                                                        \
 326       } while (0)
 327
 328 /* ------[ Function Definitions ]------ */
 329
 330 /* ----[ general utility functions ]---- */
 331
 332
 333 /*
 334  *  Varargs capable error reporting via lsd_fatal_error()
 335  */
 336 static void _error(char *file, int line, char *msg, ...)
 337 {
 338     va_list ap;
 339     char    buf[1024];
 340     int     len = 0;
 341     va_start(ap, msg);
 342
 343     len = vsnprintf(buf, 1024, msg, ap);
 344     if ((len < 0) || (len > 1024))
 345         buf[1023] = '\0';
 346
 347     lsd_fatal_error(file, line, buf);
 348
 349     va_end(ap);
 350     return;
 351 }
 352
 353 static int _advance_past_brackets (char *tok, char **str)
 354 {
 355     /* if _single_ opening bracket exists b/w tok and str, push str
 356      * past first closing bracket to next seperator */
 357     if (   memchr(tok, '[', *str - tok) != NULL
 358         && memchr(tok, ']', *str - tok) == NULL ) {
 359         char *q = strchr(*str, ']');
 360         if (q && memchr(*str, '[', q - *str) == NULL) {
 361             *str = q + 1;
 362             return (1);
 363         }
 364     }
 365
 366     return 0;
 367 }
 368
 369 /*
 370  * Helper function for host list string parsing routines
 371  * Returns a pointer to the next token; additionally advance *str
 372  * to the next separator.
 373  *
 374  * next_tok was taken directly from pdsh courtesy of Jim Garlick.
 375  * (with modifications to support bracketed hostlists, i.e.:
 376  *  xxx[xx,xx,xx] is a single token)
 377  *
 378  */
 379 static char * _next_tok(char *sep, char **str)
 380 {
 381     char *tok;
 382
 383     /* push str past any leading separators */
 384     while (**str != '\0' && strchr(sep, **str) != '\0')
 385         (*str)++;
 386
 387     if (**str == '\0')
 388         return NULL;
 389
 390     /* assign token ptr */
 391     tok = *str;
 392
 393     /*
 394      * Advance str past any separators, but if a separator occurs between
 395      *  brackets, e.g. foo[0-3,5], then advance str past closing brackets and
 396      *  try again.
 397      */
 398     do {
 399         /* push str past token and leave pointing to first separator */
 400         while (**str != '\0' && strchr(sep, **str) == '\0')
 401             (*str)++;
 402     } while (_advance_past_brackets (tok, str));
 403
 404    /* nullify consecutive separators and push str beyond them */
 405     while (**str != '\0' && strchr(sep, **str) != '\0')
 406         *(*str)++ = '\0';
 407
 408     return tok;
 409 }
 410
 411
 412 /* return the number of zeros needed to pad "num" to "width"
 413  */
 414 static int _zero_padded(unsigned long num, int width)
 415 {
 416     int n = 1;
 417     while (num /= 10L)
 418         n++;
 419     return width > n ? width - n : 0;
 420 }
 421
 422 /* test whether two format `width' parameters are "equivalent"
 423  * The width arguments "wn" and "wm" for integers "n" and "m"
 424  * are equivalent if:
 425  *
 426  *  o  wn == wm  OR
 427  *
 428  *  o  applying the same format width (either wn or wm) to both of
 429  *     'n' and 'm' will not change the zero padding of *either* 'm' nor 'n'.
 430  *
 431  *  If this function returns 1 (or true), the appropriate width value
 432  *  (either 'wm' or 'wn') will have been adjusted such that both format
 433  *  widths are equivalent.
 434  */
 435 static int _width_equiv(unsigned long n, int *wn, unsigned long m, int *wm)
 436 {
 437     int npad, nmpad, mpad, mnpad;
 438
 439     if (wn == wm)
 440         return 1;
 441
 442     npad = _zero_padded(n, *wn);
 443     nmpad = _zero_padded(n, *wm);
 444     mpad = _zero_padded(m, *wm);
 445     mnpad = _zero_padded(m, *wn);
 446
 447     if (npad != nmpad && mpad != mnpad)
 448         return 0;
 449
 450     if (npad != nmpad) {
 451         if (mpad == mnpad) {
 452             *wm = *wn;
 453             return 1;
 454         } else
 455             return 0;
 456     } else {        /* mpad != mnpad */
 457         if (npad == nmpad) {
 458             *wn = *wm;
 459             return 1;
 460         } else
 461             return 0;
 462     }
 463
 464     /* not reached */
 465 }
 466
 467
 468 /* ----[ hostname_t functions ]---- */
 469
 470 /*
 471  * return the location of the last char in the hostname prefix
 472  */
 473 static int host_prefix_end(const char *hostname)
 474 {
 475     int idx = strlen(hostname) - 1;
 476
 477     while (idx >= 0 && isdigit((char) hostname[idx]))
 478         idx--;
 479     return idx;
 480 }
 481
 482 /*
 483  * create a hostname_t object from a string hostname
 484  */
 485 static hostname_t hostname_create(const char *hostname)
 486 {
 487     hostname_t hn = NULL;
 488     char *p = '\0';
 489     int idx = 0;
 490
 491     assert(hostname != NULL);
 492
 493     if (!(hn = (hostname_t) malloc(sizeof(*hn))))
 494         out_of_memory("hostname create");
 495
 496     idx = host_prefix_end(hostname);
 497
 498     if (!(hn->hostname = strdup(hostname))) {
 499         free(hn);
 500         out_of_memory("hostname create");
 501     }
 502
 503     hn->num = 0;
 504     hn->prefix = NULL;
 505     hn->suffix = NULL;
 506
 507     if (idx == strlen(hostname) - 1) {
 508         if ((hn->prefix = strdup(hostname)) == NULL) {
 509             hostname_destroy(hn);
 510             out_of_memory("hostname prefix create");
 511         }
 512         return hn;
 513     }
 514
 515     hn->suffix = hn->hostname + idx + 1;
 516     hn->num = strtoul(hn->suffix, &p, 10);
 517
 518     if ((*p == '\0') && (hn->num <= MAX_HOST_SUFFIX)) {
 519         if (!(hn->prefix = malloc((idx + 2) * sizeof(char)))) {
 520             hostname_destroy(hn);
 521             out_of_memory("hostname prefix create");
 522         }
 523         memcpy(hn->prefix, hostname, idx + 1);
 524         hn->prefix[idx + 1] = '\0';
 525     } else {
 526         if (!(hn->prefix = strdup(hostname))) {
 527             hostname_destroy(hn);
 528             out_of_memory("hostname prefix create");
 529         }
 530         hn->suffix = NULL;
 531     }
 532
 533     return hn;
 534 }
 535
 536 /* free a hostname object
 537  */
 538 static void hostname_destroy(hostname_t hn)
 539 {
 540     if (hn == NULL)
 541         return;
 542     hn->suffix = NULL;
 543     if (hn->hostname)
 544         free(hn->hostname);
 545     if (hn->prefix)
 546         free(hn->prefix);
 547     free(hn);
 548 }
 549
 550 /* return true if the hostname has a valid numeric suffix
 551  */
 552 static int hostname_suffix_is_valid(hostname_t hn)
 553 {
 554     return hn->suffix != NULL;
 555 }
 556
 557 /* return the width (in characters) of the numeric part of the hostname
 558  */
 559 static int hostname_suffix_width(hostname_t hn)
 560 {
 561     assert(hn->suffix != NULL);
 562     return (int) strlen(hn->suffix);
 563 }
 564
 565
 566 /* ----[ hostrange_t functions ]---- */
 567
 568 /* allocate a new hostrange object
 569  */
 570 static hostrange_t hostrange_new(void)
 571 {
 572     hostrange_t new = (hostrange_t) malloc(sizeof(*new));
 573     if (!new)
 574         out_of_memory("hostrange create");
 575     return new;
 576 }
 577
 578 /* Create a hostrange_t containing a single host without a valid suffix
 579  * hr->prefix will represent the entire hostname.
 580  */
 581 static hostrange_t hostrange_create_single(const char *prefix)
 582 {
 583     hostrange_t new;
 584
 585     assert(prefix != NULL);
 586
 587     if ((new = hostrange_new()) == NULL)
 588         goto error1;
 589
 590     if ((new->prefix = strdup(prefix)) == NULL)
 591         goto error2;
 592
 593     new->singlehost = 1;
 594     new->lo = 0L;
 595     new->hi = 0L;
 596     new->width = 0;
 597
 598     return new;
 599
 600   error2:
 601     free(new);
 602   error1:
 603     out_of_memory("hostrange create single");
 604 }
 605
 606
 607 /* Create a hostrange object with a prefix, hi, lo, and format width
 608  */
 609 static hostrange_t
 610 hostrange_create(char *prefix, unsigned long lo, unsigned long hi, int width)
 611 {
 612     hostrange_t new;
 613
 614     assert(prefix != NULL);
 615
 616     if ((new = hostrange_new()) == NULL)
 617         goto error1;
 618
 619     if ((new->prefix = strdup(prefix)) == NULL)
 620         goto error2;
 621
 622     new->lo = lo;
 623     new->hi = hi;
 624     new->width = width;
 625
 626     new->singlehost = 0;
 627
 628     return new;
 629
 630   error2:
 631     free(new);
 632   error1:
 633     out_of_memory("hostrange create");
 634 }
 635
 636
 637 /* Return the number of hosts stored in the hostrange object
 638  */
 639 static unsigned long hostrange_count(hostrange_t hr)
 640 {
 641     assert(hr != NULL);
 642     if (hr->singlehost)
 643         return 1;
 644     else
 645         return hr->hi - hr->lo + 1;
 646 }
 647
 648 /* Copy a hostrange object
 649  */
 650 static hostrange_t hostrange_copy(hostrange_t hr)
 651 {
 652     assert(hr != NULL);
 653
 654     if (hr->singlehost)
 655         return hostrange_create_single(hr->prefix);
 656     else
 657         return hostrange_create(hr->prefix, hr->lo, hr->hi,
 658                     hr->width);
 659 }
 660
 661
 662 /* free memory allocated by the hostrange object
 663  */
 664 static void hostrange_destroy(hostrange_t hr)
 665 {
 666     if (hr == NULL)
 667         return;
 668     if (hr->prefix)
 669         free(hr->prefix);
 670     free(hr);
 671 }
 672
 673 /* hostrange_delete_host() deletes a specific host from the range.
 674  * If the range is split into two, the greater range is returned,
 675  * and `hi' of the lesser range is adjusted accordingly. If the
 676  * highest or lowest host is deleted from a range, NULL is returned
 677  * and the hostrange hr is adjusted properly.
 678  */
 679 static hostrange_t hostrange_delete_host(hostrange_t hr, unsigned long n)
 680 {
 681     hostrange_t new = NULL;
 682
 683     assert(hr != NULL);
 684     assert(n >= hr->lo && n <= hr->hi);
 685
 686     if (n == hr->lo)
 687         hr->lo++;
 688     else if (n == hr->hi)
 689         hr->hi--;
 690     else {
 691         if (!(new = hostrange_copy(hr)))
 692             out_of_memory("hostrange copy");
 693         hr->hi = n - 1;
 694         new->lo = n + 1;
 695     }
 696
 697     return new;
 698 }
 699
 700 /* hostrange_cmp() is used to sort hostrange objects. It will
 701  * sort based on the following (in order):
 702  *  o result of strcmp on prefixes
 703  *  o if widths are compatible, then:
 704  *       sort based on lowest suffix in range
 705  *    else
 706  *       sort based on width                     */
 707 static int hostrange_cmp(hostrange_t h1, hostrange_t h2)
 708 {
 709     int retval;
 710
 711     assert(h1 != NULL);
 712     assert(h2 != NULL);
 713
 714     if ((retval = hostrange_prefix_cmp(h1, h2)) == 0)
 715         retval = hostrange_width_combine(h1, h2) ?
 716             h1->lo - h2->lo : h1->width - h2->width;
 717
 718     return retval;
 719 }
 720
 721
 722 /* compare the prefixes of two hostrange objects.
 723  * returns:
 724  *    < 0   if h1 prefix is less than h2 OR h1 == NULL.
 725  *
 726  *      0   if h1's prefix and h2's prefix match,
 727  *          UNLESS, either h1 or h2 (NOT both) do not have a valid suffix.
 728  *
 729  *    > 0   if h1's prefix is greater than h2's OR h2 == NULL. */
 730 static int hostrange_prefix_cmp(hostrange_t h1, hostrange_t h2)
 731 {
 732     int retval;
 733     if (h1 == NULL)
 734         return 1;
 735     if (h2 == NULL)
 736         return -1;
 737
 738     retval = strcmp(h1->prefix, h2->prefix);
 739     return retval == 0 ? h2->singlehost - h1->singlehost : retval;
 740 }
 741
 742 /* returns true if h1 and h2 would be included in the same bracketed hostlist.
 743  * h1 and h2 will be in the same bracketed list iff:
 744  *
 745  *  1. h1 and h2 have same prefix
 746  *  2. neither h1 nor h2 are singlet hosts (i.e. invalid suffix)
 747  *
 748  *  (XXX: Should incompatible widths be placed in the same bracketed list?
 749  *        There's no good reason not to, except maybe aesthetics)
 750  */
 751 static int hostrange_within_range(hostrange_t h1, hostrange_t h2)
 752 {
 753     if (hostrange_prefix_cmp(h1, h2) == 0)
 754         return h1->singlehost || h2->singlehost ? 0 : 1;
 755     else
 756         return 0;
 757 }
 758
 759
 760 /* compare two hostrange objects to determine if they are width
 761  * compatible,  returns:
 762  *  1 if widths can safely be combined
 763  *  0 if widths cannot be safely combined
 764  */
 765 static int hostrange_width_combine(hostrange_t h0, hostrange_t h1)
 766 {
 767     assert(h0 != NULL);
 768     assert(h1 != NULL);
 769
 770     return _width_equiv(h0->lo, &h0->width, h1->lo, &h1->width);
 771 }
 772
 773
 774 /* Return true if hostrange hr contains no hosts, i.e. hi < lo
 775  */
 776 static int hostrange_empty(hostrange_t hr)
 777 {
 778     assert(hr != NULL);
 779     return ((hr->hi < hr->lo) || (hr->hi == (unsigned long) -1));
 780 }
 781
 782 /* return the string representation of the last host in hostrange hr
 783  * and remove that host from the range (i.e. decrement hi if possible)
 784  *
 785  * Returns NULL if malloc fails OR there are no more hosts left
 786  */
 787 static char *hostrange_pop(hostrange_t hr)
 788 {
 789     size_t size = 0;
 790     char *host = NULL;
 791
 792     assert(hr != NULL);
 793
 794     if (hr->singlehost) {
 795         hr->lo++;    /* effectively set count == 0 */
 796         host = strdup(hr->prefix);
 797     } else if (hostrange_count(hr) > 0) {
 798         size = strlen(hr->prefix) + hr->width + 16;
 799         if (!(host = (char *) malloc(size * sizeof(char))))
 800             out_of_memory("hostrange pop");
 801         snprintf(host, size, "%s%0*lu", hr->prefix,
 802              hr->width, hr->hi--);
 803     }
 804
 805     return host;
 806 }
 807
 808 /* Same as hostrange_pop(), but remove host from start of range */
 809 static char *hostrange_shift(hostrange_t hr)
 810 {
 811     size_t size = 0;
 812     char *host = NULL;
 813
 814     assert(hr != NULL);
 815
 816     if (hr->singlehost) {
 817         hr->lo++;
 818         if (!(host = strdup(hr->prefix)))
 819             out_of_memory("hostrange shift");
 820     } else if (hostrange_count(hr) > 0) {
 821         size = strlen(hr->prefix) + hr->width + 16;
 822         if (!(host = (char *) malloc(size * sizeof(char))))
 823             out_of_memory("hostrange shift");
 824         snprintf(host, size, "%s%0*lu", hr->prefix,
 825              hr->width, hr->lo++);
 826     }
 827
 828     return host;
 829 }
 830
 831
 832 /* join two hostrange objects.
 833  *
 834  * returns:
 835  *
 836  * -1 if ranges do not overlap (including incompatible zero padding)
 837  *  0 if ranges join perfectly
 838  * >0 number of hosts that were duplicated in  h1 and h2
 839  *
 840  * h2 will be coalesced into h1 if rc >= 0
 841  *
 842  * it is assumed that h1->lo <= h2->lo, i.e. hr1 <= hr2
 843  *
 844  */
 845 static int hostrange_join(hostrange_t h1, hostrange_t h2)
 846 {
 847     int duplicated = -1;
 848
 849     assert(h1 != NULL);
 850     assert(h2 != NULL);
 851     assert(hostrange_cmp(h1, h2) <= 0);
 852
 853     if (hostrange_prefix_cmp(h1, h2) == 0 &&
 854         hostrange_width_combine(h1, h2)) {
 855
 856         if (h1->singlehost && h2->singlehost) {    /* matching singlets  */
 857             duplicated = 1;
 858         } else if (h1->hi == h2->lo - 1) {    /* perfect join       */
 859             h1->hi = h2->hi;
 860             duplicated = 0;
 861         } else if (h1->hi >= h2->lo) {    /* some duplication   */
 862             if (h1->hi < h2->hi) {
 863                 duplicated = h1->hi - h2->lo + 1;
 864                 h1->hi = h2->hi;
 865             } else
 866                 duplicated = hostrange_count(h2);
 867         }
 868     }
 869
 870     return duplicated;
 871 }
 872
 873 /* hostrange intersect returns the intersection (common hosts)
 874  * of hostrange objects h1 and h2. If there is no intersection,
 875  * NULL is returned.
 876  *
 877  * It is assumed that h1 <= h2 (i.e. h1->lo <= h2->lo)
 878  */
 879 static hostrange_t hostrange_intersect(hostrange_t h1, hostrange_t h2)
 880 {
 881     hostrange_t new = NULL;
 882
 883     assert(h1 != NULL);
 884     assert(h2 != NULL);
 885
 886     if (h1->singlehost || h2->singlehost)
 887         return NULL;
 888
 889     assert(hostrange_cmp(h1, h2) <= 0);
 890
 891     if ((hostrange_prefix_cmp(h1, h2) == 0)
 892         && (h1->hi > h2->lo)
 893         && (hostrange_width_combine(h1, h2))) {
 894
 895         if (!(new = hostrange_copy(h1)))
 896             return NULL;
 897         new->lo = h2->lo;
 898         new->hi = h2->hi < h1->hi ? h2->hi : h1->hi;
 899     }
 900
 901     return new;
 902 }
 903
 904 /* return 1 if hostname hn is within the hostrange hr
 905  *        0 if not.
 906  */
 907 static int hostrange_hn_within(hostrange_t hr, hostname_t hn)
 908 {
 909     int retval = 0;
 910
 911     if (hr->singlehost && (strcmp(hn->hostname, hr->prefix) == 0))
 912         return 1;
 913
 914     if (strcmp(hr->prefix, hn->prefix) == 0) {
 915         if (!hostname_suffix_is_valid(hn)) {
 916             if (hr->singlehost)
 917                 retval = 1;
 918         } else if (hn->num <= hr->hi && hn->num >= hr->lo) {
 919             int width = hostname_suffix_width(hn);
 920             int num = hn->num;
 921             retval = _width_equiv(hr->lo, &hr->width, num, &width);
 922         }
 923     }
 924     return retval;
 925 }
 926
 927
 928 /* copy a string representation of the hostrange hr into buffer buf,
 929  * writing at most n chars including NUL termination
 930  */
 931 static size_t
 932 hostrange_to_string(hostrange_t hr, size_t n, char *buf, char *separator)
 933 {
 934     unsigned long i;
 935     int truncated = 0;
 936     int len = 0;
 937     char sep = separator == NULL ? ',' : separator[0];
 938
 939     if (n == 0)
 940         return 0;
 941
 942     if (hr->singlehost)
 943         return snprintf(buf, n, "%s", hr->prefix);
 944
 945     for (i = hr->lo; i <= hr->hi; i++) {
 946         size_t m = (n - len) <= n ? n - len : 0; /* check for < 0 */
 947         int ret = snprintf(buf + len, m, "%s%0*lu",
 948                    hr->prefix, hr->width, i);
 949         if (ret < 0 || ret >= m) {
 950             len = n;
 951             truncated = 1;
 952             break;
 953         }
 954         len+=ret;
 955         buf[len++] = sep;
 956     }
 957
 958     if (truncated) {
 959         buf[n-1] = '\0';
 960         return -1;
 961     } else {
 962         /* back up over final separator */
 963         buf[--len] = '\0';
 964         return len;
 965     }
 966 }
 967
 968 /* Place the string representation of the numeric part of hostrange into buf
 969  * writing at most n chars including NUL termination.
 970  */
 971 static size_t hostrange_numstr(hostrange_t hr, size_t n, char *buf)
 972 {
 973     int len = 0;
 974
 975     assert(buf != NULL);
 976
 977     if (hr->singlehost || n == 0)
 978         return 0;
 979
 980     len = snprintf(buf, n, "%0*lu", hr->width, hr->lo);
 981
 982     if ((len >= 0) && (len < n) && (hr->lo < hr->hi)) {
 983         int len2 = snprintf(buf+len, n-len, "-%0*lu", hr->width, hr->hi);
 984         if (len2 < 0)
 985             len = -1;
 986         else
 987             len += len2;
 988     }
 989
 990     return len;
 991 }
 992
 993
 994 /* ----[ hostlist functions ]---- */
 995
 996 /* Create a new hostlist object.
 997  * Returns an empty hostlist, or NULL if memory allocation fails.
 998  */
 999 static hostlist_t hostlist_new(void)
1000 {
1001     int i;
1002     hostlist_t new = (hostlist_t) malloc(sizeof(*new));
1003     if (!new)
1004         goto fail1;
1005
1006     assert(new->magic = HOSTLIST_MAGIC);
1007     mutex_init(&new->mutex);
1008
1009     new->hr = (hostrange_t *) malloc(HOSTLIST_CHUNK * sizeof(hostrange_t));
1010     if (!new->hr)
1011         goto fail2;
1012
1013     /* set entries in hostrange array to NULL */
1014     for (i = 0; i < HOSTLIST_CHUNK; i++)
1015         new->hr[i] = NULL;
1016
1017     new->size = HOSTLIST_CHUNK;
1018     new->nranges = 0;
1019     new->nhosts = 0;
1020     new->ilist = NULL;
1021     return new;
1022
1023   fail2:
1024     free(new);
1025   fail1:
1026     out_of_memory("hostlist_create");
1027 }
1028
1029
1030 /* Resize the internal array used to store the list of hostrange objects.
1031  *
1032  * returns 1 for a successful resize,
1033  *         0 if call to _realloc fails
1034  *
1035  * It is assumed that the caller has the hostlist hl locked
1036  */
1037 static int hostlist_resize(hostlist_t hl, size_t newsize)
1038 {
1039     int i;
1040     size_t oldsize;
1041     assert(hl != NULL);
1042     assert(hl->magic == HOSTLIST_MAGIC);
1043     oldsize = hl->size;
1044     hl->size = newsize;
1045     hl->hr = realloc((void *) hl->hr, hl->size*sizeof(hostrange_t));
1046     if (!(hl->hr))
1047         return 0;
1048
1049     for (i = oldsize; i < newsize; i++)
1050         hl->hr[i] = NULL;
1051
1052     return 1;
1053 }
1054
1055 /* Resize hostlist by one HOSTLIST_CHUNK
1056  * Assumes that hostlist hl is locked by caller
1057  */
1058 static int hostlist_expand(hostlist_t hl)
1059 {
1060     if (!hostlist_resize(hl, hl->size + HOSTLIST_CHUNK))
1061         return 0;
1062     else
1063         return 1;
1064 }
1065
1066 /* Push a hostrange object onto hostlist hl
1067  * Returns the number of hosts successfully pushed onto hl
1068  * or -1 if there was an error allocating memory
1069  */
1070 static int hostlist_push_range(hostlist_t hl, hostrange_t hr)
1071 {
1072     hostrange_t tail;
1073     int retval;
1074
1075     assert(hr != NULL);
1076     LOCK_HOSTLIST(hl);
1077
1078     tail = (hl->nranges > 0) ? hl->hr[hl->nranges-1] : hl->hr[0];
1079
1080     if (hl->size == hl->nranges && !hostlist_expand(hl))
1081         goto error;
1082
1083     if (hl->nranges > 0
1084         && hostrange_prefix_cmp(tail, hr) == 0
1085         && tail->hi == hr->lo - 1
1086         && hostrange_width_combine(tail, hr)) {
1087         tail->hi = hr->hi;
1088     } else {
1089         if ((hl->hr[hl->nranges++] = hostrange_copy(hr)) == NULL)
1090             goto error;
1091     }
1092
1093     retval = hl->nhosts += hostrange_count(hr);
1094
1095     UNLOCK_HOSTLIST(hl);
1096
1097     return retval;
1098
1099   error:
1100     UNLOCK_HOSTLIST(hl);
1101     return -1;
1102 }
1103
1104
1105
1106 /* Same as hostlist_push_range() above, but prefix, lo, hi, and width
1107  * are passed as args
1108  */
1109 static int
1110 hostlist_push_hr(hostlist_t hl, char *prefix, unsigned long lo,
1111          unsigned long hi, int width)
1112 {
1113     hostrange_t hr = hostrange_create(prefix, lo, hi, width);
1114     int retval = hostlist_push_range(hl, hr);
1115     hostrange_destroy(hr);
1116     return retval;
1117 }
1118
1119 /* Insert a range object hr into position n of the hostlist hl
1120  * Assumes that hl->mutex is already held by calling process
1121  */
1122 static int hostlist_insert_range(hostlist_t hl, hostrange_t hr, int n)
1123 {
1124     int i;
1125     hostrange_t tmp;
1126     hostlist_iterator_t hli;
1127
1128     assert(hl != NULL);
1129     assert(hl->magic == HOSTLIST_MAGIC);
1130     assert(hr != NULL);
1131
1132     if (n > hl->nranges)
1133         return 0;
1134
1135     if (hl->size == hl->nranges && !hostlist_expand(hl))
1136         return 0;
1137
1138     /* copy new hostrange into slot "n" in array */
1139     tmp = hl->hr[n];
1140     hl->hr[n] = hostrange_copy(hr);
1141
1142     /* push remaining hostrange entries up */
1143     for (i = n + 1; i < hl->nranges + 1; i++) {
1144         hostrange_t last = hl->hr[i];
1145         hl->hr[i] = tmp;
1146         tmp = last;
1147     }
1148     hl->nranges++;
1149
1150     /* adjust hostlist iterators if needed */
1151     for (hli = hl->ilist; hli; hli = hli->next) {
1152         if (hli->idx >= n)
1153             hli->hr = hli->hl->hr[++hli->idx];
1154     }
1155
1156     return 1;
1157 }
1158
1159 /* Delete the range at position n in the range array
1160  * Assumes the hostlist lock is already held.
1161  */
1162 static void hostlist_delete_range(hostlist_t hl, int n)
1163 {
1164     int i;
1165     hostrange_t old;
1166
1167     assert(hl != NULL);
1168     assert(hl->magic == HOSTLIST_MAGIC);
1169     assert(n < hl->nranges && n >= 0);
1170
1171     old = hl->hr[n];
1172     for (i = n; i < hl->nranges - 1; i++)
1173         hl->hr[i] = hl->hr[i + 1];
1174     hl->nranges--;
1175     hl->hr[hl->nranges] = NULL;
1176     hostlist_shift_iterators(hl, n, 0, 1);
1177
1178     /* XXX caller responsible for adjusting nhosts */
1179     /* hl->nhosts -= hostrange_count(old) */
1180
1181     hostrange_destroy(old);
1182 }
1183
1184 #if WANT_RECKLESS_HOSTRANGE_EXPANSION
1185
1186 /* The reckless hostrange expansion function.
1187  * See comment in hostlist.h:hostlist_create() for more info on
1188  * the different choices for hostlist notation.
1189  */
1190 hostlist_t _hostlist_create(const char *hostlist, char *sep, char *r_op)
1191 {
1192     char *str, *orig;
1193     char *tok, *cur;
1194     int high, low, fmt = 0;
1195     char prefix[256] = "";
1196     int pos = 0;
1197     int error = 0;
1198     char range_op = r_op[0];/* XXX support > 1 char range ops in future? */
1199
1200     hostlist_t new = hostlist_new();
1201
1202     orig = str = strdup(hostlist);
1203
1204     /* return an empty list if an empty string was passed in */
1205     if (str == NULL || strlen(str) == 0)
1206         goto done;
1207
1208     /* Use hostlist_create_bracketed if we see "[" */
1209     if (strchr(str, '[') != NULL)
1210         return _hostlist_create_bracketed(hostlist, sep, r_op);
1211
1212     while ((tok = _next_tok(sep, &str)) != NULL) {
1213
1214         /* save the current string for error messages */
1215         cur = tok;
1216
1217         high = low = 0;
1218
1219         /* find end of alpha part
1220          *   do this by finding last occurence of range_op in str */
1221         pos = strlen(tok) - 1;
1222         if (strstr(tok, r_op) != '\0') {
1223             while (pos >= 0 && (char) tok[pos] != range_op)
1224                 pos--;
1225         }
1226
1227         /* now back up past any digits */
1228         while (pos >= 0 && isdigit((char) tok[--pos])) {;}
1229
1230         /* Check for valid x-y range (x must be a digit)
1231          *   Reset pos if the range is not valid         */
1232         if (!isdigit((char) tok[++pos]))
1233             pos = strlen(tok) - 1;
1234
1235         /* create prefix string
1236          * if prefix will be zero length, but prefix already exists
1237          * use the previous prefix and fmt
1238          */
1239         if ((pos > 0) || (prefix[0] == '\0')) {
1240             memcpy(prefix, tok, (size_t) pos * sizeof(char));
1241             prefix[pos] = '\0';
1242
1243             /* push pointer past prefix */
1244             tok += pos;
1245
1246             /* count number of digits for ouput fmt */
1247             for (fmt = 0; isdigit(tok[fmt]); ++fmt) {;}
1248
1249             if (fmt == 0)
1250                 error = 1;
1251
1252         } else
1253             tok += pos;
1254
1255         /* get lower bound */
1256         low = strtoul(tok, (char **) &tok, 10);
1257
1258         if (*tok == range_op) {    /* now get range upper bound */
1259             /* push pointer past range op */
1260             ++tok;
1261
1262             /* find length of alpha part */
1263             for (pos = 0; tok[pos] && !isdigit(tok[pos]); ++pos) {;}
1264
1265             /* alpha part must match prefix or error
1266              * this could mean we've got something like "rtr1-a2"
1267              * so just record an error
1268              */
1269             if (pos > 0) {
1270                 if (pos != strlen(prefix) ||
1271                     strncmp(prefix, tok, pos) != 0)
1272                     error = 1;
1273             }
1274
1275             if (*tok != '\0')
1276                 tok += pos;
1277
1278             /* make sure we have digits to the end */
1279             for (pos = 0; tok[pos] && isdigit((char) tok[pos]); ++pos) {;}
1280
1281             if (pos > 0) {    /* we have digits to process */
1282                 high = strtoul(tok, (char **) &tok, 10);
1283             } else {    /* bad boy, no digits */
1284                 error = 1;
1285             }
1286
1287             if ((low > high) || (high - low > MAX_RANGE))
1288                 error = 1;
1289
1290         } else {    /* single value */
1291             high = 0;    /* special case, ugh. */
1292         }
1293
1294         /* error if:
1295          * 1. we are not at end of string
1296          * 2. upper bound equals lower bound
1297          */
1298         if (*tok != '\0' || high == low)
1299             error = 1;
1300
1301         if (error) {    /* assume this is not a range on any error */
1302             hostlist_push_host(new, cur);
1303         } else {
1304             if (high < low)
1305                 high = low;
1306             hostlist_push_hr(new, prefix, low, high, fmt);
1307         }
1308
1309         error = 0;
1310     }
1311
1312   done:
1313     free(orig);
1314
1315     return new;
1316 }
1317
1318 #else                /* !WANT_RECKLESS_HOSTRANGE_EXPANSION */
1319
1320 hostlist_t _hostlist_create(const char *hostlist, char *sep, char *r_op)
1321 {
1322     return _hostlist_create_bracketed(hostlist, sep, r_op);
1323 }
1324
1325 #endif                /* WANT_RECKLESS_HOSTRANGE_EXPANSION */
1326
1327 struct _range {
1328     unsigned long lo, hi;
1329     int width;
1330 };
1331
1332 /* Grab a single range from str
1333  * returns 1 if str contained a valid number or range,
1334  *         0 if conversion of str to a range failed.
1335  */
1336 static int _parse_single_range(const char *str, struct _range *range)
1337 {
1338     char *p, *q;
1339     char *orig = strdup(str);
1340     if (!orig)
1341         seterrno_ret(ENOMEM, 0);
1342
1343     if ((p = strchr(str, '-'))) {
1344         *p++ = '\0';
1345         if (*p == '-')     /* do NOT allow negative numbers */
1346             goto error;
1347     }
1348     range->lo = strtoul(str, &q, 10);
1349     if (q == str)
1350         goto error;
1351
1352     range->hi = (p && *p) ? strtoul(p, &q, 10) : range->lo;
1353
1354     if (q == p || *q != '\0')
1355         goto error;
1356
1357     if (range->lo > range->hi)
1358         goto error;
1359
1360     if (range->hi - range->lo + 1 > MAX_RANGE ) {
1361         _error(__FILE__, __LINE__, "Too many hosts in range `%s'", orig);
1362         free(orig);
1363         seterrno_ret(ERANGE, 0);
1364     }
1365
1366     free(orig);
1367     range->width = strlen(str);
1368     return 1;
1369
1370   error:
1371     _error(__FILE__, __LINE__, "Invalid range: `%s'", orig);
1372     free(orig);
1373     seterrno_ret(EINVAL, 0);
1374 }
1375
1376
1377 /*
1378  * Convert 'str' containing comma separated digits and ranges into an array
1379  *  of struct _range types (max 'len' elements).
1380  *
1381  * Return number of ranges created, or -1 on error.
1382  */
1383 static int _parse_range_list(char *str, struct _range *ranges, int len)
1384 {
1385     char *p;
1386     int count = 0;
1387
1388     while (str) {
1389         if (count == len)
1390             return -1;
1391         if ((p = strchr(str, ',')))
1392             *p++ = '\0';
1393         if (!_parse_single_range(str, &ranges[count++]))
1394             return -1;
1395         str = p;
1396     }
1397     return count;
1398 }
1399
1400 static void
1401 _push_range_list(hostlist_t hl, char *pfx, struct _range *rng,
1402              int n)
1403 {
1404     int i;
1405     for (i = 0; i < n; i++) {
1406         hostlist_push_hr(hl, pfx, rng->lo, rng->hi, rng->width);
1407         rng++;
1408     }
1409 }
1410
1411 static void
1412 _push_range_list_with_suffix(hostlist_t hl, char *pfx, char *sfx,
1413                              struct _range *rng, int n)
1414 {
1415     int i;
1416     unsigned long j;
1417     for (i = 0; i < n; i++) {
1418         for (j = rng->lo; j <= rng->hi; j++) {
1419             char host[4096];
1420             hostrange_t hr;
1421             snprintf (host, 4096, "%s%0*lu%s", pfx, rng->width, j, sfx);
1422             hr = hostrange_create_single (host);
1423             hostlist_push_range (hl, hr);
1424             /*
1425              * hr is copied in hostlist_push_range. Need to free here.
1426              */
1427             hostrange_destroy (hr);
1428         }
1429         rng++;
1430     }
1431 }
1432
1433 /*
1434  * Create a hostlist from a string with brackets '[' ']' to aid
1435  * detection of ranges and compressed lists
1436  */
1437 static hostlist_t
1438 _hostlist_create_bracketed(const char *hostlist, char *sep, char *r_op)
1439 {
1440     hostlist_t new = hostlist_new();
1441     struct _range ranges[MAX_RANGES];
1442     int nr, err;
1443     char *p, *tok, *str, *orig;
1444     char cur_tok[1024];
1445
1446     if (hostlist == NULL)
1447         return new;
1448
1449     if (!(orig = str = strdup(hostlist))) {
1450         hostlist_destroy(new);
1451         return NULL;
1452     }
1453
1454     while ((tok = _next_tok(sep, &str)) != NULL) {
1455         strncpy(cur_tok, tok, 1024);
1456
1457         if ((p = strchr(tok, '[')) != NULL) {
1458             char *q, *prefix = tok;
1459             *p++ = '\0';
1460
1461             if ((q = strchr(p, ']'))) {
1462                 *q = '\0';
1463                 nr = _parse_range_list(p, ranges, MAX_RANGES);
1464                 if (nr < 0)
1465                     goto error;
1466
1467                 if (*(++q) != '\0')
1468                     _push_range_list_with_suffix (new, prefix, q, ranges, nr);
1469                 else
1470                     _push_range_list(new, prefix, ranges, nr);
1471
1472
1473             } else
1474                 hostlist_push_host(new, cur_tok);
1475
1476         } else
1477             hostlist_push_host(new, cur_tok);
1478     }
1479
1480     free(orig);
1481     return new;
1482
1483   error:
1484     err = errno;
1485     hostlist_destroy(new);
1486     free(orig);
1487     seterrno_ret(err, NULL);
1488 }
1489
1490
1491
1492 hostlist_t hostlist_create(const char *str)
1493 {
1494     return _hostlist_create(str, "\t, ", "-");
1495 }
1496
1497
1498 hostlist_t hostlist_copy(const hostlist_t hl)
1499 {
1500     int i;
1501     hostlist_t new;
1502
1503     if (hl == NULL)
1504         return NULL;
1505
1506     LOCK_HOSTLIST(hl);
1507     if (!(new = hostlist_new()))
1508         goto done;
1509
1510     new->nranges = hl->nranges;
1511     new->nhosts = hl->nhosts;
1512     if (new->nranges > new->size)
1513         hostlist_resize(new, new->nranges);
1514
1515     for (i = 0; i < hl->nranges; i++)
1516         new->hr[i] = hostrange_copy(hl->hr[i]);
1517
1518   done:
1519     UNLOCK_HOSTLIST(hl);
1520     return new;
1521 }
1522
1523
1524 void hostlist_destroy(hostlist_t hl)
1525 {
1526     int i;
1527     if (hl == NULL)
1528         return;
1529     LOCK_HOSTLIST(hl);
1530     while (hl->ilist) {
1531         mutex_unlock(&hl->mutex);
1532         hostlist_iterator_destroy(hl->ilist);
1533         mutex_lock(&hl->mutex);
1534     }
1535     for (i = 0; i < hl->nranges; i++)
1536         hostrange_destroy(hl->hr[i]);
1537     free(hl->hr);
1538     assert(hl->magic = 0x1);
1539     UNLOCK_HOSTLIST(hl);
1540     mutex_destroy(&hl->mutex);
1541     free(hl);
1542 }
1543
1544
1545 int hostlist_push(hostlist_t hl, const char *hosts)
1546 {
1547     hostlist_t new;
1548     int retval;
1549     if (hosts == NULL)
1550         return 0;
1551     new = hostlist_create(hosts);
1552     if (!new)
1553         return 0;
1554     mutex_lock(&new->mutex);
1555     retval = new->nhosts;
1556     mutex_unlock(&new->mutex);
1557     hostlist_push_list(hl, new);
1558     hostlist_destroy(new);
1559     return retval;
1560 }
1561
1562 int hostlist_push_host(hostlist_t hl, const char *str)
1563 {
1564     hostrange_t hr;
1565     hostname_t hn;
1566
1567     if (str == NULL)
1568         return 0;
1569
1570     hn = hostname_create(str);
1571
1572     if (hostname_suffix_is_valid(hn)) {
1573         hr = hostrange_create(hn->prefix, hn->num, hn->num,
1574                       hostname_suffix_width(hn));
1575     } else
1576         hr = hostrange_create_single(str);
1577
1578     hostlist_push_range(hl, hr);
1579
1580     hostrange_destroy(hr);
1581     hostname_destroy(hn);
1582
1583     return 1;
1584 }
1585
1586 int hostlist_push_list(hostlist_t h1, hostlist_t h2)
1587 {
1588     int i, n = 0;
1589
1590     if (h2 == NULL)
1591         return 0;
1592
1593     LOCK_HOSTLIST(h2);
1594
1595     for (i = 0; i < h2->nranges; i++)
1596         n += hostlist_push_range(h1, h2->hr[i]);
1597
1598     UNLOCK_HOSTLIST(h2);
1599
1600     return n;
1601 }
1602
1603
1604 char *hostlist_pop(hostlist_t hl)
1605 {
1606     char *host = NULL;
1607
1608     LOCK_HOSTLIST(hl);
1609     if (hl->nhosts > 0) {
1610         hostrange_t hr = hl->hr[hl->nranges - 1];
1611         host = hostrange_pop(hr);
1612         hl->nhosts--;
1613         if (hostrange_empty(hr)) {
1614             hostrange_destroy(hl->hr[--hl->nranges]);
1615             hl->hr[hl->nranges] = NULL;
1616         }
1617     }
1618     UNLOCK_HOSTLIST(hl);
1619     return host;
1620 }
1621
1622 /* find all iterators affected by a shift (or deletion) at
1623  * hl->hr[idx], depth, with the deletion of n ranges */
1624 static void
1625 hostlist_shift_iterators(hostlist_t hl, int idx, int depth, int n)
1626 {
1627     hostlist_iterator_t i;
1628     for (i = hl->ilist; i; i = i->next) {
1629         if (n == 0) {
1630             if (i->idx == idx && i->depth >= depth)
1631                 i->depth = i->depth > -1 ? i->depth - 1 : -1;
1632         } else {
1633             if (i->idx >= idx) {
1634                 if ((i->idx -= n) >= 0)
1635                     i->hr = i->hl->hr[i->idx];
1636                 else
1637                     hostlist_iterator_reset(i);
1638             }
1639         }
1640     }
1641 }
1642
1643 char *hostlist_shift(hostlist_t hl)
1644 {
1645     char *host = NULL;
1646
1647     LOCK_HOSTLIST(hl);
1648
1649     if (hl->nhosts > 0) {
1650         hostrange_t hr = hl->hr[0];
1651
1652         host = hostrange_shift(hr);
1653         hl->nhosts--;
1654
1655         if (hostrange_empty(hr)) {
1656             hostlist_delete_range(hl, 0);
1657             /* hl->nranges--; */
1658         } else
1659             hostlist_shift_iterators(hl, 0, 0, 0);
1660     }
1661
1662     UNLOCK_HOSTLIST(hl);
1663
1664     return host;
1665 }
1666
1667
1668 char *hostlist_pop_range(hostlist_t hl)
1669 {
1670     int i;
1671     char buf[MAXHOSTRANGELEN + 1];
1672     hostlist_t hltmp;
1673     hostrange_t tail;
1674
1675     LOCK_HOSTLIST(hl);
1676     if (hl->nranges < 1 || !(hltmp = hostlist_new())) {
1677         UNLOCK_HOSTLIST(hl);
1678         return NULL;
1679     }
1680
1681     i = hl->nranges - 2;
1682     tail = hl->hr[hl->nranges - 1];
1683     while (i >= 0 && hostrange_within_range(tail, hl->hr[i]))
1684         i--;
1685
1686     for (i++; i < hl->nranges; i++) {
1687         hostlist_push_range(hltmp, hl->hr[i]);
1688         hostrange_destroy(hl->hr[i]);
1689         hl->hr[i] = NULL;
1690     }
1691     hl->nhosts -= hltmp->nhosts;
1692     hl->nranges -= hltmp->nranges;
1693
1694     UNLOCK_HOSTLIST(hl);
1695     hostlist_ranged_string(hltmp, MAXHOSTRANGELEN, buf);
1696     hostlist_destroy(hltmp);
1697     return strdup(buf);
1698 }
1699
1700
1701 char *hostlist_shift_range(hostlist_t hl)
1702 {
1703     int i;
1704     char buf[1024];
1705     hostlist_t hltmp = hostlist_new();
1706     if (!hltmp)
1707         return NULL;
1708
1709     LOCK_HOSTLIST(hl);
1710
1711     if (hl->nranges == 0) {
1712         hostlist_destroy(hltmp);
1713         UNLOCK_HOSTLIST(hl);
1714         return NULL;
1715     }
1716
1717     i = 0;
1718     do {
1719         hostlist_push_range(hltmp, hl->hr[i]);
1720         hostrange_destroy(hl->hr[i]);
1721     } while ( (++i < hl->nranges)
1722             && hostrange_within_range(hltmp->hr[0], hl->hr[i]) );
1723
1724     hostlist_shift_iterators(hl, i, 0, hltmp->nranges);
1725
1726     /* shift rest of ranges back in hl */
1727     for (; i < hl->nranges; i++) {
1728         hl->hr[i - hltmp->nranges] = hl->hr[i];
1729         hl->hr[i] = NULL;
1730     }
1731     hl->nhosts -= hltmp->nhosts;
1732     hl->nranges -= hltmp->nranges;
1733
1734     UNLOCK_HOSTLIST(hl);
1735
1736     hostlist_ranged_string(hltmp, 1024, buf);
1737     hostlist_destroy(hltmp);
1738
1739     return strdup(buf);
1740 }
1741
1742 /* XXX: Note: efficiency improvements needed */
1743 int hostlist_delete(hostlist_t hl, const char *hosts)
1744 {
1745     int n = 0;
1746     char *hostname = NULL;
1747     hostlist_t hltmp;
1748
1749     if (!(hltmp = hostlist_create(hosts)))
1750         seterrno_ret(EINVAL, 0);
1751
1752     while ((hostname = hostlist_pop(hltmp)) != NULL) {
1753         n += hostlist_delete_host(hl, hostname);
1754         free(hostname);
1755     }
1756     hostlist_destroy(hltmp);
1757
1758     return n;
1759 }
1760
1761
1762 /* XXX watch out! poor implementation follows! (fix it at some point) */
1763 int hostlist_delete_host(hostlist_t hl, const char *hostname)
1764 {
1765     int n = hostlist_find(hl, hostname);
1766     if (n >= 0)
1767         hostlist_delete_nth(hl, n);
1768     return n >= 0 ? 1 : 0;
1769 }
1770
1771
1772 static char *
1773 _hostrange_string(hostrange_t hr, int depth)
1774 {
1775     char buf[MAXHOSTNAMELEN + 16];
1776     int  len = snprintf(buf, MAXHOSTNAMELEN + 15, "%s", hr->prefix);
1777
1778     if (!hr->singlehost)
1779         snprintf(buf+len, MAXHOSTNAMELEN+15 - len, "%0*lu",
1780                  hr->width, hr->lo + depth);
1781     return strdup(buf);
1782 }
1783
1784 char * hostlist_nth(hostlist_t hl, int n)
1785 {
1786     char *host = NULL;
1787     int   i, count;
1788
1789     LOCK_HOSTLIST(hl);
1790     count = 0;
1791     for (i = 0; i < hl->nranges; i++) {
1792         int num_in_range = hostrange_count(hl->hr[i]);
1793
1794         if (n <= (num_in_range - 1 + count)) {
1795             host = _hostrange_string(hl->hr[i], n - count);
1796             break;
1797         } else
1798             count += num_in_range;
1799     }
1800
1801     UNLOCK_HOSTLIST(hl);
1802
1803     return host;
1804 }
1805
1806
1807 int hostlist_delete_nth(hostlist_t hl, int n)
1808 {
1809     int i, count;
1810
1811     LOCK_HOSTLIST(hl);
1812     assert(n >= 0 && n <= hl->nhosts);
1813
1814     count = 0;
1815
1816     for (i = 0; i < hl->nranges; i++) {
1817         int num_in_range = hostrange_count(hl->hr[i]);
1818         hostrange_t hr = hl->hr[i];
1819
1820         if (n <= (num_in_range - 1 + count)) {
1821             unsigned long num = hr->lo + n - count;
1822             hostrange_t new;
1823
1824             if (hr->singlehost) { /* this wasn't a range */
1825                 hostlist_delete_range(hl, i);
1826             } else if ((new = hostrange_delete_host(hr, num))) {
1827                 hostlist_insert_range(hl, new, i + 1);
1828                 hostrange_destroy(new);
1829             } else if (hostrange_empty(hr))
1830                 hostlist_delete_range(hl, i);
1831
1832             goto done;
1833         } else
1834             count += num_in_range;
1835
1836     }
1837
1838   done:
1839     UNLOCK_HOSTLIST(hl);
1840     hl->nhosts--;
1841     return 1;
1842 }
1843
1844 int hostlist_count(hostlist_t hl)
1845 {
1846     int retval;
1847     LOCK_HOSTLIST(hl);
1848     retval = hl->nhosts;
1849     UNLOCK_HOSTLIST(hl);
1850     return retval;
1851 }
1852
1853 int hostlist_find(hostlist_t hl, const char *hostname)
1854 {
1855     int i, count, ret = -1;
1856     hostname_t hn;
1857
1858     if (!hostname)
1859         return -1;
1860
1861     hn = hostname_create(hostname);
1862
1863     LOCK_HOSTLIST(hl);
1864
1865     for (i = 0, count = 0; i < hl->nranges; i++) {
1866         if (hostrange_hn_within(hl->hr[i], hn)) {
1867             if (hostname_suffix_is_valid(hn) && !hl->hr[i]->singlehost)
1868                 ret = count + hn->num - hl->hr[i]->lo;
1869             else
1870                 ret = count;
1871             goto done;
1872         } else
1873             count += hostrange_count(hl->hr[i]);
1874     }
1875
1876   done:
1877     UNLOCK_HOSTLIST(hl);
1878     hostname_destroy(hn);
1879     return ret;
1880 }
1881
1882 /* hostrange compare with void * arguments to allow use with
1883  * libc qsort()
1884  */
1885 int _cmp(const void *hr1, const void *hr2)
1886 {
1887     hostrange_t *h1 = (hostrange_t *) hr1;
1888     hostrange_t *h2 = (hostrange_t *) hr2;
1889     return hostrange_cmp((hostrange_t) * h1, (hostrange_t) * h2);
1890 }
1891
1892
1893 void hostlist_sort(hostlist_t hl)
1894 {
1895     hostlist_iterator_t i;
1896     LOCK_HOSTLIST(hl);
1897
1898     if (hl->nranges <= 1) {
1899         UNLOCK_HOSTLIST(hl);
1900         return;
1901     }
1902
1903     qsort(hl->hr, hl->nranges, sizeof(hostrange_t), &_cmp);
1904
1905     /* reset all iterators */
1906     for (i = hl->ilist; i; i = i->next)
1907         hostlist_iterator_reset(i);
1908
1909     UNLOCK_HOSTLIST(hl);
1910
1911     hostlist_coalesce(hl);
1912
1913 }
1914
1915
1916 /* search through hostlist for ranges that can be collapsed
1917  * does =not= delete any hosts
1918  */
1919 static void hostlist_collapse(hostlist_t hl)
1920 {
1921     int i;
1922
1923     LOCK_HOSTLIST(hl);
1924     for (i = hl->nranges - 1; i > 0; i--) {
1925         hostrange_t hprev = hl->hr[i - 1];
1926         hostrange_t hnext = hl->hr[i];
1927
1928         if (hostrange_prefix_cmp(hprev, hnext) == 0 &&
1929             hprev->hi == hnext->lo - 1 &&
1930             hostrange_width_combine(hprev, hnext)) {
1931             hprev->hi = hnext->hi;
1932             hostlist_delete_range(hl, i);
1933         }
1934     }
1935     UNLOCK_HOSTLIST(hl);
1936 }
1937
1938 /* search through hostlist (hl) for intersecting ranges
1939  * split up duplicates and coalesce ranges where possible
1940  */
1941 static void hostlist_coalesce(hostlist_t hl)
1942 {
1943     int i, j;
1944     hostrange_t new;
1945
1946     LOCK_HOSTLIST(hl);
1947
1948     for (i = hl->nranges - 1; i > 0; i--) {
1949
1950         new = hostrange_intersect(hl->hr[i - 1], hl->hr[i]);
1951
1952         if (new) {
1953             hostrange_t hprev = hl->hr[i - 1];
1954             hostrange_t hnext = hl->hr[i];
1955             j = i;
1956
1957             if (new->hi < hprev->hi)
1958                 hnext->hi = hprev->hi;
1959
1960             hprev->hi = new->lo;
1961             hnext->lo = new->hi;
1962
1963             if (hostrange_empty(hprev))
1964                 hostlist_delete_range(hl, i);
1965
1966             while (new->lo <= new->hi) {
1967                 hostrange_t hr = hostrange_create( new->prefix,
1968                                                    new->lo, new->lo,
1969                                                    new->width );
1970
1971                 if (new->lo > hprev->hi)
1972                     hostlist_insert_range(hl, hr, j++);
1973
1974                 if (new->lo < hnext->lo)
1975                     hostlist_insert_range(hl, hr, j++);
1976
1977                 hostrange_destroy(hr);
1978
1979                 new->lo++;
1980             }
1981             i = hl->nranges;
1982             hostrange_destroy(new);
1983         }
1984     }
1985     UNLOCK_HOSTLIST(hl);
1986
1987     hostlist_collapse(hl);
1988
1989 }
1990
1991 /* attempt to join ranges at loc and loc-1 in a hostlist  */
1992 /* delete duplicates, return the number of hosts deleted  */
1993 /* assumes that the hostlist hl has been locked by caller */
1994 /* returns -1 if no range join occurred */
1995 static int _attempt_range_join(hostlist_t hl, int loc)
1996 {
1997     int ndup;
1998     assert(hl != NULL);
1999     assert(hl->magic == HOSTLIST_MAGIC);
2000     assert(loc > 0);
2001     assert(loc < hl->nranges);
2002     ndup = hostrange_join(hl->hr[loc - 1], hl->hr[loc]);
2003     if (ndup >= 0) {
2004         hostlist_delete_range(hl, loc);
2005         hl->nhosts -= ndup;
2006     }
2007     return ndup;
2008 }
2009
2010 void hostlist_uniq(hostlist_t hl)
2011 {
2012     int i = 1;
2013     hostlist_iterator_t hli;
2014     LOCK_HOSTLIST(hl);
2015     if (hl->nranges <= 1) {
2016         UNLOCK_HOSTLIST(hl);
2017         return;
2018     }
2019     qsort(hl->hr, hl->nranges, sizeof(hostrange_t), &_cmp);
2020
2021     while (i < hl->nranges) {
2022         if (_attempt_range_join(hl, i) < 0) /* No range join occurred */
2023             i++;
2024     }
2025
2026     /* reset all iterators */
2027     for (hli = hl->ilist; hli; hli = hli->next)
2028         hostlist_iterator_reset(hli);
2029
2030     UNLOCK_HOSTLIST(hl);
2031 }
2032
2033
2034 size_t hostlist_deranged_string(hostlist_t hl, size_t n, char *buf)
2035 {
2036     int i;
2037     int len = 0;
2038     int truncated = 0;
2039
2040     LOCK_HOSTLIST(hl);
2041     for (i = 0; i < hl->nranges; i++) {
2042         size_t m = (n - len) <= n ? n - len : 0;
2043         int ret = hostrange_to_string(hl->hr[i], m, buf + len, ",");
2044         if (ret < 0 || ret > m) {
2045             len = n;
2046             truncated = 1;
2047             break;
2048         }
2049         len+=ret;
2050         buf[len++] = ',';
2051     }
2052     UNLOCK_HOSTLIST(hl);
2053
2054     buf[len > 0 ? --len : 0] = '\0';
2055     if (len == n)
2056         truncated = 1;
2057
2058     return truncated ? -1 : len;
2059 }
2060
2061 /* return true if a bracket is needed for the range at i in hostlist hl */
2062 static int _is_bracket_needed(hostlist_t hl, int i)
2063 {
2064     hostrange_t h1 = hl->hr[i];
2065     hostrange_t h2 = i < hl->nranges - 1 ? hl->hr[i + 1] : NULL;
2066     return hostrange_count(h1) > 1 || hostrange_within_range(h1, h2);
2067 }
2068
2069 /* write the next bracketed hostlist, i.e. prefix[n-m,k,...]
2070  * into buf, writing at most n chars including the terminating '\0'
2071  *
2072  * leaves start pointing to one past last range object in bracketed list,
2073  * and returns the number of bytes written into buf.
2074  *
2075  * Assumes hostlist is locked.
2076  */
2077 static int
2078 _get_bracketed_list(hostlist_t hl, int *start, const size_t n, char *buf)
2079 {
2080     hostrange_t *hr = hl->hr;
2081     int i = *start;
2082     int m, len = 0;
2083     int bracket_needed = _is_bracket_needed(hl, i);
2084
2085     len = snprintf(buf, n, "%s", hr[i]->prefix);
2086
2087     if ((len < 0) || (len > n))
2088         return n; /* truncated, buffer filled */
2089
2090     if (bracket_needed && len < n && len >= 0)
2091         buf[len++] = '[';
2092
2093     do {
2094         m = (n - len) <= n ? n - len : 0;
2095         len += hostrange_numstr(hr[i], m, buf + len);
2096         if (len >= n)
2097             break;
2098         if (bracket_needed) /* Only need commas inside brackets */
2099             buf[len++] = ',';
2100     } while (++i < hl->nranges && hostrange_within_range(hr[i], hr[i-1]));
2101
2102     if (bracket_needed && len < n && len > 0) {
2103
2104         /* Add trailing bracket (change trailing "," from above to "]" */
2105         buf[len - 1] = ']';
2106
2107         /* NUL terminate for safety, but do not add terminator to len */
2108         buf[len]   = '\0';
2109
2110     } else if (len >= n) {
2111         if (n > 0)
2112             buf[n-1] = '\0';
2113
2114     } else {
2115         /* If len is > 0, NUL terminate (but do not add to len) */
2116         buf[len > 0 ? len : 0] = '\0';
2117     }
2118
2119     *start = i;
2120     return len;
2121 }
2122
2123 size_t hostlist_ranged_string(hostlist_t hl, size_t n, char *buf)
2124 {
2125     int i = 0;
2126     int len = 0;
2127     int truncated = 0;
2128
2129     LOCK_HOSTLIST(hl);
2130     while (i < hl->nranges && len < n) {
2131         len += _get_bracketed_list(hl, &i, n - len, buf + len);
2132         if ((len > 0) && (len < n) && (i < hl->nranges))
2133             buf[len++] = ',';
2134     }
2135     UNLOCK_HOSTLIST(hl);
2136
2137     /* NUL terminate */
2138     if (len >= n) {
2139         truncated = 1;
2140         if (n > 0)
2141             buf[n-1] = '\0';
2142     } else
2143         buf[len > 0 ? len : 0] = '\0';
2144
2145     return truncated ? -1 : len;
2146 }
2147
2148 /* ----[ hostlist iterator functions ]---- */
2149
2150 static hostlist_iterator_t hostlist_iterator_new(void)
2151 {
2152     hostlist_iterator_t i = (hostlist_iterator_t) malloc(sizeof(*i));
2153     if (!i)
2154         return NULL;
2155     i->hl = NULL;
2156     i->hr = NULL;
2157     i->idx = 0;
2158     i->depth = -1;
2159     i->next = i;
2160     assert(i->magic = HOSTLIST_MAGIC);
2161     return i;
2162 }
2163
2164 hostlist_iterator_t hostlist_iterator_create(hostlist_t hl)
2165 {
2166     hostlist_iterator_t i;
2167
2168     if (!(i = hostlist_iterator_new()))
2169         out_of_memory("hostlist_iterator_create");
2170
2171     LOCK_HOSTLIST(hl);
2172     i->hl = hl;
2173     i->hr = hl->hr[0];
2174     i->next = hl->ilist;
2175     hl->ilist = i;
2176     UNLOCK_HOSTLIST(hl);
2177     return i;
2178 }
2179
2180 hostlist_iterator_t hostset_iterator_create(hostset_t set)
2181 {
2182     return hostlist_iterator_create(set->hl);
2183 }
2184
2185 void hostlist_iterator_reset(hostlist_iterator_t i)
2186 {
2187     assert(i != NULL);
2188     assert(i->magic == HOSTLIST_MAGIC);
2189     i->idx = 0;
2190     i->hr = i->hl->hr[0];
2191     i->depth = -1;
2192     return;
2193 }
2194
2195 void hostlist_iterator_destroy(hostlist_iterator_t i)
2196 {
2197     hostlist_iterator_t *pi;
2198     if (i == NULL)
2199         return;
2200     assert(i != NULL);
2201     assert(i->magic == HOSTLIST_MAGIC);
2202     LOCK_HOSTLIST(i->hl);
2203     for (pi = &i->hl->ilist; *pi; pi = &(*pi)->next) {
2204         assert((*pi)->magic == HOSTLIST_MAGIC);
2205         if (*pi == i) {
2206             *pi = (*pi)->next;
2207             break;
2208         }
2209     }
2210     UNLOCK_HOSTLIST(i->hl);
2211     assert(i->magic = 0x1);
2212     free(i);
2213 }
2214
2215 static void _iterator_advance(hostlist_iterator_t i)
2216 {
2217     assert(i != NULL);
2218     assert(i->magic == HOSTLIST_MAGIC);
2219     if (i->idx > i->hl->nranges - 1)
2220         return;
2221     if (++(i->depth) > (i->hr->hi - i->hr->lo)) {
2222         i->depth = 0;
2223         i->hr = i->hl->hr[++i->idx];
2224     }
2225 }
2226
2227 /* advance iterator to end of current range (meaning within "[" "]")
2228  * i.e. advance iterator past all range objects that could be represented
2229  * in on bracketed hostlist.
2230  */
2231 static void _iterator_advance_range(hostlist_iterator_t i)
2232 {
2233     int nr, j;
2234     hostrange_t *hr;
2235     assert(i != NULL);
2236     assert(i->magic == HOSTLIST_MAGIC);
2237
2238     nr = i->hl->nranges;
2239     hr = i->hl->hr;
2240     j = i->idx;
2241     if (++i->depth > 0) {
2242         while (++j < nr && hostrange_within_range(i->hr, hr[j])) {;}
2243         i->idx = j;
2244         i->hr = i->hl->hr[i->idx];
2245         i->depth = 0;
2246     }
2247 }
2248
2249 char *hostlist_next(hostlist_iterator_t i)
2250 {
2251     char *buf = NULL;
2252     char suffix[16];
2253     int len = 0;
2254     assert(i != NULL);
2255     assert(i->magic == HOSTLIST_MAGIC);
2256     LOCK_HOSTLIST(i->hl);
2257     _iterator_advance(i);
2258
2259     if (i->idx > i->hl->nranges - 1) {
2260         UNLOCK_HOSTLIST(i->hl);
2261         return NULL;
2262     }
2263
2264     suffix[0] = '\0';
2265
2266     if (!i->hr->singlehost)
2267         snprintf (suffix, 15, "%0*lu", i->hr->width, i->hr->lo + i->depth);
2268
2269     len = strlen (i->hr->prefix) + strlen (suffix) + 1;
2270     if (!(buf = malloc (len)))
2271         out_of_memory("hostlist_next");
2272
2273     buf[0] = '\0';
2274     strcat (buf, i->hr->prefix);
2275     strcat (buf, suffix);
2276
2277     UNLOCK_HOSTLIST(i->hl);
2278     return (buf);
2279 }
2280
2281 char *hostlist_next_range(hostlist_iterator_t i)
2282 {
2283     char buf[MAXHOSTRANGELEN + 1];
2284     int j;
2285
2286     assert(i != NULL);
2287     assert(i->magic == HOSTLIST_MAGIC);
2288     LOCK_HOSTLIST(i->hl);
2289
2290     _iterator_advance_range(i);
2291
2292     if (i->idx > i->hl->nranges - 1) {
2293         UNLOCK_HOSTLIST(i->hl);
2294         return NULL;
2295     }
2296
2297     j = i->idx;
2298     _get_bracketed_list(i->hl, &j, MAXHOSTRANGELEN, buf);
2299
2300     UNLOCK_HOSTLIST(i->hl);
2301
2302     return strdup(buf);
2303 }
2304
2305 int hostlist_remove(hostlist_iterator_t i)
2306 {
2307     hostrange_t new;
2308     assert(i != NULL);
2309     assert(i->magic == HOSTLIST_MAGIC);
2310     LOCK_HOSTLIST(i->hl);
2311     new = hostrange_delete_host(i->hr, i->hr->lo + i->depth);
2312     if (new) {
2313         hostlist_insert_range(i->hl, new, i->idx + 1);
2314         hostrange_destroy(new);
2315         i->hr = i->hl->hr[++i->idx];
2316         i->depth = -1;
2317     } else if (hostrange_empty(i->hr)) {
2318         hostlist_delete_range(i->hl, i->idx);
2319     } else
2320         i->depth--;
2321
2322     i->hl->nhosts--;
2323     UNLOCK_HOSTLIST(i->hl);
2324
2325     return 1;
2326 }
2327
2328 /* ----[ hostset functions ]---- */
2329
2330 hostset_t hostset_create(const char *hostlist)
2331 {
2332     hostset_t new;
2333
2334     if (!(new = (hostset_t) malloc(sizeof(*new))))
2335         goto error1;
2336
2337     if (!(new->hl = hostlist_create(hostlist)))
2338         goto error2;
2339
2340     hostlist_uniq(new->hl);
2341     return new;
2342
2343   error2:
2344     free(new);
2345   error1:
2346     return NULL;
2347 }
2348
2349 hostset_t hostset_copy(const hostset_t set)
2350 {
2351     hostset_t new;
2352     if (!(new = (hostset_t) malloc(sizeof(*new))))
2353         goto error1;
2354
2355     if (!(new->hl = hostlist_copy(set->hl)))
2356         goto error2;
2357
2358     return new;
2359   error2:
2360     free(new);
2361   error1:
2362     return NULL;
2363 }
2364
2365 void hostset_destroy(hostset_t set)
2366 {
2367     if (set == NULL)
2368         return;
2369     hostlist_destroy(set->hl);
2370     free(set);
2371 }
2372
2373 /* inserts a single range object into a hostset
2374  * Assumes that the set->hl lock is already held
2375  * Updates hl->nhosts
2376  */
2377 static int hostset_insert_range(hostset_t set, hostrange_t hr)
2378 {
2379     int i = 0;
2380     int inserted = 0;
2381     int nhosts = 0;
2382     int ndups = 0;
2383     hostlist_t hl;
2384
2385     hl = set->hl;
2386
2387     if (hl->size == hl->nranges && !hostlist_expand(hl))
2388         return 0;
2389
2390     nhosts = hostrange_count(hr);
2391
2392     for (i = 0; i < hl->nranges; i++) {
2393         if (hostrange_cmp(hr, hl->hr[i]) <= 0) {
2394
2395             if ((ndups = hostrange_join(hr, hl->hr[i])) >= 0)
2396                 hostlist_delete_range(hl, i);
2397             else if (ndups < 0)
2398                 ndups = 0;
2399
2400             hostlist_insert_range(hl, hr, i);
2401
2402             /* now attempt to join hr[i] and hr[i-1] */
2403             if (i > 0) {
2404                 int m;
2405                 if ((m = _attempt_range_join(hl, i)) > 0)
2406                     ndups += m;
2407             }
2408             hl->nhosts += nhosts - ndups;
2409             inserted = 1;
2410             break;
2411         }
2412     }
2413
2414     if (inserted == 0) {
2415         hl->hr[hl->nranges++] = hostrange_copy(hr);
2416         hl->nhosts += nhosts;
2417         if (hl->nranges > 1) {
2418             if ((ndups = _attempt_range_join(hl, hl->nranges - 1)) <= 0)
2419                 ndups = 0;
2420         }
2421     }
2422
2423     /*
2424      *  Return the number of unique hosts inserted
2425      */
2426     return nhosts - ndups;
2427 }
2428
2429 int hostset_insert(hostset_t set, const char *hosts)
2430 {
2431     int i, n = 0;
2432     hostlist_t hl = hostlist_create(hosts);
2433     if (!hl)
2434         return 0;
2435
2436     hostlist_uniq(hl);
2437     LOCK_HOSTLIST(set->hl);
2438     for (i = 0; i < hl->nranges; i++)
2439         n += hostset_insert_range(set, hl->hr[i]);
2440     UNLOCK_HOSTLIST(set->hl);
2441     hostlist_destroy(hl);
2442     return n;
2443 }
2444
2445
2446 /* linear search through N ranges for hostname "host"
2447  * */
2448 static int hostset_find_host(hostset_t set, const char *host)
2449 {
2450     int i;
2451     int retval = 0;
2452     hostname_t hn;
2453     LOCK_HOSTLIST(set->hl);
2454     hn = hostname_create(host);
2455     for (i = 0; i < set->hl->nranges; i++) {
2456         if (hostrange_hn_within(set->hl->hr[i], hn)) {
2457             retval = 1;
2458             goto done;
2459         }
2460     }
2461   done:
2462     UNLOCK_HOSTLIST(set->hl);
2463     hostname_destroy(hn);
2464     return retval;
2465 }
2466
2467 int hostset_within(hostset_t set, const char *hosts)
2468 {
2469     int nhosts, nfound;
2470     hostlist_t hl;
2471     char *hostname;
2472
2473     assert(set->hl->magic == HOSTLIST_MAGIC);
2474
2475     hl = hostlist_create(hosts);
2476     nhosts = hostlist_count(hl);
2477     nfound = 0;
2478
2479     while ((hostname = hostlist_pop(hl)) != NULL) {
2480         nfound += hostset_find_host(set, hostname);
2481         free(hostname);
2482     }
2483
2484     hostlist_destroy(hl);
2485
2486     return (nhosts == nfound);
2487 }
2488
2489 int hostset_delete(hostset_t set, const char *hosts)
2490 {
2491     return hostlist_delete(set->hl, hosts);
2492 }
2493
2494 int hostset_delete_host(hostset_t set, const char *hostname)
2495 {
2496     return hostlist_delete_host(set->hl, hostname);
2497 }
2498
2499 char *hostset_shift(hostset_t set)
2500 {
2501     return hostlist_shift(set->hl);
2502 }
2503
2504 char *hostset_pop(hostset_t set)
2505 {
2506     return hostlist_pop(set->hl);
2507 }
2508
2509 char *hostset_shift_range(hostset_t set)
2510 {
2511     return hostlist_shift_range(set->hl);
2512 }
2513
2514 char *hostset_pop_range(hostset_t set)
2515 {
2516     return hostlist_pop_range(set->hl);
2517 }
2518
2519 int hostset_count(hostset_t set)
2520 {
2521     return hostlist_count(set->hl);
2522 }
2523
2524 size_t hostset_ranged_string(hostset_t set, size_t n, char *buf)
2525 {
2526     return hostlist_ranged_string(set->hl, n, buf);
2527 }
2528
2529 size_t hostset_deranged_string(hostset_t set, size_t n, char *buf)
2530 {
2531     return hostlist_deranged_string(set->hl, n, buf);
2532 }
2533
2534 #if TEST_MAIN
2535
2536 int hostlist_nranges(hostlist_t hl)
2537 {
2538     return hl->nranges;
2539 }
2540
2541 int hostset_nranges(hostset_t set)
2542 {
2543     return set->hl->nranges;
2544 }
2545
2546 /* test iterator functionality on the list of hosts represented
2547  * by list
2548  */
2549 int iterator_test(char *list)
2550 {
2551     int j;
2552     char buf[1024];
2553     hostlist_t hl = hostlist_create(list);
2554     hostset_t set = hostset_create(list);
2555
2556     hostlist_iterator_t i = hostlist_iterator_create(hl);
2557     hostlist_iterator_t seti = hostset_iterator_create(set);
2558     hostlist_iterator_t i2 = hostlist_iterator_create(hl);
2559     char *host;
2560
2561
2562     hostlist_ranged_string(hl, 1024, buf);
2563     printf("iterator_test: hl = `%s' passed in `%s'\n", buf, list);
2564     host = hostlist_next(i);
2565     printf("first host in list hl = `%s'\n", host);
2566     free(host);
2567
2568     /* forge ahead three hosts with i2 */
2569     for (j = 0; j < 4; j++) {
2570         host = hostlist_next(i2);
2571         free(host);
2572     }
2573
2574     host = hostlist_shift(hl);
2575     printf("result of shift(hl)   = `%s'\n", host);
2576     free(host);
2577     host = hostlist_next(i);
2578     printf("next host in list hl  = `%s'\n", host);
2579     free(host);
2580     host = hostlist_next(i2);
2581     printf("next host for i2      = `%s'\n", host);
2582     free(host);
2583
2584     hostlist_iterator_destroy(i);
2585
2586     hostlist_destroy(hl);
2587     hostset_destroy(set);
2588     return 1;
2589 }
2590
2591 int main(int ac, char **av)
2592 {
2593     char buf[1024000];
2594     int i;
2595     char *str;
2596
2597     hostlist_t hl1, hl2, hl3;
2598     hostset_t set, set1;
2599     hostlist_iterator_t iter, iter2;
2600
2601     if (!(hl1 = hostlist_create(ac > 1 ? av[1] : NULL)))
2602         perror("hostlist_create");
2603     if (!(set = hostset_create(ac > 1 ? av[1] : NULL)))
2604         perror("hostlist_create");
2605
2606     hl3 = hostlist_create("f[0-5]");
2607     hostlist_delete(hl3, "f[1-3]");
2608     hostlist_ranged_string(hl3, 102400, buf);
2609     printf("after delete = `%s'\n", buf);
2610     hostlist_destroy(hl3);
2611
2612     for (i = 2; i < ac; i++) {
2613         hostlist_push(hl1, av[i]);
2614         hostset_insert(set, av[i]);
2615     }
2616
2617     hostlist_ranged_string(hl1, 102400, buf);
2618     printf("ranged   = `%s'\n", buf);
2619
2620     iterator_test(buf);
2621
2622     hostlist_deranged_string(hl1, 10240, buf);
2623     printf("deranged = `%s'\n", buf);
2624
2625     hostset_ranged_string(set, 1024, buf);
2626     printf("hostset  = `%s'\n", buf);
2627
2628     hostlist_sort(hl1);
2629     hostlist_ranged_string(hl1, 1024, buf);
2630     printf("sorted   = `%s'\n", buf);
2631
2632     hostlist_uniq(hl1);
2633     hostlist_ranged_string(hl1, 1024, buf);
2634     printf("uniqed   = `%s'\n", buf);
2635
2636     hl2 = hostlist_copy(hl1);
2637     printf("pop_range: ");
2638     while ((str = hostlist_pop_range(hl2))) {
2639         printf("`%s' ", str);
2640         free(str);
2641     }
2642     hostlist_destroy(hl2);
2643     printf("\n");
2644
2645     hl2 = hostlist_copy(hl1);
2646     printf("shift_range: ");
2647     while ((str = hostlist_shift_range(hl2))) {
2648         printf("`%s' ", str);
2649         free(str);
2650     }
2651     hostlist_destroy(hl2);
2652     printf("\n");
2653
2654     iter = hostset_iterator_create(set);
2655     iter2 = hostset_iterator_create(set);
2656     hostlist_iterator_destroy(iter2);
2657
2658     printf("next: ");
2659     while ((str = hostlist_next(iter))) {
2660         printf("`%s' ", str);
2661         free(str);
2662     }
2663     printf("\n");
2664
2665     hostlist_iterator_reset(iter);
2666     printf("next_range: ");
2667     while ((str = hostlist_next_range(iter))) {
2668         printf("`%s' ", str);
2669         free(str);
2670     }
2671     printf("\n");
2672
2673     printf("nranges = %d\n", hostset_nranges(set));
2674
2675     hostset_ranged_string(set, 1024, buf);
2676     printf("set = %s\n", buf);
2677
2678     hostset_destroy(set);
2679     hostlist_destroy(hl1);
2680     return 0;
2681 }
2682
2683 #endif                /* TEST_MAIN */
2684
2685 /*
2686  * vi: tabstop=4 shiftwidth=4 expandtab
2687  */