114114 </row>
115115 <row>
116116 <entry><literal>box_ops</></entry>
117- <entry>box</entry>
117+ <entry><type> box</> </entry>
118118 <entry>
119119 <literal><<</>
120120 <literal>&<</>
183183 Inner tuples are more complex, since they are branching points in the
184184 search tree. Each inner tuple contains a set of one or more
185185 <firstterm>nodes</>, which represent groups of similar leaf values.
186- A node contains a downlink that leadsto either another, lower-level inner
187- tuple, or a short list of leaf tuples that all lie on the same index page.
188- Each node has a <firstterm>label</> that describes it; for example,
186+ A node contains a downlink that leads either to another, lower-level inner
187+ tuple, orto a short list of leaf tuples that all lie on the same index page.
188+ Each nodenormally has a <firstterm>label</> that describes it; for example,
189189 in a radix tree the node label could be the next character of the string
190- value. Optionally, an inner tuple can have a <firstterm>prefix</> value
190+ value. (Alternatively, an operator class can omit the node labels, if it
191+ works with a fixed set of nodes for all inner tuples;
192+ see <xref linkend="spgist-null-labels">.)
193+ Optionally, an inner tuple can have a <firstterm>prefix</> value
191194 that describes all its members. In a radix tree this could be the common
192195 prefix of the represented strings. The prefix value is not necessarily
193196 really a prefix, but can be any data needed by the operator class;
202205 tuple, so the <acronym>SP-GiST</acronym> core provides the possibility for
203206 operator classes to manage level counting while descending the tree.
204207 There is also support for incrementally reconstructing the represented
205- value when that is needed.
208+ value when that is needed, and for passing down additional data (called
209+ <firstterm>traverse values</>) during a tree descent.
206210 </para>
207211
208212 <note>
@@ -492,9 +496,8 @@ typedef struct spgPickSplitOut
492496 <structfield>prefixDatum</> to the prefix value.
493497 Set <structfield>nNodes</> to indicate the number of nodes that
494498 the new inner tuple will contain, and
495- set <structfield>nodeLabels</> to an array of their label values.
496- (If the nodes do not require labels, set <structfield>nodeLabels</>
497- to NULL; see <xref linkend="spgist-null-labels"> for details.)
499+ set <structfield>nodeLabels</> to an array of their label values,
500+ or to NULL if node labels are not required.
498501 Set <structfield>mapTuplesToNodes</> to an array that gives the index
499502 (from zero) of the node that each leaf tuple should be assigned to.
500503 Set <structfield>leafTupleDatums</> to an array of the values to
@@ -561,7 +564,7 @@ typedef struct spgInnerConsistentIn
561564
562565 Datum reconstructedValue; /* value reconstructed at parent */
563566 void *traversalValue; /* opclass-specific traverse value */
564- MemoryContext traversalMemoryContext;
567+ MemoryContext traversalMemoryContext; /* put new traverse values here */
565568 int level; /* current level (counting from zero) */
566569 bool returnData; /* original data must be returned? */
567570
@@ -580,7 +583,6 @@ typedef struct spgInnerConsistentOut
580583 int *levelAdds; /* increment level by this much for each */
581584 Datum *reconstructedValues; /* associated reconstructed values */
582585 void **traversalValues; /* opclass-specific traverse values */
583-
584586} spgInnerConsistentOut;
585587</programlisting>
586588
@@ -599,6 +601,11 @@ typedef struct spgInnerConsistentOut
599601 parent tuple; it is <literal>(Datum) 0</> at the root level or if the
600602 <function>inner_consistent</> function did not provide a value at the
601603 parent level.
604+ <structfield>traversalValue</> is a pointer to any traverse data
605+ passed down from the previous call of <function>inner_consistent</>
606+ on the parent index tuple, or NULL at the root level.
607+ <structfield>traversalMemoryContext</> is the memory context in which
608+ to store output traverse values (see below).
602609 <structfield>level</> is the current inner tuple's level, starting at
603610 zero for the root level.
604611 <structfield>returnData</> is <literal>true</> if reconstructed data is
@@ -615,9 +622,6 @@ typedef struct spgInnerConsistentOut
615622 inner tuple, and
616623 <structfield>nodeLabels</> is an array of their label values, or
617624 NULL if the nodes do not have labels.
618- <structfield>traversalValue</> is a pointer to data that
619- <function>inner_consistent</> gets when called on child nodes from an
620- outer call of <function>inner_consistent</> on parent nodes.
621625 </para>
622626
623627 <para>
@@ -633,17 +637,20 @@ typedef struct spgInnerConsistentOut
633637 <structfield>reconstructedValues</> to an array of the values
634638 reconstructed for each child node to be visited; otherwise, leave
635639 <structfield>reconstructedValues</> as NULL.
640+ If it is desired to pass down additional out-of-band information
641+ (<quote>traverse values</>) to lower levels of the tree search,
642+ set <structfield>traversalValues</> to an array of the appropriate
643+ traverse values, one for each child node to be visited; otherwise,
644+ leave <structfield>traversalValues</> as NULL.
636645 Note that the <function>inner_consistent</> function is
637646 responsible for palloc'ing the
638- <structfield>nodeNumbers</>, <structfield>levelAdds</> and
639- <structfield>reconstructedValues</> arrays.
640- Sometimes accumulating some information is needed, while
641- descending from parent to child node was happened. In this case
642- <structfield>traversalValues</> array keeps pointers to
643- specific data you need to accumulate for every child node.
644- Memory for <structfield>traversalValues</> should be allocated in
645- the default context, but each element of it should be allocated in
646- <structfield>traversalMemoryContext</>.
647+ <structfield>nodeNumbers</>, <structfield>levelAdds</>,
648+ <structfield>reconstructedValues</>, and
649+ <structfield>traversalValues</> arrays in the current memory context.
650+ However, any output traverse values pointed to by
651+ the <structfield>traversalValues</> array should be allocated
652+ in <structfield>traversalMemoryContext</>.
653+ Each traverse value must be a single palloc'd chunk.
647654 </para>
648655 </listitem>
649656 </varlistentry>
@@ -700,6 +707,9 @@ typedef struct spgLeafConsistentOut
700707 parent tuple; it is <literal>(Datum) 0</> at the root level or if the
701708 <function>inner_consistent</> function did not provide a value at the
702709 parent level.
710+ <structfield>traversalValue</> is a pointer to any traverse data
711+ passed down from the previous call of <function>inner_consistent</>
712+ on the parent index tuple, or NULL at the root level.
703713 <structfield>level</> is the current leaf tuple's level, starting at
704714 zero for the root level.
705715 <structfield>returnData</> is <literal>true</> if reconstructed data is
@@ -859,11 +869,10 @@ typedef struct spgLeafConsistentOut
859869
860870 <para>
861871 The <productname>PostgreSQL</productname> source distribution includes
862- several examples of index operator classes for
863- <acronym>SP-GiST</acronym>. The core system currently provides radix
864- trees over text columns and two types of trees over points: quad-tree and
865- k-d tree. Look into <filename>src/backend/access/spgist/</> to see the
866- code.
872+ several examples of index operator classes for <acronym>SP-GiST</acronym>,
873+ as described in <xref linkend="spgist-builtin-opclasses-table">. Look
874+ into <filename>src/backend/access/spgist/</>
875+ and <filename>src/backend/utils/adt/</> to see the code.
867876 </para>
868877
869878</sect1>