[ccan] [PATCH 6/7] aga: Add lazytrie testcase
David Gibson
david at gibson.dropbear.id.au
Sat Jul 25 20:50:11 AEST 2015
This adds a more complex testcase to the aga module. This one is a trie
(basically a radix tree for strings).
It demonstrates different ways of constructing edge information from an
internal representation than the existing testcases. Importantly, it also
demonstrates aga's ability to cope with the edge function lazily
constructing nodes on the fly.
Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
ccan/aga/_info | 4 +
ccan/aga/test/api-lazytrie-words.txt | 1000 ++++++++++++++++++++++++++++++++++
ccan/aga/test/api-lazytrie.c | 211 +++++++
3 files changed, 1215 insertions(+)
create mode 100644 ccan/aga/test/api-lazytrie-words.txt
create mode 100644 ccan/aga/test/api-lazytrie.c
diff --git a/ccan/aga/_info b/ccan/aga/_info
index 3320d37..fa5e8fe 100644
--- a/ccan/aga/_info
+++ b/ccan/aga/_info
@@ -40,6 +40,10 @@ int main(int argc, char *argv[])
printf("ccan/container_of\n");
printf("ccan/ptrint\n");
printf("ccan/array_size\n");
+ printf("ccan/tal\n");
+ printf("ccan/tal/str\n");
+ printf("ccan/tal/grab_file\n");
+ printf("ccan/take\n");
return 0;
}
diff --git a/ccan/aga/test/api-lazytrie-words.txt b/ccan/aga/test/api-lazytrie-words.txt
new file mode 100644
index 0000000..bbba3f5
--- /dev/null
+++ b/ccan/aga/test/api-lazytrie-words.txt
@@ -0,0 +1,1000 @@
+abbotship
+abettor
+ablings
+abstractively
+accessarily
+acclimatable
+accordance
+accosts
+accoying
+accusatory
+achronychous
+acoelomous
+acoin
+adsorbing
+adversarial
+aedile
+afterdischarge
+aggur
+allophanamide
+almondy
+altumal
+ambers
+ambolic
+amerveil
+ami
+aminic
+amolilla
+amorously
+anaphorically
+ancille
+anes
+antepaschel
+anteroposteriorly
+anthography
+anthracitous
+anthropophagus
+anticomment
+anticosmetics
+antidiabetic
+antipepsin
+antiperiodic
+antiracer
+apiolin
+appetibility
+arber
+archconfraternity
+arcubalister
+argumentative
+armsize
+arrha
+assesses
+assuages
+astoundingly
+atom
+atteal
+aucht
+autochthonous
+autocraticalness
+autodrome
+aviarists
+avoiding
+backplanes
+baldrics
+bardel
+baromacrometer
+barringer
+battologized
+bedfoot
+bedplates
+bedread
+bef
+belgians
+bellyful
+bely
+bemiring
+benda
+bequeather
+bermudians
+beround
+bestows
+bestraddle
+bestrewn
+bicipitous
+bimalar
+bipyridine
+birdglue
+birthplaces
+bivalves
+blastocele
+blimpishness
+blizzard
+bloodying
+blowpit
+blowziest
+blunt
+bn
+bobwhites
+bodiced
+bombings
+bombola
+booley
+boozer
+boppist
+boracite
+borasque
+borowolframic
+bothria
+bouleuteria
+boult
+bouton
+braes
+branches
+brasero
+bronchoscopist
+bul
+bulging
+bullyingly
+bunching
+butanols
+cabin
+cacoeconomy
+cadavers
+caddices
+calamander
+calendric
+calotte
+camphoraceous
+candlebeam
+cantilenes
+cantle
+canvased
+captious
+carabineer
+carbanilic
+carcajous
+carcinolysin
+carolingian
+casque
+catafalques
+cataracteg
+cathected
+cauda
+cavilingly
+cedula
+cellulifugally
+chairpersons
+chalcolithic
+chamber
+chamfron
+chanco
+chardock
+charmfully
+chauffage
+chickenheartedness
+chimera
+chiniofon
+chiropodial
+chlorophenol
+choke
+choriomas
+chrisroot
+chronostichon
+chrysopal
+chthonophagy
+citharist
+clammish
+clarinettists
+cliffing
+closeouts
+cloturing
+clyer
+cockswain
+cocuyo
+codgers
+cogit
+commendably
+commissive
+compassing
+conciliated
+condiction
+confides
+confuting
+congreve
+conjunctiva
+connect
+constellatory
+contradictory
+contredanse
+contributes
+coony
+coper
+corded
+corespondent
+corks
+cornea
+cornsack
+corruptibilities
+cosmete
+cosmetician
+cosmically
+counterintrigues
+counterreplied
+counterretaliation
+cozy
+crackedness
+craniomalacia
+creese
+crome
+crosscrosslet
+crotchetiness
+cuemen
+cumberment
+custrel
+cynocephalic
+dawe
+debarking
+debase
+decrees
+defatigation
+defogger
+defrauds
+degold
+dejecting
+dekameters
+demagnetization
+demilitarized
+denouncements
+deodorised
+deoxidise
+deration
+dermosynovitis
+desperadoism
+detribalization
+deuterofibrinose
+devilkin
+diagnoseable
+diaphoreses
+dioptrically
+dioxanes
+disclike
+disentrain
+disillusionised
+dislodgement
+disloyally
+disray
+disrelate
+dissour
+disyllabism
+dogsled
+dolittle
+dolomite
+domboc
+doorcheek
+dozy
+dribbly
+ducklings
+duelistic
+duplexing
+dynamoelectrical
+dynapolis
+dynasty
+effused
+embargoes
+embarred
+emissaries
+emporiums
+emulsin
+enchant
+encomimia
+encysted
+endowed
+enslave
+enslavements
+enthymematical
+enwood
+ephestian
+ephidrosis
+epigramme
+epileny
+esmayle
+espinette
+espressivo
+ethnically
+euhyostyly
+euphemistic
+european
+evolved
+expecters
+exsecting
+facia
+faenas
+fanglement
+fantaddish
+faverel
+feltwork
+feoffs
+feriation
+ferulae
+feudum
+fibrocement
+fidging
+fiendish
+figurism
+filch
+fingerprinted
+fledgiest
+flogmaster
+floods
+flowstone
+fog
+foleye
+footer
+footstall
+forefeels
+foregame
+foreread
+foreshorten
+forgat
+forlornly
+fornical
+foxberry
+freckle
+fronded
+frondiform
+gainfulness
+garrotes
+generalissimo
+generification
+geometrine
+gephyrophobia
+gingalls
+gingilli
+gith
+gladify
+globosity
+glowered
+glycolytically
+gnatter
+gonepoiesis
+gonepoietic
+grades
+grainfield
+grandson
+gravimeters
+gressorious
+grouser
+grudgefulness
+guillotinist
+guily
+gulinulae
+gur
+gutierrez
+gym
+gymnotus
+gynaecological
+gynecologies
+handwaled
+harmoniphon
+harslet
+hatless
+headspace
+heartland
+heartseed
+heeder
+helicoid
+help
+hemidystrophy
+hereto
+heshvan
+heterocerous
+heteroousian
+hexoses
+hideously
+holidayer
+holocaust
+homelyn
+hominians
+homocreosol
+homoeophony
+homologumena
+horsely
+hotspurs
+howes
+humidifiers
+hydrorhizae
+hyperplastic
+hypnoidization
+hypothalamic
+hypsilophodontid
+ideaed
+illnaturedly
+immanentism
+impaint
+impayable
+imponderableness
+impugns
+imsonic
+inalienability
+incommodity
+inconsidered
+incurvity
+indifferently
+inemendable
+inexpressiveness
+informatus
+inmixture
+insinuatingly
+instabilities
+insurmounably
+interdiffusive
+interests
+interrogatives
+intrapsychical
+intreating
+introd
+io
+irredressibly
+irrepair
+isodurene
+isooleic
+isorhamnose
+italianate
+italic
+italy
+jabs
+jag
+jawless
+jetting
+jocote
+johannite
+jovialistic
+jovialty
+judicate
+kaftans
+kallidin
+kanjis
+karela
+keelman
+kippered
+kytoon
+lachrymiform
+lactesce
+lactinate
+landfills
+lapponian
+larderlike
+larine
+lask
+latifundio
+laurvikite
+leadenly
+leglessness
+leme
+lengthened
+lenis
+lensless
+lepidophytic
+leu
+leucocratic
+leucocythemic
+leviable
+lieder
+limas
+linker
+liquidus
+lithochemistry
+litster
+liveners
+localing
+lodicule
+lolloping
+loosebox
+lubricate
+ludicrousness
+lumining
+luxuriates
+magenta
+maggotpie
+maladresse
+malagma
+maleic
+malleablizing
+martyrer
+martyring
+marvelment
+masseur
+matronism
+mattresses
+mayweed
+megazooid
+melissa
+memorized
+mentiform
+merligo
+mesmeriser
+metabolous
+metagrammatism
+metapsychic
+metonic
+metran
+metric
+microbiologists
+microphysiography
+milepost
+milled
+millimho
+mimine
+minicars
+misadjusting
+mislearned
+misreaded
+moleheap
+moleproof
+mooress
+moosehood
+morlop
+morningly
+mortgagees
+mortification
+mosquitocide
+multichambered
+multinucleated
+muscologist
+myelogenic
+myoliposis
+naives
+necrophagy
+negotiates
+nettliest
+neurospora
+nicotineless
+niggling
+nihilum
+ninetyfold
+ninjas
+nitrosyls
+noctiluscence
+nominating
+nonaccumulative
+nonacidic
+nonchargeable
+noncommunicable
+nondoing
+nonexcitable
+nonfunctionally
+nonhistrionic
+nonliquid
+nonplussed
+nonprosses
+nonradiant
+nonsuccess
+nonsympathetic
+nontangibleness
+nontenant
+nontransitiveness
+norseler
+northeasts
+nould
+nounize
+nucleomicrosome
+nude
+nymphlin
+obloquious
+oboes
+occipitoaxoid
+occipitofrontal
+officiator
+onager
+oophoridiums
+openhanded
+operatable
+opiliaceous
+opiumisms
+orarion
+ordonnance
+orleways
+otodynic
+outlooks
+outpensioner
+outstunting
+outwalk
+overadvancing
+overattached
+overclothes
+overconsiderately
+overfee
+overgesticulated
+overleg
+overplump
+overrefine
+overshot
+overspended
+overwhelmingly
+paleometeorology
+palmipes
+pancreatopathy
+panoistic
+pansyish
+pantaletted
+papally
+papelonne
+papyruses
+paraaminobenzoic
+paraheliotropism
+paralepsis
+parapsychology
+pathomimesis
+patriarchism
+patriarchy
+patrioteer
+pauperizer
+payors
+peacockishly
+pedicel
+pelanos
+pengun
+penitently
+pensions
+pepperish
+perdifume
+perfectionator
+pericholecystitis
+pericranium
+peritonaea
+petronellier
+petroxolin
+phlorol
+photogenic
+phragmocyttarous
+phrasing
+phugoid
+pianka
+piazzaed
+pierre
+piolets
+pixilated
+planigraphy
+playing
+pleurectomy
+plumiest
+plungeon
+pokerishness
+politicizing
+pollenate
+polycrase
+polyglots
+polyharmonic
+polysemant
+pomp
+postganglionic
+postscenium
+pottier
+pour
+prairielike
+pratincoline
+precollapsed
+predesolate
+prefatorially
+preindulgent
+preliberally
+preluxuriously
+prenarcotic
+preneural
+preorganize
+prerecited
+procercoid
+proconformity
+proctoplegia
+profiteering
+programistic
+proletarised
+prophecymonger
+propitiating
+prorepublican
+prosecutrix
+provinces
+psalmbook
+puncture
+puppeteer
+purpurescent
+puttiers
+pygopod
+pyridoxal
+qiviuts
+quadrigamist
+quadripinnate
+quadruples
+quaggiest
+quibbled
+ramrods
+rancelmen
+rapaciously
+rape
+readability
+realign
+realpolitik
+reasonability
+reboiler
+reburial
+recalescence
+recitals
+reclivate
+reclothe
+reconsidered
+recriticized
+recruited
+reddsman
+redemptions
+redenies
+regenerator
+regicidism
+relegable
+relentment
+reoiled
+replaster
+republisher
+reran
+resorts
+restless
+restrictively
+reticuli
+retincture
+retools
+reverberator
+revues
+rigorously
+risdaler
+rockabyes
+romanticized
+roscoelite
+routineness
+rubaboo
+rucked
+ruffly
+sacrings
+sailingly
+sallyman
+sandworts
+sangrail
+sanguifier
+sarcolemmous
+scalariform
+scenically
+schalstein
+sciuromorphic
+scolders
+scorchers
+scorny
+scourges
+scrapiness
+scrooping
+scullogue
+scutiped
+sebacate
+sectarianized
+seditious
+selenoscope
+sellably
+semicomical
+semiplantigrade
+semiprofessional
+sen
+senryu
+sensoparalysis
+seraphin
+serohemorrhagic
+serratospinose
+shared
+sharked
+shelteringly
+sheria
+shinleafs
+shinplaster
+shirrel
+shoestring
+shoewoman
+showerlike
+shrivels
+sinkingly
+sisyrinchium
+slackmindedness
+slaughterous
+slobbery
+slothfulness
+smilingly
+smirk
+smit
+smithying
+snappy
+snobbier
+sociologically
+soldat
+solicitorship
+solion
+somersaults
+somnambulism
+sorptive
+spadille
+sparkback
+spatulamancy
+speakers
+specificative
+spectry
+spheroidical
+sphingomyelin
+spiffiness
+spike
+spininess
+spiriter
+spoonmaker
+spp
+spunkily
+squeezable
+stadiums
+stashie
+stegosaurus
+stellify
+stenotropic
+sterculia
+steroids
+stigmatical
+stills
+stolen
+stroyers
+stylops
+subfractionally
+subsegment
+subsidiarily
+subtaxon
+subvertible
+sulfoborite
+sultanating
+sumo
+superambition
+superattractiveness
+supercarbonate
+superfantastically
+supersarcasm
+surgier
+sybaritism
+sylvanite
+syntheticism
+syringadenous
+syringocoele
+systemiser
+tailpipes
+taniko
+tarrow
+teahouses
+tegularly
+teleview
+tenterhook
+tentory
+termagant
+terracewards
+testament
+testiere
+tetanics
+tetraborate
+tetrasymmetry
+tetraxonian
+thereup
+thick
+thinclads
+thiuram
+threated
+thunderous
+thyroria
+timberless
+timepleaser
+tipful
+titters
+toggling
+tonalmatl
+tooled
+toss
+tournel
+trabeated
+trangams
+transcoloration
+transferor
+tranships
+transvestite
+tresance
+tricing
+trifurcated
+trilingual
+tripoline
+trochils
+tromometry
+trophospore
+trundler
+trunnions
+trustor
+tubercula
+tubtail
+tumors
+tumps
+tung
+turpantineweed
+tussles
+tutrix
+twister
+umbonial
+unacceptableness
+unadjournment
+unapplied
+unapprobation
+unbehoving
+uncaptiousness
+uncaptivating
+uncoin
+uncollectable
+undepleted
+underbidders
+undershored
+undervoltage
+undreamlike
+unempt
+uneuphoniousness
+uneverted
+unexceeded
+unexcursively
+unfilially
+unforbidden
+ungarland
+unhabitually
+unhasp
+unhinge
+uninnocuously
+uninspiring
+unjournalistic
+unlethally
+unmarriable
+unpalliated
+unpeculiar
+unpopularized
+unpopulousness
+unportable
+unrecondite
+unrefrainable
+unrepugnable
+unreservedly
+unscrupulous
+unseason
+unselective
+unshiftiness
+unslinging
+unstonable
+unwhiglike
+uptuck
+uremic
+ureteropyelography
+urethrectomy
+uromancy
+utterance
+venins
+ventrotomies
+viaducts
+vialling
+vicarly
+vicilin
+victoriousness
+vidimus
+violinless
+virtuosi
+viscoidal
+waitering
+wallaroos
+wapacut
+wearifully
+wedging
+wegotism
+weighters
+wellhead
+whin
+whitecapping
+wilts
+wiredrawer
+wonderwell
+woodchopper
+worryingly
+worsteds
+writeoff
+wrive
+xanthenes
+xanthocone
+xanthous
+yachtmanship
+yade
+yampee
+yeast
+ypsiloid
+zest
+zigzagged
+zogan
+zoogenic
+zoometric
+zoomorphize
+zoopathy
diff --git a/ccan/aga/test/api-lazytrie.c b/ccan/aga/test/api-lazytrie.c
new file mode 100644
index 0000000..feea4d1
--- /dev/null
+++ b/ccan/aga/test/api-lazytrie.c
@@ -0,0 +1,211 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+
+#include <ccan/ptrint/ptrint.h>
+#include <ccan/tal/tal.h>
+#include <ccan/tal/str/str.h>
+#include <ccan/take/take.h>
+#include <ccan/tal/grab_file/grab_file.h>
+#include <ccan/container_of/container_of.h>
+
+#include <ccan/aga/aga.h>
+
+#include <ccan/tap/tap.h>
+
+#define NWORDS 1000
+#define LETTERS "abcdefghijklmnopqrstuvwxyz"
+#define NLETTERS (sizeof(LETTERS) - 1)
+
+char **wordarray;
+char **wordarrayb; /* Word array sorted by length */
+int nwords;
+
+struct trie_node {
+ int start, end;
+ const char *prefix;
+ bool isword;
+ struct trie_node *next[NLETTERS];
+ struct aga_node agan;
+};
+
+/* Sorts by length first, then alphabetically */
+static int lensort(const void *xv, const void *yv)
+{
+ char *x = *((char **)xv);
+ char *y = *((char **)yv);
+ int xn = strlen(x);
+ int yn = strlen(y);
+
+ if (xn < yn)
+ return -1;
+ else if (xn > yn)
+ return 1;
+ else
+ /* We need this because qsort is not stable */
+ return strcmp(x, y);
+}
+
+static void setup_words(void)
+{
+ char *wordfile;
+
+ /* read in the words */
+ wordfile = grab_file(NULL, "test/api-lazytrie-words.txt");
+ ok1(wordfile);
+ wordarray = tal_strsplit(NULL, take(wordfile), "\n", STR_NO_EMPTY);
+ ok1(wordarray);
+ nwords = tal_count(wordarray) - 1;
+ diag("lazytrie: %d words loaded", nwords);
+ ok1(nwords == NWORDS);
+
+ wordarrayb = tal_arr(NULL, char *, nwords);
+ memcpy(wordarrayb, wordarray, tal_count(wordarrayb) * sizeof(char *));
+
+ qsort(wordarrayb, nwords, sizeof(char *), lensort);
+}
+
+struct lazytrie {
+ struct trie_node root;
+ struct aga_graph g;
+};
+
+static void init_trie_node(struct trie_node *n, int start, int end,
+ const char *prefix)
+{
+ int i;
+
+ n->start = start;
+ n->end = end;
+ n->prefix = prefix;
+ n->isword = (strcmp(n->prefix, wordarray[n->start]) == 0);
+
+ for (i = 0; i < NLETTERS; i++)
+ n->next[i] = NULL;
+
+ aga_node_init(&n->agan);
+}
+
+static ptrint_t *lazytrie_first_edge(const struct aga_graph *g,
+ const struct aga_node *n)
+{
+ return int2ptr(1);
+}
+
+static ptrint_t *lazytrie_next_edge(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *e)
+{
+ int index = ptr2int(e);
+
+ assert((index >= 1) && (index <= NLETTERS));
+ if (index == NLETTERS)
+ return NULL;
+ else
+ return int2ptr(index + 1);
+}
+
+static int lazytrie_edge_info(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *e,
+ struct aga_edge_info *ei)
+{
+ struct trie_node *tn = container_of(n, struct trie_node, agan);
+ struct trie_node *next;
+ int index = ptr2int(e);
+
+ assert((index >= 1) && (index <= NLETTERS));
+
+ next = tn->next[index - 1];
+
+ if (!next) {
+ int depth = strlen(tn->prefix);
+ int start, end;
+
+ start = tn->start;
+ while (start < tn->end) {
+ if (wordarray[start][depth] >= LETTERS[index - 1])
+ break;
+ start++;
+ }
+
+ end = start;
+ while (end < tn->end) {
+ if (wordarray[end][depth] > LETTERS[index - 1])
+ break;
+ end++;
+ }
+
+ if (end > start) {
+ char plus[2] = { LETTERS[index - 1], '\0' };
+ next = tal(tn, struct trie_node);
+ init_trie_node(next, start, end,
+ tal_strcat(next, tn->prefix, plus));
+ }
+ }
+
+ if (next)
+ ei->to = &next->agan;
+ return 0;
+}
+
+static struct lazytrie *setup_trie(void)
+{
+ struct lazytrie *lt;
+
+ lt = tal(NULL, struct lazytrie);
+ init_trie_node(<->root, 0, nwords, "");
+ aga_init_graph(<->g, lazytrie_first_edge, lazytrie_next_edge,
+ lazytrie_edge_info);
+ return lt;
+}
+
+int main(void)
+{
+ struct lazytrie *lt;
+ struct aga_node *an;
+ int xn;
+
+ plan_tests(3 + NWORDS*2);
+ setup_words();
+
+ lt = setup_trie();
+
+ aga_dfs_start(<->g);
+
+ xn = 0;
+ aga_dfs(an, <->g, <->root.agan) {
+ struct trie_node *n = container_of(an, struct trie_node, agan);
+
+ diag("Visited \"%s\"\n", n->prefix);
+
+ if (n->isword) {
+ ok1(strcmp(n->prefix, wordarray[xn]) == 0);
+ xn++;
+ }
+ }
+
+ aga_finish(<->g);
+
+ tal_free(lt);
+
+ lt = setup_trie();
+
+ aga_bfs_start(<->g);
+
+ xn = 0;
+ aga_bfs(an, <->g, <->root.agan) {
+ struct trie_node *n = container_of(an, struct trie_node, agan);
+
+ diag("Visited \"%s\"\n", n->prefix);
+
+ if (n->isword) {
+ ok1(strcmp(n->prefix, wordarrayb[xn]) == 0);
+ xn++;
+ }
+ }
+
+ /* This exits depending on whether all tests passed */
+ return exit_status();
+}
--
2.4.3
More information about the ccan
mailing list