diff options
Diffstat (limited to 'src/keyword-list.cc')
| -rw-r--r-- | src/keyword-list.cc | 175 |
1 files changed, 175 insertions, 0 deletions
diff --git a/src/keyword-list.cc b/src/keyword-list.cc new file mode 100644 index 0000000000000..ac559f7933d26 --- /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__ */ |