1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
/* 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 <http://www.gnu.org/licenses/>. */
#include <kpathsea/config.h>
#include <kpathsea/str-llist.h>
/* 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;
}
|
