Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #147244

Re: How to use a struct with qsort()?

Show all headers | View raw

On 10/26/19 12:06 PM, Bart wrote:
> On 25/10/2019 19:30, Manfred wrote:
>> On 10/19/2019 10:26 PM, DFS wrote:
>>> int primes[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
>>>           43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}; char 
>>> *charset = "abcdefghijklmnopqrstuvwxyz";
>> Since primes and charset are strictly coupled, it is a good idea to 
>> enforce consistency of their sizes as in:
>> #include <assert.h>
>> static const unsigned int primes[] =
>> {
>>    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
>>    43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101
>> };
>> static const char charset[] = "abcdefghijklmnopqrstuvwxyz";
>> static_assert(sizeof(primes)/sizeof(primes[0]) == 
> 
>> (sizeof(charset)/sizeof(charset[0])-1),
>>      "charset and primes mismatch");
> 
> 
> Looks like overkill. Since charset is defined as a 'char' array in the 
> preceding line, you can assume that sizeof(charset[0]) is 1.

In this particular case it is more verbose than needed, but:
1) The constraint to be enforced is about number of /elements/ of the 
two arrays (modulo '\0' in the string), not /bytes/, so in this way I 
think it is more clear what it is about, even if it happens that element 
size of the second array is 1 - I see this as a coincidence that is 
orthogonal to the algorithm logic.
2) In this way the code will continue to work with /no change/ if at 
some point the character type be changed into something else, typically 
wchar_t (I know that wchar_t is not popular in *nix programming, but it 
is almost a must in any real world Windows programming)
3) You know that this is all compile-time processing, so even if it is 
more verbose it has zero impact on the compiled code.

> 
> After all, it does assume that charset[] is initialised from a string, 
> so has a "-1" (as pointed out by someone), but it will go wrong if 
> initialised from {'a',...'z'};
In the expression as written the -1 will continue to work with wchar_t, 
and yes it will not work if the array is brace initialized, but I think 
that changing a string into a brace list is not something that is easily 
overlooked by any C programmer.

> 
> It also does not report an error if the letters are not in order 
> (although for this program it doesn't matter, very often it will do).
> 
> Neither will it do so if both primes and charset both have too many 
> elements, so long as they both have the same number. Nor when they both 
> have too few (you additionally need an assert that prime has 26 elements).
> 
> Nor when some elements of prime[] are not prime numbers. Or it has 
> duplicates. Or characters inside charset are not a-z or are duplicates.
> 
> In short, so many assumptions are being made anyway...

The main purpose of this static_assert it to guarantee consistency with 
usage of the arrays, i.e. the following calcpf():
> //compute product of primes corresponding to the letters of the input word
> double calcpf(char *str, int len) {
>     double pf = 1;
>     for(i=0;i<len;i++) {
>         pf *= primes[(int)(strchr(charset, str[i]) - charset)];
>     }
>     return pf;
> } 

It is this function that is strictly coupled with the two arrays above, 
and, apart of possible overflow of the multiplication, what is required 
for this function to avoid UB is to guard the expression
> primes[(int)(strchr(charset, str[i]) - charset)];

This expression has defined behavior if and only if:
1) strchr returns a pointer into charset (hence my remark about the need 
for handling this at runtime)
2) charset and primes have the same number of elements[*] (hence the 
static_assert)

Yes, there may be many other mistakes that can be made, but at least the 
examples you mentioned would cause incorrect results rather than 
undefined behavior (and incorrect results are more likely to be caught 
during testing than UB, which is the nastiest of beasts). On the other 
hand, filling the code with static_asserts would really be overkill, and 
not what the expression is meant for.

> 
> (TBF, use of charset[] is already overkill, since its entire purpose 
> seems to be to convert 'a' to 'z' into 0 to 25, which is trivially done 
> by subtracting 'a'.
> 
> Since the program seems to rely on a word list downloaded from the 
> internet, the chances of that file being 8-bit EBCDIC are infinitesimal.)
> 

There can be much more to be said about the complete program (the OP's 
memory management mistakes and his/her remark about books being 
unhelpful suggest limited knowledge of C) - my 2c were on this piece of 
functionality that I thought was worth a comment.

[*] (strictly speaking, even if primes has more elements that charset 
there still is defined behavior.)

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 13:35 -0400
  Re: How to use a struct with qsort()? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-19 10:22 -0700
    Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 14:19 -0400
      Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-19 19:36 +0100
      Re: How to use a struct with qsort()? Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-19 18:44 +0000
  Re: How to use a struct with qsort()? Barry Schwarz <schwarzb@delq.com> - 2019-10-19 10:23 -0700
  Re: How to use a struct with qsort()? Ike Naar <ike@sdf.lonestar.org> - 2019-10-19 19:09 +0000
    Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 15:51 -0400
      Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 13:09 -0700
        Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 16:26 -0400
          Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 13:51 -0700
            Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 17:24 -0400
              Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 14:49 -0700
                Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 18:26 -0400
                Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 16:32 -0700
                Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-20 09:22 -0400
                Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-26 04:15 -0400
                Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-26 09:37 -0400
                Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-26 15:40 +0100
                Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-28 19:49 -0400
                Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-29 01:59 -0400
                Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-30 04:54 -0400
                Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-30 11:54 +0000
                Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-30 08:58 -0700
                Re: How to use a struct with qsort()? Öö Tiib <ootiib@hot.ee> - 2019-11-07 01:10 -0800
                Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-11-07 10:51 +0000
                Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-26 15:03 -0400
                Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 21:50 +0100
                Re: How to use a struct with qsort()? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-04 16:02 -0800
            Re: How to use a struct with qsort()? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-10-21 11:58 +0000
            Re: How to use a struct with qsort()? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-23 04:51 -0700
          Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-19 23:25 +0100
            Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-19 15:38 -0700
              Re: How to use a struct with qsort()? David Brown <david.brown@hesbynett.no> - 2019-10-20 14:44 +0200
              Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-22 15:42 -0400
              Re: How to use a struct with qsort()? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-23 05:47 -0700
                Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-23 16:40 +0100
                Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-23 13:51 -0700
                Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-23 23:07 +0100
                Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-23 15:50 -0700
                Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-24 01:20 +0100
                Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-23 18:20 -0700
                Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-24 10:40 +0100
                Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-24 11:00 -0700
          Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-20 00:30 +0100
            Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-20 00:44 +0100
          Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-20 01:27 +0100
          Re: How to use a struct with qsort()? Manfred <noname@add.invalid> - 2019-10-25 20:30 +0200
            Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-25 16:07 -0400
            Re: How to use a struct with qsort()? Ike Naar <ike@sdf.lonestar.org> - 2019-10-26 07:27 +0000
              Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-26 02:11 -0700
            Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-26 11:06 +0100
              Re: How to use a struct with qsort()? Manfred <noname@invalid.add> - 2019-10-26 16:58 +0200
                Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-26 18:17 -0400
                Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-26 16:08 -0700
                Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-26 21:33 -0400
                Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-26 22:10 -0700
                Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 01:48 +0100
                Re: How to use a struct with qsort()? Manfred <noname@invalid.add> - 2019-10-27 19:29 +0100
                Re: How to use a struct with qsort()? Barry Schwarz <schwarzb4aarp@gmail.com> - 2019-10-27 13:09 -0700

csiph-web