1228060Sbapt/* Keyword list. 2228060Sbapt 3228060Sbapt Copyright (C) 2002 Free Software Foundation, Inc. 4228060Sbapt Written by Bruno Haible <bruno@clisp.org>. 5228060Sbapt 6228060Sbapt This file is part of GNU GPERF. 7228060Sbapt 8228060Sbapt GNU GPERF is free software; you can redistribute it and/or modify 9228060Sbapt it under the terms of the GNU General Public License as published by 10228060Sbapt the Free Software Foundation; either version 2, or (at your option) 11228060Sbapt any later version. 12228060Sbapt 13228060Sbapt GNU GPERF is distributed in the hope that it will be useful, 14228060Sbapt but WITHOUT ANY WARRANTY; without even the implied warranty of 15228060Sbapt MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16228060Sbapt GNU General Public License for more details. 17228060Sbapt 18228060Sbapt You should have received a copy of the GNU General Public License 19228060Sbapt along with this program; see the file COPYING. 20228060Sbapt If not, write to the Free Software Foundation, Inc., 21228060Sbapt 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 22228060Sbapt 23228060Sbapt/* Specification. */ 24228060Sbapt#include "keyword-list.h" 25228060Sbapt 26228060Sbapt#include <stddef.h> 27228060Sbapt 28228060Sbapt/* -------------------------- Keyword_List class --------------------------- */ 29228060Sbapt 30228060Sbapt/* Constructor. */ 31228060SbaptKeyword_List::Keyword_List (Keyword *car) 32228060Sbapt : _cdr (NULL), _car (car) 33228060Sbapt{ 34228060Sbapt} 35228060Sbapt 36228060Sbapt/* ------------------------- KeywordExt_List class ------------------------- */ 37228060Sbapt 38228060Sbapt/* Constructor. */ 39228060SbaptKeywordExt_List::KeywordExt_List (KeywordExt *car) 40228060Sbapt : Keyword_List (car) 41228060Sbapt{ 42228060Sbapt} 43228060Sbapt 44228060Sbapt/* ------------------------ Keyword_List functions ------------------------- */ 45228060Sbapt 46228060Sbapt/* Copies a linear list, sharing the list elements. */ 47228060SbaptKeyword_List * 48228060Sbaptcopy_list (Keyword_List *list) 49228060Sbapt{ 50228060Sbapt Keyword_List *result; 51228060Sbapt Keyword_List **lastp = &result; 52228060Sbapt while (list != NULL) 53228060Sbapt { 54228060Sbapt Keyword_List *new_cons = new Keyword_List (list->first()); 55228060Sbapt *lastp = new_cons; 56228060Sbapt lastp = &new_cons->rest(); 57228060Sbapt list = list->rest(); 58228060Sbapt } 59228060Sbapt *lastp = NULL; 60228060Sbapt return result; 61228060Sbapt} 62228060Sbapt 63228060Sbapt/* Copies a linear list, sharing the list elements. */ 64228060SbaptKeywordExt_List * 65228060Sbaptcopy_list (KeywordExt_List *list) 66228060Sbapt{ 67228060Sbapt return static_cast<KeywordExt_List *> (copy_list (static_cast<Keyword_List *> (list))); 68228060Sbapt} 69228060Sbapt 70228060Sbapt/* Deletes a linear list, keeping the list elements in memory. */ 71228060Sbaptvoid 72228060Sbaptdelete_list (Keyword_List *list) 73228060Sbapt{ 74228060Sbapt while (list != NULL) 75228060Sbapt { 76228060Sbapt Keyword_List *rest = list->rest(); 77228060Sbapt delete list; 78228060Sbapt list = rest; 79228060Sbapt } 80228060Sbapt} 81228060Sbapt 82228060Sbapt/* Type of a comparison function. */ 83228060Sbapttypedef bool (*Keyword_Comparison) (Keyword *keyword1, Keyword *keyword2); 84228060Sbapt 85228060Sbapt/* Merges two sorted lists together to form one sorted list. */ 86228060Sbaptstatic Keyword_List * 87228060Sbaptmerge (Keyword_List *list1, Keyword_List *list2, Keyword_Comparison less) 88228060Sbapt{ 89228060Sbapt Keyword_List *result; 90228060Sbapt Keyword_List **resultp = &result; 91228060Sbapt for (;;) 92228060Sbapt { 93228060Sbapt if (!list1) 94228060Sbapt { 95228060Sbapt *resultp = list2; 96228060Sbapt break; 97228060Sbapt } 98228060Sbapt if (!list2) 99228060Sbapt { 100228060Sbapt *resultp = list1; 101228060Sbapt break; 102228060Sbapt } 103228060Sbapt if (less (list2->first(), list1->first())) 104228060Sbapt { 105228060Sbapt *resultp = list2; 106228060Sbapt resultp = &list2->rest(); 107228060Sbapt /* We would have a stable sorting if the next line would read: 108228060Sbapt list2 = *resultp; */ 109228060Sbapt list2 = list1; list1 = *resultp; 110228060Sbapt } 111228060Sbapt else 112228060Sbapt { 113228060Sbapt *resultp = list1; 114228060Sbapt resultp = &list1->rest(); 115228060Sbapt list1 = *resultp; 116228060Sbapt } 117228060Sbapt } 118228060Sbapt return result; 119228060Sbapt} 120228060Sbapt 121228060Sbapt/* Sorts a linear list, given a comparison function. 122228060Sbapt Note: This uses a variant of mergesort that is *not* a stable sorting 123228060Sbapt algorithm. */ 124228060SbaptKeyword_List * 125228060Sbaptmergesort_list (Keyword_List *list, Keyword_Comparison less) 126228060Sbapt{ 127228060Sbapt if (list == NULL || list->rest() == NULL) 128228060Sbapt /* List of length 0 or 1. Nothing to do. */ 129228060Sbapt return list; 130228060Sbapt else 131228060Sbapt { 132228060Sbapt /* Determine a list node in the middle. */ 133228060Sbapt Keyword_List *middle = list; 134228060Sbapt for (Keyword_List *temp = list->rest();;) 135228060Sbapt { 136228060Sbapt temp = temp->rest(); 137228060Sbapt if (temp == NULL) 138228060Sbapt break; 139228060Sbapt temp = temp->rest(); 140228060Sbapt middle = middle->rest(); 141228060Sbapt if (temp == NULL) 142228060Sbapt break; 143228060Sbapt } 144228060Sbapt 145228060Sbapt /* Cut the list into two halves. 146228060Sbapt If the list has n elements, the left half has ceiling(n/2) elements 147228060Sbapt and the right half has floor(n/2) elements. */ 148228060Sbapt Keyword_List *right_half = middle->rest(); 149228060Sbapt middle->rest() = NULL; 150228060Sbapt 151228060Sbapt /* Sort the two halves, then merge them. */ 152228060Sbapt return merge (mergesort_list (list, less), 153228060Sbapt mergesort_list (right_half, less), 154228060Sbapt less); 155228060Sbapt } 156228060Sbapt} 157228060Sbapt 158228060SbaptKeywordExt_List * 159228060Sbaptmergesort_list (KeywordExt_List *list, 160228060Sbapt bool (*less) (KeywordExt *keyword1, KeywordExt *keyword2)) 161228060Sbapt{ 162228060Sbapt return 163228060Sbapt static_cast<KeywordExt_List *> 164228060Sbapt (mergesort_list (static_cast<Keyword_List *> (list), 165228060Sbapt reinterpret_cast<Keyword_Comparison> (less))); 166228060Sbapt} 167228060Sbapt 168228060Sbapt 169228060Sbapt#ifndef __OPTIMIZE__ 170228060Sbapt 171228060Sbapt#define INLINE /* not inline */ 172228060Sbapt#include "keyword-list.icc" 173228060Sbapt#undef INLINE 174228060Sbapt 175228060Sbapt#endif /* not defined __OPTIMIZE__ */ 176