Generic combinatorics library.

Supports:

Usage examples:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

struct igt_collection *set;
struct igt_collection *subset;
struct igt_collection_iter *iter;

int i;
set = igt_collection_create(4);
iter = igt_collection_iter_init(set, 2, SUBSET);
//iter = igt_collection_iter_init(set, 2, COMBINATION);
//iter = igt_collection_iter_init(set, 2, VARIATION_R);
//iter = igt_collection_iter_init(set, 2, VARIATION_NR);

for (i = 0; i < set->size; i++) {
     igt_collection_set_value(set, i, i + 1);
     igt_collection_set_pointer(set, i, &i + i);
}

while ((subset = igt_collection_iter_next(iter))) {
     // --- do sth with subset ---
     // --- subset is a part of iterator, so don't free it! ---
}

igt_collection_iter_destroy(iter);
igt_collection_destroy(set);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

struct igt_collection *set;
struct igt_collection *subset, *result;
struct igt_collection_data *data;

for_each_subset(subset, subset_size, set)
      // --- do sth with subset ---

for_each_combination(subset, subset_size, set)
      // --- do sth with subset ---

for_each_variation_r(result, result_size, set)
      // --- do sth with result ---

for_each_variation_nr(result, result_size, set)
      // --- do sth with result ---

// macro for iteration over set data - for_each_collection_data()
for_each_subset(subset, subset_size, set)
      for_each_collection_data(data, subset)
            printf("v: %d, p: %p\n", data->value, data->ptr);

igt_collection_create ()

struct igt_collection *
igt_collection_create (int size);

Function creates a collection (set) containing igt_collection_data elements.

igt_collection_duplicate ()

struct igt_collection *
igt_collection_duplicate (const struct igt_collection *src);

Function duplicates collection. Useful to cover multithreading when different threads need to get it's own copy of the collection acquired during iteration.

igt_collection_destroy ()

void
igt_collection_destroy (struct igt_collection *set);

Function frees collection memory.

igt_collection_set_value ()

void
igt_collection_set_value (struct igt_collection *set,
                          int index,
                          int value);

Assign new value to the collection element at index .

igt_collection_get_value ()

int
igt_collection_get_value (struct igt_collection *set,
                          int index);

igt_collection_set_pointer ()

void
igt_collection_set_pointer (struct igt_collection *set,
                            int index,
                            void *ptr);

igt_collection_get_pointer ()

void *
igt_collection_get_pointer (struct igt_collection *set,
                            int index);

igt_collection_iter_create ()

struct igt_collection_iter *
igt_collection_iter_create (const struct igt_collection *set,
                            int subset_size,
                            enum igt_collection_iter_algo algorithm);

Function creates iterator which contains result collection changed each time igt_collection_iter_next() is called. For variations without repetitions (VARIATION_R) result collection size can be larger than size of base collection (although still less or equal IGT_COLLECTION_MAXSIZE). As result collection is a part of the iterator to be thread-safe igt_collection_duplicate() must be called to make result collection copy before passing it to the thread.

igt_collection_iter_destroy ()

void
igt_collection_iter_destroy (struct igt_collection_iter *iter);

Function frees iterator memory.

igt_collection_iter_next ()

struct igt_collection *
igt_collection_iter_next (struct igt_collection_iter *iter);

Function iterates over collection regarding to algorithm selected during iterator creation returning collection (subset or tuples (for variations)).

igt_collection_iter_next_or_end ()

struct igt_collection *
igt_collection_iter_next_or_end (struct igt_collection_iter *iter);

Function does the same as igt_collection_iter_next() but additionally checks when the iterator is no longer valid and frees it then. Useful for for_each_* macros to avoid necessity of manual handling the iterator.

for_each_subset()

#define             for_each_subset(__result, __size, __set)

for_each_combination()

#define             for_each_combination(__result, __size, __set)

for_each_variation_r()

#define             for_each_variation_r(__result, __size, __set)

for_each_variation_nr()

#define             for_each_variation_nr(__result, __size, __set)

for_each_collection_data()

#define             for_each_collection_data(__data, __set)

IGT_COLLECTION_MAXSIZE

#define IGT_COLLECTION_MAXSIZE 16

enum igt_collection_iter_algo

struct igt_collection_data

struct igt_collection_data {
	int value;
	void *ptr;
};

struct igt_collection

struct igt_collection {
	int size;
	struct igt_collection_data set[IGT_COLLECTION_MAXSIZE];
};

struct igt_collection_iter

struct igt_collection_iter;