Comments are welcome for two sequential search C functions

[lovecreatesbeauty]

Any comments are welcome for following the two sequential search C
functions of both integer and string versions. Though they are simple,
please do not laugh at it :) Could you give your great suggestion to
it? Thanks a lot.

/*sequentially search a array of integers for a value. val: the integer
is to be searched for in the array, array: array of integers, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#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[i]){
break;
}
}
}
return i;
}

/*sequentially search a string array for a word. word: the word is to
be searched for in the array, array: array of word string, len: item
count in the array. return the index of the value found in array, -1
for failure. the algotithm efficience of the function is O(n). - jhl,
Jul 2006*/

#include <string.h>

int slookup(const char *word, const char *array[], int len)
{
int i = -1;

if (word != NULL && array != NULL && len != 0){
for (i = 0; i < len; ++i){
if (strcmp(word, array[i]) == 0){
break;
}
}
}
return i;
}

[August Karlstrom]

Eric Sosman wrote:

August Karlstrom wrote:

>Joe Wright wrote:

>>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[i]) {
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])) {
i++;
}
if (val == array[i]) {
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[i] 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])) {
i++;
}
if (i < len) {
ret = i;
}
}
return ret;
}
August

[August Karlstrom]

Keith Thompson wrote:

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[i]){
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]

August Karlstrom wrote:

Keith Thompson wrote:

>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[i]){
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

--
Ian Collins.

[Flash Gordon]

August Karlstrom wrote:

Keith Thompson wrote:

>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[i]){
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.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc

[websnarf]

Richard Heathfield wrote:

(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])

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

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Richard Heathfield]

we******@gmail. com said:

Richard Heathfield wrote:

>(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])

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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Al Balmer]

On Sun, 09 Jul 2006 21:13:47 GMT, Keith Thompson <ks***@mib.or g>
wrote:

>Al Balmer <al******@att.n etwrites:
[...]

>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[i]) {
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.

(The
check was necessary in the original version, I think -- which is one
reason why yours is an improvement.)

--
Al Balmer
Sun City, AZ

[Al Balmer]

On Mon, 10 Jul 2006 11:08:40 GMT, August Karlstrom
<fu********@com hem.sewrote:

>Keith Thompson wrote:

>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[i]){
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.

<GI don't write code based on rumors about hardship for compilers.

--
Al Balmer
Sun City, AZ

[Ben Bacarisse]

Richard Heathfield <in*****@invali d.invalidwrote:

lovecreatesbeau ty said:

>Any comments are welcome for following the two sequential search C

<snip>

>#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[i]){
break;
}
}
}
return i;
}

<snip>

(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])
{
++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[i] for
the first time (and to give a type for "val").

--
Ben.

[Richard Heathfield]

Ben Bacarisse said:

Richard Heathfield <in*****@invali d.invalidwrote:

<a very silly bug>

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? :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)