Page MenuHomeFreeBSD

bsearc.3: Add EXAMPLES section
ClosedPublic

Authored by fernape on Apr 13 2019, 5:15 PM.
Tags
None
Referenced Files
Unknown Object (File)
Sun, Mar 17, 3:27 AM
Unknown Object (File)
Sun, Mar 17, 3:27 AM
Unknown Object (File)
Sun, Mar 17, 3:27 AM
Unknown Object (File)
Sun, Mar 17, 3:23 AM
Unknown Object (File)
Sun, Mar 17, 3:23 AM
Unknown Object (File)
Sun, Mar 17, 3:19 AM
Unknown Object (File)
Sun, Mar 17, 3:19 AM
Unknown Object (File)
Feb 17 2024, 9:54 PM
Subscribers

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

Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 23674
Build 22651: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

A small typo fix, the rest looks good.

bsearch.3
87 ↗(On Diff #56177)

s/searchs/searches/

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 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.

  • Eliminate cast to different size warning
  • Replace comments with assertions
This revision now requires review to proceed.Apr 14 2019, 4:58 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.

This revision is now accepted and ready to land.Apr 15 2019, 4:39 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?

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.

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.

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.
head/lib/libc/stdlib/bsearch.3
96 ↗(On Diff #57413)

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

101 ↗(On Diff #57413)
  • 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 ↗(On Diff #57413)

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 ↗(On Diff #57413)

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

114 ↗(On Diff #57413)

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 ↗(On Diff #57413)

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

124 ↗(On Diff #57413)

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

len = sizeof(friends) / sizeof(friends[0]);
126 ↗(On Diff #57413)
  • 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).
head/lib/libc/stdlib/bsearch.3
128 ↗(On Diff #57413)

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).

head/lib/libc/stdlib/bsearch.3
128 ↗(On Diff #57413)

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

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 ↗(On Diff #57413)

Ah, I see. Thanks. Please forget it.

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.

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.

lib/libc/stdlib/bsearch.3
85–141

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 ')'.

85–141

Blanks lines are excessive.

85–141

This return is not needed.

86

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.

87

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

  • 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()
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.

lib/libc/stdlib/bsearch.3
85–141

Add declaration

int age;

right after this line.

85–141

Leave this line as pure asignment,

age = 22;
85–141

No need for the blank line.

Address last of kib's comments.

lib/libc/stdlib/bsearch.3
86

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);

Do not copy values into local variables

fernape added inline comments.
lib/libc/stdlib/bsearch.3
86

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 added inline comments.
lib/libc/stdlib/bsearch.3
86

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 added inline comments.
lib/libc/stdlib/bsearch.3
86

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.