07/26/82 sort_items_ The sort_items_ subroutine provides a generalized, yet highly efficient, sorting facility. Entry points are provided for sorting fixed binary (35) numbers, float binary (63) numbers, fixed-length character strings, varying character strings, and fixed-length bit strings. A generalized entry point is provided for sorting other data types (including data structures and data aggregates) and for sorting data into a user-defined order. The procedure implements the QUICKSORT algorithm of M. H. van Emden, including the Wheeler modification to detect ordered sequences. The subroutine takes a vector of unaligned pointers to the data items to be sorted and rearranges the elements of this vector to point to the data items in correct order. Only the pointers are moved or copied into temporary storage; the data items remain where they were when sort_items_ was invoked. Entry points in sort_items_: (List is generated by the help command) :Entry: fixed_bin: 07/26/82 sort_items_$fixed_bin Function: This entry point sorts a group of aligned fixed binary (35,0) numbers into numerical order by reordering a pointer array whose elements point to the numbers in the group. Syntax: declare sort_items_$fixed_bin entry (ptr); call sort_items_$fixed_bin (v_ptr); Arguments: v_ptr points to a structure containing an array of unaligned pointers to the aligned fixed binary (35,0) numbers to be sorted. (Input) Notes: The structure pointed to by v_ptr is to be declared as follows, where n is the value of v.n: dcl 1 v aligned, 2 n fixed bin (18), 2 vector (n) ptr unaligned; :Entry: float_bin: 07/26/82 sort_items_$float_bin Function: This entry point sorts a group of aligned float binary (63) numbers into numerical order by reordering a pointer array whose elements point to the numbers in the group. Syntax: declare sort_items_$float_bin entry (ptr); call sort_items_$float_bin (v_ptr); Arguments: v_ptr points to the above structure containing an array of unaligned pointers to the aligned float binary (63) numbers to be sorted. (Input) :Entry: char: 07/26/82 sort_items_$char Function: This entry point sorts a group of fixed-length unaligned character strings into ASCII collating sequence by reordering a pointer array whose elements point to the character strings in the group. Syntax: declare sort_items_$char entry (ptr, fixed bin (24)); call sort_items_$char (v_ptr, string_lth); Arguments: v_ptr points to the structure (described in "Notes" above) containing an array of unaligned pointers to the varying character strings to be sorted. (Input) string_lth is the length of each character string. (Input) :Entry: varying_char: 07/26/82 sort_items_$varying_char Function: This entry point sorts a group of varying character strings into ASCII collating sequence by reordering a pointer array whose elements point to the character strings in the group. Syntax: declare sort_items_$varying_char entry (ptr); call sort_items_$varying_char (v_ptr); Arguments: v_ptr points to the structure (described in "Notes" above) containing an array of unaligned pointers to the varying character strings to be sorted. (Input) :Entry: bit: 07/26/82 sort_items_$bit Function: This entry point sorts a group of fixed-length unaligned bit strings into bit string order by reordering a pointer array whose elements point to the bit strings in the group. Bit string ordering guarantees that, if each ordered bit string were converted to a binary natural number, the binary value would be less than or equal to the value of its successors. Syntax: declare sort_items_$bit entry (ptr, fixed bin (24)); call sort_items_$bit (v_ptr, length); Arguments: v_ptr points the structure (described in "Notes" above) containing an array of unaligned pointers to the fixed-length unaligned bit strings to be sorted. (Input) length is the number of bits in each string. (Input) :Entry: general: 07/26/82 sort_items_$general Function: This entry point sorts a group of arbitrary data elements, structures, or other aggregates into a user-defined order by reordering a pointer array whose elements point to the data items in the group. The structure of data items, the information field or fields within each item by which items are sorted, and the data ordering principle are all decoupled from the sorting algorithm by calling a user-supplied function to order pairs of data items. The function is called with pointers to a pair of items. It must compare the items and return a value that indicates whether the first item of the pair is less than, equal to, or greater than the second item. The sorting algorithm reorders the elements of the pointer array based upon the results of the item comparisons. Syntax: declare sort_items_$general entry (ptr, entry); call sort_items_$general (v_ptr, function); Arguments: v_ptr points the structure (described in "Notes" above) containing an array of unaligned pointers to the data items to be sorted. (Input) function is a user-supplied ordering function. (Input) Its calling sequence is shown under "Notes" below. Notes: The sort_items_$general entry point calls a user-supplied function to compare pairs of data items. This function must know the structure of the data items being compared, the field or fields within each item that are to be compared, and the ordering principle to be used in performing the comparisons. The function returns a relationship code as its value. The calling sequence of the function is shown below. declare function entry (ptr unaligned, ptr unaligned) returns (fixed bin(1)); value = function (ptr_first_item, ptr_second_item); Structure elements: ptr_first_item is an unaligned pointer to the first data item. (Input) ptr_second_item is an unaligned pointer to a data item to be compared with the first data item. (Input) value is the value of the first data item compared to the second data item. (Output) It can be: -1 the first data item is less than the second. 0 the first data item is equal to the second. +1 the first data item is greater than the second. ----------------------------------------------------------- Historical Background This edition of the Multics software materials and documentation is provided and donated to Massachusetts Institute of Technology by Group BULL including BULL HN Information Systems Inc. as a contribution to computer science knowledge. This donation is made also to give evidence of the common contributions of Massachusetts Institute of Technology, Bell Laboratories, General Electric, Honeywell Information Systems Inc., Honeywell BULL Inc., Groupe BULL and BULL HN Information Systems Inc. to the development of this operating system. Multics development was initiated by Massachusetts Institute of Technology Project MAC (1963-1970), renamed the MIT Laboratory for Computer Science and Artificial Intelligence in the mid 1970s, under the leadership of Professor Fernando Jose Corbato. Users consider that Multics provided the best software architecture for managing computer hardware properly and for executing programs. Many subsequent operating systems incorporated Multics principles. Multics was distributed in 1975 to 2000 by Group Bull in Europe , and in the U.S. by Bull HN Information Systems Inc., as successor in interest by change in name only to Honeywell Bull Inc. and Honeywell Information Systems Inc. . ----------------------------------------------------------- Permission to use, copy, modify, and distribute these programs and their documentation for any purpose and without fee is hereby granted,provided that the below copyright notice and historical background appear in all copies and that both the copyright notice and historical background and this permission notice appear in supporting documentation, and that the names of MIT, HIS, BULL or BULL HN not be used in advertising or publicity pertaining to distribution of the programs without specific prior written permission. Copyright 1972 by Massachusetts Institute of Technology and Honeywell Information Systems Inc. Copyright 2006 by BULL HN Information Systems Inc. Copyright 2006 by Bull SAS All Rights Reserved