Add list and iter data types to libsepol

As part of some work to improve the parser in checkpolicy and module data structures in libsepol, I have implemented doubly-linked list and iterator data types. The attached patch adds these to libsepol.

I would appreciate feedback on these before I submit larger patches that make use of them. In particular:

* Is the iterator concept acceptable (I plan to add iterator support to other data types including hashtabs)?

As part of some work to improve the parser in checkpolicy and module data structures in libsepol, I have implemented doubly-linked list and iterator data types. The attached patch adds these to libsepol.

I would appreciate feedback on these before I submit larger patches that make use of them. In particular:

* Is the iterator concept acceptable (I plan to add iterator support to other data types including hashtabs)?

* We've discussed dropping the use of typedefs on structs (which I do in this patch). Is this what we want to do, or should I add typedefs?

Quoted 5 lines · Karl MacMillan

As part of some work to improve the parser in checkpolicy and module data structures in libsepol, I have implemented doubly-linked list and iterator data types. The attached patch adds these to libsepol.

I would appreciate feedback on these before I submit larger patches that make use of them. In particular:

* Is the iterator concept acceptable (I plan to add iterator support to other data types including hashtabs)?

How does this compare with Kevin Carr's previous iterator proposal?

How
does it compare with the existing _iterate functions in libsepol?

Quoted 1 line

* We've discussed dropping the use of typedefs on structs (which I do in this patch). Is this what we want to do, or should I add typedefs?

Omitting typedefs is preferred I think.

Quoted 5 lines · Stephen Smalley

Quoted 4 lines · Karl MacMillan

As part of some work to improve the parser in checkpolicy and module data structures in libsepol, I have implemented doubly-linked list and iterator data types. The attached patch adds these to libsepol.

Quoted 7 lines

Quoted 5 lines

I would appreciate feedback on these before I submit larger patches that make use of them. In particular:

* Is the iterator concept acceptable (I plan to add iterator support to other data types including hashtabs)?

How does this compare with Kevin Carr's previous iterator proposal?

Different implementations and - as far as I remember - different design. Same basic idea, though.

Quoted 3 lines

How
does it compare with the existing _iterate functions in libsepol?

The iterate functions (which are basically the same as the hashtab callbacks) have the same basic goal of allowing external callers to iterate over the elements of a data structure without exposing the implementation of the data structure. To me, the _iterate functions and callbacks have a few problems solved by the iterators:

* Defining callbacks is cumbersome and ofter requires defining data structures for passing complex state (see link.c).

* Iterating through nested data structures using callbacks is even more painful (see semodule_deps.c for an example of where callbacks would have been almost unusable).

* Iterating through multiple, related data structures with the callbacks is also difficult or impossible. Think of what the equivalent callbacks for the example below would be like (simplified):

int reta, retb;
struct sepol_iter *itera, *iterb;
struct sepol_list *a, *b;

reta = sepol_list_begin(a, itera);
retb = sepol_list_begin(b, iterb);

while (reta == SEPOL_OK && retb == SEPOL_OK) {
	// do something with the data
	sepol_iter_next(itera);
	sepol_iter_next(iterb);
}

* Controlling the traversal (e.g., only visiting every other element or stopping traversal) is cumbersome.

* Inserting or removing elements into data structures via callbacks is also problematic. At best the performance will be worse. The iterators I am proposing can hold whatever state is needed for fast insertion / deletion while with the callbacks it is hard to connect the callback driver function state (e.g., hashtab_map) with the insertion / deletion functions. The hashtab_map_remove_on_error function does work around this, but mixing insertion and deletions would be very difficult. See test-list.c for an example of how the iterators help with this.

The summary, I think, is that these are a better model overall which is why it is a popular approach (at least in non-C languages). Granted, the situation is that the callbacks are working for our current needs. So I'm not asking for this to be merged without code actually using it (which is coming) - just if there are any fundamental objections.