Comments are welcome for two sequential search C functions

[August Karlstrom]

Using break; is ugly. Consider..

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
for (i = 0; i < len; ++i) {
if (val == array) {
ret = i; /* set the return value */
i = len; /* kill the for loop */
}
}
}
return ret;
}

I think a while-loop is even clearer:

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
i = 0;
while ((i < len) && (val != array)) {
i++;
}
if (val == array) {
ret = i;
}
}
return ret;
}

It might be clearer, but it's also wrong. On any
unsuccessful search, the loop terminates with i==len.
Then the test val==array gives undefined behavior due
to the out-of-bounds array index.

Yes, of course. How careless of me. It should be:

int lookup(int val, const int array[], int len)
{
int i, ret = -1;
if (array != NULL && len > 0) {
i = 0;
while ((i < len) && (val != array)) {
i++;
}
if (i < len) {
ret = i;
}
}
return ret;
}


August

 

[August Karlstrom]

Applying my advice to your code (which, of course, you're entirely
free to ignore), we get this (not tested):

/*lookup.c*/
#include <stddef.h>
int lookup(int val, const int array[], int len){
int i;

if (array != NULL && len > 0){
for (i = 0; i < len; ++i){
if (val == array){
return i;
}
}
}
return -1;
}

I have heard that multiple exit points makes function inline
optimization more difficult. If that is the case, the use of a result
variable might be a better choice.


August

 

[Ian Collins]

Applying my advice to your code (which, of course, you're entirely
free to ignore), we get this (not tested):

/*lookup.c*/
#include <stddef.h>
int lookup(int val, const int array[], int len){
int i;

if (array != NULL && len > 0){
for (i = 0; i < len; ++i){
if (val == array){
return i;
}
}
}
return -1;
}

I have heard that multiple exit points makes function inline
optimization more difficult. If that is the case, the use of a result
variable might be a better choice.

They can also cause logic errors if the setting of a state gets missed,
releasing a lock for example

 

[Flash Gordon]

Applying my advice to your code (which, of course, you're entirely
free to ignore), we get this (not tested):

/*lookup.c*/
#include <stddef.h>
int lookup(int val, const int array[], int len){
int i;

if (array != NULL && len > 0){
for (i = 0; i < len; ++i){
if (val == array){
return i;
}
}
}
return -1;
}

I have heard that multiple exit points makes function inline
optimization more difficult. If that is the case, the use of a result
variable might be a better choice.

First rule of optimisation: Don't do it.
Second rule (for experts only): Don't do it yet.

Unless you have measured and found this to be a problem, use the
solution that is easier to implement correctly and easier to maintain.
Some people might choose the single exit for that reason, some might
choose the multiple exit for that reason.

In any case, this is a common enough idiom that I would be surprised if
optimisers did not handle it well.

 

[websnarf]

(b) here is a way to write it without break:

int lookup(val, const int array[], int len)
{
int i = -1;
if(array != NULL && len != 0)
{
while(i < len && val != array)

And this won't try to access array[-1] ? Just goes to show, even the
most experience programmers are not immune to buffer overflows.

 

[Richard Heathfield]

(e-mail address removed) said:

(b) here is a way to write it without break:

int lookup(val, const int array[], int len)
{
int i = -1;
if(array != NULL && len != 0)
{
while(i < len && val != array)

And this won't try to access array[-1] ?

Ouch! Nice spot.

Fortunately for my peace of mind, in my own code I clearly separate the
concepts of "output data" and "error information". The above boo-boo is a
result of trying to combine them.

 

[Al Balmer]

Different strokes, I guess. I find the break less ugly. In fact, not
being quite so uptight about multiple returns in tiny functions, I'd
probably write (untested)

int lookup(int val, const int array[], int len)
{
int i;
if (array != NULL && len > 0) {
for (i = 0; i < len; ++i) {
if (val == array) {
return i;
}
}
}
return -1;
}

In this version, the "&& len > 0" is redundant. If len == 0, the loop
won't execute, and you'll fall through to the "return -1;".

(Or len < 0) Quite true, of course. I just replaced the inner loop. In
real life, I'd look a little closer, especially since the
non-idiomatic style of the original would indicate (in my environment)
a less experienced programmer.

 

[Al Balmer]

Applying my advice to your code (which, of course, you're entirely
free to ignore), we get this (not tested):

/*lookup.c*/
#include <stddef.h>
int lookup(int val, const int array[], int len){
int i;

if (array != NULL && len > 0){
for (i = 0; i < len; ++i){
if (val == array){
return i;
}
}
}
return -1;
}

I have heard that multiple exit points makes function inline
optimization more difficult. If that is the case, the use of a result
variable might be a better choice.

<G> I don't write code based on rumors about hardship for compilers.

 

[Ben Bacarisse]

lovecreatesbeauty said:

Any comments are welcome for following the two sequential search C

#include <stddef.h>

int lookup(int val, const int array[], int len)
{
int i = -1;

if (array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (val == array){
break;
}
}
}
return i;
}

(b) here is a way to write it without break:

int lookup(val, const int array[], int len)
{
int i = -1;
if(array != NULL && len != 0)
{
while(i < len && val != array)
{
++i;
}
if(i == len)
{
i = -1;
}
}
return i;
}

This has one of the worst kinds of UB as it will run correctly on a
wide range of systems and you probably won't even *smell* a dragon --
it just might report, sometimes, that an element is "not there" when in
fact it is.

You need, of course, to set i to 0 before asking about array for
the first time (and to give a type for "val").

 

[Richard Heathfield]

Ben Bacarisse said:

Richard Heathfield <[email protected]> wrote:

This has one of the worst kinds of UB

I know, I know - very embarrassing and all that. Would you believe me if I
told you my personal code library doesn't do things that way?

 

[August Karlstrom]

Ben Bacarisse said:




I know, I know - very embarrassing and all that. Would you believe me if I
told you my personal code library doesn't do things that way?

Richard Heathfield wrote (in thread "Inflexible array members"):

Just as I wouldn't criticise my wife for failing to tell me to fasten my
seatbelt, so I don't criticise my compiler for failing to tell me about
buffer overruns. Remembering to fasten my seatbelt is /my/ job, and I can
take care of it myself, but of course someone needs to keep an eye on the
kids in the back. Avoiding buffer overruns is /my/ job, and I can take care
of it myself, but of course someone needs to keep an eye on the Java kids
in the back.

You're not one of those kids in the back, are you? ;-)

Sorry for being such a pain in the behind. Just couldn't help myself.


August

 

[Richard Heathfield]

August Karlstrom said:

Richard Heathfield wrote (in thread "Inflexible array members"):

All right, all right! I KNOW! I KNOW!

It was my job to check that the code was correct before I posted it, and I
failed to do that. This is now the third time I have acknowledged the fact.
What do you want, sack-cloth and ashes?

If anything, this little incident does help to show why comp.lang.c is such
a valuable resource. The code reviews are first-class, and nobody is immune
from them. That's a Good Thing, even (or perhaps /especially/) when it
bites a reg.

But can we drop it now, please?

Sorry for being such a pain in the behind. Just couldn't help myself.

Don't worry about it. I'll get you the next time.