1 05/17/86  find_char_
  2 
  3 
  4 This subroutine uses the EIS test character and translate (TCT)
  5 instruction to perform the function of the PL/I search and verify
  6 builtin functions in a highly efficient manner.  Search and verify
  7 operations can be performed from either the left or right end of the
  8 string.
  9 
 10 
 11 The search function looks for the first occurrence of any of a set of
 12 characters (the search characters) within an input character string.
 13 The verify function checks that all characters within an input string
 14 are also characters in a verify string.  It searches in the input
 15 string for the first occurrence of a character not in the verify
 16 string.
 17 
 18 
 19 Notes:  The TCT instruction uses a test-and-translate table to control
 20 the searching.  Entrypoints are provided to build a table that can be
 21 used for several search or verify operations, or to build tables as
 22 part of each search or verify operation.
 23 
 24 
 25 The PL/I compiler generates efficient, in-line TCT or TCTR instructions
 26 when the second argument of the search or verify builtin function is a
 27 constant (so that the test-and-translate table can be constructed at
 28 compile time).  However, when the second argument is a variable, PL/I
 29 uses a less efficient operator call to perform the search or verify
 30 operation.  This operator tests each character of the first string to
 31 see if it appears in the second string.  The rationale for PL/I
 32 operator is that, for short first arguments, it is more expensive to
 33 construct a test-and-translate table at run-time than to do the
 34 indexing.  Programs which must search lengthy strings with a variable
 35 second argument can use find_char_ to avoid using the PL/I operator,
 36 thereby regaining the efficiency of the TCT instruction.
 37 
 38 
 39 The test-and-translate table is an aligned, fixed length character
 40 string, 512 characters long to cover all possible Multics 9-bit byte
 41 values.  It consists of "\000" characters and characters which are not
 42 "\000".  Searching (or verifying) using a test-and-translate table
 43 progresses as follows:
 44 
 45 1)   Examine the first (or next) character of the input string.  If i
 46      is the index of the character being examined, then:
 47 
 48         input_char = substr(string, i, 1)
 49 
 50 2)   For each input_char, examine its corresponding table_char
 51      value:
 52 
 53         table_char = substr(table,rank(input_char)+1,1)
 54 
 55 
 56 3)   If table_char = "\000", then the test fails and the search
 57      continues with step 1.
 58 
 59 4)   If table_char ^= "\000", then the test succeeds and the search
 60      stops.  The current value of i is returned as the index value.
 61      For the find_char_$translate_first_in_table and
 62      $translate_last_in_table entrypoints, table_char is also returned.
 63 
 64 5)   If the input string is exhausted before the test succeeds, then a
 65      value of 0 is returned as the index argument.  For the
 66      find_char_$translate_first_in_table and $translate_last_in_table
 67      entrypoints, "\000" is returned as the table_char.
 68 
 69 
 70 Entry points in find_char_:
 71    (List is generated by the help command)
 72 
 73 
 74 :Entry:  first_in_list:  05/16/86 find_char_$first_in_list
 75 
 76 
 77 Function:  This entry performs the PL/I search function, returning the
 78 character index of the first (leftmost) occurrence of one of the
 79 search_chars in the input string.  It constructs the test-and-translate
 80 table used by the TCT instruction from search_chars string provided by
 81 the caller.
 82 
 83 
 84 Syntax:
 85 declare find_char_$first_in_list entry (char(*), char(*))
 86      returns (fixed bin(21)) reducible;
 87 
 88 index = find_char_$first_in_list (string, search_chars);
 89 
 90 
 91 Arguments:
 92 string
 93    is the character string to be searched.  (In)
 94 search_chars
 95    are characters to be found in the string.  (In)
 96 index
 97    is the result of the search.  It is the PL/I string index (character
 98    position) of the first occurrence of one of the search_chars in the
 99    input string.  0 is returned if none of the search_chars appear in
