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