aga: Add lazytrie testcase

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@gibson.dropbear.id.au>

3 files changed, 1215 insertions, 0 deletions

diff --git a/ccan/aga/_info b/ccan/aga/_info
index 3320d37a..fa5e8fe9 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 00000000..bbba3f51
--- /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 00000000..feea4d16
--- /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(&lt->root, 0, nwords, "");
+	aga_init_graph(&lt->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(&lt->g);
+
+	xn = 0;
+	aga_dfs(an, &lt->g, &lt->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(&lt->g);
+
+	tal_free(lt);
+
+	lt = setup_trie();
+
+	aga_bfs_start(&lt->g);
+
+	xn = 0;
+	aga_bfs(an, &lt->g, &lt->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();
+}