contrib/gperf/src/keyword-list.cc

   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.  */
  31 Keyword_List::Keyword_List (Keyword *car)
  32   : _cdr (NULL), _car (car)
  33 {
  34 }
  35
  36 /* ------------------------- KeywordExt_List class ------------------------- */
  37
  38 /* Constructor.  */
  39 KeywordExt_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.  */
  47 Keyword_List *
  48 copy_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.  */
  64 KeywordExt_List *
  65 copy_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.  */
  71 void
  72 delete_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.  */
  83 typedef bool (*Keyword_Comparison) (Keyword *keyword1, Keyword *keyword2);
  84
  85 /* Merges two sorted lists together to form one sorted list.  */
  86 static Keyword_List *
  87 merge (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.  */
 124 Keyword_List *
 125 mergesort_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
 158 KeywordExt_List *
 159 mergesort_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__ */