I have a single linked list of elements. Each element has a unique ID (positive integer) and a type. Each element may have a "sister" element, associated by its ID, that may also be in the list. The sister element is always of a fixed type and it does not have its own sister. The sister element may be in another list as well.

I have a function to destroy an element of a certain type. This perform some cleanup operation on the element and remove it from the list. That destroy function should also destroy its sister element. The function may also destroy all elements of a certain type, when passed ID==-1.

I'm currently using BSD's SLIST, so it looks like this:

destroy_element(list, type, ID) {
   struct elem *item, *tmp_item 
   SLIST_FOREACH_SAFE(item, list, next, tmp_item) {
       if((item->type == type) && (ID==-1 || item->ID == ID) {
           cleanup_for_element(item);
           if (item->sister_ID != -1) {
               destroy_element(item->sister_list, item->sister_ID);
           }
           SLIST_REMOVE(list, item);
       }
   }
}

SLIST_FOREACH_SAFE makes it possible to remove the current elem ('item'), but unfortunately this will crash in some case, if the sister element is in the same list (ie: list==item->sister_list) and in the wrong spot (in this particular case, if the sister element is just after the element in the list)

I'm looking for a better construct here. For SLIST in particular, but in term of general algorithm as well.

Edit:

I was wondering if this "walk the list twice" solution is safe:

destroy_element(list, type, ID) {
   struct elem *item, *tmp_item 
   SLIST_FOREACH_SAFE(item, list, next, tmp_item) {
       if((item->type == type) && (ID==-1 || item->ID == ID) {
           if (item->sister_ID != -1) {
               destroy_element(item->sister_list, item->sister_ID);
           }
       }
   }
   SLIST_FOREACH_SAFE(item, list, next, tmp_item) {
       if((item->type == type) && (ID==-1 || item->ID == ID) {
           cleanup_for_element(item);
           SLIST_REMOVE(list, item);
       }
   }
}

It seems to work (ie: crash is gone), but I'm not sure it's a guarantee in all cases.

up vote 3 down vote accepted

The bug is caused by a (somewhat) complex interaction between:

SLIST_FORACH_SAFE, and the recursive invocation of destroy_element, and the removal that they each do.

SLIST_FOREACH_SAFE makes itself "safe" to delete the current element, by caching a copy of the next element after this one — and it does this basically before your part of the loop body.  Thus, unlike SLIST_FOREACH, it does not rely on the current object being valid when it continues the loop for the next iteration, but it does rely on the next after item being still valid, since it is caching that!

However, in your case, the recursive call may destroy the cached element, thus, that element is no longer valid.

I don't think the double traversal will fix this problem (it may change the behavior but it still will have a logic error) since the wrong cached value of next will still be used in the first loop (as the result of the sister's removal during the recursive invocation).

I suppose you could fix this in several ways:

(a) write your own version of the for loop.  Copying from the template of the SLIST_FOREACH:

for (item = SLIST_FIRST(list);
    item;
    /*item = SLIST_NEXT(item, next)*/) {
    if((item->type == type) && (ID==-1 || item->ID == ID) {
        cleanup_for_element(item);
        if (item->sister_ID != -1) {
            destroy_element(item->sister_list, item->sister_ID);
        }
        item = SLIST_NEXT(item, next);
        SLIST_REMOVE(list, item);
   }
   else {
       item = SLIST_NEXT(item, next);
   }
}

(b) reload the cached value after the recursive invocation

destroy_element(list, type, ID) {
   struct elem *item, *tmp_item 
   SLIST_FOREACH_SAFE(item, list, next, tmp_item) {
       if((item->type == type) && (ID==-1 || item->ID == ID) {
           cleanup_for_element(item);
           if (item->sister_ID != -1) {
               destroy_element(item->sister_list, item->sister_ID);
               tmp_item = SLIST_NEXT(item, field);  // update the next item
           }
           SLIST_REMOVE(list, item);
       }
   }
}

The following two approaches capture what is to be deleted without using a recursive call, and wait until after the main loop to delete the sister:

(c) capture the sister elements to be deleted in a separate list and delete them after the main loop.  This would require a secondary list.

(d) mark the elements as "should delete" and after the main loop run thru the list one more time deleting anything marked "should delete".  This would require a boolean to capture this state.

Either of these ways could be made simpler by teasing apart the -1 magic value you're using meaning "all" from the simpler case of removing just one element .  I would separate delete_element from delete_all.  Then the delete_element can delete a sister after the main loop, without a list (and without recursion if you like).

The delete_all, can use a secondary list, or, with solid understanding of the domain, for example, iterate over all the available lists so no secondary list is needed.


As these kinds of problems are not that unique, some languages offer iterating constructs that do not allow modification of the data structure being traversed, and will fault immediately if any changes are made, even "safe" ones.


You should be aware that your single loop version traverses the list many times:

(1) the outer loop is one traversal

(2) the recursive call is another traversal

(3) the SLIST_REMOVE does another traversal

On the plus side, they early out so when they find the element they stop.

So, to remove an element with a sister, you get 4 travesals of the list, though with early out.


Reference: https://github.com/freebsd/freebsd/blob/master/sys/sys/queue.h

  • It might not be necessary to have an additional flag/bool: Setting ID to -1 might do the trick. – Deduplicator Oct 11 at 2:23
  • I think the multiple traversals for the sister elements is unavoidable in my real-world scenario, as the sister elements maybe in another list. That other list may even be in a different process or different machine. The destroy call in the real version would potentially be a RPC call. – Droopycom Oct 11 at 3:39
  • Being already inside a traversal of the list, one ought to be able to remove the current element from the list without starting an additional traversal, though I don't see support for that in the header file... – Erik Eidt Oct 11 at 13:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.