1 | /* Keyword list. |
2 | |
3 | Copyright (C) 2002 Free Software Foundation, Inc. |
4 | Written by Bruno Haible <bruno@clisp.org>. |
5 | |
6 | This file is part of GNU GPERF. |
7 | |
8 | This program is free software: you can redistribute it and/or modify |
9 | it under the terms of the GNU General Public License as published by |
10 | the Free Software Foundation; either version 3 of the License, or |
11 | (at your option) any later version. |
12 | |
13 | This program is distributed in the hope that it will be useful, |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
16 | GNU General Public License for more details. |
17 | |
18 | You should have received a copy of the GNU General Public License |
19 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
20 | |
21 | /* Specification. */ |
22 | #include "keyword-list.h" |
23 | |
24 | #include <stddef.h> |
25 | |
26 | /* -------------------------- Keyword_List class --------------------------- */ |
27 | |
28 | /* Constructor. */ |
29 | Keyword_List::Keyword_List (Keyword *car) |
30 | : _cdr (NULL), _car (car) |
31 | { |
32 | } |
33 | |
34 | /* ------------------------- KeywordExt_List class ------------------------- */ |
35 | |
36 | /* Constructor. */ |
37 | KeywordExt_List::KeywordExt_List (KeywordExt *car) |
38 | : Keyword_List (car) |
39 | { |
40 | } |
41 | |
42 | /* ------------------------ Keyword_List functions ------------------------- */ |
43 | |
44 | /* Copies a linear list, sharing the list elements. */ |
45 | Keyword_List * |
46 | copy_list (Keyword_List *list) |
47 | { |
48 | Keyword_List *result; |
49 | Keyword_List **lastp = &result; |
50 | while (list != NULL) |
51 | { |
52 | Keyword_List *new_cons = new Keyword_List (list->first()); |
53 | *lastp = new_cons; |
54 | lastp = &new_cons->rest(); |
55 | list = list->rest(); |
56 | } |
57 | *lastp = NULL; |
58 | return result; |
59 | } |
60 | |
61 | /* Copies a linear list, sharing the list elements. */ |
62 | KeywordExt_List * |
63 | copy_list (KeywordExt_List *list) |
64 | { |
65 | return static_cast<KeywordExt_List *> (copy_list (static_cast<Keyword_List *> (list))); |
66 | } |
67 | |
68 | /* Deletes a linear list, keeping the list elements in memory. */ |
69 | void |
70 | delete_list (Keyword_List *list) |
71 | { |
72 | while (list != NULL) |
73 | { |
74 | Keyword_List *rest = list->rest(); |
75 | delete list; |
76 | list = rest; |
77 | } |
78 | } |
79 | |
80 | /* Type of a comparison function. */ |
81 | typedef bool (*Keyword_Comparison) (Keyword *keyword1, Keyword *keyword2); |
82 | |
83 | /* Merges two sorted lists together to form one sorted list. */ |
84 | static Keyword_List * |
85 | merge (Keyword_List *list1, Keyword_List *list2, Keyword_Comparison less) |
86 | { |
87 | Keyword_List *result; |
88 | Keyword_List **resultp = &result; |
89 | for (;;) |
90 | { |
91 | if (!list1) |
92 | { |
93 | *resultp = list2; |
94 | break; |
95 | } |
96 | if (!list2) |
97 | { |
98 | *resultp = list1; |
99 | break; |
100 | } |
101 | if (less (list2->first(), list1->first())) |
102 | { |
103 | *resultp = list2; |
104 | resultp = &list2->rest(); |
105 | /* We would have a stable sorting if the next line would read: |
106 | list2 = *resultp; */ |
107 | list2 = list1; list1 = *resultp; |
108 | } |
109 | else |
110 | { |
111 | *resultp = list1; |
112 | resultp = &list1->rest(); |
113 | list1 = *resultp; |
114 | } |
115 | } |
116 | return result; |
117 | } |
118 | |
119 | /* Sorts a linear list, given a comparison function. |
120 | Note: This uses a variant of mergesort that is *not* a stable sorting |
121 | algorithm. */ |
122 | Keyword_List * |
123 | mergesort_list (Keyword_List *list, Keyword_Comparison less) |
124 | { |
125 | if (list == NULL || list->rest() == NULL) |
126 | /* List of length 0 or 1. Nothing to do. */ |
127 | return list; |
128 | else |
129 | { |
130 | /* Determine a list node in the middle. */ |
131 | Keyword_List *middle = list; |
132 | for (Keyword_List *temp = list->rest();;) |
133 | { |
134 | temp = temp->rest(); |
135 | if (temp == NULL) |
136 | break; |
137 | temp = temp->rest(); |
138 | middle = middle->rest(); |
139 | if (temp == NULL) |
140 | break; |
141 | } |
142 | |
143 | /* Cut the list into two halves. |
144 | If the list has n elements, the left half has ceiling(n/2) elements |
145 | and the right half has floor(n/2) elements. */ |
146 | Keyword_List *right_half = middle->rest(); |
147 | middle->rest() = NULL; |
148 | |
149 | /* Sort the two halves, then merge them. */ |
150 | return merge (mergesort_list (list, less), |
151 | mergesort_list (right_half, less), |
152 | less); |
153 | } |
154 | } |
155 | |
156 | KeywordExt_List * |
157 | mergesort_list (KeywordExt_List *list, |
158 | bool (*less) (KeywordExt *keyword1, KeywordExt *keyword2)) |
159 | { |
160 | return |
161 | static_cast<KeywordExt_List *> |
162 | (mergesort_list (static_cast<Keyword_List *> (list), |
163 | reinterpret_cast<Keyword_Comparison> (less))); |
164 | } |
165 | |
166 | |
167 | #ifndef __OPTIMIZE__ |
168 | |
169 | #define INLINE /* not inline */ |
170 | #include "keyword-list.icc" |
171 | #undef INLINE |
172 | |
173 | #endif /* not defined __OPTIMIZE__ */ |
174 | |