aboutsummaryrefslogtreecommitdiffstats
path: root/src/keyword-list.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/keyword-list.cc')
-rw-r--r--src/keyword-list.cc175
1 files changed, 175 insertions, 0 deletions
diff --git a/src/keyword-list.cc b/src/keyword-list.cc
new file mode 100644
index 000000000000..ac559f7933d2
--- /dev/null
+++ b/src/keyword-list.cc
@@ -0,0 +1,175 @@
+/* Keyword list.
+
+ Copyright (C) 2002 Free Software Foundation, Inc.
+ Written by Bruno Haible <bruno@clisp.org>.
+
+ This file is part of GNU GPERF.
+
+ GNU GPERF is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ GNU GPERF is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; see the file COPYING.
+ If not, write to the Free Software Foundation, Inc.,
+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
+
+/* Specification. */
+#include "keyword-list.h"
+
+#include <stddef.h>
+
+/* -------------------------- Keyword_List class --------------------------- */
+
+/* Constructor. */
+Keyword_List::Keyword_List (Keyword *car)
+ : _cdr (NULL), _car (car)
+{
+}
+
+/* ------------------------- KeywordExt_List class ------------------------- */
+
+/* Constructor. */
+KeywordExt_List::KeywordExt_List (KeywordExt *car)
+ : Keyword_List (car)
+{
+}
+
+/* ------------------------ Keyword_List functions ------------------------- */
+
+/* Copies a linear list, sharing the list elements. */
+Keyword_List *
+copy_list (Keyword_List *list)
+{
+ Keyword_List *result;
+ Keyword_List **lastp = &result;
+ while (list != NULL)
+ {
+ Keyword_List *new_cons = new Keyword_List (list->first());
+ *lastp = new_cons;
+ lastp = &new_cons->rest();
+ list = list->rest();
+ }
+ *lastp = NULL;
+ return result;
+}
+
+/* Copies a linear list, sharing the list elements. */
+KeywordExt_List *
+copy_list (KeywordExt_List *list)
+{
+ return static_cast<KeywordExt_List *> (copy_list (static_cast<Keyword_List *> (list)));
+}
+
+/* Deletes a linear list, keeping the list elements in memory. */
+void
+delete_list (Keyword_List *list)
+{
+ while (list != NULL)
+ {
+ Keyword_List *rest = list->rest();
+ delete list;
+ list = rest;
+ }
+}
+
+/* Type of a comparison function. */
+typedef bool (*Keyword_Comparison) (Keyword *keyword1, Keyword *keyword2);
+
+/* Merges two sorted lists together to form one sorted list. */
+static Keyword_List *
+merge (Keyword_List *list1, Keyword_List *list2, Keyword_Comparison less)
+{
+ Keyword_List *result;
+ Keyword_List **resultp = &result;
+ for (;;)
+ {
+ if (!list1)
+ {
+ *resultp = list2;
+ break;
+ }
+ if (!list2)
+ {
+ *resultp = list1;
+ break;
+ }
+ if (less (list2->first(), list1->first()))
+ {
+ *resultp = list2;
+ resultp = &list2->rest();
+ /* We would have a stable sorting if the next line would read:
+ list2 = *resultp; */
+ list2 = list1; list1 = *resultp;
+ }
+ else
+ {
+ *resultp = list1;
+ resultp = &list1->rest();
+ list1 = *resultp;
+ }
+ }
+ return result;
+}
+
+/* Sorts a linear list, given a comparison function.
+ Note: This uses a variant of mergesort that is *not* a stable sorting
+ algorithm. */
+Keyword_List *
+mergesort_list (Keyword_List *list, Keyword_Comparison less)
+{
+ if (list == NULL || list->rest() == NULL)
+ /* List of length 0 or 1. Nothing to do. */
+ return list;
+ else
+ {
+ /* Determine a list node in the middle. */
+ Keyword_List *middle = list;
+ for (Keyword_List *temp = list->rest();;)
+ {
+ temp = temp->rest();
+ if (temp == NULL)
+ break;
+ temp = temp->rest();
+ middle = middle->rest();
+ if (temp == NULL)
+ break;
+ }
+
+ /* Cut the list into two halves.
+ If the list has n elements, the left half has ceiling(n/2) elements
+ and the right half has floor(n/2) elements. */
+ Keyword_List *right_half = middle->rest();
+ middle->rest() = NULL;
+
+ /* Sort the two halves, then merge them. */
+ return merge (mergesort_list (list, less),
+ mergesort_list (right_half, less),
+ less);
+ }
+}
+
+KeywordExt_List *
+mergesort_list (KeywordExt_List *list,
+ bool (*less) (KeywordExt *keyword1, KeywordExt *keyword2))
+{
+ return
+ static_cast<KeywordExt_List *>
+ (mergesort_list (static_cast<Keyword_List *> (list),
+ reinterpret_cast<Keyword_Comparison> (less)));
+}
+
+
+#ifndef __OPTIMIZE__
+
+#define INLINE /* not inline */
+#include "keyword-list.icc"
+#undef INLINE
+
+#endif /* not defined __OPTIMIZE__ */