/* str-llist.c: implementation of a linked list of strings. Copyright 1993, 2008 Karl Berry. This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, see . */ #include #include /* Add the new string STR to the end of the list L. */ void str_llist_add (str_llist_type *l, string str) { str_llist_elt_type *e; str_llist_elt_type *new_elt = XTALLOC1 (str_llist_elt_type); /* The new element will be at the end of the list. */ STR_LLIST (*new_elt) = str; STR_LLIST_MOVED (*new_elt) = false; STR_LLIST_NEXT (*new_elt) = NULL; /* Find the current end of the list. */ for (e = *l; e && STR_LLIST_NEXT (*e); e = STR_LLIST_NEXT (*e)) ; if (!e) *l = new_elt; else STR_LLIST_NEXT (*e) = new_elt; } /* Move an element towards the top. The idea is that when a file is found in a given directory, later files will likely be in that same directory, and looking for the file in all the directories in between is thus a waste. */ void str_llist_float (str_llist_type *l, str_llist_elt_type *mover) { str_llist_elt_type *last_moved, *unmoved; /* If we've already moved this element, never mind. */ if (STR_LLIST_MOVED (*mover)) return; /* Find the first unmoved element (to insert before). We're guaranteed this will terminate, since MOVER itself is currently unmoved, and it must be in L (by hypothesis). */ for (last_moved = NULL, unmoved = *l; STR_LLIST_MOVED (*unmoved); last_moved = unmoved, unmoved = STR_LLIST_NEXT (*unmoved)) ; /* If we are the first unmoved element, nothing to relink. */ if (unmoved != mover) { /* Remember `mover's current successor, so we can relink `mover's predecessor to it. */ str_llist_elt_type *before_mover; str_llist_elt_type *after_mover = STR_LLIST_NEXT (*mover); /* Find `mover's predecessor. */ for (before_mover = unmoved; STR_LLIST_NEXT (*before_mover) != mover; before_mover = STR_LLIST_NEXT (*before_mover)) ; /* `before_mover' now links to `after_mover'. */ STR_LLIST_NEXT (*before_mover) = after_mover; /* Insert `mover' before `unmoved' and after `last_moved' (or at the head of the list). */ STR_LLIST_NEXT (*mover) = unmoved; if (!last_moved) *l = mover; else STR_LLIST_NEXT (*last_moved) = mover; } /* We've moved it. */ STR_LLIST_MOVED (*mover) = true; }