|
1268
|
1 /* str-llist.c: Implementation of a linked list of strings. |
|
|
2 |
|
|
3 Copyright (C) 1993 Karl Berry. |
|
|
4 |
|
|
5 This program is free software; you can redistribute it and/or modify |
|
|
6 it under the terms of the GNU General Public License as published by |
|
|
7 the Free Software Foundation; either version 2, or (at your option) |
|
|
8 any later version. |
|
|
9 |
|
|
10 This program 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 |
|
|
13 GNU General Public License for more details. |
|
|
14 |
|
|
15 You should have received a copy of the GNU General Public License |
|
|
16 along with this program; if not, write to the Free Software |
|
1315
|
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ |
|
1268
|
18 |
|
|
19 #include <kpathsea/config.h> |
|
|
20 |
|
|
21 #include <kpathsea/str-llist.h> |
|
|
22 |
|
|
23 |
|
|
24 /* Add the new string STR to the end of the list L. */ |
|
|
25 |
|
|
26 void |
|
|
27 str_llist_add P2C(str_llist_type *, l, string, str) |
|
|
28 { |
|
|
29 str_llist_elt_type *e; |
|
|
30 str_llist_elt_type *new_elt = XTALLOC1 (str_llist_elt_type); |
|
|
31 |
|
|
32 /* The new element will be at the end of the list. */ |
|
|
33 STR_LLIST (*new_elt) = str; |
|
|
34 STR_LLIST_MOVED (*new_elt) = false; |
|
|
35 STR_LLIST_NEXT (*new_elt) = NULL; |
|
|
36 |
|
|
37 /* Find the current end of the list. */ |
|
|
38 for (e = *l; e && STR_LLIST_NEXT (*e); e = STR_LLIST_NEXT (*e)) |
|
|
39 ; |
|
|
40 |
|
|
41 if (!e) |
|
|
42 *l = new_elt; |
|
|
43 else |
|
|
44 STR_LLIST_NEXT (*e) = new_elt; |
|
|
45 } |
|
|
46 |
|
|
47 /* Move an element towards the top. The idea is that when a file is |
|
|
48 found in a given directory, later files will likely be in that same |
|
|
49 directory, and looking for the file in all the directories in between |
|
|
50 is thus a waste. */ |
|
|
51 |
|
|
52 void |
|
|
53 str_llist_float P2C(str_llist_type *, l, str_llist_elt_type *, mover) |
|
|
54 { |
|
|
55 str_llist_elt_type *last_moved, *unmoved; |
|
|
56 |
|
|
57 /* If we've already moved this element, never mind. */ |
|
|
58 if (STR_LLIST_MOVED (*mover)) |
|
|
59 return; |
|
|
60 |
|
|
61 /* Find the first unmoved element (to insert before). We're |
|
|
62 guaranteed this will terminate, since MOVER itself is currently |
|
|
63 unmoved, and it must be in L (by hypothesis). */ |
|
|
64 for (last_moved = NULL, unmoved = *l; STR_LLIST_MOVED (*unmoved); |
|
|
65 last_moved = unmoved, unmoved = STR_LLIST_NEXT (*unmoved)) |
|
|
66 ; |
|
|
67 |
|
|
68 /* If we are the first unmoved element, nothing to relink. */ |
|
|
69 if (unmoved != mover) |
|
|
70 { /* Remember `mover's current successor, so we can relink `mover's |
|
|
71 predecessor to it. */ |
|
|
72 str_llist_elt_type *before_mover; |
|
|
73 str_llist_elt_type *after_mover = STR_LLIST_NEXT (*mover); |
|
|
74 |
|
|
75 /* Find `mover's predecessor. */ |
|
|
76 for (before_mover = unmoved; STR_LLIST_NEXT (*before_mover) != mover; |
|
|
77 before_mover = STR_LLIST_NEXT (*before_mover)) |
|
|
78 ; |
|
|
79 |
|
|
80 /* `before_mover' now links to `after_mover'. */ |
|
|
81 STR_LLIST_NEXT (*before_mover) = after_mover; |
|
|
82 |
|
|
83 /* Insert `mover' before `unmoved' and after `last_moved' (or at |
|
|
84 the head of the list). */ |
|
|
85 STR_LLIST_NEXT (*mover) = unmoved; |
|
|
86 if (!last_moved) |
|
|
87 *l = mover; |
|
|
88 else |
|
|
89 STR_LLIST_NEXT (*last_moved) = mover; |
|
|
90 } |
|
|
91 |
|
|
92 /* We've moved it. */ |
|
|
93 STR_LLIST_MOVED (*mover) = true; |
|
|
94 } |
