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. */
Keyword_List(Keyword * car)29 Keyword_List::Keyword_List (Keyword *car)
30 : _cdr (NULL), _car (car)
31 {
32 }
33
34 /* ------------------------- KeywordExt_List class ------------------------- */
35
36 /* Constructor. */
KeywordExt_List(KeywordExt * car)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 *
copy_list(Keyword_List * 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 *
copy_list(KeywordExt_List * 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
delete_list(Keyword_List * list)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 *
merge(Keyword_List * list1,Keyword_List * list2,Keyword_Comparison less)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 *
mergesort_list(Keyword_List * list,Keyword_Comparison less)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 *
mergesort_list(KeywordExt_List * list,bool (* less)(KeywordExt * keyword1,KeywordExt * keyword2))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