keyword-list.cc revision 303975
11556Srgrimes/* Keyword list. 21556Srgrimes 31556Srgrimes Copyright (C) 2002 Free Software Foundation, Inc. 41556Srgrimes Written by Bruno Haible <bruno@clisp.org>. 51556Srgrimes 61556Srgrimes This file is part of GNU GPERF. 71556Srgrimes 81556Srgrimes GNU GPERF is free software; you can redistribute it and/or modify 91556Srgrimes it under the terms of the GNU General Public License as published by 101556Srgrimes the Free Software Foundation; either version 2, or (at your option) 111556Srgrimes any later version. 121556Srgrimes 131556Srgrimes GNU GPERF is distributed in the hope that it will be useful, 141556Srgrimes but WITHOUT ANY WARRANTY; without even the implied warranty of 151556Srgrimes MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 161556Srgrimes GNU General Public License for more details. 171556Srgrimes 181556Srgrimes You should have received a copy of the GNU General Public License 191556Srgrimes along with this program; see the file COPYING. 201556Srgrimes If not, write to the Free Software Foundation, Inc., 211556Srgrimes 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 221556Srgrimes 231556Srgrimes/* Specification. */ 241556Srgrimes#include "keyword-list.h" 251556Srgrimes 261556Srgrimes#include <stddef.h> 271556Srgrimes 281556Srgrimes/* -------------------------- Keyword_List class --------------------------- */ 291556Srgrimes 301556Srgrimes/* Constructor. */ 311556SrgrimesKeyword_List::Keyword_List (Keyword *car) 321556Srgrimes : _cdr (NULL), _car (car) 331556Srgrimes{ 341556Srgrimes} 351556Srgrimes 361556Srgrimes/* ------------------------- KeywordExt_List class ------------------------- */ 371556Srgrimes 381556Srgrimes/* Constructor. */ 391556SrgrimesKeywordExt_List::KeywordExt_List (KeywordExt *car) 401556Srgrimes : Keyword_List (car) 411556Srgrimes{ 421556Srgrimes} 431556Srgrimes 441556Srgrimes/* ------------------------ Keyword_List functions ------------------------- */ 451556Srgrimes 461556Srgrimes/* Copies a linear list, sharing the list elements. */ 471556SrgrimesKeyword_List * 481556Srgrimescopy_list (Keyword_List *list) 491556Srgrimes{ 501556Srgrimes Keyword_List *result; 511556Srgrimes Keyword_List **lastp = &result; 521556Srgrimes while (list != NULL) 531556Srgrimes { 541556Srgrimes Keyword_List *new_cons = new Keyword_List (list->first()); 551556Srgrimes *lastp = new_cons; 561556Srgrimes lastp = &new_cons->rest(); 571556Srgrimes list = list->rest(); 581556Srgrimes } 591556Srgrimes *lastp = NULL; 601556Srgrimes return result; 611556Srgrimes} 621556Srgrimes 631556Srgrimes/* Copies a linear list, sharing the list elements. */ 641556SrgrimesKeywordExt_List * 651556Srgrimescopy_list (KeywordExt_List *list) 661556Srgrimes{ 671556Srgrimes return static_cast<KeywordExt_List *> (copy_list (static_cast<Keyword_List *> (list))); 681556Srgrimes} 691556Srgrimes 701556Srgrimes/* Deletes a linear list, keeping the list elements in memory. */ 711556Srgrimesvoid 721556Srgrimesdelete_list (Keyword_List *list) 731556Srgrimes{ 741556Srgrimes while (list != NULL) 751556Srgrimes { 761556Srgrimes Keyword_List *rest = list->rest(); 771556Srgrimes delete list; 781556Srgrimes list = rest; 791556Srgrimes } 801556Srgrimes} 811556Srgrimes 821556Srgrimes/* Type of a comparison function. */ 831556Srgrimestypedef bool (*Keyword_Comparison) (Keyword *keyword1, Keyword *keyword2); 841556Srgrimes 851556Srgrimes/* Merges two sorted lists together to form one sorted list. */ 861556Srgrimesstatic Keyword_List * 871556Srgrimesmerge (Keyword_List *list1, Keyword_List *list2, Keyword_Comparison less) 881556Srgrimes{ 891556Srgrimes Keyword_List *result; 901556Srgrimes Keyword_List **resultp = &result; 911556Srgrimes for (;;) 921556Srgrimes { 931556Srgrimes if (!list1) 941556Srgrimes { 951556Srgrimes *resultp = list2; 961556Srgrimes break; 971556Srgrimes } 981556Srgrimes if (!list2) 991556Srgrimes { 1001556Srgrimes *resultp = list1; 1011556Srgrimes break; 1021556Srgrimes } 1031556Srgrimes if (less (list2->first(), list1->first())) 1041556Srgrimes { 1051556Srgrimes *resultp = list2; 1061556Srgrimes resultp = &list2->rest(); 1071556Srgrimes /* We would have a stable sorting if the next line would read: 1081556Srgrimes list2 = *resultp; */ 1091556Srgrimes list2 = list1; list1 = *resultp; 1101556Srgrimes } 1111556Srgrimes else 1121556Srgrimes { 1131556Srgrimes *resultp = list1; 1141556Srgrimes resultp = &list1->rest(); 1151556Srgrimes list1 = *resultp; 1161556Srgrimes } 1171556Srgrimes } 1181556Srgrimes return result; 1191556Srgrimes} 1201556Srgrimes 1211556Srgrimes/* Sorts a linear list, given a comparison function. 1221556Srgrimes Note: This uses a variant of mergesort that is *not* a stable sorting 1231556Srgrimes algorithm. */ 1241556SrgrimesKeyword_List * 1251556Srgrimesmergesort_list (Keyword_List *list, Keyword_Comparison less) 1261556Srgrimes{ 1271556Srgrimes if (list == NULL || list->rest() == NULL) 1281556Srgrimes /* List of length 0 or 1. Nothing to do. */ 1291556Srgrimes return list; 1301556Srgrimes else 1311556Srgrimes { 1321556Srgrimes /* Determine a list node in the middle. */ 1331556Srgrimes Keyword_List *middle = list; 1341556Srgrimes for (Keyword_List *temp = list->rest();;) 1351556Srgrimes { 1361556Srgrimes temp = temp->rest(); 1371556Srgrimes if (temp == NULL) 1381556Srgrimes break; 1391556Srgrimes temp = temp->rest(); 1401556Srgrimes middle = middle->rest(); 1411556Srgrimes if (temp == NULL) 1421556Srgrimes break; 1431556Srgrimes } 1441556Srgrimes 1451556Srgrimes /* Cut the list into two halves. 1461556Srgrimes If the list has n elements, the left half has ceiling(n/2) elements 1471556Srgrimes and the right half has floor(n/2) elements. */ 1481556Srgrimes Keyword_List *right_half = middle->rest(); 1491556Srgrimes middle->rest() = NULL; 1501556Srgrimes 1511556Srgrimes /* Sort the two halves, then merge them. */ 1521556Srgrimes return merge (mergesort_list (list, less), 1531556Srgrimes mergesort_list (right_half, less), 1541556Srgrimes less); 1551556Srgrimes } 1561556Srgrimes} 1571556Srgrimes 1581556SrgrimesKeywordExt_List * 1591556Srgrimesmergesort_list (KeywordExt_List *list, 1601556Srgrimes bool (*less) (KeywordExt *keyword1, KeywordExt *keyword2)) 1611556Srgrimes{ 1621556Srgrimes return 1631556Srgrimes static_cast<KeywordExt_List *> 1641556Srgrimes (mergesort_list (static_cast<Keyword_List *> (list), 1651556Srgrimes reinterpret_cast<Keyword_Comparison> (less))); 1661556Srgrimes} 1671556Srgrimes 1681556Srgrimes 1691556Srgrimes#ifndef __OPTIMIZE__ 1701556Srgrimes 1711556Srgrimes#define INLINE /* not inline */ 1721556Srgrimes#include "keyword-list.icc" 1731556Srgrimes#undef INLINE 1741556Srgrimes 1751556Srgrimes#endif /* not defined __OPTIMIZE__ */ 1761556Srgrimes