Page MenuHomeFreeBSD

bsearc.3: Add EXAMPLES section
ClosedPublic

Authored by fernape on Apr 13 2019, 5:15 PM.

Details

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

Diff Detail

Repository
rS FreeBSD src repository
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
bcr added a subscriber: bcr.Apr 13 2019, 5:34 PM

A small typo fix, the rest looks good.

bsearch.3
87 ↗(On Diff #56177)

s/searchs/searches/

fernape updated this revision to Diff 56180.Apr 13 2019, 5:56 PM

Fix typo

fernape marked an inline comment as done.Apr 13 2019, 5:56 PM
bcr accepted this revision.Apr 13 2019, 6:14 PM

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

This revision is now accepted and ready to land.Apr 13 2019, 6:14 PM
jilles added a subscriber: jilles.Apr 13 2019, 7:38 PM
jilles added inline comments.
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.

dab accepted this revision.Apr 13 2019, 7:59 PM
fernape updated this revision to Diff 56203.Apr 14 2019, 4:58 PM
  • Eliminate cast to different size warning
  • Replace comments with assertions
This revision now requires review to proceed.Apr 14 2019, 4:58 PM
fernape added inline comments.Apr 14 2019, 5:01 PM
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.

jilles accepted this revision.Apr 15 2019, 4:39 PM
This revision is now accepted and ready to land.Apr 15 2019, 4:39 PM
0mp accepted this revision.Apr 16 2019, 8:57 AM
fernape updated this revision to Diff 56301.Apr 17 2019, 5:52 PM

Properly escape \n sequences

This revision now requires review to proceed.Apr 17 2019, 5:52 PM

Is there anything else that needs to be done?

bcr added a comment.May 15 2019, 3:46 PM

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

This revision was not accepted when it landed; it landed in state Needs Review.May 15 2019, 3:54 PM
This revision was automatically updated to reflect the committed changes.
bcr reopened this revision.May 18 2019, 8:32 PM

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!

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

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 added a subscriber: hrs.May 19 2019, 7:37 PM
hrs added a comment.May 19 2019, 7:55 PM

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 added inline comments.May 19 2019, 8:36 PM
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 added inline comments.May 19 2019, 8:37 PM
head/lib/libc/stdlib/bsearch.3
128

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

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 added inline comments.May 19 2019, 8:51 PM
head/lib/libc/stdlib/bsearch.3
128

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

hrs added a comment.May 19 2019, 9:26 PM

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 updated this revision to Diff 57607.May 20 2019, 9:09 PM

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.

fernape marked 7 inline comments as done.May 20 2019, 9:11 PM
In D19902#437991, @hrs 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 added inline comments.May 21 2019, 6:43 AM
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 updated this revision to Diff 57774.May 23 2019, 3:55 PM
  • 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 marked 5 inline comments as done.May 23 2019, 3:56 PM
In D19902#437991, @hrs 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 added inline comments.May 23 2019, 4:08 PM
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 updated this revision to Diff 57801.May 23 2019, 8:53 PM

Address last of kib's comments.

fernape marked 3 inline comments as done.May 23 2019, 8:54 PM
kib added inline comments.May 23 2019, 9:08 PM
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 updated this revision to Diff 57845.May 24 2019, 4:28 PM

Do not copy values into local variables

fernape marked an inline comment as done.May 24 2019, 4:29 PM
fernape added inline comments.
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 accepted this revision.May 24 2019, 4:53 PM
kib added inline comments.
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.

This revision is now accepted and ready to land.May 24 2019, 4:53 PM
fernape marked an inline comment as done.May 24 2019, 4:57 PM
fernape added inline comments.
lib/libc/stdlib/bsearch.3
104 ↗(On Diff #57801)

Understood.

Thanks!

Hi there,

Is there anything that prevents this review to be committed?

Thanks!

This revision was automatically updated to reflect the committed changes.