bsearc.3: Add EXAMPLES section

[fernape]

Summary

Add a small EXAMPLES section to bsearch(3) man page.

Test Plan

• Apply the patch
• man ./bsearch.3 and inspect results
• compile and run example

[bcr]

A small typo fix, the rest looks good.

bsearch.3

87 ↗

(On Diff #56177)

s/searchs/searches/

[fernape]

Fix typo

[bcr]

Approved. Don't forget to bump the .Dd to today. Thank you!

[jilles]

bsearch.3

100 ↗

(On Diff #56180)

Strict compiler warning settings will warn about casts between pointers and integers of different size. You can pass the integer by pointer or add intermediate (intptr_t) casts.

123 ↗

(On Diff #56180)

An alternative to comments could be some form of assertion (such as assert(3)) that can be verified automatically.

[fernape]

• Eliminate cast to different size warning
• Replace comments with assertions

[fernape]

bsearch.3

100 ↗

(On Diff #56180)

Sorry I didn't catch that. clang -Wall doesn't complain about it, but it seems gcc8 -Wall does.

[fernape]

Properly escape \n sequences

[fernape]

Is there anything else that needs to be done?

[bcr]

I don't think so. I'll get this committed soon. Thank you for adding this example!

[bcr]

Reopen this based on comments by Konstantin and Bruce after the MFC to stable/12. @fernape: Can you look into their comments and address them in a followup patch? Thank you!

[bcr]

Adding Konstantin and Rod for review. I could not find Bruce Evans as a reviewer account...

[fernape]

In D19902#437776, @bcr wrote:

Reopen this based on comments by Konstantin and Bruce after the MFC to stable/12. @fernape: Can you look into their comments and address them in a followup patch? Thank you!

Sure thing. I'm AFK but I will try and have a look in the next couple of days.

[hrs]

As already pointed out on the mailing list, this example has a lot of problems which are not only style bugs. Ones I think as critical except for the style issues are the following:

• The function to compare two elements should accept the same type, not using an "age" field value by using a pointer type. It is a function to compare, not look up a matched element in the definition of bsearch(3). Passing a raw value as (void *) type is not impossible, but it is not suitable for a "textbook" example.
• Using assert() looks strange to me. Instead, this program should accept a value of "key" from the command line argument and show the results of bsearch(3) depending on the specified key, and this manual page should describe what results are expected.

[hrs]

head/lib/libc/stdlib/bsearch.3

96

Do not use a hard-coded array length here. (const char *) should be enough.

101

• As explained in my other comment, two arguments are supposed to be pointers for an object (the key object and an array member object), not a key "value" and an object.
• Use simple variable names such as "a" and "b", which are commonly used in this kind of examples.

104

Two problems:

• Use a pointer instead of copying the array_member. This causes unnecessary overhead.
• "const" must be used because array_member is (const void *).

Thus (const struct person *) is better.

110

Use main(void) if you do not use the command line arguments.

114

I think it is better to move the definition of "friends" to just after the declaration of struct person. It is easier for the readers to understand an example which has data structure and contents on a close location.

115

Do not use a hard-coded array length. [] works.

124

Do not use sizeof(type) wherever possible. The following is better:

len = sizeof(friends) / sizeof(friends[0]);

126

• Create a key object for "22" and pass it as the first argument without casting.
• Use sizeof(friends[0]) or sizeof("key object name") instead of sizeof(struct person).

[hrs]

head/lib/libc/stdlib/bsearch.3

128

Why "\e" is used here? I guess "\n" is intended.

[jilles]

In D19902#437950, @hrs wrote:

As already pointed out on the mailing list, this example has a lot of problems which are not only style bugs. Ones I think as critical except for the style issues are the following:

• The function to compare two elements should accept the same type, not using an "age" field value by using a pointer type. It is a function to compare, not look up a matched element in the definition of bsearch(3). Passing a raw value as (void *) type is not impossible, but it is not suitable for a "textbook" example.

Perhaps it is cleaner to pass the int age to be searched for by reference. However, the asymmetry in the compare function is intentional as this allows finding an object with more data given the key, while having only one storage array.

• Using assert() looks strange to me. Instead, this program should accept a value of "key" from the command line argument and show the results of bsearch(3) depending on the specified key, and this manual page should describe what results are expected.

I suggested assert() to make it possible to verify the example automatically. If assert() is deemed unsuitable, I'm fine with any mechanism that can write an error message and exit with a non-zero status if an unexpected result is found.

Testing examples in man pages is a pain and I rarely add examples for that reason. Perhaps some "doctest" mechanism could be written that automatically extracts examples, compiles them and runs them (if sensible).

[jilles]

head/lib/libc/stdlib/bsearch.3

128

The \e is required due to mdoc markup. Writing just \n does not render properly.

[hrs]

In D19902#437962, @jilles wrote:

Perhaps it is cleaner to pass the int age to be searched for by reference. However, the asymmetry in the compare function is intentional as this allows finding an object with more data given the key, while having only one storage array.

Asymmetry of the two arguments gives more capability of data lookup? I do not see a big difference between passing an int value 22 by casting it to (void *) as in the original patch and passing a pointer to a struct person which contains age = 22, in terms of the lookup operation. Can you elaborate a case in which the symmetry arguments do not work?

I suggested assert() to make it possible to verify the example automatically. If assert() is deemed unsuitable, I'm fine with any mechanism that can write an error message and exit with a non-zero status if an unexpected result is found.

I do not object to importance of assert() and testing. I just thought this code fragments should be kept simple and short as possible since they are intended to show how to use bsearch(3). From this viewpoint, using if-else clause would be sufficient. I fully agree we should have a way to extract examples and do test automatically.

head/lib/libc/stdlib/bsearch.3

128

Ah, I see. Thanks. Please forget it.

[fernape]

Addressing most of the issues with the revision:

• Use const whenever possible, including casts
• Use simpler names in comparison function
• Use pointers instead of copy of data in comparison function
• Indent struct names
• Order struct fields by size
• Use common idiom to get number of array elements
• Don't use K&R main() definition
• Use proper object when calling bsearch(3) instead of a casted constant
• Add comment for "fred" case

I like the assert() better than the if, but I will change it if that is the
consensus in the review.

For the "fred" case, the OR'ed assert was intended since the man page states
that in case of repetition (the two 25 were intended too, not poorly chosen) any
matching value will be returned. I added a comment to make this clear in case
someone jumps to the example instead of reading a few paragraphs above.

[jilles]

In D19902#437991, @hrs wrote:

In D19902#437962, @jilles wrote:

Perhaps it is cleaner to pass the int age to be searched for by reference. However, the asymmetry in the compare function is intentional as this allows finding an object with more data given the key, while having only one storage array.

Asymmetry of the two arguments gives more capability of data lookup? I do not see a big difference between passing an int value 22 by casting it to (void *) as in the original patch and passing a pointer to a struct person which contains age = 22, in terms of the lookup operation. Can you elaborate a case in which the symmetry arguments do not work?

The problem is not that it does not work, but that it creates a bogus value of type struct person which only contains an age. Although C's type system is unsound, I still prefer to avoid subverting it like this.

[kib]

lib/libc/stdlib/bsearch.3

103 ↗

(On Diff #57607)

Style(9) disallows initialization in declaration for locals. You cannot avoid it for const locals, but person_X vars are not const.

Casts should not have space after ')'.

113 ↗

(On Diff #57607)

Blanks lines are excessive.

127 ↗

(On Diff #57607)

I do not believe that the standard in any way specifies that the key (AKA first) argument to bsearch() and compare() must point to an object of the same type as the array element. It should be a valid pointer to some object, and it is up to compare() to make proper use of it.

Let it put another way, you can just pass a pointer to int, and dereference int instead of struct person, for the first argument of compare. Then you do not need to create fake name for the search key element.

133 ↗

(On Diff #57607)

Multi-line comment should have a blank line before it.

145 ↗

(On Diff #57607)

This return is not needed.

[fernape]

• Don't initialize locals in declaration
• Remove spaces after casts
• Remove excesive blank lines
• Revert to "asymmetric" compare function
• Add blank line before multi-line comment
• Remove return in main()

[fernape]

In D19902#438246, @jilles wrote:

In D19902#437991, @hrs wrote:

In D19902#437962, @jilles wrote:

Perhaps it is cleaner to pass the int age to be searched for by reference. However, the asymmetry in the compare function is intentional as this allows finding an object with more data given the key, while having only one storage array.

Asymmetry of the two arguments gives more capability of data lookup? I do not see a big difference between passing an int value 22 by casting it to (void *) as in the original patch and passing a pointer to a struct person which contains age = 22, in terms of the lookup operation. Can you elaborate a case in which the symmetry arguments do not work?

The problem is not that it does not work, but that it creates a bogus value of type struct person which only contains an age. Although C's type system is unsound, I still prefer to avoid subverting it like this.

[kib]

lib/libc/stdlib/bsearch.3

115 ↗

(On Diff #57774)

Add declaration

int age;

right after this line.

125 ↗

(On Diff #57774)

No need for the blank line.

128 ↗

(On Diff #57774)

Leave this line as pure asignment,

age = 22;

[fernape]

Address last of kib's comments.

[kib]

lib/libc/stdlib/bsearch.3

104 ↗

(On Diff #57801)

I somehow missed it previous time. Why do you copy key/element into local variables ? `

 const int *age;
 const struct person *person;

age = a;
person = b;
return (*age - person->age);

[fernape]

Do not copy values into local variables

[fernape]

lib/libc/stdlib/bsearch.3

104 ↗

(On Diff #57801)

Regarding this copy into local variables and also their initialization, is the qsort(3) EXAMPLE in -current following style(9)?

Thanks for your time reviewing this!

[kib]

lib/libc/stdlib/bsearch.3

104 ↗

(On Diff #57801)

First, it i not a style(9) issue, but just a question of reasonable code. Second, for int's used in the qsort(3) example, it really does not matter do you dereference the values manually as done in the example, or use *a *b an comparision and leave tracking of the values to compiler.

But there, I do not see a point to read the name pointer which is implied by assigning the whole structure to the local instance. Even if clever optimizing compiler notes that it can only copy single member, it still has cognitive load on the meat-and-fat reader.

[fernape]

lib/libc/stdlib/bsearch.3

104 ↗

(On Diff #57801)

Understood.

Thanks!

[fernape]

Hi there,

Is there anything that prevents this review to be committed?

Thanks!