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   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)
11   any later version.
12
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.
17
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.  */
22
23/* Specification. */
24#include "keyword-list.h"
25
26#include <stddef.h>
27
28/* -------------------------- Keyword_List class --------------------------- */
29
30/* Constructor.  */
31Keyword_List::Keyword_List (Keyword *car)
32  : _cdr (NULL), _car (car)
33{
34}
35
36/* ------------------------- KeywordExt_List class ------------------------- */
37
38/* Constructor.  */
39KeywordExt_List::KeywordExt_List (KeywordExt *car)
40  : Keyword_List (car)
41{
42}
43
44/* ------------------------ Keyword_List functions ------------------------- */
45
46/* Copies a linear list, sharing the list elements.  */
47Keyword_List *
48copy_list (Keyword_List *list)
49{
50  Keyword_List *result;
51  Keyword_List **lastp = &result;
52  while (list != NULL)
53    {
54      Keyword_List *new_cons = new Keyword_List (list->first());
55      *lastp = new_cons;
56      lastp = &new_cons->rest();
57      list = list->rest();
58    }
59  *lastp = NULL;
60  return result;
61}
62
63/* Copies a linear list, sharing the list elements.  */
64KeywordExt_List *
65copy_list (KeywordExt_List *list)
66{
67  return static_cast<KeywordExt_List *> (copy_list (static_cast<Keyword_List *> (list)));
68}
69
70/* Deletes a linear list, keeping the list elements in memory.  */
71void
72delete_list (Keyword_List *list)
73{
74  while (list != NULL)
75    {
76      Keyword_List *rest = list->rest();
77      delete list;
78      list = rest;
79    }
80}
81
82/* Type of a comparison function.  */
83typedef bool (*Keyword_Comparison) (Keyword *keyword1, Keyword *keyword2);
84
85/* Merges two sorted lists together to form one sorted list.  */
86static Keyword_List *
87merge (Keyword_List *list1, Keyword_List *list2, Keyword_Comparison less)
88{
89  Keyword_List *result;
90  Keyword_List **resultp = &result;
91  for (;;)
92    {
93      if (!list1)
94        {
95          *resultp = list2;
96          break;
97        }
98      if (!list2)
99        {
100          *resultp = list1;
101          break;
102        }
103      if (less (list2->first(), list1->first()))
104        {
105          *resultp = list2;
106          resultp = &list2->rest();
107          /* We would have a stable sorting if the next line would read:
108             list2 = *resultp;  */
109          list2 = list1; list1 = *resultp;
110        }
111      else
112        {
113          *resultp = list1;
114          resultp = &list1->rest();
115          list1 = *resultp;
116        }
117    }
118  return result;
119}
120
121/* Sorts a linear list, given a comparison function.
122   Note: This uses a variant of mergesort that is *not* a stable sorting
123   algorithm.  */
124Keyword_List *
125mergesort_list (Keyword_List *list, Keyword_Comparison less)
126{
127  if (list == NULL || list->rest() == NULL)
128    /* List of length 0 or 1.  Nothing to do.  */
129    return list;
130  else
131    {
132      /* Determine a list node in the middle.  */
133      Keyword_List *middle = list;
134      for (Keyword_List *temp = list->rest();;)
135        {
136          temp = temp->rest();
137          if (temp == NULL)
138            break;
139          temp = temp->rest();
140          middle = middle->rest();
141          if (temp == NULL)
142            break;
143        }
144
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;
150
151      /* Sort the two halves, then merge them.  */
152      return merge (mergesort_list (list, less),
153                    mergesort_list (right_half, less),
154                    less);
155    }
156}
157
158KeywordExt_List *
159mergesort_list (KeywordExt_List *list,
160                bool (*less) (KeywordExt *keyword1, KeywordExt *keyword2))
161{
162  return
163    static_cast<KeywordExt_List *>
164      (mergesort_list (static_cast<Keyword_List *> (list),
165                       reinterpret_cast<Keyword_Comparison> (less)));
166}
167
168
169#ifndef __OPTIMIZE__
170
171#define INLINE /* not inline */
172#include "keyword-list.icc"
173#undef INLINE
174
175#endif /* not defined __OPTIMIZE__ */
176