3 Copyright (C) 2002 Free Software Foundation, Inc.
4 Written by Bruno Haible <bruno@clisp.org>.
6 This file is part of GNU GPERF.
8 GNU GPERF 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 2, or (at your option)
13 GNU GPERF 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.
18 You should have received a copy of the GNU General Public License
19 along with this program; see the file COPYING.
20 If not, write to the Free Software Foundation, Inc.,
21 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
24 #include "keyword-list.h"
28 /* -------------------------- Keyword_List class --------------------------- */
31 Keyword_List::Keyword_List (Keyword *car)
32 : _cdr (NULL), _car (car)
36 /* ------------------------- KeywordExt_List class ------------------------- */
39 KeywordExt_List::KeywordExt_List (KeywordExt *car)
44 /* ------------------------ Keyword_List functions ------------------------- */
46 /* Copies a linear list, sharing the list elements. */
48 copy_list (Keyword_List *list)
51 Keyword_List **lastp = &result;
54 Keyword_List *new_cons = new Keyword_List (list->first());
56 lastp = &new_cons->rest();
63 /* Copies a linear list, sharing the list elements. */
65 copy_list (KeywordExt_List *list)
67 return static_cast<KeywordExt_List *> (copy_list (static_cast<Keyword_List *> (list)));
70 /* Deletes a linear list, keeping the list elements in memory. */
72 delete_list (Keyword_List *list)
76 Keyword_List *rest = list->rest();
82 /* Type of a comparison function. */
83 typedef bool (*Keyword_Comparison) (Keyword *keyword1, Keyword *keyword2);
85 /* Merges two sorted lists together to form one sorted list. */
87 merge (Keyword_List *list1, Keyword_List *list2, Keyword_Comparison less)
90 Keyword_List **resultp = &result;
103 if (less (list2->first(), list1->first()))
106 resultp = &list2->rest();
107 /* We would have a stable sorting if the next line would read:
109 list2 = list1; list1 = *resultp;
114 resultp = &list1->rest();
121 /* Sorts a linear list, given a comparison function.
122 Note: This uses a variant of mergesort that is *not* a stable sorting
125 mergesort_list (Keyword_List *list, Keyword_Comparison less)
127 if (list == NULL || list->rest() == NULL)
128 /* List of length 0 or 1. Nothing to do. */
132 /* Determine a list node in the middle. */
133 Keyword_List *middle = list;
134 for (Keyword_List *temp = list->rest();;)
140 middle = middle->rest();
145 /* Cut the list into two halves.
146 If the list has n elements, the left half has ceiling(n/2) elements
147 and the right half has floor(n/2) elements. */
148 Keyword_List *right_half = middle->rest();
149 middle->rest() = NULL;
151 /* Sort the two halves, then merge them. */
152 return merge (mergesort_list (list, less),
153 mergesort_list (right_half, less),
159 mergesort_list (KeywordExt_List *list,
160 bool (*less) (KeywordExt *keyword1, KeywordExt *keyword2))
163 static_cast<KeywordExt_List *>
164 (mergesort_list (static_cast<Keyword_List *> (list),
165 reinterpret_cast<Keyword_Comparison> (less)));
171 #define INLINE /* not inline */
172 #include "keyword-list.icc"
175 #endif /* not defined __OPTIMIZE__ */