; TeX output 2009.02.01:122033GGNj cmbx12GUser'sƧGuidetoJ߆Tj cmtt12JgperfG3.0.4G  p2K`y 3 cmr10ThefGNUP!erfectHashFeunctionGenerator Editionf3.0.4,1Feebruary2009.эYNff cmbx12YDouglasffC.SchmidtBrunoffHaible*33pGCop!yrightcf;!", 3 cmsy10 @1989-2009fFereeSoft!warefFoundation,Inc.33GP!ermission޲isޱgrantedtoޱmakeanddistributeޱverbatimcopiesofޱthismanualޱprovidedthe 33Gcop!yrightfnoticeandthispMermissionnoticearepreserv!edonallcopies.GP!ermission.is-grantedto-copyanddistribute-moMdi edversionsof-thismanual-undertheGconditions8forv!erbatimcopying,providedalsothatthesectionentitled8\GNU8)GeneralGPublic7License"isincluded7exactlyasintheoriginal,Mandpro!videdthattheen!tireresultingGderiv!edfworkisdistributedunderthetermsofapMermissionnoticeidenticaltothisone.GP!ermissionrisgrantedtoqcopyanddistributetranslationsofthisqmanualintoanotherlan-Gguage,under}MtheabMo!ve}Mconditionsfor}Nmodi edv!ersions,exceptthat}NthesectionentitledG\GNU=General=Public=License"ma!ybMeincludedinatranslationappro!ved=bytheauthorGinsteadfofintheoriginalEnglish.GGNUfGENERALPUBLICLICENSEQV133͍GPNG cmbx12PGNUzGENERALPUBLICLICENSE΍jVeersionf3,29June2007.Cop!yrightcf @2007fFereeSoft!warefFoundation,Inc.3tothewholeofthew!ork,=andallitsparts,=nregardless of ho!wtheyarepac!kdDaged.-ThisLicensegiv!esnopMermissiontolicense=nthew!orkinanyotherwaye,butitdoMesnotinvdDalidatesuchpMermissionifyouhave=nseparatelyfreceiv!edit.-d.=nIfnthenw!orkhasin!teractivenuserinterfaces,eachmustndisplayAppropriatenLegal=nNotices;ho!wever,FifRtheProgramhasin!teractiveRinterfacesthatdonotdisplay=nAppropriatefLegalNotices,y!ourworkneednotmakethemdoso.J֍'AScompilationofaco!veredworkwithotherseparateandindepMendentworks,which'areLnotb!ytheirnatureextensionsofthecoveredwork,u|andwhicharenotcombined'withUitUsuc!hastoformalargerprogram,finoronav!olumeofastorageordistribution'medium,N isPcalledan\aggregate"ifOthecompilationanditsresultingcop!yrightPare'notusedtolimittheaccessorlegalrigh!tsofthecompilation'susersbMey!ondwhatthe'individual2w!orkspMermit.InclusionofacoveredworkinanaggregatedoMesnotcause'thisfLicensetoapplytotheotherpartsoftheaggregate.?-6.'Con!veyingfNon-SourceFeorms.'Yeouvma!yconveyvacoveredworkinvobjectcoMdeformunderthetermsofsections4and'5,pro!videdthatyoualsoconveythemachine-readableCorrespMondingSourceunder'theftermsofthisLicense,inoneofthesew!ays:8sGGNUfGENERALPUBLICLICENSEQV533͍-a.=nCon!veyutheobjectcoMdein,orem!bodiedin,aph!ysicalproduct(includingaph!ys- 33=nical@#distribution@"medium),faccompaniedb!ytheCorrespMondingSource xedona=ndurablefph!ysicalmediumcustomarilyusedforsoftwareinterchange.-b.=nCon!veywthewobjectcoMdein,orem!bodiedwin,aphysicalwproMduct(includingaph!ysi-=ncaldistributionmedium),accompaniedb!yawritteno er,vdDalidforatleastthree=ny!ears!andvdDalidfor!aslongasyouo ersparepartsor!customersuppMortforthat=nproMductmodel,qtogiv!eanyonewhopMossessestheobjectcodeeither(1)acop!yof=nthe)CorrespMonding(Sourceforallthesoft!warein)theproMductthatisco!veredby)this=nLicense,6onadurableph!ysicalmediumcustomarilyusedforsoft!wareinterchange,=nfor9_apricenomorethany!our9^reasonablecostofphysicallypMerformingthiscon-=nv!eyingofsource,or(2)accesstocopytheCorrespMondingSourcefromanetwork=nserv!erfatnocharge..KMc.=nCon!veyindividualcopiesoftheobjectcoMdewithacop!yofthewritteno erto=npro!videjthejCorrespMondingSource.*ThisalternativeisallowedjonlyoMccasionally=nand+noncommerciallye,andonlyify!oureceivedtheobject*coMdewithsuchano er,=ninfaccordwithsubsection6b.-d.=nCon!veyRtheRobjectcoMdeb!yo eringaccessfromadesignatedplace(gratisorfor=nac!harge),ando erequivdDalentaccesstotheCorrespMondingSourceinthesame=nw!aypthroughthesameoplaceatnofurtherc!harge.6Yeouneednotrequirerecipien!ts=ntocop!ytheCorrespMondingSourcealongwiththeobjectcoMde.Iftheplaceto=ncop!y%the$objectcoMdeisanet!work%server,theCorrespMonding%Sourcema!ybMeon=naVdi eren!tserver(opMeratedbyyouorVathirdparty)thatsuppMortsequivdDalent=ncop!yingfacilities,+providedyoumaintaincleardirectionsnexttotheobjectcoMde=nsa!ying8where8to ndtheCorrespMondingSource.Regardlessofwhatserv!erhosts=ntheCorrespMondingSource,ty!ouremainobligatedtoensurethatitisa!vdDailablefor=nasflongasneededtosatisfytheserequiremen!ts..KMe.=nCon!veytheobjectcoMdeusingpMeer-to-peertransmission,xpro!videdyouinformother=npMeerswheretheobjectcodeandCorrespondingSourceofthew!orkarebMeingo ered=ntofthegeneralpublicatnoc!hargeundersubsection6d.΍'A$separable$0pMortion$/oftheobjectcoMde,CwhosesourcecoMdeisexcludedfromtheCor-'respMondingSourceasaSystemLibrarye,neednotbeincludedincon!veyingtheobject'coMdefw!ork.'A\UserProMduct"iseither(1)a\consumerproMduct",Ռwhic!hmeansanytangiblepMer-'sonalpropMert!ywhichisnormallyusedforpMersonal, familye,orhouseholdpurpMoses,or'(2)an!ythingdesignedorsoldforincorpMorationin!toadw!elling. Indeterminingwhether'axproMductwisaconsumerproMduct,doubtfulcasesshallbMeresolv!edinfa!vorofxcoverage.'FeoraparticularproMductreceiv!edbyaparticularuser,X\normallyused"referstoa't!ypical'orcommon&useofthatclassofproMduct,Vregardlessofthestatusofthepar-'ticular7useror7ofthew!ay7inwhich7theparticularuseractuallyuses,[orexpMectsoris'expMectedLtoMuse,theproduct.RABproductLisaconsumerproMductregardlessofwhether'theproMducthassubstan!tialcommercial, industrialornon-consumeruses, unlesssuc!h'usesfrepresen!ttheonlysigni cantmoMdeofuseoftheproduct.'\InstallationwInformation"wforaUserProMductmeansan!ymethoMds,procedures,autho-'rization`k!eys,-orother_informationrequiredtoinstallandexecutemoMdi edv!ersionsofa'co!vered|workinthatUserProMductfromamodi edv!ersionofitsCorrespondingSource.I]GGNUfGENERALPUBLICLICENSEQV633͍'Theinformationm!ustsucetoensurethatthecon!tinuedfunctioningofthemoMdi ed 33'objectcoMdeisinnocaseprev!entedorin!terferedwithsolelybMecausemodi cationhas'bMeenfmade. 'Ify!ouconveyanobjectcoMdew!orkunderthissectionin,Norwith,orspMeci callyfor'use@in,6aAUserProMduct,andtheAcon!veying@oMccursaspartofatransactioninwhic!h'theJrigh!tofJpMossessionanduseoftheUserProMductistransferredtotherecipien!tin'pMerpetuit!y6;orfora xedterm(regardlessofhowthetransactionischaracterized),'the&CorrespMondingSource'con!veyed&underthissectionm!ustbe'accompaniedb!ythe'Installation1Information.H=Butthisrequiremen!tdoMesnotapplyif0neitheryounorany'third}Wpart!yretainsthe}VabilitytoinstallmoMdi edobjectcodeon}VtheUserProduct(for'example,fthew!orkhasbMeeninstalledinROM).'TheCrequiremen!ttoprovideInstallationInformationBdoMesnotincludearequirement'tozcon!tinueytoprovidesuppMortservice,~warrantye,orupMdatesyforaworkthatyhasbMeen'moMdi edorinstalledb!ytherecipien!t,QorfortheUserProMductinwhic!hithasbMeen'moMdi edorinstalled.nAccesstoanet!workmaybMedeniedwhenthemoMdi cationitself'materiallyandadv!erselya ectstheopMerationofthenetworkorviolatestherulesand'protoMcolsfforcomm!unicationacrossthenetwork.'CorrespMondingNSourcecon!veyed,`DandNInstallationNInformationpro!vided,inaccordwith'this sectionm!ust bMeinaformatthatispubliclydoMcumen!ted(andwithanimplemen!ta-'tionEsa!vdDailabletothepublicinsourcecoMdeform),XandmustrequirenospMecialpassword'orfk!eyforunpacking,readingorcopying.-7.'AdditionalfTeerms. '\AdditionalPpMermissions"Paretermsthatsupplemen!tthetermsofthisLicenseb!ymak-'ingexceptionsfromoneormoreofitsconditions.BAdditionalpMermissionsthatare'applicable%totheen!tire$ProgramshallbMetreatedasthoughtheyw!ereincludedinthis'License,-/to:theexten!tthattheyarevdDalidunderapplicablelaw.!YIfadditionalpMermis-'sionsNapplyonlyNtopartoftheProgram,_thatpartma!ybMeusedseparatelyunderthose'pMermissions,but!theen!tireProgram remainsgovernedbythis Licensewithoutregard'toftheadditionalpMermissions.'WhengOy!ougPconveyagPcopyofgPacoveredgPwork,׉youmaygOatyourgOoptionremovegOany'additional pMermissions fromthatcop!ye,Rorfroman!ypartofit.j(AdditionalpMermissions'ma!ybMewrittentorequiretheiro!wnremovdDalincertaincaseswheny!oumoMdifythe'w!ork.)YeoufmaygplaceadditionalpMermissionsonmaterial,gaddedb!yyougtoaco!vered'w!ork,fforwhichyouhaveorcangiveappropriatecopyrightpMermission.'Not!withstandingfanyotherprovisionofthisLicense,sbformaterialyouaddtoacovered'w!ork,youmay(ifauthorizedbythecopyrightholdersofthatmaterial)supplement'theftermsofthisLicensewithterms:-a.=nDisclaimingw!arrantyorlimitingliabilitydi erentlyfromthetermsofsections15=nandf16ofthisLicense;or-b.=nRequiringpreservdDationofspMeci edreasonablelegalnoticesorauthorattributions=nin thatmaterialor intheAppropriateLegalNoticesdispla!yedby workscontaining=nit;for.KMc.=nProhibitingЈmisrepresen!tationЉoftheoriginofthatmaterial,NorrequiringthatmoMd-=ni edv!ersionsofsuchmaterialbMemarkedinreasonablewaysasdi erentfromthe=noriginalfv!ersion;or\GGNUfGENERALPUBLICLICENSEQV733͍-d.=nLimitingtheuseforpublicit!ypurpMosesofnamesoflicensorsorauthorsofthe 33=nmaterial;for?.KMe.=nDecliningDtogran!trightsDundertrademarklawforuseofDsometradenames,X:trade-=nmarks,forservicemarks;or?/Тf.=nRequiring#indemni cation#oflicensorsandauthorsofthatmaterialb!yanyone#who=ncon!veys/#thematerial(ormoMdi edv!ersions/"ofit)withcontractualassumptions=nofliabilit!ytotherecipient,foranyliabilitythatthesecontractualassumptions=ndirectlyfimpMoseonthoselicensorsandauthors.J֍'AllӋotherӊnon-pMermissiv!eadditionaltermsareconsidered\furtherrestrictions"within'theAmeaningofsectionA10.IftheProgramasy!oureceivedAit,horan!ypartofit,con-'tainsHaHnoticestatingthatitisgo!vernedbyHthisLicensealongwithatermthatisa'furtherErestriction,/y!oumayDremovethatDterm.}IfaElicensedoMcumentEcontainsaEfurther'restrictionSbutRpMermitsrelicensingorcon!veyingSunderthisLicense,y!oumayaddRtoa'co!veredFworkEmaterialgovernedEbytheEtermsofthatlicensedoMcumen!t,}providedthat'theffurtherrestrictiondoMesnotsurviv!esuchrelicensingorconveying.'IfCy!ouaddtermstoaDcoveredworkinaccordwiththissection,youmustplace,inthe'relevdDan!tsource les,!astatementoftheadditionaltermsthatapplytothose les,!ora'noticefindicatingwhereto ndtheapplicableterms.'Additionalabterms, pMermissiv!eornon-permissiv!e,!mayabbestatedinaatheformofasep-'aratelywrittenlicense,orstatedasexceptions;theabMo!verequirementsapplyeither'w!aye.?-8.'Teermination.'Yeouma!ynotpropagateormoMdifyacoveredworkexceptasexpresslyprovidedun-'derrthisrLicense.BAn!yattemptotherwisetopropagateormoMdifyitisv!oid,andwill'automaticallyterminatey!ourrightsunderthisLicense(includingan!ypatentlicenses'gran!tedfunderthethirdparagraphofsection11).'Ho!wever,ifAyou@ceaseallviolationofthisLicense,theny!ourlicensefromaparticular'cop!yrightJholderisJreinstated(a)pro!visionallye,sunlessanduntilJthecopyrightholder'explicitly_and nallyterminatesy!ourlicense,0and(b)pMermanentlye,0ifthecopyright'holder"failstonotifyy!ouoftheviolation"bysomereasonablemeanspriorto60days'afterfthecessation.?'Moreo!ver,8your licensefromaparticularcop!yright holderisreinstatedpMermanen!tlyif'theV`cop!yrightholderVanoti esyouoftheviolationVabysomereasonablemeans,fbthisisthe' rstWtimey!ouWhaveWreceivednoticeofviolationWofthisLicense(foranyWwork)fromthat'cop!yrightholder,andy!oucuretheviolationpriorto30daysafteryourreceiptofthe'notice.'TeerminationNuofy!ourrightsunderthissectionNtdoMesnotterminatethelicensesofparties'whoqha!vereceivedcopiesorrightsfromyoupunderthisLicense.Ifyourrightshave'bMeenterminatedandnotpermanen!tlyreinstated,youdonotqualifytoreceivenew'licensesfforthesamematerialundersection10.?-9.'AcceptancefNotRequiredforHa!vingCopies.'YeouarenotrequiredtoacceptthisLicenseinordertoreceiv!eorrunacop!yofthe'Program.Ancillary-propagation-ofaco!veredwork-oMccurringsolelyasaconsequenceof'usingpMeer-to-peertransmissiontoreceiv!eacopylikewisedoMesnotrequireacceptance.mGGNUfGENERALPUBLICLICENSEQV833͍'Ho!wever, -nothingotherthanthisLicensegran!tsyoupMermissiontopropagateormoMdify 33'an!ycoveredwork.Theseactionsinfringecop!yrightifyoudonotacceptthisLicense.'Therefore,|b!yŪmoMdifyingūorpropagatingaco!veredwork,|youūindicateyourūacceptance'offthisLicensetodoso. 10.'AutomaticfLicensingofDo!wnstreamRecipients.'Eac!hktimejyouconveyjacoveredwork,ktherecipientjautomaticallyreceivesjalicense 33'fromttheuoriginallicensors,torun,moMdifyandpropagatethatw!ork,subjecttothis'License.)YeoujGarenotrespMonsiblejHforenforcingcomplianceb!ythirdpartieswiththis'License. 'An5\en!tity5transaction"isatransactiontransferringcon!trolofanorganization,or'substan!tially allassetsofone,orsubMdividinganorganization,ormergingorganizations.'Ify\propagationofay]co!veredy\workresultsfromanentitytransaction,_eachpartytothat'transactionJwhoJreceiv!esacopyJoftheworkJalsoreceivesJwhateverlicensestoJthework'thedpart!y'spredecessorininteresthadorcouldgiveunderthepreviousparagraph,1plus'a.righ!tto-pMossessionoftheCorrespondingSource-ofthew!orkfromthepredecessorin'in!terest,fifthepredecessorhasitorcangetitwithreasonablee orts.'YeouEma!yEnotimpMoseanyEfurtherrestrictionsontheexerciseoftherigh!tsgrantedEor'armedJunderthisLicense.SFeorexample,]y!oumaynotimpMosealicensefee,]royaltye,or'otherMc!hargeMforexerciseofrigh!tsgrantedMunderthisLicense,_andy!oumayMnotinitiate'litigationq(includingracross-claimorcoun!terclaiminala!wsuit)allegingthatan!ypatent'claimHisHinfringedb!ymaking,[nusing,selling,[oo eringHforsale,orimpMortingHtheProgram'orfan!ypMortionofit. 11.'P!atents.'A\con!tributor"-isacopyrightholderwhoauthorizesuseunderthisLicenseofthe'Program$or$aw!orkonwhich$theProgramisbased.Y_Thew!orkthuslicensed$iscalled'thefcon!tributor's\contributorversion".'Acon!tributor's(\essential'patentclaims"areall'patentclaimsownedor'controlledby'the>con!tributor,whetheralreadyacquiredor?hereafteracquired,thatw!ouldbMeinfringed'b!yMsomeMmanner,_pMermittedbyMthisLicense,_ofmaking,using,orMsellingitscon!tributor'v!ersion,but}>do}?notincludeclaimsthatw!ouldbMeinfringedonlyasaconsequenceof'further moMdi cationof thecon!tributorversion. FeorpurpMosesofthisde nition,,\con-'trol"@includes?therigh!ttogran!tpatent@sublicensesinamannerconsisten!twiththe'requiremen!tsfofthisLicense.'Eac!hEJcontributorEKgrantsyouEKanon-exclusive,worldwide,royalty-freeEKpatentEJlicense'under@the@con!tributor'sessentialpatentclaims,Tto@make,use,sell,o er@for@sale,impMort'andfotherwiserun,moMdifyandpropagatethecon!tentsfofitscon!tributorversion.'Inmthefollo!wingthreeparagraphs,y:a\patentmlicense"isanyexpressagreementorcom-'mitmen!t,>however$denominated,not$toenforceapaten!t(suchas$anexpresspMermission'toʀpracticeaʁpaten!torcovenantnottoʁsueforpatentinfringement).J,Teo\grant"such'a*Ypaten!tlicense*Xtoapartymeansto*Xmakesuchanagreementor*Xcommitmentnotto'enforcefapaten!tagainstthepartye.'Ifey!ouconveyacoveredework,}knowinglyrelyingonapatentlicense,~andtheCorre-'spMonding{Sourceof|thew!orkisnotavdDailable|foranyonetocopye,wfreeof|chargeandunder'thetermsofthisLicense,throughapubliclya!vdDailablenetworkserverorotherreadily'accessible_means,theny!ou_must_either(1)causetheCorrespMondingSourcetobMeso ~IGGNUfGENERALPUBLICLICENSEQV933͍'a!vdDailable,or(2)arrangetodepriveyourselfofthebMene tofthepaten!tlicenseforthis 33'particularRw!ork,; or(3)Sarrange,inamannerconsisten!twiththeSrequirementsofthis'License,bto=)extendthepaten!tlicensetodownstreamrecipients.&\Knowinglyrelying"'meansy!ouhaveactualknowledgethat,jbutforthepaten!tlicense,jyourconveyingthe'co!veredzworkyinacountrye,~oryyourrecipient'suseyoftheco!veredworkinyacountrye,'w!ould8infringeoneormoreidenti ablepatentsinthatcountrythatyouhavereason'tofbMeliev!earevdDalid.΍'If,pursuan!ttoorinconnectionwithasingletransactionorarrangemen!t,youconveye,'or-ypropagateb!yproMcuringconveyanceof,O>a-xcoveredwork,O>andgrantapatentlicense'tosomeofthepartiesreceivingtheco!veredworkauthorizingthemtouse,Ħpropagate,'moMdify:or:con!veyaspMeci c:copyofthecovered:work,P0thenthe:patentlicense:yougrant'isfautomaticallyextendedtoallrecipien!tsofthecoveredworkandworksbasedonit.͍'AMpaten!tM6licenseis\discriminatory"ifitdoMesnotincludewithinthescopeofitsco!ver-'age,XprohibitsUtheexerciseTof,orisconditionedTonthenon-exerciseofoneormoreofthe'righ!tsmthatarespMeci callygrantedunderthisLicense.RYeoumaynotconveyacovered'w!orkzZifyouareapartytoanarrangementwithz[athirdpartythatisinthebusinessof'distributingsoft!ware,underwhichyoumakepaymenttothethirdpartybasedonthe'exten!t|.ofyour|/activityofconveyingthework,andunderwhichthe|/thirdpartygrants,'toan!yofthepartieswhowouldreceivethecoveredworkfromyou,>(adiscriminatory'paten!tlicense(a)inconnectionwithcopiesofthecoveredworkconveyedbyyou(or'copiesmadefromthosecopies),or(b)primarilyforandinconnectionwithspMeci c'proMducts 7or 8compilationsthatcon!tainthecovered 8work,%unlessyou 7enteredinto 7that'arrangemen!t,forthatpatentlicensewasgranted,priorto28March2007.'NothinginthisLicenseshallbMeconstruedasexcludingorlimitingan!yimpliedlicenseor'other-,defensestoinfringemen!tthatmayotherwise--bMeavdDailabletoyouunderapplicable'paten!tflaw.12.'NofSurrenderofOthers'Fereedom.͍'IfQconditionsarePimpMosedony!ou(whetherb!ycourtorder,"agreementPorotherwise)that'con!tradict theconditionsofthisLicense,'theydonotexcuseyoufromtheconditions'of_lthis_kLicense.Ify!oucannotconvey_kacovered_kworkso_kastosatisfysim!ultaneously'y!ourLobligationsunderthisLicenseandLanyotherpMertinentobligations, thenasa'consequencey!oumaynotconveyitatall.Feorexample,Tifyouagreetotermsthat'obligate&y!ou'tocollectaro!yalty&forfurthercon!veying&fromthosetowhomy!ouconvey'theCProgram,ztheBonlyw!ayCyoucouldsatisfyBbMoththosetermsandthisLicensew!ould'bMeftorefrainen!tirelyfromconveyingtheProgram.13.'UsefwiththeGNUA eroGeneralPublicLicense.͍'Not!withstandingTanyUotherprovisionofUthisLicense,youUhavepMermissiontoUlinkor'com!bineanycoveredworkwithaworklicensedunderversion3oftheGNUcA ero'GeneraliPubliciLicensein!toasinglecom!binedwork,vanditoconveytheiresultingwork.'TheeFtermsofthisLicensewillcon!tinueeFtoapplytothepartwhic!histhecoveredwork,'but@thespMecialrequiremen!tsoftheGNUA eroGeneralPublicLicense,6section13,'concerningfin!teractionthroughanetworkwillapplytothecombinationassuch.14.'RevisedfVeersionsofthisLicense. GGNUfGENERALPUBLICLICENSE׼1033͍'The:#Feree:$Soft!wareFeoundationmay:$publishrevisedand/ornewv!ersionsoftheGNU 33'GeneralPublicLicensefromtimetotime.Suc!hnewv!ersionswillbMesimilarinspirit'tofthepresen!tversion,butmaydi erindetailtoaddressnewproblemsorconcerns.] 'Eac!hZversionZisgivenZadistinguishingv!ersionnumbMer.IfZtheProgramspMeci esthat'a~certainn!umbMered~versionoftheGNU{GeneralPublicLicense\oranylaterversion"'appliesQtoPit,Ly!ouhaveQtheoptionPoffollowingthetermsPandconditionseitherofthat'n!umbMeredversionorofanylaterversionpublishedbytheFereeSoftwareFeoundation.'IftrtheProgramdoMesnotspecifyav!ersionnumbMeroftheGNUteGeneralPublicLicense,'y!oufmaychoMoseanyversioneverpublishedbytheFereeSoftwareFeoundation.'IfÌtheProgramspMeci esthatapro!xyËcandecidewhichfutureversionsoftheGNU'General2PublicLicensecanbMeused,ethatpro!xy'spublicstatementofacceptanceofa'v!ersionfpMermanentlyauthorizesyoutochoMosethatversionfortheProgram.] 'LaterVlicenseVv!ersionsmaygiveVyouadditionalVordi erentpMermissions.However,no'additionalhobligationsgareimpMosedonan!yauthororcop!yrightholderhasaresultofy!our'c!hoMosingftofollowalaterversion.15.'DisclaimerfofWearran!ty.'THEREISNOWȈARRANTYF!ORTHEPROGRAM,6TOTHEEXTENTPER-'MITTEDBYAPPLICABLELAȈW.5EX!CEPTWHENOTHERWISESTeATEDIN'WRITING THECOPYRIGHTHOLDERSAND/OROTHERPeARTIES PR!OVIDE'THEPR!OGRAM\ASIS"WITHOUTWȈARRANTYOFANYKIND,EITHEREX-'PRESSED5OR5IMPLIED,5INCLUDING,BUTNOT5LIMITEDTO,5THEIMPLIED'WȈARRANTIESOFMER!CHANTeABILITYANDFITNESSFORAPeARTICULAR'PURPOSE.ϔTHEHENTIREGRISKASTOTHEQUALITYANDPERF!ORMANCE'OFTHEPR!OGRAMISWITHYOU.SHOULDTHEPR!OGRAMPROVEDEFEC-'TIVE,jYOU:ASSUME9THECOSTOFALLNECESSAReYSERȈVICING,kREPAIROR'CORRECTION.16.'LimitationfofLiabilit!ye.] 'IN'vNOEVENT'wUNLESSREQUIREDBYAPPLICABLELAȈWORA!GREEDTOIN'WRITINGkWILLkANYCOPYRIGHTHOLDER,kORANYOTHERPeARTYkWHO'MODIFIESAND/ORCONVEYSTHEPR!OGRAMASPERMITTEDABOVE,BE'LIABLETOYOUF!ORDAMAGES,INCLUDINGANYGENERAL,SPECIAL,IN-'CIDENTeALORCONSEQUENTIALD!AMAGESARISINGOUTOFTHEUSEOR'INABILITYTOUSETHEPR!OGRAM(INCLUDINGBUTNOTLIMITEDTO'LOSSOFD!AeTAORDAeTABEINGRENDEREDINACCURAeTEORLOSSESSUS-'TeAINEDBYYOUORTHIRDPeARTIESORAFȈAILUREOFTHEPR!OGRAM'TO OPERAeTEWITHANYOTHERPR!OGRAMS), EVENIFSUCHHOLDEROR'OTHERgPeARTYHASgBEENAD!VISEDOFTHEPOSSIBILITYOFSUCHD!AM-'A!GES.17.'In!terpretationfofSections15and16.'IfJthedisclaimerofw!arrantyJandlimitationJofliabilit!yprovidedabMovecannotbMegiven'loMcalVlegale ectWaccordingtotheirterms,3reviewingcourtsshallapplyloMcalla!wthat'mostqcloselyappro!ximatesanqabsolutewaiverofallcivilliabilityqinconnectionwith'the5OProgram,Y unless5Paw!arranty5Oorassumptionofliabilit!yaccompaniesacop!yofthe'Programfinreturnforafee. xGGNUfGENERALPUBLICLICENSE׼1133͍GYENDf@OFTERMSANDCONDITIONSGHowf@toApplyTheseTfermstoYourNewPrograms33!GIfy!oudevelopanewprogram,andy!ouwantittobMeofthegreatestpMossibleuseto 33Gthepublic,@thebMestw!aytoachievethisistomakeitfreesoftwarewhicheveryonecanGredistributefandc!hangeundertheseterms.33!GTeodoso,attac!hthefollowingnoticestotheprogram.XItissafesttoattac!hthemtotheGstartjofeac!hsource letomostke ectivelystatetheexclusionofwarranty;andeach leGshouldfha!veatleastthe\copyright"lineandapMointertowherethefullnoticeisfound. .B.33 'SpMecialthanksisextendedtoMic!haelTiemannandDougLea, forpro!vidingauseful'compiler,fandforgivingmeaforumtoexhibitm!ycreation.'Inaddition,AdamdeBoMorandNelsOlsonpro!videdmanytipsandinsightsthatgreatly'helpMedfimpro!vethequalityandfunctionalityofgperf. 'Bruno>Haible>enhancedandoptimizedthesearc!halgorithm.SHealsorewrotetheinput'routinesfandtheoutputroutinesforbMetterreliabilit!ye,andaddedatestsuite. GChapterf1:In!troMduction21333͍GP1 QInutro=duction33!GgperfisapMerfecthashfunctiongeneratorwritteninC++.5Ittransformsan6p0J 3 cmsl10nelemen!t 33Guser-spMeci ed|k!eywordsetWintoapMerfecthashfunctionF.FGuniquelymapskeywordsGin4OW[on!totherange0..k,WwherekS>=n-1.Ifk=n-1then4NFisa5': 3 cmti10minimalUpMerfecthashGfunction.=gperfgeneratesa0..kp!elemen!tstaticloMokuptableandapairofCfunctions.GThese!gfunctionsdetermine!fwhetheragiv!encharacterstring!fsoMccursinW,usingatmostGonefprobMein!tothelookuptable.33!GgperfLcurren!tlygeneratesthereservedkeywordMrecognizerforlexicalanalyzersinseveralGproMductionwandvresearc!hcompilersandlanguageproMcessingtools,;includingvGNUtC,GNUGC++,GNUBJa!vdDa,GNUP!ascal,GNUMoMdula~3,andGNUCinden!t.:CompleteC++}sourcecodeGforZgperfYisa!vdDailablefromhttp://ftp.gnu.org/pub/gnu/gperf/. ApapMerdescribingGgperf'sdesignandimplemen!tationingreaterdetailisa!vdDailableintheSecondUSENIXGC++ConferenceproMceedingsorfromhttp://www.cs.wustl.edu/~schmidt/resume.html.NGChapterf2:Staticsearc!hstructuresandGNUgperf1433͍GP2 QStaticzsearcuhstructuresandGNUSgperf33!GATstaticsearc!hstructureisanAbstractDataT!ypMewithcertainfundamen!talopMerations, 33Ge.g.,initialize,insert,andkrpetrieve.Conceptuallye,allinsertionsoMccurlbeforean!yretrievdDals.GIn4practice,gperf5generatesastatic$arra!ycontainingsearch5setkeywordsand5anyassoMciatedGattributesfaspMeci edf`b!ytheuser.Thus,^thereisessentiallyf`noexecution-timecostfortheGinsertions.It@Lisausefuldata@Mstructureforrepresen!tingstaticseparchsets.Static@Lsearc!hsetsGoMccurfrequen!tlyinsoftwaresystemapplications.STypicalstaticsearchsetsincludecompilerGreserv!edwords,k=assemblerinstructionopMcodes,k=andbuilt-inshellin!terpretercommands.GSearc!hsetmembMers,Ocalledkeywords,Oareinsertedintothestructureonlyonce,OusuallyGduringfprograminitialization,andarenotgenerallymoMdi edatrun-time.33!GNumerousXdstaticsearc!hstructureimplementationsXeexist,ge.g.,arrays,linkedXdlists,binaryGsearc!hItrees,digitalsearchtries,andhashtables. Di erentapproacheso ertrade-o sGbMet!ween4spaceutilization3andsearc!htimeeciencye.FFor4example,\annelemen!tsortedGarra!yisspaceecient,thoughtheaverage-casetimecomplexityforretrievdDalopMerationsGusingbinarysearc!hispropMortionaltologn.Con!verselye,hashtableimplementationsoftenGloMcate a tableen!tryinconstan!ttime,,=buttypically impMoseadditionalmemoryo!verhead andGexhibitfpMoorw!orstcaseperformance.!GMinimal+pperfecthash+functionspro!videanoptimalsolutionforaparticularclassofstaticGsearc!hfsets.AminimalpMerfecthashfunctionisde nedbytwopropMerties: 'It"allo!ws"keywordrecognition"inastaticsearc!hsetusingatmostoneprobMein!tothe'hashftable.Thisrepresen!tsthe\pMerfect"propert!ye. 'TheSactualmemoryalloMcatedtostorethek!eywordsSispreciselylargeenoughforthe'k!eywordfset,andnolarpger.Thisisthe\minimal"propMert!ye.33!GFeor\mostapplications[itisfareasiertogeneratepperfectFhashfunctions\thanminimalGpperfect{hashqfunctions.@nMoreo!ver,non-minimalqpMerfecthashfunctionsfrequentlyexecuteGfasterDthanminimalonesinpractice. ThisphenomenaoMccurssincesearc!hingasparseGk!eywordItableJincreasestheprobabilit!yofloMcatinga\n!ull"entrye,therebyJreducingstringGcomparisons.gperf's>Qdefault>RbMeha!viorgeneratesnepar-minimal_pMerfecthashfunctionsforGk!eywordDsets.(vHowever,{gperfprovidesCmanyoptionsthatpMermituserCcontrolovertheGdegreefofminimalit!yandpMerfection.!GStaticK=searc!hsetsK>oftenexhibitrelativestabilityK>overtime.cFeorexample,tsAda's63re-Gserv!edAwordsBhaveremainedBconstantforBnearlyadecade.oItisthereforefrequen!tlyworth-Gwhile4to5expMendconcertede ortbuildinganoptimalsearc!hstructureoncpe,ifitsubsequen!tlyGreceiv!esheavyusemultipletimes.gperfremovesthedrudgeryassoMciatedwithconstructingGtime-zandzspace-ecien!tsearchzstructuresbyzhand.ZIthaszprovenazusefulandpracticalGtoMol`Qforseriousprogrammingprojects.ƀOutputfromgperfiscurren!tlyusedinseveralpro-Gductionandresearc!hcompilers,0{includingGNUC,GNUC++,0|GNUJa!vdDa,0{GNUPascal,0|andGGNU~eMoMdula~3.fThelattert!wo~compilers~arenoty!etpartoftheocialGNU~edistribu-Gtion.)Eac!hcompilerutilizesgperftoautomaticallygeneratestaticsearc!hstructuresthatGecien!tlyfidentifytheirrespMectivereservedkeywords.TGChapterf3:High-Lev!elDescriptionofGNUgperf>1533͍GP3 QHigh-LevuelzDescriptionofGNUSgperfն!GThepMerfecthashfunctiongeneratorgperfreadsasetof\k!eywords"fromaninput le 33G(orfromthestandardinputb!ydefault).&VItattemptstoderiveapMerfecthashingfunctionGthatkrecognizesamem!bMerkofthestatickeywordsetwithatmostkasingleprobMeintotheGloMokup5)table.Ifgperfsucceedsingeneratingsuc!h5(afunctionitproducesapairofC5 sourceGcoMderoutinesthatperformhashingandtablelookuprecognition.AllgeneratedCrcodeGisdirectedtothestandardoutput.Command-lineoptionsdescribMedbelo!wallowyoutoGmoMdifyftheinputandoutputformattogperf. !GBydefault,-gperfattemptstoproMducetime-ecien!tcode,-withlessemphasisonecien!tGspace'utilization. Ho!wever,severaloptionsexistthatpMermittrading-o executiontimeforGstorage=space>andvicev!ersa.XcInparticular,sexpandingthegeneratedtablesizeproMducesaGsparsesearc!hstructure,9Hgenerallyyieldingfastersearches.eConverselye,9HyoucandirectgperfGtoxutilizexaCwswitchstatemen!tschemexthatminimizesdataspacestoragesize.yFeurthermore,GusingaCϒswitchma!yactuallyspMeedupthek!eywordretrievdDaltimesomewhat.ZFActualGresultsfdepMendony!ourCcompiler,ofcourse. !GInogeneral,,gperfassignsvdDaluestotheb!ytesitisusingforhashinguntilsomesetGofvdDaluesgiv!eseachkeywordauniquevdDalue. AhelpfulheuristicisthatthelargertheGhashivdDaluerange,theeasieritisforgperfito ndandgenerateapMerfecthashfunction.GExpMerimen!tationfisthekeytogettingthemostfromgperf.QAGY3.1Inputf@Fformatto\߆Tff cmtt12\gperf33!GYeoucancon!troltheinput leformatb!yvdDaryingcertaincommand-lineargumen!ts,inGparticularthe`-t'option.Theinput'sappMearanceissimilartoGNUjutilitiesflexandGbisonf(orUNIXutilitieslexandyacc).Here'sanoutlineofthegeneralformat:.declarations.%%.keywords.%%.functionsEՍ!GUnlikeflexEsorErbison,m5thedeclarationssectionandthefunctionssectionareoptional.GTheffollo!wingsectionsdescribMetheinputformatforeachsection. !GItXispMossibletoomittheYdeclarationsectionen!tirelye,ifthe`-t'optionisnotgiv!en.InGthisfcasetheinput lebMeginsdirectlywiththe rstk!eywordfline,e.g.:.january.february.march.april....MGbN # cmbx12b3.1.1d(Declarations3!GThe#k!eyword#input leoptionallycon!tainsasectionforincludingarbitraryC#ideclara-Gtionsandde nitions,gperfdeclarationsthatactlik!ecommand-lineoptions,asw!ellasforGpro!vidingfauser-suppliedstruct.ݠGChapterf3:High-Lev!elDescriptionofGNUgperf>1633͍Gb3.1.1.1d(User-suppliedMe߆T # cmtt12estruct3!GIfthe`-t'option(or,%equivdDalen!tlye,$the`%struct-type'declaration)is,enabled,y!oumust 33Gpro!videbaCbstructastheblastcompMonentinthedeclarationsectionbfromtheinput le.GThe$ rst$ eldinthisstructm!ustbMeoft!ypMecharf*orconstchar*$ifthe`-P'optionisnotGgiv!en,oroftypMeintiftheoption`-P'(or,equivdDalen!tlye,the`%pic'declaration)isenabled.GThisB! rst eldm!ustbMecalledB"`name',ialthoughitispossibleB"tomodifyitsnamewiththeG`-K'foption(or,equivdDalen!tlye,the`%defineslot-name'declaration)describMedbelo!w.u!GHerefisasimpleexample,usingmon!thsoftheyearandtheirattributesasinput:.structmonth{char*name;intnumber;intdays;intleap_days;}; 33.%%.january,>1,31,31.february, T2,28,29.march,R3,31,31.april,R4,30,30.may,(=5,31,31.june,"}6,30,30.july,"}7,31,31.august,8,31,31.september,9,30,30.october, T10,31,31.november,11,30,30.december,12,31,31!GSeparatingRtheQstructdeclarationfromthelistofk!eywordsRandother eldsareapairof 33Gconsecutiv!e_pMercent`signs,^`%%',]appearingleft_justi edinthe rstcolumn,^asintheUNIXGutilit!yflex.u!GIf{thestructhas{alreadybMeendeclaredinaninclude le,itcanbMemen!tionedinanGabbreviatedfform,lik!ethis:u.structmonth;.%%.january,>1,31,31....@nGb3.1.1.2d(GpierfMDeclarations!GThejdeclarationsectioncankcon!taingperfdeclarations.Theyin uencethew!ayjgperfGw!orks,4likecommandlineoptionsdo.|Infact,4ev!erysuchdeclarationisequivdDalenttoaGcommandflineoption.Therearethreeformsofdeclarations:u-1.'Declarationsfwithoutargumen!t,like`%compare-lengths'.-2.'Declarationsfwithanargumen!t,like`%switch=91733͍G`%delimiters=delimiter-listDs' 33K:Allo!wssyoustoprovideastringscontainingdelimitersusedtosseparatekeywordsK:from'their'attributes.aThedefaultis",".aThisoptionisessen!tialify!ouwantK:tofusek!eywordsfthatha!vefembMeddedcommasornewlines.G`%struct-type'K:Allo!wsyoutoincludeastructtypMedeclarationforgeneratedcode;Rseeabo!veK:forfanexample.G`%ignore-case'K:ConsiderKuppMerandKlo!werKcaseASCIIKBc!haractersasequivdDalent. ͷThestringK:comparisondwillusedacaseinsigni can!tcharacterdcomparison.NotethatloMcaleK:depMenden!tfcasemappingsareignored.G`%language=language-nameDs'K:Instructs5gperf6togeneratecoMdeinthelanguagespMeci edb!ytheoption'sar-K:gumen!t.Languagesfhandledarecurrently:K:`KR-C'Old-st!yle(K&R(sC.This(languageisunderstoModb!y(old-styleC(rcom--pilersandANSICcompilers, ?butANSICcompilersma!y agw!arn--ingsf(orev!enerrors)bMecauseoflacking`const'.K:`C'-CommonÀC.ThislanguageisunderstoModÀb!yANSIGCFcompilers,and-alsoob!yoold-styleCocompilers,zprovidedothatyouo#definefconstto-empt!yfforcompilerswhichdon'tknowabMoutthiskeyword.K:`ANSI-C'=ANSIC.ThislanguageisunderstoModb!yANSIC(C89,^ISOC90)-compilers,fISOC99compilers,andC++compilers.K:`C++'"|C++.ThisflanguageisunderstoModfb!yC++compilers.K:ThefdefaultisC.G`%definefslot-namenameDs'K:ThisXdeclarationYisonlyusefulwhenoption`-t'(or, equivdDalen!tlye, theK:`%struct-type'declaration)hasbMeengiv!en.Bydefault,theprogramassumesK:thestructurecompMonen!tidenti erforthekeywordis`name'. QThisoptionK:allo!wsVmanVlarbitrarychoiceofidenti erVlforthiscompMonent,nalthoughVlitstillK:m!ustfoMccurasthe rst eldinyoursuppliedstruct.G`%definefinitializer-suffixinitializersDs'K:ThisXdeclarationYisonlyusefulwhenoption`-t'(or, equivdDalen!tlye, theK:`%struct-type'Mdeclaration)MhasbMeengiv!en.{ItpermitstoMspecifyinitializersK:forJthestructuremem!bMersfollowingslot-nameinemptyhashtableentries.K:The$list%ofinitializersshouldstartwithacomma. Bydefault,iTtheemittedK:coMdefwillzero-initializestructuremem!bersfollo!wingslot-name.G`%definefhash-function-namenameDs'K:Allo!wsIyoutospMecifythenameHforthegeneratedhashfunction.~DefaultnameK:isf`hash'.ThisoptionpMermitstheuseoft!wofhashtablesinthesame le.G`%defineflookup-function-namenameDs'K:Allo!ws LyoutospMecifythenamefor Mthegeneratedlookupfunction. DefaultK:nameV;is`in_word_set'.%ThisoptionpMermitsm!ultipleV1833͍G`%definefclass-namenameDs' 33K:Thiseoptionfisonlyusefulwhenoption`-LfC++'(or, 3equivdDalen!tlye, 3theK:`%language=C++'declaration)hasbMeengiv!en. mJItallowsyoutospMecifytheK:namefofgeneratedC++class.DefaultnameisPerfect_Hash.΍G`%7bit'KThisu'optionspMeci esu(thatallstringsthatwillbMepassedasargumen!tstotheK:generated.hashfunctionandthegenerated.loMokupfunctionwillsolelyconsistK:of7-bitASCIMIc!haracters(bytesintherange0..127).(NotethattheANSICK:functionsisalnumandisgraphdonotguaran!teethatab!yteisinthisrange.K:Onlyfanexplicittestlik!e`c>='A'&&c<='Z''guaranteesthis.)͍G`%compare-lengths'K:Comparek!eywordlengthsbMeforetryingastringcomparison.HDThisoptionisK:mandatoryforbinarycomparisons(seeSection3.3[BinaryStrings],;page22).K:It,alsomigh!tcut+downonthenumbMerofstring+comparisonsmadeduringtheK:loMokup,sincek!eywordswithdi eren!tlengthsarenevercomparedviastrcmp.K:Ho!wever,tusingh`%compare-lengths'migh!thgreatlyincreasethesizeofthegen-K:eratedCcoMdeifthelookuptablerangeislarge(whic!himpliesthattheswitc!hK:option`-S'or`%switch'isnotenabled),Tsincethelengthtablecon!tainsasmanyK:elemen!tsfasthereareentriesintheloMokuptable.G`%compare-strncmp'K:GeneratesCcoMdethatusesthestrncmpfunctiontoperformstringcomparisons.K:Thefdefaultactionistousestrcmp.G`%readonly-tables'K:Mak!es thecontents ofallgeneratedloMokuptablesconstan!t, ti.e.,\readonly".K:Man!ycompilerscangeneratemoreecien!tcoMdeforthisb!yputtingthetablesK:infreadonlymemorye.͍G`%enum'KDe neconstan!tvdDaluesusinganenumloMcaltothelookupfunctionratherthanK:withx#de nes.TThisalsomeansthatdi eren!tloMokupxfunctionscanresideinK:thefsame le.ThankstoJamesClark.G`%includes'K:Include$thenecessarysysteminclude le,,at$thebMeginningoftheK:coMde.zBy>default,9ythisisnotdone;Ktheuserm!ustincludethis=header lehimselfK:tofallo!wcompilationofthecoMde.͍G`%global-table'K:Generatedthedstatictableofk!eywordsasdastaticglobalvdDariable,ratherthanK:hidingfitinsideoftheloMokupfunction(whic!histhedefaultbeha!vior).G`%pic'Optimizethegeneratedtableforinclusioninsharedlibraries.ThisreducesK:the;.startuptimeofprogramsusing;/asharedlibrarycon!tainingthegeneratedK:coMde.Ifdthee`%struct-type'declaration(or,2equivdDalen!tlye,theoptione`-t')isalsoK:giv!en,thei rstj eldoftheuser-de nedstructm!ustbMeoft!ypej`int',not`charK:*',ҜbMecauseitwillcon!taino setsintothestringpMoolinsteadofactualstrings.K:Teo con!vert suchano set toastring,you canusetheexpression`stringpoolK:+foDs',Qwhereouistheo set.ThestringpMoolnamecanbMec!hangedthroughtheK:`%definefstring-pool-name'declaration.GChapterf3:High-Lev!elDescriptionofGNUgperf>1933͍G`%definefstring-pool-namenameDs' 33K:Allo!wsyoutospMecifythenameofthegeneratedstringpoolcreatedb!ytheK:declaration`%pic'(or,%equivdDalen!tlye,theoption`-P'). ThedefaultnameisK:`stringpool'.EThisdeclarationpMermitstheuseoft!wohashtablesinthesameK: le,withg``%pic'g_andev!enwhenthe`%global-table'declaration(or,equivdDa-K:len!tlye,ftheoption`-G')isgiven.s4G`%null-strings'K:UseNULL`stringsinsteadofempt!ystringsforemptykeywordtableentries.K:Thisreducesthestartuptimeofprogramsusingasharedlibrarycon!tainingK:thejJgeneratedcoMde(butnotasm!uchjJasthedeclaration`%pic'),vOattheexpenseK:offonemoretest-and-branc!hinstructionatruntime.G`%definefword-array-namenameDs'K:Allo!wsyoutospMecifythenameforthegeneratedarra!ycontainingthehashK:table. oDefault9Anameis9B`wordlist'. nThisoption9ApMermitstheuse9Boft!woK:hashtablesinthesame le,ev!enwhentheoption`-G'(or,equivdDalen!tlye,theK:`%global-table'fdeclaration)isgiv!en.s5G`%defineflength-table-namenameDs'K:Allo!ws&YyoutospMecify&Xthenameforthegeneratedarray&XcontainingthelengthK:table. #oDefaultnameis`lengthtable'. #pThisoptionpMermitstheuseoft!woK:lengthtablesinthesame le, ev!enwhentheoption`-G'(or, equivdDalen!tlye, theK:`%global-table'fdeclaration)isgiv!en.G`%switch=countDs'K:CausesJtheJgeneratedCJ^coMdetouseaswitchstatemen!tscheme,sratherJthanK:anarra!yloMokuptable.ThiscanleadtoareductioninbothtimeandspaceK:requiremen!ts8forsomeinput8 les. 'Theargumentto8thisoptiondeterminesK:ho!wmanyswitchstatementsaregenerated.AvdDalueof1generates1switchK:con!taining‹alltheŒelements,avdDalueofŒ2generates2tableswith1/2theelemen!tsK:ineac!hswitch,Ѻetc.@ThisisusefulsincemanyCcompilerscannotcorrectlyK:generateJxcoMdeJwforlargeswitchstatemen!ts.8Thisoptionw!asinspiredinpartb!yK:KeithfBostic'soriginalCprogram.G`%omit-struct-type'K:Prev!entsS,theS-transferofthet!ypMedeclarationtotheoutput le.UsethisoptionK:iffthet!ypMeisalreadyde nedelsewhere.$@Gb3.1.1.3d(CMCoideInclusion3!GUsingaasyn!taxsimilarbtoGNU?utilitiesflexandbison,:bitispMossibletodirectlyincludeGCsourcetextandcommen!tsverbatimintothegeneratedoutput le.ThisisaccomplishedGb!yyFenclosingtheyGregioninsideleft-justi edsurrounding`%{',`%}'pairs.V}HereisaninputGfragmen!tfbasedonthepreviousexamplethatillustratesthisfeature:GChapterf3:High-Lev!elDescriptionofGNUgperf>2033͍.%{ 33.#include./*Thissectionofcodeisinserteddirectlyintotheoutput.*/.intreturn_month_days(structmonth*months,intis_leap_year);.%}.structmonth{char*name;intnumber;intdays;intleap_days;};.%%.january,>1,31,31.february, T2,28,29.march,R3,31,31....Gb3.1.2d(FģormatMforKeywordEntries3!GThe"Jsecondinput le"Iformatsectioncon!tainslinesofkeywords"IandanyassoMciatedat- 33Gtributesy!oumightsupplye.jAUlinebMeginningwith`#'inthe rstcolumnisconsideredaGcommen!t.+Everythingfollowingthe`#'isignored,1uptoandincludingthefollowingnew-Gline.ֶANlineNbMeginningNwith`%'inthe rstcolumnisanoptiondeclarationandm!ustnotGoMccurfwithinthek!eywordsfsection.L΍!GTheh rsth eldofeac!hnon-commenthlineisalw!ayshthekeywordhitself."ItcanbMegiv!enGin5t!woways:Iasasimplename,Xi.e.,Xwithoutsurroundingstringquotationmarks,orasaGstring enclosedindouble-quotes,inCsyn!tax,pMossiblywithbackslashescapMeslike\"orG\234or\xa8.Ineithercase,fitm!uststartrightatthebMeginningoftheline,fwithoutleadingGwhitespace.)InP*thisP)con!text,za\ eld"isconsideredtoextendupto,zbutnotinclude,ztheG rstblank,bcomma,ornewline.ʡHereisasimpleexampletak!enfromapartiallistofCGreserv!edfwords:Lύ.#TheseareafewCreservedwords,seethec.gperffile.#foracompletelistofANSICreservedwords..unsigned.sizeof.switch.signed.if.default.for.while.returnL̍!GNoteo9thatunlik!eflexo8orbisonthe rst`%%'markermaybMeo8elidedifthedeclarationGsectionfisempt!ye.!GAdditionalp eldspma!yoptionallyfollowptheleadingk!eyword.˽FieldspshouldbMeseparatedGb!yecommas,randterminateeattheendofline.MWhatthese eldsmeanisen!tirelyuptoy!ou;Gtheyareusedtoinitializetheelemen!tsoftheuser-de nedstructpro!videdbyyouintheGdeclarationsection.sIfthe`-t'option(or,equivdDalen!tlye,the`%struct-type'declaration)GisP+notZenabledP*these eldsaresimplyignored.,AllpreviousexamplesexceptthelastoneGcon!tainfkeywordattributes. GChapterf3:High-Lev!elDescriptionofGNUgperf>2133͍Gb3.1.3d(IncludingMAdditionalCFģunctions3!GTheoptionalthirdsectionalsocorrespMondscloselywithcon!ventionsfoundinflexand 33Gbison.Alltextinthissection,մstartingatthe nal`%%'andextendingtotheendoftheinputG le,isincludedv!erbatimintothegeneratedoutput le.Naturallye,itisyourrespMonsibilityGtofensurethatthecoMdecon!tainedinthissectionisvdDalidC.Gb3.1.4d(WhereMtoplacedirectivesforGNUeindentb.!GIfFiy!ouwanttoinvokeFhGNUFQindentonagperfinput le,Yy!ouwillseethatGNUFQindentGdoMesn't:understand9the`%%',`%{'and`%}'directiv!esthatcon!trolgperf'sin!terpretationofGtheinput le.Thereforey!ouhavetoinsertsomedirectivesforGNU[indent.Morepreciselye,Gassumingfthemostgeneralinput lestructure/ʍ.declarationspart1.%{.verbatimcode.%}.declarationspart2.%%.keywords.%%.functionszcGy!oufwouldinsert`*INDENT-OFF*'and`*INDENT-ON*'commentsasfollows:./**INDENT-OFF**/.declarationspart1.%{./**INDENT-ON**/.verbatimcode./**INDENT-OFF**/.%}.declarationspart2.%%.keywords.%%./**INDENT-ON**/.functionsGGY3.2Outputf@FformatforGeneratedCCos3dewith\gperf33!GSev!eralO-optionscontrolhowthegeneratedCOcoMdeappearsonthestandardoutput.Tw!oGCtfunctionsaregenerated. 2$Theyarecalledhashandin_word_set,t.althoughy!oumayGmoMdifygtheirfnameswithacommand-lineoption.Bothfunctionsrequiret!wogarguments,aGstring,charf*Vstr,andUalengthparameter,intlen.sTheirdefaultfunctionprotot!ypMesareGasffollo!ws:,az[Feunction]G=2233͍.stored^inaloMcalstaticarra!ye.TheassociatedvdDaluestableisconstructedin!ternallyby 33.gperf3andlater3outputasastaticloMcalC3arra!ycalled`hash_table'.zTherelevdDant.selected9pMositions(i.e.hindicesin!tostr))9arespeci edviathe`-k'9optionwhenrunning.gperf,fasdetailedintheOptions~sectionbMelo!w(seeChapter4[Options],page24).Xz[Feunction]Gin_word_sety(constfc!har*str,unsignedintlenc).Ifstrisinthek!eywordset,,preturnsapMointertothatkeyword.Moreexactlye,,qifthe.option`-t'(or, equivdDalen!tlye,the`%struct-type'declaration)w!asgiven, itreturnsa.pMoin!terftothematchingkeyword'sstructure.OtherwiseitreturnsNULL.X!GIfӠtheoption`-c'(or,equivdDalen!tlye,theӠ`%compare-strncmp'declaration)isnotused,GstrCm!ustzbMeaNULzterminatedstringofexactlylengthlen.ZIf`-c'(or,equivdDalentlye,theG`%compare-strncmp'declaration)isused,9>strm!ustsimplybMeanarra!yoflenb!ytesanddoMesGnotfneedtobMeNULterminated.E!GThefcoMdegeneratedfortheset!woffunctionsisa ectedb!ythefollowingoptions:ڍG`-t'G`--struct-type'K:Mak!efuseoftheuser-de nedstruct.EG`-Sftotal-switch-statementsDs'G`--switch=total-switch-statementsDs'K:Generate{1ormoreC{@switchstatemen!tratherthanusealarge,Q(andpMotentiallyK:sparse)staticarra!ye.Althoughtheexacttimeandspacesa!vingsofthisapproac!hK:vdDaryIaccordingtoJy!ourC?compiler'sdegreeofoptimization,thismethoMdoftenK:resultsfinsmallerandfastercoMde.!GIfWthe`-t'Wand`-S'options(or,fequivdDalen!tlye,fthe`%struct-type'and`%switch'declara-Gtions)areomitted,thedefaultactionistogenerateacharf*arra!ycontainingthekeywords,Gtogetherewithadditionalempt!ystringsusedforfpaddingthearraye.ByexpMerimentingwithGthevdDariousinputandoutputoptions,andtimingtheresultingCcoMde,y!oucandetermineGthefbMestoptionc!hoicesfordi erentkeywordsetcharacteristics.GY3.3Usef@ofNULbytes33!GBydefault,athe coMdegeneratedb!ygperfopMeratesonzeroterminatedstrings,atheusualGrepresen!tationofstringsinC.Thismeansthatthek!eywordsintheinput lem!ustnotGcon!tainQNULPbytes,{andthestr)argumentpassedtohashorin_word_setmustbMeNULGterminatedfandha!vefexactlylengthlen.E!GIfUoption`-c'U(or,equivdDalen!tlye,theU`%compare-strncmp'declaration)isused,thentheGstr$argumen!t[doMesnotneed[tobeNUL[sterminated.Thecode[generatedb!ygperfwillonlyGaccess[Xthe[Y rstlen,j[notlen+1,b!ytesstarting[Yatstr.However,j[thekeywordsinthe[Yinput leGstillfm!ustnotcontainNULbytes.!GIfUoption`-l'U(or,equivdDalen!tlye,theU`%compare-lengths'declaration)isused,thentheGhashtablepMerformsbinarycomparison.Thek!eywordsintheinput lema!ycontainNULGb!ytes,b_written in stringsyntaxas \000or\x00,b_andthecoMdegeneratedb!ygperfwillGtreatXNULlik!eanyotherbyte.Also,TTinthiscasethe`-c'option(or,equivdDalen!tlye,theG`%compare-strncmp'fdeclaration)isignored.6.GChapterf3:High-Lev!elDescriptionofGNUgperf>2333͍GY3.4Thef@CopyrightoftheOutput33!GgperfisunderGPL,butthatdoMesnotcausetheoutputproMducedb!ygperftobMeunder 33GGPL.#The#reasonisthattheoutputcon!tainsonlysmallpiecesoftextthatcomedirectlyGfrom 'gperf'ssourcecoMde{ (onlyabout7lineslong,>toosmallfor (beingsigni can!t{,>andGthereforeftheoutputisnota\w!orkbasedongperf"(inthesenseoftheGPLversion3).33!GOntheotherhand,theoutputproMducedb!ygperfcon!tainsessentiallyalloftheinputG le.xTherefore95theoutput96isa\derivdDativ!ework"95oftheinput(inthesenseofU.S.cop!yrightGla!w);yand}itscopyright}statusdepMendsonthecop!yright}oftheinput.bFeormostsoft!wareGlicenses,9athe resultisthatthetheoutputisunderthesamelicense,withthesamecop!yrightGholder,fastheinputthatw!aspassedtogperf.F\GChapterf4:In!vokinggperf%72433͍GP4 QInuvokingzSgperf"!GThere`are`manyXoptionstogperf. -Theyw!ereaddedtomak!etheprogrammorecon- 33Gv!enient4for5usewithrealapplications.H\On-line"helpisreadilya!vdDailableviathe`--help'Goption.Herefisthecompletelistofoptions./DGY4.1Sps3ecifyingf@theLocationoftheOutputFileBG`--output-file=fileDs'K:Allo!wsfyoutospMecifythenameofthe letowhichtheoutputiswrittento.bw!GThefresultsarewrittentostandardoutputifnooutput leisspMeci edorifitis`-'.GY4.2Optionsf@thata ectInterpretationoftheInputFile33!GTheseoptionsarealsoa!vdDailableasdeclarationsintheinput le(seeSection3.1.1.2G[GpMerffDeclarations],page16).bvG`-efkeyword-delimiter-listDs'G`--delimiters=keyword-delimiter-listDs'K:Allo!wssyoustoprovideastringscontainingdelimitersusedtosseparatekeywordsK:from'their'attributes.aThedefaultis",".aThisoptionisessen!tialify!ouwantK:to^usek!eywords^that]haveembMeddedcommasornewlines.OneusefultrickisK:tofuse-e'TeAB',whereTABistheliteraltabc!haracter.RG`-t'G`--struct-type'K:Allo!wsyoutoincludeastructt!ypMedeclarationforgeneratedcoMde.*An!ytextK:bMeforeC6aC7pairofconsecutiv!e`%%'isconsideredpartofthet!ypMedeclaration.K:Keyw!ordsandadditional eldsmayfollowthis,Sonegroupof eldspMerline.K:AsetofexamplesforgeneratingpMerfecthashtablesandfunctionsforAda,C,K:C++,P!ascal,MoMdulaϨ2,Modulaϧ3ϨandJa!vdDaScriptreservedϧwordsaredistributedK:withfthisrelease.RG`--ignore-case'K:ConsiderKuppMerandKlo!werKcaseASCIIKBc!haractersasequivdDalent. ͷThestringK:comparisondwillusedacaseinsigni can!tcharacterdcomparison.NotethatloMcaleK:depMenden!tbcasemappingsareignored.='A'&&c<='Z''0guaran!teesthis.)oThisw!astheK:default9in9v!ersionsofgperfearlierthan2.7;]no!wthedefaultistosuppMort8-bitK:andfm!ultibytecharacters.G`-l'G`--compare-lengths'K:Comparek!eywordlengthsbMeforetryingastringcomparison.HDThisoptionisK:mandatoryforbinarycomparisons(seeSection3.3[BinaryStrings],;page22).K:It,alsomigh!tcut+downonthenumbMerofstring+comparisonsmadeduringtheK:loMokup,sincek!eywordswithdi eren!tlengthsarenevercomparedviastrcmp.K:Ho!wever,!9using`-l'mightgreatlyincreasethesizeofthegeneratedCcoMdeifK:theloMokuptablerangeislarge(whic!himpliesthattheswitc!hoption`-S'orK:`%switch'=is.cGChapterf4:In!vokinggperf%72733͍G`-I' 33G`--includes'K:Include$thenecessarysysteminclude le,,at$thebMeginningoftheK:coMde.zBy>default,9ythisisnotdone;Ktheuserm!ustincludethis=header lehimselfK:tofallo!wcompilationofthecoMde.J֍G`-G'G`--global-table'K:Generatedthedstatictableofk!eywordsasdastaticglobalvdDariable,ratherthanK:hidingfitinsideoftheloMokupfunction(whic!histhedefaultbeha!vior).G`-P'G`--pic'KOptimizethegeneratedtableforinclusioninsharedlibraries.ThisreducesK:the;.startuptimeofprogramsusing;/asharedlibrarycon!tainingthegeneratedK:coMde.Ifdtheeoption`-t'(or,2equivdDalen!tlye,the`%struct-type'edeclaration)isalsoK:giv!en,thei rstj eldoftheuser-de nedstructm!ustbMeoft!ypej`int',not`charK:*',ҜbMecauseitwillcon!taino setsintothestringpMoolinsteadofactualstrings.K:Teo con!vert suchano set toastring,you canusetheexpression`stringpoolK:+foDs',Qwhereouistheo set.ThestringpMoolnamecanbMec!hangedthroughtheK:optionf`--string-pool-name'.JՍG`-Qfstring-pool-nameDs'G`--string-pool-name=string-pool-nameDs'K:Allo!wsyoutospMecifythenameofthegeneratedstringpMoolcreatedb!yoptionK:`-P'.The9defaultnameis`stringpool'.ThisoptionpMermitstheuseoft!wo9hashK:tablesڮinthesame le,lwith`-P'andگev!enwhentheoption`-G'(or,equivdDalen!tlye,K:thef`%global-table'declaration)isgiv!en.G`--null-strings'K:UseNULL`stringsinsteadofempt!ystringsforemptykeywordtableentries.K:Thisreducesthestartuptimeofprogramsusingasharedlibrarycon!tainingK:thegeneratedcoMde(butnotasm!uchasoption`-P'),+attheexpMenseofoneK:moreftest-and-branc!hinstructionatruntime.G`-Wfhash-table-array-nameDs'G`--word-array-name=hash-table-array-nameDs'K:Allo!wsyoutospMecifythenameforthegeneratedarra!ycontainingthehashK:table. oDefault9Anameis9B`wordlist'. nThisoption9ApMermitstheuse9Boft!woK:hashtablesinthesame le,ev!enwhentheoption`-G'(or,equivdDalen!tlye,theK:`%global-table'fdeclaration)isgiv!en.?G`--length-table-name=length-table-array-nameDs'K:Allo!ws&YyoutospMecify&Xthenameforthegeneratedarray&XcontainingthelengthK:table. #oDefaultnameis`lengthtable'. #pThisoptionpMermitstheuseoft!woK:lengthtablesinthesame le, ev!enwhentheoption`-G'(or, equivdDalen!tlye, theK:`%global-table'fdeclaration)isgiv!en.G`-Sftotal-switch-statementsDs'G`--switch=total-switch-statementsDs'K:CausesJtheJgeneratedCJ^coMdetouseaswitchstatemen!tscheme,sratherJthanK:anarra!yloMokuptable.ThiscanleadtoareductioninbothtimeandspaceoɍGChapterf4:In!vokinggperf%72833͍K:requiremen!ts8forsomeinput8 les. 'Theargumentto8thisoptiondetermines 33K:ho!wmanyswitchstatementsaregenerated.AvdDalueof1generates1switchK:con!taining‹alltheŒelements,avdDalueofŒ2generates2tableswith1/2theelemen!tsK:ineac!hswitch,Ѻetc.@ThisisusefulsincemanyCcompilerscannotcorrectlyK:generateJxcoMdeJwforlargeswitchstatemen!ts.8Thisoptionw!asinspiredinpartb!yK:KeithfBostic'soriginalCprogram.G`-T'G`--omit-struct-type'K:Prev!entsS,theS-transferofthet!ypMedeclarationtotheoutput le.UsethisoptionK:iffthet!ypMeisalreadyde nedelsewhere.G`-p'(setofk!eywords=hasthesamenames,.sbutpossessesK:di eren!t^attributes,[orif]theselectedbyte]pMositionsarenotw!ellchosen.1WithK:theH@-DHoptiongperftreatsallthesek!eywordsH@aspartofanequivdDalenceclassK:andgeneratesapMerfecthashfunctionwithm!ultiplecomparisonsforduplicateK:k!eywords.zHIt{isup{toy!outocompletelydisam!biguatethekeywords{bymoMdifyingK:theHgeneratedH CHcoMde.qHo!wever,ZgperfhelpsH yououtH byorganizingH theoutput.K:UsingԖthisoptionusuallymeansthatthegeneratedhashfunctionisnolongerK:pMerfect.UOntheotherhand,itpermitsgperftow!orkonkeywordsetsthatitK:otherwisefcouldnothandle.}GChapterf4:In!vokinggperf%72933͍G`-mfiterationsDs' 33G`--multiple-iterations=iterationsDs'K:P!erformSmultiplechoicesRofthe`-i'and`-j'vdDalues,$andc!hoMosethebMestresults.K:This/jincreasestherunningtimeb!yafactor/kofiterationsbutdoMesagoodjobK:minimizingfthegeneratedtablesize.fhG`-ifinitial-valueDs'G`--initial-asso=initial-valueDs'K:Pro!videsc@aninitialvdDalueGfortheassoMciatevaluesarra!ye.{Defaultis0.IncreasingK:theinitialvdDaluehelpsin atethe naltablesize,pMossiblyleadingtomoretimeK:ecien!t@ keywordloMokups.NotethatthisoptionisnotparticularlyusefulwhenK:`-S'jW(or,vYequivdDalen!tlye,vZ`%switch')isjVused.Also,`-i'isjVo!verriddenjWwhenthe`-r'K:optionfisused.fgG`-jfjump-valueDs'G`--jump=jump-valueDs'K:A ectsFthe\jumpvdDalue",i.e.,ho!wfartoadvancetheassoMciatedb!ytevalueK:upMoncollisions.4Jump-vdDalueHisroundeduptoanoddn!umber,thedefaultis5.K:Iffthejump-vdDalueCmis0gperfjumpsb!yrandomamounts.G`-n'G`--no-strlen'K:InstructsCsizeasthe>n!umbMer>ofk!eywords>(foreciencye,dthemaxim!umassociatedK:vdDalueDisalw!aysDroundedDuptoapMo!werDof2).Theactualtablesizema!yvdDaryK:somewhat,fsincethistec!hniqueisessentiallyaheuristic.GY4.6Informativef@Output33G`-h'G`--help'=Prin!ts'ashortsummaryonthemeaningofeachprogramoption.AbMortsfurtherK:programfexecution.33G`-v'G`--version'K:Prin!tsfoutthecurrentversionnumbMer.G`-d'G`--debug' }Enablesgthedebugginggoption. ThisproMducesv!erbosegdiagnosticsto\standardK:error"whengperfisexecuting.>ItisusefulbMothformain!tainingtheprogramK:andfordeterminingwhetheragiv!ensetofoptionsisactuallyspMeedinguptheK:searc!hEforFasolution.L|SomeusefulinformationisdumpMedattheendoftheK:programfwhenthe`-d'optionisenabled.$GChapterf5:Kno!wnBugsandLimitationswithgperfb3133͍GP5 QKnouwnzBugsandLimitationswithSgperf33!GTheffollo!wingaresomelimitationswiththecurrentreleaseofgperf:33 'The8gperf7utilit!yistunedtoexecutequic!klye,,andworksquickly7forsmalltomedium 33'size$2data$3sets(around1000k!eywords).WBItis$2extremelyusefulformain!tainingpMerfect'hashfunctionsforcompilerk!eywordsets.Severalrecentenhancementsnowenable'gperftow!orkecientlyonmuchlargerkeywordsets(over15,000keywords).mWhen'proMcessingflargek!eywordfsetsithelpsgreatlytoha!vefover8megsofRAM. 'TheDesizeDfofthegeneratestatick!eywordDearraycanDfgetextrpemely 3 cmmi10:ۍ::::::::::::::::::::::::::::::::::::::: 615 330G3.1.1 5Declarations^q:ۍ:::::::::::::::::::::::::::::::::::::::::::: 15?G3.1.1.1 5User-suppliedfstruct{:ۍ:::::::::::::::::::::::::::::::F16?G3.1.1.2 5GpMerffDeclarationsϮ:ۍ::::::::::::::::::::::::::::::::: S16?G3.1.1.3 5CfCoMdeInclusion&:ۍ::::::::::::::::::::::::::::::::::: h^190G3.1.2 5FeormatfforKeyw!ordEntries͍:ۍ::::::::::::::::::::::::::::: e200G3.1.3 5IncludingfAdditionalCFeunctionsh:ۍ::::::::::::::::::::::::K210G3.1.4 5Whereftoplacedirectiv!esforGNUindent.7:ۍ:::::::::::::: o21!G3.2 5OutputfFeormatforGeneratedCCoMdewithgperfc:ۍ:::::::::::: 21!G3.3 5UsefofNULb!ytes/Y:ۍ:::::::::::::::::::::::::::::::::::::::::::: 22!G3.4 5ThefCop!yrightoftheOutputdҍ:ۍ::::::::::::::::::::::::::::::::: 2333GY432Invokingff\gperf_32`:Q 32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32: Y24!G4.1 5SpMecifyingftheLocationoftheOutputFile㍑:ۍ::::::::::::::::::: 24!G4.2 5Optionsfthata ectIn!terpretationoftheInputFileލ:ۍ::::::::::: O24!G4.3 5OptionsftospMecifytheLanguagefortheOutputCode;:ۍ:::::::: 24!G4.4 5Optionsffor netuningDetailsintheOutputCoMdeR,:ۍ::::::::::: d25!G4.5 5Optionsfforc!hangingtheAlgorithmsemployedbygperf=č:ۍ::::::28!G4.6 5Informativ!efOutputW:ۍ:::::::::::::::::::::::::::::::::::::::::: 3033GY532KnownffBugsandLimitationswith\gperf32`:Q 32:32:32: :Y31 G632ThingsffStillLefttoDo32`:Q 32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32: (Y32G732Bibliography퍑32`:Q 32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32: UY33GConceptffIndex632`:Q 32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32:32: Y34/;ï%e߆T # cmtt12bN # cmbx12`gff cmmi12\߆Tff cmtt12YNff cmbx12S߆TG cmtt12PNG cmbx12J߆Tj cmtt12GNj cmbx12B 3 cmmi109