keyword-list.cc revision 302408
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