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>
9 * This file is part of SLURM, a resource management program.
10 * For details, see <http://www.llnl.gov/linux/slurm/>.
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)
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
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 \*****************************************************************************/
35 #else /* !HAVE_CONFIG_H */
38 #endif /* HAVE_CONFIG_H */
46 #include <sys/param.h>
52 * lsd_fatal_error : fatal error macro
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) \
61 fprintf(stderr, "ERROR: [%s:%d] %s: %s\n", \
62 file, line, mesg, strerror(errno)); \
64 # endif /* !lsd_fatal_error */
65 #endif /* !WITH_LSD_FATAL_ERROR_FUNC */
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 */
81 * Automatically call lsd_nomem_error with appropriate args
82 * and set errno to ENOMEM
84 #define out_of_memory(mesg) \
87 return(lsd_nomem_error(__FILE__, __LINE__, mesg)); \
91 * Some constants and tunables:
94 /* number of elements to allocate when extending the hostlist array */
95 #define HOSTLIST_CHUNK 16
97 /* max host range: anything larger will be assumed to be an error */
98 #define MAX_RANGE 16384 /* 16K Hosts */
100 /* max host suffix value */
101 #define MAX_HOST_SUFFIX 1<<25
103 /* max number of ranges that will be processed between brackets */
104 #define MAX_RANGES 10240 /* 10K Ranges */
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
112 /* max size of internal hostrange buffer */
113 #define MAXHOSTRANGELEN 1024
115 /* ----[ Internal Data Structures ]---- */
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 */
123 /* string representation of numeric suffix
124 * points into `hostname' */
128 typedef struct hostname_components *hostname_t;
130 /* hostrange type: A single prefix with `hi' and `lo' numeric suffix values */
131 struct hostrange_components {
132 char *prefix; /* alphanumeric prefix: */
134 /* beginning (lo) and end (hi) of suffix range */
135 unsigned long lo, hi;
137 /* width of numeric output format
138 * (pad with zeros up to this width) */
141 /* If singlehost is 1, `lo' and `hi' are invalid */
142 unsigned singlehost:1;
145 typedef struct hostrange_components *hostrange_t;
147 /* The hostlist type: An array based list of hostrange_t's */
150 #define HOSTLIST_MAGIC 57005
154 pthread_mutex_t mutex;
155 #endif /* WITH_PTHREADS */
157 /* current number of elements available in array */
160 /* current number of ranges stored in array */
163 /* current number of hosts stored in hostlist */
166 /* pointer to hostrange array */
169 /* list of iterators */
170 struct hostlist_iterator *ilist;
175 /* a hostset is a wrapper around a hostlist */
180 struct hostlist_iterator {
184 /* hostlist we are traversing */
187 /* current index of iterator in hl->hr[] */
190 /* current hostrange object in list hl, i.e. hl->hr[idx] */
193 /* current depth we've traversed into range hr */
196 /* next ptr for lists of iterators */
197 struct hostlist_iterator *next;
203 /* ------[ static function prototypes ]------ */
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 *);
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);
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 *);
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,
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);
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);
256 static int hostset_find_host(hostset_t, const char *);
258 /* ------[ macros ]------ */
261 # define mutex_init(mutex) \
263 int e = pthread_mutex_init(mutex, NULL); \
266 lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex init:"); \
271 # define mutex_lock(mutex) \
273 int e = pthread_mutex_lock(mutex); \
276 lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex lock:"); \
281 # define mutex_unlock(mutex) \
283 int e = pthread_mutex_unlock(mutex); \
286 lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex unlock:"); \
291 # define mutex_destroy(mutex) \
293 int e = pthread_mutex_destroy(mutex); \
296 lsd_fatal_error(__FILE__, __LINE__, "hostlist mutex destroy:"); \
301 #else /* !WITH_PTHREADS */
303 # define mutex_init(mutex)
304 # define mutex_lock(mutex)
305 # define mutex_unlock(mutex)
306 # define mutex_destroy(mutex)
308 #endif /* WITH_PTHREADS */
310 #define LOCK_HOSTLIST(_hl) \
312 assert(_hl != NULL); \
313 mutex_lock(&(_hl)->mutex); \
314 assert((_hl)->magic == HOSTLIST_MAGIC); \
317 #define UNLOCK_HOSTLIST(_hl) \
319 mutex_unlock(&(_hl)->mutex); \
322 #define seterrno_ret(_errno, _rc) \
328 /* ------[ Function Definitions ]------ */
330 /* ----[ general utility functions ]---- */
334 * Varargs capable error reporting via lsd_fatal_error()
336 static void _error(char *file, int line, char *msg, ...)
343 len = vsnprintf(buf, 1024, msg, ap);
344 if ((len < 0) || (len > 1024))
347 lsd_fatal_error(file, line, buf);
353 static int _advance_past_brackets (char *tok, char **str)
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) {
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.
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)
379 static char * _next_tok(char *sep, char **str)
383 /* push str past any leading separators */
384 while (**str != '\0' && strchr(sep, **str) != '\0')
390 /* assign token ptr */
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
399 /* push str past token and leave pointing to first separator */
400 while (**str != '\0' && strchr(sep, **str) == '\0')
402 } while (_advance_past_brackets (tok, str));
404 /* nullify consecutive separators and push str beyond them */
405 while (**str != '\0' && strchr(sep, **str) != '\0')
412 /* return the number of zeros needed to pad "num" to "width"
414 static int _zero_padded(unsigned long num, int width)
419 return width > n ? width - n : 0;
422 /* test whether two format `width' parameters are "equivalent"
423 * The width arguments "wn" and "wm" for integers "n" and "m"
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'.
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.
435 static int _width_equiv(unsigned long n, int *wn, unsigned long m, int *wm)
437 int npad, nmpad, mpad, mnpad;
442 npad = _zero_padded(n, *wn);
443 nmpad = _zero_padded(n, *wm);
444 mpad = _zero_padded(m, *wm);
445 mnpad = _zero_padded(m, *wn);
447 if (npad != nmpad && mpad != mnpad)
456 } else { /* mpad != mnpad */
468 /* ----[ hostname_t functions ]---- */
471 * return the location of the last char in the hostname prefix
473 static int host_prefix_end(const char *hostname)
475 int idx = strlen(hostname) - 1;
477 while (idx >= 0 && isdigit((char) hostname[idx]))
483 * create a hostname_t object from a string hostname
485 static hostname_t hostname_create(const char *hostname)
487 hostname_t hn = NULL;
491 assert(hostname != NULL);
493 if (!(hn = (hostname_t) malloc(sizeof(*hn))))
494 out_of_memory("hostname create");
496 idx = host_prefix_end(hostname);
498 if (!(hn->hostname = strdup(hostname))) {
500 out_of_memory("hostname create");
507 if (idx == strlen(hostname) - 1) {
508 if ((hn->prefix = strdup(hostname)) == NULL) {
509 hostname_destroy(hn);
510 out_of_memory("hostname prefix create");
515 hn->suffix = hn->hostname + idx + 1;
516 hn->num = strtoul(hn->suffix, &p, 10);
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");
523 memcpy(hn->prefix, hostname, idx + 1);
524 hn->prefix[idx + 1] = '\0';
526 if (!(hn->prefix = strdup(hostname))) {
527 hostname_destroy(hn);
528 out_of_memory("hostname prefix create");
536 /* free a hostname object
538 static void hostname_destroy(hostname_t hn)
550 /* return true if the hostname has a valid numeric suffix
552 static int hostname_suffix_is_valid(hostname_t hn)
554 return hn->suffix != NULL;
557 /* return the width (in characters) of the numeric part of the hostname
559 static int hostname_suffix_width(hostname_t hn)
561 assert(hn->suffix != NULL);
562 return (int) strlen(hn->suffix);
566 /* ----[ hostrange_t functions ]---- */
568 /* allocate a new hostrange object
570 static hostrange_t hostrange_new(void)
572 hostrange_t new = (hostrange_t) malloc(sizeof(*new));
574 out_of_memory("hostrange create");
578 /* Create a hostrange_t containing a single host without a valid suffix
579 * hr->prefix will represent the entire hostname.
581 static hostrange_t hostrange_create_single(const char *prefix)
585 assert(prefix != NULL);
587 if ((new = hostrange_new()) == NULL)
590 if ((new->prefix = strdup(prefix)) == NULL)
603 out_of_memory("hostrange create single");
607 /* Create a hostrange object with a prefix, hi, lo, and format width
610 hostrange_create(char *prefix, unsigned long lo, unsigned long hi, int width)
614 assert(prefix != NULL);
616 if ((new = hostrange_new()) == NULL)
619 if ((new->prefix = strdup(prefix)) == NULL)
633 out_of_memory("hostrange create");
637 /* Return the number of hosts stored in the hostrange object
639 static unsigned long hostrange_count(hostrange_t hr)
645 return hr->hi - hr->lo + 1;
648 /* Copy a hostrange object
650 static hostrange_t hostrange_copy(hostrange_t hr)
655 return hostrange_create_single(hr->prefix);
657 return hostrange_create(hr->prefix, hr->lo, hr->hi,
662 /* free memory allocated by the hostrange object
664 static void hostrange_destroy(hostrange_t hr)
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.
679 static hostrange_t hostrange_delete_host(hostrange_t hr, unsigned long n)
681 hostrange_t new = NULL;
684 assert(n >= hr->lo && n <= hr->hi);
688 else if (n == hr->hi)
691 if (!(new = hostrange_copy(hr)))
692 out_of_memory("hostrange copy");
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
706 * sort based on width */
707 static int hostrange_cmp(hostrange_t h1, hostrange_t h2)
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;
722 /* compare the prefixes of two hostrange objects.
724 * < 0 if h1 prefix is less than h2 OR h1 == NULL.
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.
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)
738 retval = strcmp(h1->prefix, h2->prefix);
739 return retval == 0 ? h2->singlehost - h1->singlehost : retval;
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:
745 * 1. h1 and h2 have same prefix
746 * 2. neither h1 nor h2 are singlet hosts (i.e. invalid suffix)
748 * (XXX: Should incompatible widths be placed in the same bracketed list?
749 * There's no good reason not to, except maybe aesthetics)
751 static int hostrange_within_range(hostrange_t h1, hostrange_t h2)
753 if (hostrange_prefix_cmp(h1, h2) == 0)
754 return h1->singlehost || h2->singlehost ? 0 : 1;
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
765 static int hostrange_width_combine(hostrange_t h0, hostrange_t h1)
770 return _width_equiv(h0->lo, &h0->width, h1->lo, &h1->width);
774 /* Return true if hostrange hr contains no hosts, i.e. hi < lo
776 static int hostrange_empty(hostrange_t hr)
779 return ((hr->hi < hr->lo) || (hr->hi == (unsigned long) -1));
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)
785 * Returns NULL if malloc fails OR there are no more hosts left
787 static char *hostrange_pop(hostrange_t hr)
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--);
808 /* Same as hostrange_pop(), but remove host from start of range */
809 static char *hostrange_shift(hostrange_t hr)
816 if (hr->singlehost) {
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++);
832 /* join two hostrange objects.
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
840 * h2 will be coalesced into h1 if rc >= 0
842 * it is assumed that h1->lo <= h2->lo, i.e. hr1 <= hr2
845 static int hostrange_join(hostrange_t h1, hostrange_t h2)
851 assert(hostrange_cmp(h1, h2) <= 0);
853 if (hostrange_prefix_cmp(h1, h2) == 0 &&
854 hostrange_width_combine(h1, h2)) {
856 if (h1->singlehost && h2->singlehost) { /* matching singlets */
858 } else if (h1->hi == h2->lo - 1) { /* perfect join */
861 } else if (h1->hi >= h2->lo) { /* some duplication */
862 if (h1->hi < h2->hi) {
863 duplicated = h1->hi - h2->lo + 1;
866 duplicated = hostrange_count(h2);
873 /* hostrange intersect returns the intersection (common hosts)
874 * of hostrange objects h1 and h2. If there is no intersection,
877 * It is assumed that h1 <= h2 (i.e. h1->lo <= h2->lo)
879 static hostrange_t hostrange_intersect(hostrange_t h1, hostrange_t h2)
881 hostrange_t new = NULL;
886 if (h1->singlehost || h2->singlehost)
889 assert(hostrange_cmp(h1, h2) <= 0);
891 if ((hostrange_prefix_cmp(h1, h2) == 0)
893 && (hostrange_width_combine(h1, h2))) {
895 if (!(new = hostrange_copy(h1)))
898 new->hi = h2->hi < h1->hi ? h2->hi : h1->hi;
904 /* return 1 if hostname hn is within the hostrange hr
907 static int hostrange_hn_within(hostrange_t hr, hostname_t hn)
911 if (hr->singlehost && (strcmp(hn->hostname, hr->prefix) == 0))
914 if (strcmp(hr->prefix, hn->prefix) == 0) {
915 if (!hostname_suffix_is_valid(hn)) {
918 } else if (hn->num <= hr->hi && hn->num >= hr->lo) {
919 int width = hostname_suffix_width(hn);
921 retval = _width_equiv(hr->lo, &hr->width, num, &width);
928 /* copy a string representation of the hostrange hr into buffer buf,
929 * writing at most n chars including NUL termination
932 hostrange_to_string(hostrange_t hr, size_t n, char *buf, char *separator)
937 char sep = separator == NULL ? ',' : separator[0];
943 return snprintf(buf, n, "%s", hr->prefix);
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) {
962 /* back up over final separator */
968 /* Place the string representation of the numeric part of hostrange into buf
969 * writing at most n chars including NUL termination.
971 static size_t hostrange_numstr(hostrange_t hr, size_t n, char *buf)
977 if (hr->singlehost || n == 0)
980 len = snprintf(buf, n, "%0*lu", hr->width, hr->lo);
982 if ((len >= 0) && (len < n) && (hr->lo < hr->hi)) {
983 int len2 = snprintf(buf+len, n-len, "-%0*lu", hr->width, hr->hi);
994 /* ----[ hostlist functions ]---- */
996 /* Create a new hostlist object.
997 * Returns an empty hostlist, or NULL if memory allocation fails.
999 static hostlist_t hostlist_new(void)
1002 hostlist_t new = (hostlist_t) malloc(sizeof(*new));
1006 assert(new->magic = HOSTLIST_MAGIC);
1007 mutex_init(&new->mutex);
1009 new->hr = (hostrange_t *) malloc(HOSTLIST_CHUNK * sizeof(hostrange_t));
1013 /* set entries in hostrange array to NULL */
1014 for (i = 0; i < HOSTLIST_CHUNK; i++)
1017 new->size = HOSTLIST_CHUNK;
1026 out_of_memory("hostlist_create");
1030 /* Resize the internal array used to store the list of hostrange objects.
1032 * returns 1 for a successful resize,
1033 * 0 if call to _realloc fails
1035 * It is assumed that the caller has the hostlist hl locked
1037 static int hostlist_resize(hostlist_t hl, size_t newsize)
1042 assert(hl->magic == HOSTLIST_MAGIC);
1045 hl->hr = realloc((void *) hl->hr, hl->size*sizeof(hostrange_t));
1049 for (i = oldsize; i < newsize; i++)
1055 /* Resize hostlist by one HOSTLIST_CHUNK
1056 * Assumes that hostlist hl is locked by caller
1058 static int hostlist_expand(hostlist_t hl)
1060 if (!hostlist_resize(hl, hl->size + HOSTLIST_CHUNK))
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
1070 static int hostlist_push_range(hostlist_t hl, hostrange_t hr)
1078 tail = (hl->nranges > 0) ? hl->hr[hl->nranges-1] : hl->hr[0];
1080 if (hl->size == hl->nranges && !hostlist_expand(hl))
1084 && hostrange_prefix_cmp(tail, hr) == 0
1085 && tail->hi == hr->lo - 1
1086 && hostrange_width_combine(tail, hr)) {
1089 if ((hl->hr[hl->nranges++] = hostrange_copy(hr)) == NULL)
1093 retval = hl->nhosts += hostrange_count(hr);
1095 UNLOCK_HOSTLIST(hl);
1100 UNLOCK_HOSTLIST(hl);
1106 /* Same as hostlist_push_range() above, but prefix, lo, hi, and width
1107 * are passed as args
1110 hostlist_push_hr(hostlist_t hl, char *prefix, unsigned long lo,
1111 unsigned long hi, int width)
1113 hostrange_t hr = hostrange_create(prefix, lo, hi, width);
1114 int retval = hostlist_push_range(hl, hr);
1115 hostrange_destroy(hr);
1119 /* Insert a range object hr into position n of the hostlist hl
1120 * Assumes that hl->mutex is already held by calling process
1122 static int hostlist_insert_range(hostlist_t hl, hostrange_t hr, int n)
1126 hostlist_iterator_t hli;
1129 assert(hl->magic == HOSTLIST_MAGIC);
1132 if (n > hl->nranges)
1135 if (hl->size == hl->nranges && !hostlist_expand(hl))
1138 /* copy new hostrange into slot "n" in array */
1140 hl->hr[n] = hostrange_copy(hr);
1142 /* push remaining hostrange entries up */
1143 for (i = n + 1; i < hl->nranges + 1; i++) {
1144 hostrange_t last = hl->hr[i];
1150 /* adjust hostlist iterators if needed */
1151 for (hli = hl->ilist; hli; hli = hli->next) {
1153 hli->hr = hli->hl->hr[++hli->idx];
1159 /* Delete the range at position n in the range array
1160 * Assumes the hostlist lock is already held.
1162 static void hostlist_delete_range(hostlist_t hl, int n)
1168 assert(hl->magic == HOSTLIST_MAGIC);
1169 assert(n < hl->nranges && n >= 0);
1172 for (i = n; i < hl->nranges - 1; i++)
1173 hl->hr[i] = hl->hr[i + 1];
1175 hl->hr[hl->nranges] = NULL;
1176 hostlist_shift_iterators(hl, n, 0, 1);
1178 /* XXX caller responsible for adjusting nhosts */
1179 /* hl->nhosts -= hostrange_count(old) */
1181 hostrange_destroy(old);
1184 #if WANT_RECKLESS_HOSTRANGE_EXPANSION
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.
1190 hostlist_t _hostlist_create(const char *hostlist, char *sep, char *r_op)
1194 int high, low, fmt = 0;
1195 char prefix[256] = "";
1198 char range_op = r_op[0];/* XXX support > 1 char range ops in future? */
1200 hostlist_t new = hostlist_new();
1202 orig = str = strdup(hostlist);
1204 /* return an empty list if an empty string was passed in */
1205 if (str == NULL || strlen(str) == 0)
1208 /* Use hostlist_create_bracketed if we see "[" */
1209 if (strchr(str, '[') != NULL)
1210 return _hostlist_create_bracketed(hostlist, sep, r_op);
1212 while ((tok = _next_tok(sep, &str)) != NULL) {
1214 /* save the current string for error messages */
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)
1227 /* now back up past any digits */
1228 while (pos >= 0 && isdigit((char) tok[--pos])) {;}
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;
1235 /* create prefix string
1236 * if prefix will be zero length, but prefix already exists
1237 * use the previous prefix and fmt
1239 if ((pos > 0) || (prefix[0] == '\0')) {
1240 memcpy(prefix, tok, (size_t) pos * sizeof(char));
1243 /* push pointer past prefix */
1246 /* count number of digits for ouput fmt */
1247 for (fmt = 0; isdigit(tok[fmt]); ++fmt) {;}
1255 /* get lower bound */
1256 low = strtoul(tok, (char **) &tok, 10);
1258 if (*tok == range_op) { /* now get range upper bound */
1259 /* push pointer past range op */
1262 /* find length of alpha part */
1263 for (pos = 0; tok[pos] && !isdigit(tok[pos]); ++pos) {;}
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
1270 if (pos != strlen(prefix) ||
1271 strncmp(prefix, tok, pos) != 0)
1278 /* make sure we have digits to the end */
1279 for (pos = 0; tok[pos] && isdigit((char) tok[pos]); ++pos) {;}
1281 if (pos > 0) { /* we have digits to process */
1282 high = strtoul(tok, (char **) &tok, 10);
1283 } else { /* bad boy, no digits */
1287 if ((low > high) || (high - low > MAX_RANGE))
1290 } else { /* single value */
1291 high = 0; /* special case, ugh. */
1295 * 1. we are not at end of string
1296 * 2. upper bound equals lower bound
1298 if (*tok != '\0' || high == low)
1301 if (error) { /* assume this is not a range on any error */
1302 hostlist_push_host(new, cur);
1306 hostlist_push_hr(new, prefix, low, high, fmt);
1318 #else /* !WANT_RECKLESS_HOSTRANGE_EXPANSION */
1320 hostlist_t _hostlist_create(const char *hostlist, char *sep, char *r_op)
1322 return _hostlist_create_bracketed(hostlist, sep, r_op);
1325 #endif /* WANT_RECKLESS_HOSTRANGE_EXPANSION */
1328 unsigned long lo, hi;
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.
1336 static int _parse_single_range(const char *str, struct _range *range)
1339 char *orig = strdup(str);
1341 seterrno_ret(ENOMEM, 0);
1343 if ((p = strchr(str, '-'))) {
1345 if (*p == '-') /* do NOT allow negative numbers */
1348 range->lo = strtoul(str, &q, 10);
1352 range->hi = (p && *p) ? strtoul(p, &q, 10) : range->lo;
1354 if (q == p || *q != '\0')
1357 if (range->lo > range->hi)
1360 if (range->hi - range->lo + 1 > MAX_RANGE ) {
1361 _error(__FILE__, __LINE__, "Too many hosts in range `%s'", orig);
1363 seterrno_ret(ERANGE, 0);
1367 range->width = strlen(str);
1371 _error(__FILE__, __LINE__, "Invalid range: `%s'", orig);
1373 seterrno_ret(EINVAL, 0);
1378 * Convert 'str' containing comma separated digits and ranges into an array
1379 * of struct _range types (max 'len' elements).
1381 * Return number of ranges created, or -1 on error.
1383 static int _parse_range_list(char *str, struct _range *ranges, int len)
1391 if ((p = strchr(str, ',')))
1393 if (!_parse_single_range(str, &ranges[count++]))
1401 _push_range_list(hostlist_t hl, char *pfx, struct _range *rng,
1405 for (i = 0; i < n; i++) {
1406 hostlist_push_hr(hl, pfx, rng->lo, rng->hi, rng->width);
1412 _push_range_list_with_suffix(hostlist_t hl, char *pfx, char *sfx,
1413 struct _range *rng, int n)
1417 for (i = 0; i < n; i++) {
1418 for (j = rng->lo; j <= rng->hi; j++) {
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);
1425 * hr is copied in hostlist_push_range. Need to free here.
1427 hostrange_destroy (hr);
1434 * Create a hostlist from a string with brackets '[' ']' to aid
1435 * detection of ranges and compressed lists
1438 _hostlist_create_bracketed(const char *hostlist, char *sep, char *r_op)
1440 hostlist_t new = hostlist_new();
1441 struct _range ranges[MAX_RANGES];
1443 char *p, *tok, *str, *orig;
1446 if (hostlist == NULL)
1449 if (!(orig = str = strdup(hostlist))) {
1450 hostlist_destroy(new);
1454 while ((tok = _next_tok(sep, &str)) != NULL) {
1455 strncpy(cur_tok, tok, 1024);
1457 if ((p = strchr(tok, '[')) != NULL) {
1458 char *q, *prefix = tok;
1461 if ((q = strchr(p, ']'))) {
1463 nr = _parse_range_list(p, ranges, MAX_RANGES);
1468 _push_range_list_with_suffix (new, prefix, q, ranges, nr);
1470 _push_range_list(new, prefix, ranges, nr);
1474 hostlist_push_host(new, cur_tok);
1477 hostlist_push_host(new, cur_tok);
1485 hostlist_destroy(new);
1487 seterrno_ret(err, NULL);
1492 hostlist_t hostlist_create(const char *str)
1494 return _hostlist_create(str, "\t, ", "-");
1498 hostlist_t hostlist_copy(const hostlist_t hl)
1507 if (!(new = hostlist_new()))
1510 new->nranges = hl->nranges;
1511 new->nhosts = hl->nhosts;
1512 if (new->nranges > new->size)
1513 hostlist_resize(new, new->nranges);
1515 for (i = 0; i < hl->nranges; i++)
1516 new->hr[i] = hostrange_copy(hl->hr[i]);
1519 UNLOCK_HOSTLIST(hl);
1524 void hostlist_destroy(hostlist_t hl)
1531 mutex_unlock(&hl->mutex);
1532 hostlist_iterator_destroy(hl->ilist);
1533 mutex_lock(&hl->mutex);
1535 for (i = 0; i < hl->nranges; i++)
1536 hostrange_destroy(hl->hr[i]);
1538 assert(hl->magic = 0x1);
1539 UNLOCK_HOSTLIST(hl);
1540 mutex_destroy(&hl->mutex);
1545 int hostlist_push(hostlist_t hl, const char *hosts)
1551 new = hostlist_create(hosts);
1554 mutex_lock(&new->mutex);
1555 retval = new->nhosts;
1556 mutex_unlock(&new->mutex);
1557 hostlist_push_list(hl, new);
1558 hostlist_destroy(new);
1562 int hostlist_push_host(hostlist_t hl, const char *str)
1570 hn = hostname_create(str);
1572 if (hostname_suffix_is_valid(hn)) {
1573 hr = hostrange_create(hn->prefix, hn->num, hn->num,
1574 hostname_suffix_width(hn));
1576 hr = hostrange_create_single(str);
1578 hostlist_push_range(hl, hr);
1580 hostrange_destroy(hr);
1581 hostname_destroy(hn);
1586 int hostlist_push_list(hostlist_t h1, hostlist_t h2)
1595 for (i = 0; i < h2->nranges; i++)
1596 n += hostlist_push_range(h1, h2->hr[i]);
1598 UNLOCK_HOSTLIST(h2);
1604 char *hostlist_pop(hostlist_t hl)
1609 if (hl->nhosts > 0) {
1610 hostrange_t hr = hl->hr[hl->nranges - 1];
1611 host = hostrange_pop(hr);
1613 if (hostrange_empty(hr)) {
1614 hostrange_destroy(hl->hr[--hl->nranges]);
1615 hl->hr[hl->nranges] = NULL;
1618 UNLOCK_HOSTLIST(hl);
1622 /* find all iterators affected by a shift (or deletion) at
1623 * hl->hr[idx], depth, with the deletion of n ranges */
1625 hostlist_shift_iterators(hostlist_t hl, int idx, int depth, int n)
1627 hostlist_iterator_t i;
1628 for (i = hl->ilist; i; i = i->next) {
1630 if (i->idx == idx && i->depth >= depth)
1631 i->depth = i->depth > -1 ? i->depth - 1 : -1;
1633 if (i->idx >= idx) {
1634 if ((i->idx -= n) >= 0)
1635 i->hr = i->hl->hr[i->idx];
1637 hostlist_iterator_reset(i);
1643 char *hostlist_shift(hostlist_t hl)
1649 if (hl->nhosts > 0) {
1650 hostrange_t hr = hl->hr[0];
1652 host = hostrange_shift(hr);
1655 if (hostrange_empty(hr)) {
1656 hostlist_delete_range(hl, 0);
1657 /* hl->nranges--; */
1659 hostlist_shift_iterators(hl, 0, 0, 0);
1662 UNLOCK_HOSTLIST(hl);
1668 char *hostlist_pop_range(hostlist_t hl)
1671 char buf[MAXHOSTRANGELEN + 1];
1676 if (hl->nranges < 1 || !(hltmp = hostlist_new())) {
1677 UNLOCK_HOSTLIST(hl);
1681 i = hl->nranges - 2;
1682 tail = hl->hr[hl->nranges - 1];
1683 while (i >= 0 && hostrange_within_range(tail, hl->hr[i]))
1686 for (i++; i < hl->nranges; i++) {
1687 hostlist_push_range(hltmp, hl->hr[i]);
1688 hostrange_destroy(hl->hr[i]);
1691 hl->nhosts -= hltmp->nhosts;
1692 hl->nranges -= hltmp->nranges;
1694 UNLOCK_HOSTLIST(hl);
1695 hostlist_ranged_string(hltmp, MAXHOSTRANGELEN, buf);
1696 hostlist_destroy(hltmp);
1701 char *hostlist_shift_range(hostlist_t hl)
1705 hostlist_t hltmp = hostlist_new();
1711 if (hl->nranges == 0) {
1712 hostlist_destroy(hltmp);
1713 UNLOCK_HOSTLIST(hl);
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]) );
1724 hostlist_shift_iterators(hl, i, 0, hltmp->nranges);
1726 /* shift rest of ranges back in hl */
1727 for (; i < hl->nranges; i++) {
1728 hl->hr[i - hltmp->nranges] = hl->hr[i];
1731 hl->nhosts -= hltmp->nhosts;
1732 hl->nranges -= hltmp->nranges;
1734 UNLOCK_HOSTLIST(hl);
1736 hostlist_ranged_string(hltmp, 1024, buf);
1737 hostlist_destroy(hltmp);
1742 /* XXX: Note: efficiency improvements needed */
1743 int hostlist_delete(hostlist_t hl, const char *hosts)
1746 char *hostname = NULL;
1749 if (!(hltmp = hostlist_create(hosts)))
1750 seterrno_ret(EINVAL, 0);
1752 while ((hostname = hostlist_pop(hltmp)) != NULL) {
1753 n += hostlist_delete_host(hl, hostname);
1756 hostlist_destroy(hltmp);
1762 /* XXX watch out! poor implementation follows! (fix it at some point) */
1763 int hostlist_delete_host(hostlist_t hl, const char *hostname)
1765 int n = hostlist_find(hl, hostname);
1767 hostlist_delete_nth(hl, n);
1768 return n >= 0 ? 1 : 0;
1773 _hostrange_string(hostrange_t hr, int depth)
1775 char buf[MAXHOSTNAMELEN + 16];
1776 int len = snprintf(buf, MAXHOSTNAMELEN + 15, "%s", hr->prefix);
1778 if (!hr->singlehost)
1779 snprintf(buf+len, MAXHOSTNAMELEN+15 - len, "%0*lu",
1780 hr->width, hr->lo + depth);
1784 char * hostlist_nth(hostlist_t hl, int n)
1791 for (i = 0; i < hl->nranges; i++) {
1792 int num_in_range = hostrange_count(hl->hr[i]);
1794 if (n <= (num_in_range - 1 + count)) {
1795 host = _hostrange_string(hl->hr[i], n - count);
1798 count += num_in_range;
1801 UNLOCK_HOSTLIST(hl);
1807 int hostlist_delete_nth(hostlist_t hl, int n)
1812 assert(n >= 0 && n <= hl->nhosts);
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];
1820 if (n <= (num_in_range - 1 + count)) {
1821 unsigned long num = hr->lo + n - count;
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);
1834 count += num_in_range;
1839 UNLOCK_HOSTLIST(hl);
1844 int hostlist_count(hostlist_t hl)
1848 retval = hl->nhosts;
1849 UNLOCK_HOSTLIST(hl);
1853 int hostlist_find(hostlist_t hl, const char *hostname)
1855 int i, count, ret = -1;
1861 hn = hostname_create(hostname);
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;
1873 count += hostrange_count(hl->hr[i]);
1877 UNLOCK_HOSTLIST(hl);
1878 hostname_destroy(hn);
1882 /* hostrange compare with void * arguments to allow use with
1885 int _cmp(const void *hr1, const void *hr2)
1887 hostrange_t *h1 = (hostrange_t *) hr1;
1888 hostrange_t *h2 = (hostrange_t *) hr2;
1889 return hostrange_cmp((hostrange_t) * h1, (hostrange_t) * h2);
1893 void hostlist_sort(hostlist_t hl)
1895 hostlist_iterator_t i;
1898 if (hl->nranges <= 1) {
1899 UNLOCK_HOSTLIST(hl);
1903 qsort(hl->hr, hl->nranges, sizeof(hostrange_t), &_cmp);
1905 /* reset all iterators */
1906 for (i = hl->ilist; i; i = i->next)
1907 hostlist_iterator_reset(i);
1909 UNLOCK_HOSTLIST(hl);
1911 hostlist_coalesce(hl);
1916 /* search through hostlist for ranges that can be collapsed
1917 * does =not= delete any hosts
1919 static void hostlist_collapse(hostlist_t 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];
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);
1935 UNLOCK_HOSTLIST(hl);
1938 /* search through hostlist (hl) for intersecting ranges
1939 * split up duplicates and coalesce ranges where possible
1941 static void hostlist_coalesce(hostlist_t hl)
1948 for (i = hl->nranges - 1; i > 0; i--) {
1950 new = hostrange_intersect(hl->hr[i - 1], hl->hr[i]);
1953 hostrange_t hprev = hl->hr[i - 1];
1954 hostrange_t hnext = hl->hr[i];
1957 if (new->hi < hprev->hi)
1958 hnext->hi = hprev->hi;
1960 hprev->hi = new->lo;
1961 hnext->lo = new->hi;
1963 if (hostrange_empty(hprev))
1964 hostlist_delete_range(hl, i);
1966 while (new->lo <= new->hi) {
1967 hostrange_t hr = hostrange_create( new->prefix,
1971 if (new->lo > hprev->hi)
1972 hostlist_insert_range(hl, hr, j++);
1974 if (new->lo < hnext->lo)
1975 hostlist_insert_range(hl, hr, j++);
1977 hostrange_destroy(hr);
1982 hostrange_destroy(new);
1985 UNLOCK_HOSTLIST(hl);
1987 hostlist_collapse(hl);
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)
1999 assert(hl->magic == HOSTLIST_MAGIC);
2001 assert(loc < hl->nranges);
2002 ndup = hostrange_join(hl->hr[loc - 1], hl->hr[loc]);
2004 hostlist_delete_range(hl, loc);
2010 void hostlist_uniq(hostlist_t hl)
2013 hostlist_iterator_t hli;
2015 if (hl->nranges <= 1) {
2016 UNLOCK_HOSTLIST(hl);
2019 qsort(hl->hr, hl->nranges, sizeof(hostrange_t), &_cmp);
2021 while (i < hl->nranges) {
2022 if (_attempt_range_join(hl, i) < 0) /* No range join occurred */
2026 /* reset all iterators */
2027 for (hli = hl->ilist; hli; hli = hli->next)
2028 hostlist_iterator_reset(hli);
2030 UNLOCK_HOSTLIST(hl);
2034 size_t hostlist_deranged_string(hostlist_t hl, size_t n, char *buf)
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) {
2052 UNLOCK_HOSTLIST(hl);
2054 buf[len > 0 ? --len : 0] = '\0';
2058 return truncated ? -1 : len;
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)
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);
2069 /* write the next bracketed hostlist, i.e. prefix[n-m,k,...]
2070 * into buf, writing at most n chars including the terminating '\0'
2072 * leaves start pointing to one past last range object in bracketed list,
2073 * and returns the number of bytes written into buf.
2075 * Assumes hostlist is locked.
2078 _get_bracketed_list(hostlist_t hl, int *start, const size_t n, char *buf)
2080 hostrange_t *hr = hl->hr;
2083 int bracket_needed = _is_bracket_needed(hl, i);
2085 len = snprintf(buf, n, "%s", hr[i]->prefix);
2087 if ((len < 0) || (len > n))
2088 return n; /* truncated, buffer filled */
2090 if (bracket_needed && len < n && len >= 0)
2094 m = (n - len) <= n ? n - len : 0;
2095 len += hostrange_numstr(hr[i], m, buf + len);
2098 if (bracket_needed) /* Only need commas inside brackets */
2100 } while (++i < hl->nranges && hostrange_within_range(hr[i], hr[i-1]));
2102 if (bracket_needed && len < n && len > 0) {
2104 /* Add trailing bracket (change trailing "," from above to "]" */
2107 /* NUL terminate for safety, but do not add terminator to len */
2110 } else if (len >= n) {
2115 /* If len is > 0, NUL terminate (but do not add to len) */
2116 buf[len > 0 ? len : 0] = '\0';
2123 size_t hostlist_ranged_string(hostlist_t hl, size_t n, char *buf)
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))
2135 UNLOCK_HOSTLIST(hl);
2143 buf[len > 0 ? len : 0] = '\0';
2145 return truncated ? -1 : len;
2148 /* ----[ hostlist iterator functions ]---- */
2150 static hostlist_iterator_t hostlist_iterator_new(void)
2152 hostlist_iterator_t i = (hostlist_iterator_t) malloc(sizeof(*i));
2160 assert(i->magic = HOSTLIST_MAGIC);
2164 hostlist_iterator_t hostlist_iterator_create(hostlist_t hl)
2166 hostlist_iterator_t i;
2168 if (!(i = hostlist_iterator_new()))
2169 out_of_memory("hostlist_iterator_create");
2174 i->next = hl->ilist;
2176 UNLOCK_HOSTLIST(hl);
2180 hostlist_iterator_t hostset_iterator_create(hostset_t set)
2182 return hostlist_iterator_create(set->hl);
2185 void hostlist_iterator_reset(hostlist_iterator_t i)
2188 assert(i->magic == HOSTLIST_MAGIC);
2190 i->hr = i->hl->hr[0];
2195 void hostlist_iterator_destroy(hostlist_iterator_t i)
2197 hostlist_iterator_t *pi;
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);
2210 UNLOCK_HOSTLIST(i->hl);
2211 assert(i->magic = 0x1);
2215 static void _iterator_advance(hostlist_iterator_t i)
2218 assert(i->magic == HOSTLIST_MAGIC);
2219 if (i->idx > i->hl->nranges - 1)
2221 if (++(i->depth) > (i->hr->hi - i->hr->lo)) {
2223 i->hr = i->hl->hr[++i->idx];
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.
2231 static void _iterator_advance_range(hostlist_iterator_t i)
2236 assert(i->magic == HOSTLIST_MAGIC);
2238 nr = i->hl->nranges;
2241 if (++i->depth > 0) {
2242 while (++j < nr && hostrange_within_range(i->hr, hr[j])) {;}
2244 i->hr = i->hl->hr[i->idx];
2249 char *hostlist_next(hostlist_iterator_t i)
2255 assert(i->magic == HOSTLIST_MAGIC);
2256 LOCK_HOSTLIST(i->hl);
2257 _iterator_advance(i);
2259 if (i->idx > i->hl->nranges - 1) {
2260 UNLOCK_HOSTLIST(i->hl);
2266 if (!i->hr->singlehost)
2267 snprintf (suffix, 15, "%0*lu", i->hr->width, i->hr->lo + i->depth);
2269 len = strlen (i->hr->prefix) + strlen (suffix) + 1;
2270 if (!(buf = malloc (len)))
2271 out_of_memory("hostlist_next");
2274 strcat (buf, i->hr->prefix);
2275 strcat (buf, suffix);
2277 UNLOCK_HOSTLIST(i->hl);
2281 char *hostlist_next_range(hostlist_iterator_t i)
2283 char buf[MAXHOSTRANGELEN + 1];
2287 assert(i->magic == HOSTLIST_MAGIC);
2288 LOCK_HOSTLIST(i->hl);
2290 _iterator_advance_range(i);
2292 if (i->idx > i->hl->nranges - 1) {
2293 UNLOCK_HOSTLIST(i->hl);
2298 _get_bracketed_list(i->hl, &j, MAXHOSTRANGELEN, buf);
2300 UNLOCK_HOSTLIST(i->hl);
2305 int hostlist_remove(hostlist_iterator_t i)
2309 assert(i->magic == HOSTLIST_MAGIC);
2310 LOCK_HOSTLIST(i->hl);
2311 new = hostrange_delete_host(i->hr, i->hr->lo + i->depth);
2313 hostlist_insert_range(i->hl, new, i->idx + 1);
2314 hostrange_destroy(new);
2315 i->hr = i->hl->hr[++i->idx];
2317 } else if (hostrange_empty(i->hr)) {
2318 hostlist_delete_range(i->hl, i->idx);
2323 UNLOCK_HOSTLIST(i->hl);
2328 /* ----[ hostset functions ]---- */
2330 hostset_t hostset_create(const char *hostlist)
2334 if (!(new = (hostset_t) malloc(sizeof(*new))))
2337 if (!(new->hl = hostlist_create(hostlist)))
2340 hostlist_uniq(new->hl);
2349 hostset_t hostset_copy(const hostset_t set)
2352 if (!(new = (hostset_t) malloc(sizeof(*new))))
2355 if (!(new->hl = hostlist_copy(set->hl)))
2365 void hostset_destroy(hostset_t set)
2369 hostlist_destroy(set->hl);
2373 /* inserts a single range object into a hostset
2374 * Assumes that the set->hl lock is already held
2375 * Updates hl->nhosts
2377 static int hostset_insert_range(hostset_t set, hostrange_t hr)
2387 if (hl->size == hl->nranges && !hostlist_expand(hl))
2390 nhosts = hostrange_count(hr);
2392 for (i = 0; i < hl->nranges; i++) {
2393 if (hostrange_cmp(hr, hl->hr[i]) <= 0) {
2395 if ((ndups = hostrange_join(hr, hl->hr[i])) >= 0)
2396 hostlist_delete_range(hl, i);
2400 hostlist_insert_range(hl, hr, i);
2402 /* now attempt to join hr[i] and hr[i-1] */
2405 if ((m = _attempt_range_join(hl, i)) > 0)
2408 hl->nhosts += nhosts - ndups;
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)
2424 * Return the number of unique hosts inserted
2426 return nhosts - ndups;
2429 int hostset_insert(hostset_t set, const char *hosts)
2432 hostlist_t hl = hostlist_create(hosts);
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);
2446 /* linear search through N ranges for hostname "host"
2448 static int hostset_find_host(hostset_t set, const char *host)
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)) {
2462 UNLOCK_HOSTLIST(set->hl);
2463 hostname_destroy(hn);
2467 int hostset_within(hostset_t set, const char *hosts)
2473 assert(set->hl->magic == HOSTLIST_MAGIC);
2475 hl = hostlist_create(hosts);
2476 nhosts = hostlist_count(hl);
2479 while ((hostname = hostlist_pop(hl)) != NULL) {
2480 nfound += hostset_find_host(set, hostname);
2484 hostlist_destroy(hl);
2486 return (nhosts == nfound);
2489 int hostset_delete(hostset_t set, const char *hosts)
2491 return hostlist_delete(set->hl, hosts);
2494 int hostset_delete_host(hostset_t set, const char *hostname)
2496 return hostlist_delete_host(set->hl, hostname);
2499 char *hostset_shift(hostset_t set)
2501 return hostlist_shift(set->hl);
2504 char *hostset_pop(hostset_t set)
2506 return hostlist_pop(set->hl);
2509 char *hostset_shift_range(hostset_t set)
2511 return hostlist_shift_range(set->hl);
2514 char *hostset_pop_range(hostset_t set)
2516 return hostlist_pop_range(set->hl);
2519 int hostset_count(hostset_t set)
2521 return hostlist_count(set->hl);
2524 size_t hostset_ranged_string(hostset_t set, size_t n, char *buf)
2526 return hostlist_ranged_string(set->hl, n, buf);
2529 size_t hostset_deranged_string(hostset_t set, size_t n, char *buf)
2531 return hostlist_deranged_string(set->hl, n, buf);
2536 int hostlist_nranges(hostlist_t hl)
2541 int hostset_nranges(hostset_t set)
2543 return set->hl->nranges;
2546 /* test iterator functionality on the list of hosts represented
2549 int iterator_test(char *list)
2553 hostlist_t hl = hostlist_create(list);
2554 hostset_t set = hostset_create(list);
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);
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);
2568 /* forge ahead three hosts with i2 */
2569 for (j = 0; j < 4; j++) {
2570 host = hostlist_next(i2);
2574 host = hostlist_shift(hl);
2575 printf("result of shift(hl) = `%s'\n", host);
2577 host = hostlist_next(i);
2578 printf("next host in list hl = `%s'\n", host);
2580 host = hostlist_next(i2);
2581 printf("next host for i2 = `%s'\n", host);
2584 hostlist_iterator_destroy(i);
2586 hostlist_destroy(hl);
2587 hostset_destroy(set);
2591 int main(int ac, char **av)
2597 hostlist_t hl1, hl2, hl3;
2598 hostset_t set, set1;
2599 hostlist_iterator_t iter, iter2;
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");
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);
2612 for (i = 2; i < ac; i++) {
2613 hostlist_push(hl1, av[i]);
2614 hostset_insert(set, av[i]);
2617 hostlist_ranged_string(hl1, 102400, buf);
2618 printf("ranged = `%s'\n", buf);
2622 hostlist_deranged_string(hl1, 10240, buf);
2623 printf("deranged = `%s'\n", buf);
2625 hostset_ranged_string(set, 1024, buf);
2626 printf("hostset = `%s'\n", buf);
2629 hostlist_ranged_string(hl1, 1024, buf);
2630 printf("sorted = `%s'\n", buf);
2633 hostlist_ranged_string(hl1, 1024, buf);
2634 printf("uniqed = `%s'\n", buf);
2636 hl2 = hostlist_copy(hl1);
2637 printf("pop_range: ");
2638 while ((str = hostlist_pop_range(hl2))) {
2639 printf("`%s' ", str);
2642 hostlist_destroy(hl2);
2645 hl2 = hostlist_copy(hl1);
2646 printf("shift_range: ");
2647 while ((str = hostlist_shift_range(hl2))) {
2648 printf("`%s' ", str);
2651 hostlist_destroy(hl2);
2654 iter = hostset_iterator_create(set);
2655 iter2 = hostset_iterator_create(set);
2656 hostlist_iterator_destroy(iter2);
2659 while ((str = hostlist_next(iter))) {
2660 printf("`%s' ", str);
2665 hostlist_iterator_reset(iter);
2666 printf("next_range: ");
2667 while ((str = hostlist_next_range(iter))) {
2668 printf("`%s' ", str);
2673 printf("nranges = %d\n", hostset_nranges(set));
2675 hostset_ranged_string(set, 1024, buf);
2676 printf("set = %s\n", buf);
2678 hostset_destroy(set);
2679 hostlist_destroy(hl1);
2683 #endif /* TEST_MAIN */
2686 * vi: tabstop=4 shiftwidth=4 expandtab