2
/*___INFO__MARK_BEGIN__*/
4
/*************************************************************************
6
* The Contents of this file are made available subject to the terms of
7
* the Sun Industry Standards Source License Version 1.2
9
* Sun Microsystems Inc., March, 2001
12
* Sun Industry Standards Source License Version 1.2
13
* =================================================
14
* The contents of this file are subject to the Sun Industry Standards
15
* Source License Version 1.2 (the "License"); You may not use this file
16
* except in compliance with the License. You may obtain a copy of the
17
* License at http://gridengine.sunsource.net/Gridengine_SISSL_license.html
19
* Software provided under this License is provided on an "AS IS" basis,
20
* WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
21
* WITHOUT LIMITATION, WARRANTIES THAT THE SOFTWARE IS FREE OF DEFECTS,
22
* MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE, OR NON-INFRINGING.
23
* See the License for the specific provisions governing your rights and
24
* obligations concerning the Software.
26
* The Initial Developer of the Original Code is: Sun Microsystems, Inc.
28
* Copyright: 2001 by Sun Microsystems, Inc.
30
* All Rights Reserved.
32
************************************************************************/
34
/*___INFO__MARK_END__*/
47
#include "sge_unistd.h"
48
#include "sge_dstring.h"
50
#include "sge_string.h"
51
#include "sge_all_listsL.h"
53
#include "sge_sched.h"
54
#include "cull_sort.h"
57
#include "sge_parse_num_par.h"
59
#include "sge_range.h"
60
#include "sge_schedd_text.h"
61
#include "sge_answer.h"
63
#include "msg_sgeobjlib.h"
65
#define RANGE_SEPARATOR_CHARS ","
66
#define RANGE_LAYER BASIS_LAYER
69
static bool range_is_overlapping(const lListElem *range1,
70
const lListElem *range2);
72
static void expand_range_list(lListElem *r, lList **rl);
74
/* we keep a descending sorted list of non overlapping ranges */
75
/* MT-NOTE: expand_range_list() is MT safe */
76
static void expand_range_list(lListElem *r, lList **rl)
78
u_long32 rmin, rmax, rstep;
81
DENTER(TOP_LAYER, "expand_range_list");
83
rmin = lGetUlong(r, RN_min);
84
rmax = lGetUlong(r, RN_max);
85
rstep = lGetUlong(r, RN_step);
89
*rl = lCreateList("ranges", RN_Type);
92
if (lGetNumberOfElem(*rl) != 0) {
96
if (rstep != lGetUlong(ep, RN_step) || rstep > 1 ||
97
lGetUlong(ep, RN_step) > 1) {
98
lInsertElem(*rl, NULL, r);
100
} else if (rmin > lGetUlong(ep, RN_max)) {
103
** r and ep are non-overlapping and r is to be
104
** sorted ahead of ep.
106
lInsertElem(*rl, NULL, r);
109
} else if (rmax < lGetUlong(ep, RN_min)) {
111
** r and ep are non-overlapping and r is to be
112
** sorted after ep ==> go for the next iteration
116
/* We are at the end of the list ==> append r */
122
} else if ((rmax <= lGetUlong(ep, RN_max)) &&
123
(rmin >= lGetUlong(ep, RN_min))) {
126
** r is fully contained within ep ==> delete it
131
} else if (rmin < lGetUlong(ep, RN_min)) {
134
** ep is either fully contained within r
135
** or r overlaps ep at ep's bottom ==>
136
** overwrite ep and see if further list elements
139
if (rmax > lGetUlong(ep, RN_max)) {
141
lSetUlong(ep, RN_max, rmax);
143
lSetUlong(ep, RN_min, rmin);
145
/* we're already sure we can free r */
150
if (rmin < lGetUlong(ep, RN_min)) {
152
/* it also contains this one */
155
lRemoveElem(*rl, &r);
157
} else if (rmin <= lGetUlong(ep, RN_max)) {
159
/* these overlap ==> glue them */
160
lSetUlong(rr, RN_min, lGetUlong(ep, RN_min));
164
lRemoveElem(*rl, &r);
168
/* they are non overlapping */
174
/* we're now sure we inserted it */
176
} else if (rmax > lGetUlong(ep, RN_max)) {
178
** r and ep overlap and r starts above ep
181
lSetUlong(ep, RN_max, rmax);
193
/****** sgeobj/range/range_correct_end() **************************************
195
* range_correct_end() -- correct end of a range element
198
* static void range_correct_end(lListElem *this_range)
201
* This function modifies the the 'end' id of the 'this_range'
202
* element if it is not correct. After the modification the
203
* 'end' id is the last valid id which is part of the range.
206
* lListElem *this_range - RN_Type
209
* 'this_range' will be modified
212
* 1-6:2 (1,3,5) will be modified to 1-5:2
215
* sgeobj/range/RN_Type
216
*******************************************************************************/
217
void range_correct_end(lListElem *this_range)
219
DENTER(RANGE_LAYER, "range_correct_end");
220
if (this_range != NULL) {
221
u_long32 start, end, step;
223
range_get_all_ids(this_range, &start, &end, &step);
225
if ((end - start) % step) {
228
factor = (end - start) / step;
229
end = start + factor * step;
230
range_set_all_ids(this_range, start, end, step);
235
range_set_all_ids(this_range, start, end, step);
240
/****** sgeobj/range/range_is_overlapping() ***********************************
242
* range_is_overlapping() -- Do two ranges interleave?
245
* static bool range_is_overlapping(const lListElem *this_elem,
246
* const lListElem *range)
249
* True will be returned when the given ranges interleave. This
250
* does not necessaryly mean that certain ids exist in both ranges.
253
* const lListElem *this_elem - RN_Type
254
* const lListElem *range - RN_Type
257
* static bool - false or true
260
* 1-5:3 4-10:7 => true
261
* 1-5:3 5-10:6 => true
262
* 1-5:3 6-10:4 => false
265
* sgeobj/range/RN_Type
268
* MT-NOTE: range_is_overlapping() is MT safe
269
*******************************************************************************/
270
static bool range_is_overlapping(const lListElem *this_elem,
271
const lListElem *range)
275
DENTER(RANGE_LAYER, "range_is_overlapping");
276
if (this_elem != NULL && range != NULL) {
277
u_long32 start1, end1, step1;
278
u_long32 start2, end2, step2;
280
range_get_all_ids(this_elem, &start1, &end1, &step1);
281
range_get_all_ids(range, &start2, &end2, &step2);
282
if (end1 >= start2) {
289
/****** sgeobj/range/range_list_initialize() **********************************
291
* range_list_initialize() -- (Re)initialize a range list
294
* void range_list_initialize(lList **this_list,
295
* lList **answer_list)
298
* 'this_list' will be created if it does not exist. If it already
299
* exists all elements contained in this list will be removed.
302
* lList **this_list - Pointer to a RN_Type-list
303
* lList **answer_list - Pointer to a AN_Type-list or NULL
306
* *this_list will be an empty RN_Type list
307
* *answer_list may contain error messages
310
* sgeobj/range/RN_Type
311
*******************************************************************************/
312
void range_list_initialize(lList **this_list, lList **answer_list)
314
DENTER(RANGE_LAYER, "range_list_initialize");
315
if (this_list != NULL) {
316
if (*this_list != NULL) {
318
lListElem *next_range;
321
* EB: CLEANUP: implement a new CULL function lEmptyList(lList *list)
324
next_range = lFirst(*this_list);
325
while ((range = next_range)) {
326
next_range = lNext(range);
328
lRemoveElem(*this_list, &range);
331
*this_list = lCreateList("", RN_Type);
332
if (*this_list == NULL) {
333
answer_list_add(answer_list, "unable to create range list",
334
STATUS_ERROR1, ANSWER_QUALITY_ERROR);
341
/****** sgeobj/range/range_list_get_number_of_ids() ***************************
343
* range_list_get_number_of_ids() -- Determines the number of ids
346
* u_long32 range_list_get_number_of_ids(const lList *this_list)
349
* This function determines the number of ids contained
350
* in 'this_list'. If 'this_list' is NULL then 0 will be returned.
353
* const lList *this_list - RN_Type list
356
* u_long32 - number of ids
359
* 1-5:2, 7-10:3, 20-23:1 (1, 3, 5, 7, 10, 20, 21, 22, 23) => 9
362
* sgeobj/range/RN_Type
365
* MT-NOTE: range_list_get_number_of_ids() is MT safe
366
*******************************************************************************/
367
u_long32 range_list_get_number_of_ids(const lList *this_list)
372
DENTER(RANGE_LAYER, "range_list_get_number_of_ids");
373
for_each(range, this_list) {
374
ret += range_get_number_of_ids(range);
379
/****** sgeobj/range/range_get_number_of_ids() ********************************
381
* range_get_number_of_ids() -- Number of ids within a range
384
* u_long32 range_get_number_of_ids(const lList *this_elem)
387
* This function determines the number of ids contained
391
* const lList *this_elem - RN_Type element
394
* u_long32 - number of ids
397
* 1-5:2 (1, 3, 5) => 3
400
* sgeobj/range/RN_Type
401
*******************************************************************************/
402
u_long32 range_get_number_of_ids(const lListElem *this_elem)
404
u_long32 start, end, step, ret;
406
DENTER(RANGE_LAYER, "range_get_number_of_ids");
407
range_get_all_ids(this_elem, &start, &end, &step);
408
ret = 1 + (end - start) / step;
412
/****** sgeobj/range/range_list_print_to_string() *****************************
414
* range_list_print_to_string() -- Print range list into the string
417
* void range_list_print_to_string(const lList *this_list,
418
* dstring *string, bool ignore_step,
419
* bool comma_as_separator)
422
* Print all ranges given in 'this_list' into the dynamic 'string'.
423
* If 'this_list' is NULL then the word "UNDEFINED" will be added
424
* to 'string'. If 'ignore_step' is 'true' then the stepsize of all
425
* ranges will be suppressed.
428
* const lList *this_list - RN_Type
429
* dstring *string - dynamic string
430
* bool ignore_step - ignore step for printing
431
* bool comma_as_separator - use the format 1,2,3 instead of 1-2:
432
* bool print_always_as_range - even if the range has only one id
435
* string will be modified
438
* sgeobj/range/RN_Type
439
*******************************************************************************/
441
range_list_print_to_string(const lList *this_list,
442
dstring *string, bool ignore_step,
443
bool comma_as_separator, bool print_always_as_range)
445
DENTER(RANGE_LAYER, "range_list_print_to_string");
446
if (string != NULL) {
447
if (this_list != NULL) {
450
for_each(range, this_list) {
451
u_long32 start, end, step;
453
range_get_all_ids(range, &start, &end, &step);
454
range_to_dstring(start, end, step, string, ignore_step,
455
comma_as_separator, print_always_as_range);
458
sge_dstring_append(string, "UNDEFINED");
464
/****** sgeobj/range/range_list_get_first_id() ********************************
466
* range_list_get_first_id() -- First id contained in the list
469
* u_long32 range_list_get_first_id(const lList *range_list,
470
* lList **answer_list)
473
* The first id of the first range element of the list will
474
* be returned. If 'range_list' is NULL or empty 0 will be
475
* returned and 'answer_list' will be filled with an error
479
* const lList *range_list - RN_Type list
480
* lList **answer_list - Pointer to an AN_Type list
483
* u_long32 - First id or 0
486
* sgeobj/range/RN_Type
487
* sgeobj/range/range_list_get_last_id()
490
* MT-NOTE: range_list_get_first_id() is MT safe
492
******************************************************************************/
493
u_long32 range_list_get_first_id(const lList *range_list, lList **answer_list)
496
lListElem *range = NULL;
498
DENTER(RANGE_LAYER, "range_list_get_first_id");
499
range = lFirst(range_list);
503
range_get_all_ids(range, &start, &end, &step);
505
answer_list_add(answer_list, "range_list containes no elements",
506
STATUS_ERROR1, ANSWER_QUALITY_ERROR);
511
/****** sgeobj/range/range_list_get_last_id() *********************************
513
* range_list_get_last_id() -- Returns last id contained in the list
516
* u_long32 range_list_get_last_id(const lList *range_list,
517
* lList **answer_list)
520
* The last id of the last range element of the list will be
521
* returned. If 'range_list' is NULL or empty 0 will be
522
* returned and 'answer_list' will be filled with an error
526
* const lList *range_list - RN_Type list
527
* lList **answer_list - Pointer to an AN_Type list
530
* u_long32 - Last id or 0
533
* sgeobj/range/RN_Type
534
* sgeobj/range/range_list_get_first_id()
535
******************************************************************************/
536
u_long32 range_list_get_last_id(const lList *range_list, lList **answer_list)
539
lListElem *range = NULL;
541
DENTER(RANGE_LAYER, "range_list_get_last_id");
542
range = lLast(range_list);
544
u_long32 start, step;
545
range_get_all_ids(range, &start, &end, &step);
547
answer_list_add(answer_list, "range_list containes no elements",
548
STATUS_ERROR1, ANSWER_QUALITY_ERROR);
553
/****** sgeobj/range/range_list_get_average() *********************************
555
* range_list_get_average() -- Return average of all numbers in range.
558
* double range_list_get_average(const lList *this_list)
561
* The average of all numbers in the range is returned. For an empty
562
* range 0 is returned.
565
* const lList *this_list - RN_Type list
566
* u_long32 upperbound - This is used as range upperbound if non-0
569
* double - the average
572
* MT-NOTES: range_list_get_average() is MT safe
573
*******************************************************************************/
574
double range_list_get_average(const lList *this_list, u_long32 upperbound)
578
u_long32 id, min, max, step;
581
for_each (range, this_list) {
582
range_get_all_ids(range, &min, &max, &step);
583
if (upperbound != 0) {
584
max = MIN(max, upperbound);
586
for (id=min; id<=max; id+= step) {
591
return (n > 0) ? (sum/n) : 0;
594
/******asgeobj/range/range_list_sort_uniq_compress() **************************
596
* range_list_sort_uniq_compress() -- makes lists fit as a fiddle
599
* void range_list_sort_uniq_compress(lList *range_list,
600
* lList **answer_list)
603
* After a call to this function 'range_list' fulfills
604
* following conditions:
605
* (1) all ids are in ascending order
606
* (2) each id is contained in the list only once
607
* (3) ids are grouped so that a min of range elements exist
610
* lList *range_list - RN_Type list
611
* lList **answer_list - Pointer to an AN_Type list
612
* bool correct_end - if true, range_list is treated as id enumeration
615
* range_list will be modified
618
* 12-12:7,1-7:1,3-5:2,14-16:2 => 1-7:1,12-16:2
621
* sgeobj/range/RN_Type
624
* MT-NOTE: range_list_sort_uniq_compress() is MT safe
625
******************************************************************************/
626
void range_list_sort_uniq_compress(lList *range_list, lList **answer_list, bool correct_end)
628
DENTER(RANGE_LAYER, "range_list_sort_uniq_compress");
630
lListElem *range1, *next_range1;
631
lListElem *range2, *next_range2;
635
* Sort the incomming stuff
637
lPSortList(range_list, "%I+", RN_min);
640
* Remove overlapping ranges
642
tmp_list = lCreateList("", RN_Type);
644
for (next_range1 = lFirst(range_list); (range1 = next_range1); next_range1 = lNext(range1)) {
645
next_range2 = lNext(next_range1);
647
range_correct_end(range1);
648
while ((range2 = next_range2)) {
649
next_range2 = lNext(range2);
651
range_correct_end(range2);
652
if (range_is_overlapping(range1, range2)) {
653
range2 = lDechainElem(range_list, range2);
654
lAppendElem(tmp_list, range2);
662
* Insert all removed entries at the correct position
664
for_each(range1, tmp_list) {
665
u_long32 start1, end1, step1;
667
range_get_all_ids(range1, &start1, &end1, &step1);
668
for (; start1 <= end1; start1 += step1) {
669
range_list_insert_id(&range_list, answer_list, start1);
673
lFreeList(&tmp_list);
676
* Join sequenced ranges
678
range_list_compress(range_list);
680
answer_list_add(answer_list, "unable to create range list",
681
STATUS_ERROR1, ANSWER_QUALITY_ERROR);
687
/****** sgeobj/range/range_list_compress() ************************************
689
* range_list_compress() -- Joins sequenced ranges within a list
692
* void range_list_compress(lList *range_list)
695
* Consecutive ranges within the list will be joined by this
696
* function. Following pre-conditions have to be fulfilled, so
697
* that this function works correctly:
698
* (1) ids have to be in ascending order
699
* (2) Only the first/last id of a range may be contained
700
* in the predecessor/successor range
703
* lList *range_list - RN_Type list
706
* 'range_list' will be modified
709
* 1-3:1,4-5:1,6-8:2,8-10:2 => 1-5:1,6-10:2
712
* sgeobj/range/RN_Type
715
* MT-NOTE: range_list_compress() is MT safe
716
******************************************************************************/
717
void range_list_compress(lList *range_list)
719
DENTER(RANGE_LAYER, "range_list_compress");
720
if (range_list != NULL) {
721
lListElem *range1 = NULL;
722
lListElem *range2 = NULL;
723
lListElem *next_range1 = lFirst(range_list);
724
lListElem *next_range2 = lNext(next_range1);
726
while ((range1 = next_range1) && (range2 = next_range2)) {
727
u_long32 start1, end1, step1;
728
u_long32 start2, end2, step2;
730
range_get_all_ids(range1, &start1, &end1, &step1);
731
range_get_all_ids(range2, &start2, &end2, &step2);
732
if (end1 + step1 == start2 && step1 == step2) {
735
range_set_all_ids(range1, start1, end1, step1);
736
lRemoveElem(range_list, &range2);
738
next_range1 = range1;
739
} else if (start1 == end1 && step1 == 1 && end1 == start2 - step2) {
742
range_set_all_ids(range1, start1, end1, step1);
743
lRemoveElem(range_list, &range2);
745
next_range1 = range1;
746
} else if (start2 == end2 && step2 == 1 && end1 + step1 == end2) {
748
range_set_all_ids(range1, start1, end1, step1);
749
lRemoveElem(range_list, &range2);
751
next_range1 = range1;
752
} else if (start1 == end1 && start2 == end2 && step1 == step2 &&
755
step1 = end1 - start1;
756
range_set_all_ids(range1, start1, end1, step1);
757
lRemoveElem(range_list, &range2);
759
next_range1 = range1;
761
next_range1 = lNext(range1);
763
next_range2 = lNext(next_range1);
769
/****** sgeobj/range/range_list_is_id_within() ********************************
771
* range_list_is_id_within() -- Is id contained in range list?
775
* range_list_is_id_within(const lList *range_list, u_long32 id)
778
* True is returned by this function if 'id' is part of at least
779
* one range element of 'range_list'
782
* const lList *range_list - RN_Type list
786
* bool - true or false
789
* sgeobj/range/RN_Type
792
* MT-NOTE: range_list_is_id_within() is MT safe
793
*******************************************************************************/
794
bool range_list_is_id_within(const lList *range_list, u_long32 id)
796
lListElem *range = NULL;
799
DENTER(RANGE_LAYER, "range_list_is_id_within");
800
for_each(range, range_list) {
801
if (range_is_id_within(range, id)) {
809
/****** sgeobj/range/range_list_containes_id_less_than() **********************
811
* range_list_containes_id_less_than() -- has id less than x
814
* bool range_list_containes_id_less_than(const lList *range_list,
818
* Is at least one id in the "range_list" less than "id"
821
* const lList *range_list - RN_Type list
822
* u_long32 id - number
825
* bool - true or false
826
*******************************************************************************/
827
bool range_list_containes_id_less_than(const lList *range_list, u_long32 id)
829
lListElem *range = NULL;
832
DENTER(RANGE_LAYER, "range_list_containes_id_less_than");
833
for_each(range, range_list) {
834
if (range_containes_id_less_than(range, id)) {
842
/****** sgeobj/range/range_list_is_empty() ************************************
844
* range_list_is_empty() -- check if id lists containes ids
847
* bool range_list_is_empty(const lList *range_list)
850
* Returns true if "range_list" containes no ids.
853
* const lList *range_list - RN_Type list
856
* bool - true or false
859
* sgeobj/range/RN_Type
860
******************************************************************************/
861
bool range_list_is_empty(const lList *range_list)
863
return (range_list_get_number_of_ids(range_list) == 0 ? true : false);
866
/****** sgeobj/range/range_containes_id_less_than() ***************************
868
* range_containes_id_less_than() -- is one id less than given id
872
* range_containes_id_less_than(const lListElem *range, u_long32 id)
875
* This function tests if at least one id in "range" is less
879
* const lListElem *range - RN_Type element
880
* u_long32 id - number
883
* bool - true or false
884
******************************************************************************/
885
bool range_containes_id_less_than(const lListElem *range, u_long32 id)
889
DENTER(RANGE_LAYER, "range_containes_id_less_than");
891
u_long32 start, end, step;
893
range_get_all_ids(range, &start, &end, &step);
901
/****** sgeobj/range/range_is_id_within() *************************************
903
* range_is_id_within() -- Is id contained in range?
906
* bool range_is_id_within(const lListElem *range, u_long32 id)
909
* True is returned by this function if 'id' is part of 'range'
912
* const lListElem *range - RN_Type element
916
* bool - true or false
919
* sgeobj/range/RN_Type
922
* MT-NOTE: range_is_id_within() is MT safe
923
******************************************************************************/
924
bool range_is_id_within(const lListElem *range, u_long32 id)
928
DENTER(RANGE_LAYER, "range_is_id_within");
930
u_long32 start, end, step;
932
range_get_all_ids(range, &start, &end, &step);
933
if (id >= start && id <= end && ((id - start) % step) == 0) {
940
/****** sgeobj/range/range_list_remove_id() ***********************************
942
* range_list_remove_id() -- remove an id from a range list
946
* range_list_remove_id(lList **range_list, lList **answer_list,
950
* 'id' will be removed from 'range_list'.
953
* lList **range_list - pointer to a RN_Type list
954
* lList **answer_list - pointer to a AN_Type list
955
* u_long32 id - new id
958
* range_list and answer_list may be modified
961
* sgeobj/range/RN_Type
962
******************************************************************************/
963
void range_list_remove_id(lList **range_list, lList **answer_list, u_long32 id)
965
lListElem *range = NULL;
967
DENTER(RANGE_LAYER, "range_list_remove_id");
968
if (range_list != NULL && *range_list != NULL) {
969
lListElem *next_range = lFirst(*range_list);
971
while ((range = next_range) != NULL) {
972
u_long32 start, end, step;
974
next_range = lNext(range);
975
range_get_all_ids(range, &start, &end, &step);
976
if (id >= start && id <= end && ((id - start) % step) == 0) {
977
if ((id == start) && ((id == end) || (id + step > end))) {
978
lRemoveElem(*range_list, &range);
980
} else if (id == start) {
982
range_set_all_ids(range, start, end, step);
984
} else if (id == end) {
986
range_set_all_ids(range, start, end, step);
989
lListElem *new_range = lCreateElem(RN_Type);
991
if (new_range != NULL) {
992
range_set_all_ids(range, start, id - step, step);
993
range_set_all_ids(new_range, id + step, end, step);
994
lInsertElem(*range_list, range, new_range);
996
answer_list_add(answer_list, "unable to split range element",
997
STATUS_ERROR1, ANSWER_QUALITY_ERROR);
1003
if (lGetNumberOfElem(*range_list) == 0) {
1004
lFreeList(range_list);
1010
/****** sgeobj/range/range_list_move_first_n_ids() ****************************
1012
* range_list_move_first_n_ids() -- split a range list
1015
* void range_list_move_first_n_ids(lList **range_list,
1016
* lList **answer_list,
1017
* lList **range_list2,
1021
* The first 'n' ids within 'range_list' will be moved into
1022
* 'range_list2'. Error messages may be found in 'answer_list'
1025
* lList **range_list - pointer to a RN_Type list (source)
1026
* lList **answer_list - pointer to an AN_Type list
1027
* lList **range_list2 - pointer to a RN_Type list (destination)
1028
* u_long32 n - number of ids
1031
* range_list, range_list2, answer_list may be modified
1034
* sgeobj/range/RN_Type
1035
******************************************************************************/
1036
void range_list_move_first_n_ids(lList **range_list, lList **answer_list,
1037
lList **range_list2, u_long32 n)
1039
DENTER(RANGE_LAYER, "range_list_move_first_n_ids");
1040
if (range_list && *range_list && range_list2) {
1041
lListElem *range = NULL;
1044
for_each(range, *range_list) {
1045
for (id = lGetUlong(range, RN_min);
1046
id <= lGetUlong(range, RN_max);
1047
id += lGetUlong(range, RN_step)) {
1048
range_list_insert_id(range_list2, answer_list, id);
1049
range_list_compress(*range_list2);
1056
for_each(range, *range_list2) {
1057
for (id = lGetUlong(range, RN_min);
1058
id <= lGetUlong(range, RN_max);
1059
id += lGetUlong(range, RN_step)) {
1060
range_list_remove_id(range_list, answer_list, id);
1067
/****** sgeobj/range/range_list_insert_id() ***********************************
1069
* range_list_insert_id() -- insert an id into a range list
1072
* void range_list_insert_id(lList **range_list, lList **answer_list,
1076
* 'id' will be inserted into 'range_list'.
1079
* lList **range_list - pointer to a RN_Type list
1080
* lList **answer_list - pointer to a AN_Type list
1081
* u_long32 id - new id
1084
* It may be possible that 'id' is multiply contained in 'range_list'
1085
* after using this function. Use range_list_compress() or
1086
* range_list_sort_uniq_compress() to eliminate them.
1089
* range_list and answer_list may be modified
1092
* sgeobj/range/RN_Type
1093
* sgeobj/range/range_list_compress()
1094
* sgeobj/range/range_list_sort_uniq_compress()
1097
* MT-NOTE: range_list_insert_id() is MT safe
1098
******************************************************************************/
1099
void range_list_insert_id(lList **range_list, lList **answer_list, u_long32 id)
1101
lListElem *range, *prev_range, *next_range;
1104
DENTER(RANGE_LAYER, "range_insert_id");
1106
lPSortList(*range_list, "%I+", RN_min);
1109
if (*range_list == NULL) {
1110
*range_list = lCreateList("task_id_range", RN_Type);
1111
if (*range_list == NULL) {
1112
answer_list_add(answer_list, "unable to insert id into range",
1113
STATUS_ERROR1, ANSWER_QUALITY_ERROR);
1116
prev_range = lLast(*range_list);
1117
while ((next_range = range, range = prev_range)) {
1118
u_long32 start, end, step;
1119
u_long32 prev_start, prev_end, prev_step;
1120
u_long32 next_start, next_end, next_step;
1122
prev_range = lPrev(range);
1123
range_get_all_ids(range, &start, &end, &step);
1137
range_get_all_ids(next_range, &next_start, &next_end, &next_step);
1140
range_get_all_ids(prev_range, &prev_start, &prev_end, &prev_step);
1144
if (next_range && id > next_start) {
1145
if (((id - next_start) % next_step == 0)) {
1146
/* id is already part of the range */
1149
lListElem *new_range1, *new_range2;
1150
u_long32 factor, prev_id, next_id;
1152
factor = ((id - next_start) / next_step);
1153
prev_id = next_start + factor * next_step;
1154
next_id = next_start + (factor + 1) * next_step;
1155
range_set_all_ids(next_range, next_start, prev_id, next_step);
1156
new_range1 = lCreateElem(RN_Type);
1157
range_set_all_ids(new_range1, id, id, 1);
1158
lInsertElem(*range_list, next_range, new_range1);
1159
new_range2 = lCreateElem(RN_Type);
1160
range_set_all_ids(new_range2, next_id, next_end, next_step);
1161
lInsertElem(*range_list, new_range1, new_range2);
1165
if ((range && (end == id)) || (next_range && (next_start == id))) {
1166
/* id is already part of the range */
1168
} else if (range && (end + step == id)) {
1171
range_set_all_ids(range, start, end, step);
1173
} else if (next_range && (next_start - next_step == id)) {
1176
range_set_all_ids(next_range, next_start, next_end, next_step);
1179
lListElem *new_range;
1182
new_range = lCreateElem(RN_Type);
1183
range_set_all_ids(new_range, id, id, 1);
1184
lInsertElem(*range_list, range, new_range);
1193
lListElem *new_range;
1195
new_range = lCreateElem(RN_Type);
1196
range_set_all_ids(new_range, id, id, 1);
1197
lAppendElem(*range_list, new_range);
1203
/****** sgeobj/range/range_get_all_ids() **************************************
1205
* range_get_all_ids() -- reads 'start', 'end' and 'step'
1208
* void range_get_all_ids(const lListElem *range, u_long32 *min,
1209
* u_long32 *max, u_long32 *step)
1212
* Reads 'min' (start), 'max' (end) and 'step' from a range element.
1213
* If 'range' is NULL then 'min', 'max' and 'step' will be set to 0.
1216
* const lListElem *range - range element of type RN_Type
1217
* u_long32 *min - start value
1218
* u_long32 *max - end value
1219
* u_long32 *step - step size
1222
* sgeobj/range/RN_Type
1225
* MT-NOTE: range_get_all_ids() is MT safe
1226
******************************************************************************/
1227
void range_get_all_ids(const lListElem *range, u_long32 *min, u_long32 *max,
1230
DENTER(RANGE_LAYER, "range_get_all_ids");
1231
if (min != NULL && max != NULL && step != NULL) {
1232
if (range != NULL) {
1233
*min = lGetUlong(range, RN_min);
1234
*max = lGetUlong(range, RN_max);
1235
*step = lGetUlong(range, RN_step);
1237
*min = *max = *step = 0;
1243
/****** sgeobj/range/range_set_all_ids() **************************************
1245
* range_set_all_ids() -- writes 'start', 'end' and 'step'
1248
* void range_set_all_ids(lListElem *range, u_long32 min,
1249
* u_long32 max, u_long32 step)
1252
* Writes 'min' (start), 'max' (end) and 'step' into a range element
1255
* lListElem *range - range element of type RN_Type
1256
* u_long32 min - start value
1257
* u_long32 max - end value
1258
* u_long32 step - step size
1261
* Step values will be nomalized. (e.g. 1-1:3 => 1-1:1)
1264
* sgeobj/range/RN_Type
1267
* MT-NOTE: range_set_all_ids() is MT safe
1268
******************************************************************************/
1269
void range_set_all_ids(lListElem *range, u_long32 min, u_long32 max,
1272
DENTER(RANGE_LAYER, "range_set_all_ids");
1273
if (range != NULL) {
1274
lSetUlong(range, RN_min, min);
1275
lSetUlong(range, RN_max, max);
1277
lSetUlong(range, RN_step, step);
1279
lSetUlong(range, RN_step, 1);
1285
/****** sgeobj/range/range_list_calculate_union_set() *************************
1287
* range_list_calculate_union_set() -- Union set of two range lists
1290
* void range_list_calculate_union_set(lList **range_list,
1291
* lList **answer_list,
1292
* const lList *range_list1,
1293
* const lList *range_list2)
1296
* All ids contained in 'range_list1' and 'range_list2' will be
1297
* contained in 'range_list' after a call of this function.
1301
* lList **range_list - pointer to union set RN_Type list
1302
* lList **answer_list - pointer to AN_Type list
1303
* const lList *range_list1 - first source RN_Type list
1304
* const lList *range_list2 - second source RN_Type list
1307
* range_list and answer_list may be modified
1310
* sgeobj/range/RN_Type
1311
******************************************************************************/
1312
void range_list_calculate_union_set(lList **range_list,
1313
lList **answer_list,
1314
const lList *range_list1,
1315
const lList *range_list2)
1317
DENTER(RANGE_LAYER, "range_list_calculate_union_set");
1318
if (range_list != NULL && (range_list1 != NULL || range_list2 != NULL)) {
1319
lFreeList(range_list);
1321
if (range_list1 != NULL) {
1322
*range_list = lCopyList("", range_list1);
1324
*range_list = lCopyList("", range_list2);
1326
if (*range_list == NULL) {
1331
range_list_sort_uniq_compress(*range_list, answer_list, true);
1332
if (answer_list_has_error(answer_list)) {
1337
if (range_list1 != NULL && range_list2 != NULL) {
1338
lListElem *range2 = NULL;
1340
for_each(range2, range_list2) {
1341
u_long32 start2, end2, step2;
1343
range_get_all_ids(range2, &start2, &end2, &step2);
1344
for (; start2 <= end2; start2 += step2) {
1345
range_list_insert_id(range_list, answer_list, start2);
1348
range_list_compress(*range_list);
1354
lFreeList(range_list);
1355
answer_list_add(answer_list, "unable to calculate union set",
1356
STATUS_ERROR1, ANSWER_QUALITY_ERROR);
1360
/****** sgeobj/range/range_list_calculate_difference_set() ********************
1362
* range_list_calculate_difference_set() -- Difference set list
1365
* void range_list_calculate_difference_set(lList **range_list,
1366
* lList **answer_list,
1367
* const lList *range_list1,
1368
* const lList *range_list2)
1371
* 'range_list' will contain all ids part of 'range_list1' but not
1372
* contained in 'range_list2'
1375
* lList **range_list - pointer to result RN_Type list
1376
* lList **answer_list - pointer to AN_Type list
1377
* const lList *range_list1 - first source RN_Type list
1378
* const lList *range_list2 - second source RN_Type list
1381
* sgeobj/range/RN_Type
1382
******************************************************************************/
1383
void range_list_calculate_difference_set(lList **range_list,
1384
lList **answer_list,
1385
const lList *range_list1,
1386
const lList *range_list2)
1388
DENTER(RANGE_LAYER, "range_list_calculate_difference_set");
1389
if (range_list != NULL && range_list1 != NULL) {
1390
lFreeList(range_list);
1391
*range_list = lCopyList("difference_set range list", range_list1);
1392
if (*range_list == NULL) {
1396
range_list_sort_uniq_compress(*range_list, answer_list, true);
1397
if (answer_list_has_error(answer_list)) {
1401
if (range_list2 != NULL) {
1402
lListElem *range2 = NULL;
1404
for_each(range2, range_list2) {
1405
u_long32 start2, end2, step2;
1407
range_get_all_ids(range2, &start2, &end2, &step2);
1408
for (; start2 <= end2; start2 += step2) {
1409
range_list_remove_id(range_list, answer_list, start2);
1410
if (answer_list_has_error(answer_list)) {
1415
range_list_compress(*range_list);
1421
lFreeList(range_list);
1422
answer_list_add(answer_list, "unable to calculate union set",
1423
STATUS_ERROR1, ANSWER_QUALITY_ERROR);
1427
/****** sgeobj/range/range_list_calculate_intersection_set() ******************
1429
* range_list_calculate_intersection_set() -- Intersection set
1432
* void range_list_calculate_intersection_set(lList **range_list,
1433
* lList **answer_list,
1434
* const lList *range_list1,
1435
* const lList *range_list2)
1438
* 'range_list' will contain all ids which are contained in
1439
* 'range_list1' and also in 'range_list2'.
1442
* lList **range_list - pointer to result RN_Type list
1443
* lList **answer_list - pointer to AN_Type list
1444
* const lList *range_list1 - first source RN_Type list
1445
* const lList *range_list2 - second source RN_Type list
1448
* sgeobj/range/RN_Type
1449
******************************************************************************/
1450
void range_list_calculate_intersection_set(lList **range_list,
1451
lList **answer_list,
1452
const lList *range_list1,
1453
const lList *range_list2)
1455
DENTER(RANGE_LAYER, "range_list_calculate_intersection_set");
1456
lFreeList(range_list);
1457
if (range_list1 && range_list2) {
1460
for_each(range, range_list1) {
1461
u_long32 start, end, step;
1463
range_get_all_ids(range, &start, &end, &step);
1464
for (; start <= end; start += step) {
1465
if (range_list_is_id_within(range_list2, start)) {
1466
lListElem *new_range;
1468
if (*range_list == NULL) {
1469
*range_list = lCreateList("", RN_Type);
1470
if (*range_list == NULL) {
1474
new_range = lCreateElem(RN_Type);
1475
if (new_range == NULL) {
1478
range_set_all_ids(new_range, start, start, 1);
1479
lAppendElem(*range_list, new_range);
1483
range_list_compress(*range_list);
1488
lFreeList(range_list);
1489
answer_list_add(answer_list, "unable to calculate intersection set",
1490
STATUS_ERROR1, ANSWER_QUALITY_ERROR);
1494
/****** sgeobj/range/range_to_dstring() **************************************
1496
* range_to_dstring() -- Appends a range to a dynamic string
1499
* void range_to_dstring(u_long32 start,
1502
* dstring *dyn_taskrange_str)
1505
* Appends a range to a dynamic string.
1508
* u_long32 start - min id
1509
* u_long32 end - max id
1510
* int step - step size
1511
* dstring *dyn_taskrange_str - dynamic string
1512
* int ignore_step - ignore step for output
1513
* bool use_comma_as_separator - use a comma instead of '-' and ':' for separation
1514
* bool print_always_as_range - even if the range has only one id
1517
* sgeobj/range/RN_Type
1518
******************************************************************************/
1519
void range_to_dstring(u_long32 start, u_long32 end, int step,
1520
dstring * dyn_taskrange_str, int ignore_step,
1521
bool use_comma_as_separator, bool print_always_as_range)
1523
char tail[256] = "";
1525
char step_char = ':';
1527
if (use_comma_as_separator) {
1531
if (dyn_taskrange_str->length > 0) {
1532
sge_dstring_append(dyn_taskrange_str, ",");
1535
if (start == end && !print_always_as_range) {
1536
sprintf(tail, sge_u32, start);
1537
} else if (start == end && print_always_as_range) {
1538
sprintf(tail, sge_u32 "%c" sge_u32, start, to_char, end);
1539
} else if (start + step == end) {
1540
sprintf(tail, sge_u32 "," sge_u32, start, end);
1543
sprintf(tail, sge_u32 "%c" sge_u32, start, to_char, end);
1545
sprintf(tail, sge_u32 "%c" sge_u32 "%c%d", start, to_char, end, step_char, step);
1548
sge_dstring_append(dyn_taskrange_str, tail);
1551
/* MT-NOTE: range_parse_from_string() is MT safe */
1552
void range_parse_from_string(lListElem **range,
1553
lList **answer_list,
1555
int step_allowed, int inf_allowed)
1557
const char *old_str;
1559
u_long32 rmin, rmax, ldummy, step = 1;
1563
DENTER(TOP_LAYER, "range_parse_from_string");
1567
if (!strcasecmp(rstr, "UNDEFINED")) {
1571
r = lCreateElem(RN_Type);
1574
if (rstr[0] == '-') {
1575
/* rstr e.g. is "-<n>" ==> min=1 */
1578
if (*rstr == '\0') {
1580
/* rstr is just "-" <==> "1-inf" */
1581
lSetUlong(r, RN_min, rmin);
1582
lSetUlong(r, RN_max, RANGE_INFINITY);
1592
/* rstr should point to a decimal now */
1593
ldummy = strtol(rstr, &dptr, 10);
1594
if ((ldummy == 0) && (rstr == dptr)) {
1595
sprintf(msg, MSG_GDI_INITIALPORTIONSTRINGNODECIMAL_S, rstr);
1596
answer_list_add(answer_list, msg, STATUS_ESYNTAX, ANSWER_QUALITY_ERROR);
1603
/* rstr is "-<n>" and ldummy contains <n>
1604
* dptr poits right after <n>.
1606
if (*dptr != '\0' || (step_allowed && *dptr != ':')) {
1607
sprintf(msg, MSG_GDI_RANGESPECIFIERWITHUNKNOWNTRAILER_SS,
1609
answer_list_add(answer_list, msg, STATUS_ESYNTAX, ANSWER_QUALITY_ERROR);
1614
/* <n> is the max-value */
1617
} else { /* rmin==0) */
1619
** rstr is "<n>" or "<n>-..." and ldummy contains <n>
1620
** dptr poits right after <n>.
1622
if (*dptr == '\0') {
1623
/* rstr is just "<n>" */
1627
/* rstr should be "<n>-..." */
1629
(*dptr == '-' || isdigit((int) *(dptr + 1)) || *(dptr + 1) == '\0'
1630
|| (step_allowed && *dptr == ':'))) {
1632
sprintf(msg, MSG_GDI_RANGESPECIFIERWITHUNKNOWNTRAILER_SS,
1634
answer_list_add(answer_list, msg, STATUS_ESYNTAX, ANSWER_QUALITY_ERROR);
1639
/* it is. set min to ldummy. now, what's after the - */
1642
if (*rstr == '\0') {
1643
/* the range string was "<n>-" <==> "ldummy-inf" */
1645
rmax = RANGE_INFINITY;
1651
/* the trailer should contain a decimal - go for it */
1652
ldummy = strtol(rstr, &dptr, 10);
1653
if ((ldummy == 0) && (rstr == dptr)) {
1654
sprintf(msg, MSG_GDI_INITIALPORTIONSTRINGNODECIMAL_S, rstr);
1655
answer_list_add(answer_list, msg, STATUS_ESYNTAX,
1656
ANSWER_QUALITY_ERROR);
1662
if (!(*dptr == '\0' || (step_allowed && *dptr == ':'))) {
1663
sprintf(msg, MSG_GDI_RANGESPECIFIERWITHUNKNOWNTRAILER_SS,
1665
answer_list_add(answer_list, msg, STATUS_ESYNTAX,
1666
ANSWER_QUALITY_ERROR);
1671
/* finally, we got the max-value in ldummy */
1674
if (step_allowed && *dptr && *dptr == ':') {
1675
const double epsilon = 1.0E-12;
1679
dbldummy = strtod(rstr, &dptr);
1683
if (( dbldummy - ldummy > epsilon) ||
1684
((ldummy == 0) && (rstr == dptr))) {
1685
sprintf(msg, MSG_GDI_INITIALPORTIONSTRINGNODECIMAL_S,
1687
answer_list_add(answer_list, msg, STATUS_ESYNTAX,
1688
ANSWER_QUALITY_ERROR);
1694
else if (dptr == rstr) {
1695
sprintf(msg, MSG_GDI_INITIALPORTIONSTRINGNODECIMAL_S,
1697
answer_list_add(answer_list, msg, STATUS_ESYNTAX,
1698
ANSWER_QUALITY_ERROR);
1704
sprintf( msg, MSG_GDI_NEGATIVSTEP );
1705
answer_list_add(answer_list, msg, STATUS_ESYNTAX,
1706
ANSWER_QUALITY_ERROR);
1712
if (*dptr != '\0') {
1713
sprintf(msg, MSG_GDI_RANGESPECIFIERWITHUNKNOWNTRAILER_SS,
1715
answer_list_add(answer_list, msg, STATUS_ESYNTAX,
1716
ANSWER_QUALITY_ERROR);
1721
/* finally, we got the max-value in ldummy */
1725
} /* if (*rstr == '\0') -- else clause */
1726
} /* if (*dptr != '-') -- else clause */
1727
} /* if (*dptr == '\0') -- else clause */
1728
} /* if (r->min != 0) -- else clause */
1730
/* We're ready? Not quite! We still have to check whether min<=max */
1737
lSetUlong(r, RN_min, rmin);
1738
lSetUlong(r, RN_max, rmax);
1739
lSetUlong(r, RN_step, step);
1741
/* Ughhhh! Done ... */
1749
converts a range string into a range cull list
1751
an undefined range return NULL
1753
if answer_list is delivered no exit occurs instead the function fills the
1754
answer list and returns NULL, *answer_list must be NULL !
1756
MT-NOTE: range_list_parse_from_string() is MT safe
1759
range_list_parse_from_string(lList **this_list, lList **answer_list,
1760
const char *string, bool just_parse,
1761
bool step_allowed, bool inf_allowed)
1764
lListElem *range = NULL;
1765
lList *range_list = NULL;
1766
bool undefined = false, first = true;
1767
struct saved_vars_s *context = NULL;
1769
DENTER(TOP_LAYER, "range_list_parse_from_string");
1772
this_list = &range_list;
1775
for (s = sge_strtok_r(string, RANGE_SEPARATOR_CHARS, &context);
1776
s; s = sge_strtok_r(NULL, RANGE_SEPARATOR_CHARS, &context)) {
1777
if (!first && undefined) {
1778
/* first was undefined - no more ranges allowed */
1779
ERROR((SGE_EVENT, MSG_GDI_UNEXPECTEDRANGEFOLLOWINGUNDEFINED));
1780
sge_free_saved_vars(context);
1781
answer_list_add(answer_list, SGE_EVENT, STATUS_ESYNTAX,
1782
ANSWER_QUALITY_ERROR);
1787
range_parse_from_string(&range, answer_list, s,
1788
step_allowed, inf_allowed);
1790
if (range == NULL) {
1794
/* second range may not be undefined ! */
1795
ERROR((SGE_EVENT, MSG_GDI_UNEXPECTEDUNDEFINEDFOLLOWINGRANGE));
1796
sge_free_saved_vars(context);
1797
answer_list_add(answer_list, SGE_EVENT, STATUS_ESYNTAX,
1798
ANSWER_QUALITY_ERROR);
1806
expand_range_list(range, this_list);
1813
sge_free_saved_vars(context);
added
removed
source/libs/sgeobj/sge_range.c
