1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
|
<html>
<head>
<title>netrik hacker's manual: text search</title>
</head>
<body>
<h1 align="center">netrik hacker's manual<br />>========================<</h1>
<p>
[This file contains a description of the text search functionality. See
hacking.txt or <a href="hacking.html">hacking.html</a> for an overview
of the manual.]
</p>
<a name="framework" id="framework">
<h2>Framework</h2>
<p>
Though by far not as complicated as link handling, the text search
functionality is also somewhat distributed: The serach command is given in the
pager (<a href="hacking-pager.html#display">display()</a>, see
hacking-pager.*), and after the search the new position is also activated here.
The search itself however is done in main(). (There is no real reason for this,
except that reading the search string has to be done in scroll mode, as well es
displaying a warning/error if search is wrapped or nothing found.)
</p>
<p>
When the search command key ('/') was entered in the pager, display() quits
with RET_SEARCH. Additionally, "search.type" (see
<a href="#struct">Search Struct</a> below) is set to
SEARCH_FORWARD.
</p>
<p>
In <a href="hacking.html#main">main()</a> (see hacking.*), when
RET_SEARCH is encountered, first the search string is read from the user with
readline("/"). If '^D' was typed, the search is immediately aborted. If nothing
was typed in (just <return>), we reuse the previous search string; otherwise we
store the new one.
</p>
<p>
Having this, the actual search is performed. This is described under
<a href="#search">Search</a> below.
</p>
<p>
The result of the search operation is a new cursor position. The main loop
iteration is ended now, and the pager gets restarted in the next iteration. The
display() then knows to jump to the new position by "search.type" being set.
</p>
</a> <!-- framework -->
<a name="struct" id="struct">
<h2>Search Struct</h2>
<p>
For passing information between the search code in the pager and in main(), as
well as between multiple searches, a global "search" struct is defined in
search.c.
</p>
<p>
This struct is of type "struct Search" and presently contains the following data:
<ul> <li>
"string" is the current/last search string requested. It is stored so it can
be reused when the user request search again (typing <return> immediately at
the search prompt, see <a href="#framework">Framework</a> above.
</li><li>
"type" has a dual function: In the pager it is set so the search function in
main() will know what kind of search to perform: forward, backward, next...
(This is presently a no-op, as there is only one search type available...)
When returning to a pager the presence of this flag means there was a search
and the cursor needs to be set to the new position. Again, see
<a href="#framework">Framework</a> for details.
</li></ul>
</p>
</a> <!-- struct -->
<a name="search" id="search">
<h2>Search</h2>
<p>
The search itself is done in several steps. First we need to determine where on
the page the cursor stands to know where to search from, i.e. find out in which
text item, and the exact position inside this item's text string.
</p>
<p>
This part is fairly complicated, as there are several possibilities; it's
actually the most complicated part of all. The most basic possibility is that
the cursor stands inmidst some text line. For this to find out, we have to
check all text items present in the cursor line (using the
<a href="hacking-layout.html#pageMap">page_map[]</a>, which is described
under <a href="hacking-layout.html#createMap">create_map()</a> in
hacking-layout.*). For each of those items we look up the beginning and end of
the text line visible in the scanned page line using the helper functions from
<a href="hacking-layout.html#itemsC">items.c</a> (see
hacking-layout.*). Note that
<a href="hacking-layout.html#lineStartEnd">line_start() and
line_end()</a> return the position of the line inside the text string,
while <a href="hacking-layout.html#linePos">line_pos()</a> gives
the page position of the line start.
</p>
<p>
Now if the cursor actually stands inside the line (the offset of the cursor
position ralatively to the beginning of the line is >=0 and smaller than the
line width), we simply store the string position of the cursor, which is the
string position of the line start plus the offset.
</p>
<p><pre>
page:
First paragraph
with centered text. <-- cursor_y
| ^
|<------->|
line_pos() offset cursor_x
string: "First paragraph with centered text."
| ^
|<------->|
line_start() offset start_pos
</pre></p>
<p>
The cursor may also stand before the beginning of the line. In this case we
want to search from the beginning of the line. This is achieved by just
assuming the cursor *does* stand at the beginning of the line (setting "offset"
to 0).
</p>
<p><pre>
First paragraph
with centered text. <--
^ |
|<->|
offset<0
</pre></p>
<p>
A third case is that the cursor stands behind the end of the text line, but
still inside the text block (i.e. this is not the last line). Here, the search
starts with the beginning of the next line. (Which is equal to the end of this
one.)
</p>
<p><pre>
line_start() line_end()
v v
First paragraph <--
with centered text.
| ^
|<--------------->|
offset >= line_end()-line_start()
</pre></p>
<p>
Another procedure is necessary if the cursor doesn't stand inside a text item
at all (the above search has no result). In this case we have to search from
the beginning of the next text item. For this, we simply scan all text items in
the page and take the first one that starts after "cursor_y". (Alternatively we
could scan the page linewise starting with the next line... This would be way
more efficient, but may cause problems when tables and similar things are
implemented. We will revise this at some point.)
</p>
<p><pre>
First paragraph <-- item->y_start <= cursor_y
with centered text.
<-- cursor_y
Second paragraph. <-- item->y_start > cursor_y <== start_item
^
start_pos=0
</pre></p>
<p>
Now the real search can start. It is done item by item, till the page end. In
each text item, we search for the search string inside the item's text string
with strstr(). For the first item, we start with "start_pos" as offset, so only
the string part after the cursor position is searched; for all following items,
"start_pos" is set to 0.
</p>
<p>
As soon as strstr() returns the first match, the matching item and the position
inside the string are memorized, and the search is terminated.
</p>
<p>
If nothing was found, the search is wrapped: In a second step, all items
beginning with the first one on the page and ending with the start item are
scanned. (Note that the start item is searched again, this time starting at the
beginning of the string. The part after "start_pos" is searched a second time,
but this shouldn't matter.)
</p>
<p>
There is an exception if the search started at the page end ("start_item" is
NULL): We can't scan up to the start item inclusive in this case, of course;
instead, we simply scan to the page end. (No special handling of this case is
necessary in the first pass, as that one just scans to the page end, thus will
simply terminate immediately.)
</p>
<p>
Finally the match position needs to be transformed back to page coordinates
again. This is much simpler than the other way round: We just need to find out
in which line of the text item the match position is located, and can calculate
y and x coordinates from the line number and the line position then.
</p>
<p><pre>
line_end(0) line_end(1)
v v
string: "First paragraph with centered text."
| ^
|<----------->|
line_start(1) offset match_pos
page:
First paragraph
with centered text. <-- cursor_y=line_end(1)
| ^
|<----------->|
line_pos(1) offset cursor_x
</pre></p>
</a> <!-- search -->
</body>
</html>
|