100    the input string.  (Out)
101 
102 
103 :Entry:  last_in_list:  05/16/86 find_char_$last_in_list
104 
105 
106 Function:  This entry returns the character index (character position
107 relative to the beginning of the string) of the last (rightmost)
108 occurrence of one of the search_chars in the input string.  It performs
109 the PL/I function:
110 
111    index = length(string) - search (reverse(string), chars) + 1
112                  [when char searched for is found in string]
113    index = 0     [when char searched for is not found.]
114 
115 It constructs the test-and-translate table used by the TCT instruction
116 from search_chars string provided by the caller.
117 
118 
119 Syntax:
120 declare find_char_$last_in_list entry (char(*), char(*))
121      returns (fixed bin(21)) reducible;
122 
123 index = find_char_$last_in_list (string, search_chars);
124 
125 
126 Arguments:
127 string
128    is the character string to be searched.  (In)
129 search_chars
130    are characters to be found in the string.  (In)
131 index
132    is the result of the search.  It is the PL/I string index (character
133    position) of the last (rightmost) occurrence of one of the
134    search_chars in the input string.  0 is returned if none of the
135    search_chars appear in the input string.  (Out)
136 
137 
138 :Entry:  first_not_in_list:  05/16/86 find_char_$first_not_in_list
139 
140 
141 Function:  This entry performs the PL/I verify function, returning the
142 character index of the first (leftmost) occurrence in the input string
143 of a character which is not one of the verify_chars.  It constructs the
144 test-and-translate table from the verify_chars provided by the caller.
145 
146 
147 Syntax:
148 declare find_char_$first_not_in_list entry (char(*), char(*))
149      returns (fixed bin(21)) reducible;
150 
151 index = find_char_$first_not_in_list (string, verify_chars);
152 
153 
154 Arguments:
155 string
156    is the character string to be searched.  (In)
157 verify_chars
158    are characters which are skipped over when searching the string.
159    (In)
160 index
161    is the result of the verify.  It is the PL/I string index (character
162    position) of the first (leftmost) occurrence of a character in the
163    input string which is not one of the verify_chars.  0 is returned if
164    the entire input string contains only the characters in
165    verify_chars.  (Out)
166 
167 
168 :Entry:  last_not_in_list:  05/16/86 find_char_$last_not_in_list
169 
170 
171 Function:  This entry returns the index (character position relative to
172 the beginning of the string) of the last (rightmost) occurrence of a
173 character in the input string which is not one of the verify_chars.  It
174 performs the PL/I function:
175 
176     index = length(string) - verify (reverse(string), chars) + 1;
177                  [when character not in chars is found in string]
178     index = 0;   [when character not in chars is not found in string.]
179 
180 It constructs the test-and-translate table from the verify_chars
181 provided by the caller.
182 
183 
184 Syntax:
185 declare find_char_$last_not_in_list entry (char(*), char(*))
186      returns (fixed bin(21)) reducible;
187 
188 index = find_char_$last_not_in_list (string, verify_chars);
189 
190 
191 Arguments:
192 string
193    is the character string to be searched.  (In)
194 verify_chars
195    are characters to be skipped over when searching the string.  (In)
196 index
197    is the result of the verify.  It is the PL/I string index (character
198    position) of the last (rightmost) occurrence of a character in the
199    input string which is not one of the verify_chars.  0 is returned if
200    the entire input string contains only the characters in
201    verify_chars.  (Out)
202 
203 
204 :Entry:  first_in_table:  05/16/86 find_char_$first_in_table
205 
206 
207 Function:  This entry point searches an input string from the left,
208 using a user-defined test-and-translate table.  Either a search or a
209 verify operation can be performed, depending upon the contents of the
210 table.  find_char_$make_table_from_chars_in_list can be used to
211 construct a search_table from a set of search_chars;
212 find_char_$make_table_from_chars_not_in_list can be used to construct a
213 verify_table from a set of verify_chars; or the user can create a table
214 containing his own values.  As described in the Notes, searching
215 continues until an input string character corresponds to a nonzero
216 element of the table.  The character index of the input string
217 character is returned.
218 
219 
220 Syntax:
221 declare find_char_$first_in_table entry (char(*), char(512) aligned)
222      returns (fixed bin(21)) reducible;
223 
224 index = find_char_$first_in_table (string, table);
225 
226 
227 Arguments:
228 string
229    is the character string to be searched.  (In)
230 table
231    is the test-and-translate table.  (In)
232 index
233    is the result of the search.  It is a PL/I string index (character
234    position) of the first (leftmost) input character corresponding to a
235    nonzero table element.  0 is returned if no input characters
236    correspond to a nonzero table element.  (Out)
237 
238 
239 :Entry:  last_in_table:  05/16/86 find_char_$last_in_table
240 
241 
242 Function:  This entry point searches an input string from the right,
243 using a user-defined test-and-translate table.  Either a search or a
244 verify operation can be performed, depending upon the contents of the
245 table.  find_char_$make_table_from_chars_in_list can be used to
246 construct a search_table from a set of search_chars;
247 find_char_$make_table_from_chars_not_in_list can be used to construct a
248 verify_table from a set of verify_chars; or the user can create a table
249 containing his own values.  As described in the Notes, searching
250 continues until an input string character corresponds to a nonzero
251 element of the table.  The character index of the input string
252 character is returned.
253 
254 
255 Syntax:
256 declare find_char_$last_in_table entry (char(*), char(512) aligned)
257      returns (fixed bin(21)) reducible;
258 
259 index = find_char_$last_in_table (string, table);
260 
261 
262 Arguments:
263 string
264    is the character string to be searched.  (In)
265 table
266    is the test-and-translate table.  (In)
267 index
268    is the result of the search.  It is a PL/I string index (character
269    position) of the last (rightmost) input character corresponding to a
270    nonzero table element.  0 is returned if no input characters
271    correspond to a nonzero table element.  (Out)
272 
273 
274 :Entry:  translate_first_in_table:  05/16/86 find_char_$translate_first_in_table
275 
276 
277 Function:  This entry point searches an input string from the left,
278 using a user-defined test-and-translate table.  Either a search or a
279 verify operation can be performed, depending upon the contents of the
280 table.  As described in the Notes, searching continues until an input
281 string character corresponds to a nonzero element of the table.  The
282 character index of the input string character is returned, along with
283 the nonzero table element.
284 
285 
286 Syntax:
287 declare find_char_$translate_first_in_table entry (char(*),
288      char(512) aligned, fixed bin(21)) returns (char(1));
289 
290 table_element = find_char_$translate_first_in_table (string, table,
291      index);
292 
293 
294 Arguments:
295 string
296    is the character string to be searched.  (In)
297 table
298    is the test-and-translate table.  (In)
299 index
300    is the result of the search.  It is a PL/I string index (character
301    position) of the first (leftmost) input character corresponding to a
302    nonzero table element.  0 is returned if no input characters
303    correspond to a nonzero table element.  (Out)
304 table_element
305    is the character from the test-and-translate table which corresponds
306    to the input string character selected by index.  "\000" is returned
307    when index=0.  (Out)
308 
309 
310 :Entry:  translate_last_in_table:  05/16/86 find_char_$translate_last_in_table
311 
312 
313 Function:  This entry point searches an input string from the right,
314 using a user-defined test-and-translate table.  Either a search or a
315 verify operation can be performed, depending upon the contents of the
316 table.  As described in the Notes, searching continues until an input
317 string character corresponds to a nonzero element of the table.  The
318 character index of the input string character is returned, along with
319 the nonzero table element.
320 
321 
322 Syntax:
323 declare find_char_$translate_last_in_table entry (char(*),
324      char(512) aligned, fixed bin(21)) returns (char(1));
325 
326 table_element = find_char_$translate_last_in_table (string, table,
327      index);
328 
329 
330 Arguments:
331 string
332    is the character string to be searched.  (In)
333 table
334    is the test-and-translate table.  (In)
335 index
336    is the result of the search.  It is a PL/I string index (character
337    position) of the last (rightmost) input character corresponding to a
338    nonzero table element.  0 is returned if no input characters
339    correspond to a nonzero table element.  (Out)
340 table_element
341    is the character from the test-and-translate table which corresponds
342    to the input string character selected by index.  "\000" is returned
343    when index=0.  (Out)
344 
345 
346 :Entry:  make_table_of_chars_in_list:  05/16/86 find_char_$make_table_of_chars_in_list
347 
348 
349 Function:  This entry constructs a test-and-translate table for use
350 with the find_char_$first_in_table and find_char_$last_in_table
351 entrypoints.  Table entries corresponding to characters of search_chars
352 are marked with \777 in the search table.  Other table entries are
353 filled with \000.
354 
355 
356 Syntax:
357 declare find_char_$make_table_of_chars_in_list entry (char(*),
358      char(512) aligned);
359 
360 call find_char_$make_table_of_chars_in_list (search_chars,
361      search_table);
362 
363 
364 Arguments:
365 search_chars
366    is a string of characters whose corresponding entries are to be
367    marked in the resulting translate table.  (In)
368 search_table
369    is the test-and-translate table.  (Out)
370 
371 
372 :Entry:  make_table_of_chars_not_in_list:  05/16/86 find_char_$make_table_of_chars_not_in_list
373 
374 
375 Function:  This entry constructs a test-and-translate table for use
376 with the find_char_$first_in_table and find_char_$last_in_table
377 entrypoints.  Table entries corresponding to characters of verify_chars
378 remain unmarked (\000 elements) in the table.  Other table elements are
379 filled with \777.
380 
381 
382 Syntax:
383 declare find_char_$make_table_of_chars_not_in_list entry (char(*),
384      char(512) aligned);
385 
386 call find_char_$make_table_of_chars_not_in_list (verify_chars,
387      verify_table);
388 
389 
390 Arguments:
391 verify_chars
392    is a string of characters whose corresponding entries are to remain
393    unmarked in the resulting translate table.  (In)
394 verify_table
395    is the test-and-translate table.  (Out)
396 
397 
398 :Entry:  not_ascii_table:  05/16/86 find_char_$not_ascii_table
399 
400 
401 Function:  This entrypoint is an external variable containing a
402 predefined test-and-translate table which can be used to detect any
403 non-ASCII characters in a character string.  Non-ASCII characters are
404 those in which one or both of the 2 leftmost bits of the 9-bit
405 character byte are "1"b (i.e., character > "\177").  The first 128
406 values in the table are "\000".  The next 384 table characters are set
407 to their character offset within the table.  This means that:
408 
409    substr(table,n+1,1) = "\000", for n:  000 <= n <= 127
410    substr(table,n+1,1) = "\n",   for n:  128 <= n <= 511
411 
412 
413 Syntax:
414 declare find_char_$not_ascii_table char(512) aligned external static;
415