1 /* str-llist.c: implementation of a linked list of strings.
3 Copyright 1993, 2008 Karl Berry.
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public License
16 along with this library; if not, see <http://www.gnu.org/licenses/>. */
18 #include <kpathsea/config.h>
20 #include <kpathsea/str-llist.h>
23 /* Add the new string STR to the end of the list L. */
26 str_llist_add (str_llist_type
*l
, string str
)
28 str_llist_elt_type
*e
;
29 str_llist_elt_type
*new_elt
= XTALLOC1 (str_llist_elt_type
);
31 /* The new element will be at the end of the list. */
32 STR_LLIST (*new_elt
) = str
;
33 STR_LLIST_MOVED (*new_elt
) = false;
34 STR_LLIST_NEXT (*new_elt
) = NULL
;
36 /* Find the current end of the list. */
37 for (e
= *l
; e
&& STR_LLIST_NEXT (*e
); e
= STR_LLIST_NEXT (*e
))
43 STR_LLIST_NEXT (*e
) = new_elt
;
46 /* Move an element towards the top. The idea is that when a file is
47 found in a given directory, later files will likely be in that same
48 directory, and looking for the file in all the directories in between
52 str_llist_float (str_llist_type
*l
, str_llist_elt_type
*mover
)
54 str_llist_elt_type
*last_moved
, *unmoved
;
56 /* If we've already moved this element, never mind. */
57 if (STR_LLIST_MOVED (*mover
))
60 /* Find the first unmoved element (to insert before). We're
61 guaranteed this will terminate, since MOVER itself is currently
62 unmoved, and it must be in L (by hypothesis). */
63 for (last_moved
= NULL
, unmoved
= *l
; STR_LLIST_MOVED (*unmoved
);
64 last_moved
= unmoved
, unmoved
= STR_LLIST_NEXT (*unmoved
))
67 /* If we are the first unmoved element, nothing to relink. */
69 { /* Remember `mover's current successor, so we can relink `mover's
71 str_llist_elt_type
*before_mover
;
72 str_llist_elt_type
*after_mover
= STR_LLIST_NEXT (*mover
);
74 /* Find `mover's predecessor. */
75 for (before_mover
= unmoved
; STR_LLIST_NEXT (*before_mover
) != mover
;
76 before_mover
= STR_LLIST_NEXT (*before_mover
))
79 /* `before_mover' now links to `after_mover'. */
80 STR_LLIST_NEXT (*before_mover
) = after_mover
;
82 /* Insert `mover' before `unmoved' and after `last_moved' (or at
83 the head of the list). */
84 STR_LLIST_NEXT (*mover
) = unmoved
;
88 STR_LLIST_NEXT (*last_moved
) = mover
;
92 STR_LLIST_MOVED (*mover
) = true;