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

Groups > comp.lang.c > #147078 > unrolled thread

How to use a struct with qsort()?

Back to article view | Back to comp.lang.c

Contents

  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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#147322

DFS wrote:
> On 10/26/2019 10:40 AM, Bart wrote:
>> On 26/10/2019 14:37, DFS wrote:
>>> On 10/26/2019 4:15 AM, Paul wrote:
>>
>>>> What was your original bar bet anyway ?
>>>
>>> Well, I was finishing a bottle of Bacardi 151 and web browsing and 
>>> came across https://wordsmith.org/anagram/
>>>
>>> It generated so many anagrams so fast I was blown away.  So I went 
>>> looking for algorithms.  The first one I came across was the 
>>> prime-products, which looked easy to implement.  Once I got the code 
>>> written, I saw how fast it was in C.  Sorting the data made it much 
>>> faster.
>>
>> Preprocessing the data is the key.
>>
>> Your simple tests combine the processing of all the data (like, 
>> reading in the whole file), with finding anagrams of just one word.
>>> One kind of preprocessing can just chain together all anagrams anyway,
>> then it comes down to looking up one word in a dictionary, which can 
>> be under a millionth of a second. The anagram part should then take 
>> zero time, following a handful of links.
>>
>> (This preprocessing need not be done in the program each time it 
>> starts; it can be a separate program that generates a special, linked 
>> version of words_alpha.txt for example.)
> 
> 
> Yeah, I wondered how you might do that in C.
> 
> I've of course written various programs that load data, then wait for 
> keyboard input, and wait for Ctrl+Z to quit, etc.
> 
> 
> 
>>>> You could, of course,
>>>> store the entire word file inside the program, and
>>>> eliminate the preprocessing time :-)
>>>
>>> heh!
>>
>> (You can do that easily with the right language; one of mine can do this:
>>
>>      var []ichar words = textinclude "/texts/words_alpha.txt"
>>
>>      proc start=
>>          println words.len
>>          println words[1]
>>          println words[$]
>>      end
>>
>> output is:
>>
>>      370099
>>      a
>>      zwitterionic
>>
>> However, it slows down compilation (as it deals with 370,000 string 
>> expressions). Much faster is to deal with the file as one string and 
>> then separate into words at runtime.
> 
> Splitting a big string is faster than fgets() for each line (which 
> requires ~1 second to read 370K lines, calculate the prime product, and 
> store it in a struct)?

I tested the fgets on mine, and it was about 20% of the processing
time for the input file. So 80% must be my "lousy multiply method"
for pf.

    0.047725s to fgets the file       <=== measure(read file), then rewind()

    0.273223s to load 370103 words    <=== measure(read file and multiply primes)

I assume, with some work, we could get the time down to zero,
by placing the entire array and pre-computed prime values
in the source. But that's cheating, and it'll still take time
for the loader to load the bloated executable.

And now that I've fixed my time stamper, the time to do the
binary search and find the index of the consecutive anagrams,
is getting damn close to zero. It's likely the printf
time would be dominant if I included it.

    Searching for anagrams of 'players'...
    asperly parleys parsley pyrales replays sparely splayer
    7 anagram(s) found in 0.000003s <=== binary search time, no printf
    Done

   Paul

[toc] | [prev] | [next] | [standalone]

#147355

Paul wrote:
> DFS wrote:
>> On 10/26/2019 10:40 AM, Bart wrote:
>>> On 26/10/2019 14:37, DFS wrote:
>>>> On 10/26/2019 4:15 AM, Paul wrote:
>>>
>>>>> What was your original bar bet anyway ?
>>>>
>>>> Well, I was finishing a bottle of Bacardi 151 and web browsing and 
>>>> came across https://wordsmith.org/anagram/
>>>>
>>>> It generated so many anagrams so fast I was blown away.  So I went 
>>>> looking for algorithms.  The first one I came across was the 
>>>> prime-products, which looked easy to implement.  Once I got the code 
>>>> written, I saw how fast it was in C.  Sorting the data made it much 
>>>> faster.
>>>
>>> Preprocessing the data is the key.
>>>
>>> Your simple tests combine the processing of all the data (like, 
>>> reading in the whole file), with finding anagrams of just one word.
>>>> One kind of preprocessing can just chain together all anagrams anyway,
>>> then it comes down to looking up one word in a dictionary, which can 
>>> be under a millionth of a second. The anagram part should then take 
>>> zero time, following a handful of links.
>>>
>>> (This preprocessing need not be done in the program each time it 
>>> starts; it can be a separate program that generates a special, linked 
>>> version of words_alpha.txt for example.)
>>
>>
>> Yeah, I wondered how you might do that in C.
>>
>> I've of course written various programs that load data, then wait for 
>> keyboard input, and wait for Ctrl+Z to quit, etc.
>>
>>
>>
>>>>> You could, of course,
>>>>> store the entire word file inside the program, and
>>>>> eliminate the preprocessing time :-)
>>>>
>>>> heh!
>>>
>>> (You can do that easily with the right language; one of mine can do 
>>> this:
>>>
>>>      var []ichar words = textinclude "/texts/words_alpha.txt"
>>>
>>>      proc start=
>>>          println words.len
>>>          println words[1]
>>>          println words[$]
>>>      end
>>>
>>> output is:
>>>
>>>      370099
>>>      a
>>>      zwitterionic
>>>
>>> However, it slows down compilation (as it deals with 370,000 string 
>>> expressions). Much faster is to deal with the file as one string and 
>>> then separate into words at runtime.
>>
>> Splitting a big string is faster than fgets() for each line (which 
>> requires ~1 second to read 370K lines, calculate the prime product, 
>> and store it in a struct)?
> 
> I tested the fgets on mine, and it was about 20% of the processing
> time for the input file. So 80% must be my "lousy multiply method"
> for pf.
> 
>    0.047725s to fgets the file       <=== measure(read file), then rewind()
> 
>    0.273223s to load 370103 words    <=== measure(read file and multiply 
> primes)
> 
> I assume, with some work, we could get the time down to zero,
> by placing the entire array and pre-computed prime values
> in the source. But that's cheating, and it'll still take time
> for the loader to load the bloated executable.
> 
> And now that I've fixed my time stamper, the time to do the
> binary search and find the index of the consecutive anagrams,
> is getting damn close to zero. It's likely the printf
> time would be dominant if I included it.
> 
>    Searching for anagrams of 'players'...
>    asperly parleys parsley pyrales replays sparely splayer
>    7 anagram(s) found in 0.000003s <=== binary search time, no printf
>    Done
> 
>   Paul

I switched from GMP to "ttmath", and got a modest improvement
in compute time for the primes. This is probably due to more
details being exposed during compile, and more opportunities to
optimize away stuff.

"ttmath" is just a bunch of header files, and runs under C++.
I didn't use the ASM option, which is for Intel x64 opportunities.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <inttypes.h>
#include <stdint.h>
#include <windows.h>
#include "ttmath/ttmath.h"

/* also requires a DLL for C++ ... */
/* g++ -O2 -c anagrams3.c */
/* g++ -O2 -o anagrams3.exe anagrams3.o -L. */

/* declarations are pretty simple */

ttmath::Int<4> tttemp;  /* four limbs for my 128 bit storage */

//build struct
#define maxletter 32     /* 31 char plus terminator */
#define linecount 370103 /* use test file for benchmarks */
struct words {char word[maxletter]; ttmath::Int<4> wordpf;};
struct words wordrec[linecount];

/* Thanks to operator overloading, tttemp is easier to load up */

     int i;
     int arrindex;
     uint64_t pflow = 1;
     uint64_t pfhigh = 1;
     uint64_t pftemp = 0;

     /* do most math without ttmath */
     for(i=0;i<len;i++) {
         arrindex = (int)(strchr(charset, str[i]) - charset);

         if (pflow > 182641030432767836) {
            pfhigh *= primes[arrindex];
         } else {
            pflow *= primes[arrindex];
         }
     }

     /* save the potential 64 bit x 64 bit = 128 bit multiply for last */
     /* needed a cast to get the math values right */

     if (pfhigh == 1) {
        tttemp = (ttmath::Int<4>) pflow; /* a global passed back to main */
     } else {
        tttemp = (ttmath::Int<4>) pfhigh * (ttmath::Int<4>) pflow;
     }

/* Printing the struct is pretty easy too, base 10 only */

     for(i=0;i<wordcnt;i++) {
         if(i<10 || i>(wordcnt-11)) {
             printf("%d.      %-18s ",i, wordrec[i].word);
             std::cout << wordrec[i].wordpf << std::endl;
         }
     }

/* In the QSort, writing an equivalent to mpz_cmp is easy. */
/* And because all the math is out in the open, the compiler
    can optimize some of it. */

    int compar; /* compare two ttmath 4 limb variables */

    compar = (a->wordpf > b->wordpf) - (a->wordpf < b->wordpf); /* -1,0,+1 */

/* And I don't need the clumsy mpz_cmp for comparisons in binary search */
/* I can use > and == and the 128 bit math is all taken care of for me */

     ttmath::Int<4> searchpf;
     ...
     while (lowindex <= highindex) {
         mid = (highindex - lowindex) / 2 + lowindex;
         if ( wordrec[mid].wordpf > searchpf ) {
             highindex = mid - 1;
         } else if ( wordrec[mid].wordpf == searchpf ) {
             startindex = mid;
             highindex = mid - 1;
         } else {
             lowindex = mid + 1;
         }
     }

And I get a modest improvement in program speed (prime calc part).

The GMP package is OK, with the exception of moving data
into MPZ_t is harder than it needs to be. They could use
some bitshift operations (which perhaps I missed in my
rush to get done).

The disadvantage of the ttmath, is it doesn't automatically
add limbs like GMP does. But if you insist on bounding
your problem (only using a single test file as the only input),
it seems to be a good option.

    Paul

[toc] | [prev] | [next] | [standalone]

#147357

On 30/10/2019 08:54, Paul wrote:

> I switched from GMP to "ttmath", and got a modest improvement
> in compute time for the primes. This is probably due to more
> details being exposed during compile, and more opportunities to
> optimize away stuff.
> 
> "ttmath" is just a bunch of header files, and runs under C++.
> I didn't use the ASM option, which is for Intel x64 opportunities.
> 
> #include <stdlib.h>
> #include <stdio.h>
> #include <string.h>
> #include <inttypes.h>
> #include <stdint.h>
> #include <windows.h>
> #include "ttmath/ttmath.h"
> 
> /* also requires a DLL for C++ ... */
> /* g++ -O2 -c anagrams3.c */
> /* g++ -O2 -o anagrams3.exe anagrams3.o -L. */
> 
> /* declarations are pretty simple */
> 
> ttmath::Int<4> tttemp;  /* four limbs for my 128 bit storage */

If limiting to only 128 bits, then why not just use gcc's 128-bit type? 
It will be gcc-C, but it will be C and not C++.

128 bit unsigned (or even signed) should be enough to calculate unique 
prime products of all the words in DFS's words_alpha.txt file, provided 
the lowest primes are assigned to the most frequently occurring letters. 
I used this distribution:

  etaoinsrhdlucmfywgpbvkxqjz

Results for this selection of long words were:

                        u128max : 340282366920938463463374607431768211455
          superincomprehensibleness : 26614471915993452185017619296
       antidisestablishmentarianism : 102879614831278334667979432500
        microspectrophotometrically : 12258750173089048569082178231580
    dichlorodiphenyltrichloroethane : 55812442766843314104001446573936360
        hydroxydesoxycorticosterone : 11439122699486099825961557331528
       hydroxydehydrocorticosterone : 102741319610621788160461244551704
      cyclotrimethylenetrinitramine : 1931266618078335397504853448240
      trinitrophenylmethylnitramine : 11507752575836791498576659467160


(Not calculated with gcc-C's 128-bit types but with my script language. 
I thought I might as well try it in gcc-C, then I found there was no 
ready-made way to print a 128-bit result!

(However for the OP's purpose, printing of 128 bits is not necessary, 
but if needed, could be done in two halves.)

I then took the C I had written, up to the printf statement, and 
converted it to my own static language with fledgling 128-bit support, 
but it does have print! (But the primes[] array had to be 64-bit rather 
than 128, and it's missing *:= (ie. *=) support). It gave the same 
results as above.

See https://github.com/sal55/qx/blob/master/u128demo.m)

[toc] | [prev] | [next] | [standalone]

#147364

Bart <bc@freeuk.com> writes:
[...]
> If limiting to only 128 bits, then why not just use gcc's 128-bit type? 
> It will be gcc-C, but it will be C and not C++.

gcc only supports __int128 on 64-bit targets.  (Of course you can
accept that limitation if you want to.)

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#147700

On Wednesday, 30 October 2019 13:55:04 UTC+2, Bart  wrote:
> 
> If limiting to only 128 bits, then why not just use gcc's 128-bit type? 
> It will be gcc-C, but it will be C and not C++.

Because it is not guaranteed that maintenance does not add
pneumonoultramicroscopicsilicovolcanoconiosis to the dictionary.

[toc] | [prev] | [next] | [standalone]

#147704

On 07/11/2019 09:10, Öö Tiib wrote:
> On Wednesday, 30 October 2019 13:55:04 UTC+2, Bart  wrote:
>>
>> If limiting to only 128 bits, then why not just use gcc's 128-bit type?
>> It will be gcc-C, but it will be C and not C++.
> 
> Because it is not guaranteed that maintenance does not add
> pneumonoultramicroscopicsilicovolcanoconiosis to the dictionary.
> 

I said "if limited to 128 bits" anyway. Although as it happens, that 
word still fits, within both i128 and u128:

u128max:
      340282366920938463463374607431768211455
pneumonoultramicroscopicsilicovolcanoconiosis:
      145012305810655771806048449844001537350

[toc] | [prev] | [next] | [standalone]

#147257

DFS wrote:
> On 10/26/2019 4:15 AM, Paul wrote:
> 
> 
>> I took your code and messed around a bit with it.
> 
> <snip>
> 
> 
>> 370096.      electroencephalographically 5d9c0dac6de2d4b7af0469d810
>> 370097.      hydroxydesoxycorticosterone 9061cc85898dcac646dab48e48
>> 370098.      trinitrophenylmethylnitramine 913f8dd325653c1599e1f3cb98
>> 370099.      microspectrophotometrically 9aba287a31028f4509cc30dd1c
>> 370100.      hydroxydehydrocorticosterone 510c71bb0a52f66b6c9ac515218
>> 370101.      philosophicopsychological 26b6c1941415142b7b83d64fd613
>> 370102.      dichlorodiphenyltrichloroethane 
>> abfc410e3f54ff5649a0c76b28ee8
>>
>> Searching for anagrams of 'now'...
>> freq 3005590000
>> now  1053825389785134  now/freq  350621.804632
>> own won
>> freq 3005590000
>> now  1053825389995158  now/freq  350621.804702
>> 2 anagram(s) found in 0.000070s
>> Done
>>
>> *******
> 
> 
> Interesting thoughts!
> 
> I've been trying to use gmp (here on Windows) but no luck so far.  I did 
> get it installed.
> 
> 
>> What was your original bar bet anyway ?
> 
> Well, I was finishing a bottle of Bacardi 151 and web browsing and came 
> across https://wordsmith.org/anagram/
> 
> It generated so many anagrams so fast I was blown away.  So I went 
> looking for algorithms.  The first one I came across was the 
> prime-products, which looked easy to implement.  Once I got the code 
> written, I saw how fast it was in C.  Sorting the data made it much faster.
> 
> 
> The hosts of wordsmith.org told me:
> "Lots of horsepower we put into our server!"
> 
> 
>> Time to search for a single item, or time for the whole process ?
> 
> Fastest I got on my old Win8.1 system (i5-750@2.67GHz) is 0.00012 
> searching for 'cat'
> 
> 
> Ran it in MSYS2 and it's even faster:
> 
> Searching for anagrams of 'cat'...
> act
> 1 anagram(s) found in 0.00001s
> 
> 
> Searching for anagrams of 'players'...
> asperly parleys parsley pyrales replays sparely splayer
> 7 anagram(s) found in 0.00212s

Searching for anagrams of 'players'...
asperly parleys parsley pyrales replays sparely splayer
7 anagram(s) found in 0.000149s
Done

Searching for anagrams of 'now'...
own won
2 anagram(s) found in 0.000059s
Done

Searching for anagrams of 'cat'...
act
1 anagram(s) found in 0.000051s
Done

I think I need to put my timestamper back the way
it was in one of my other programs. Apparently it's
based on RDTSC or something. To measure short time
periods, you have to be more careful than I've been
so far.

In MinGW32, I was using

    gcc -c anagrams2.c
    gcc -o anagrams2.exe anagrams2.o -L. -lgmp-10

I'm missing the bit that would statically link "libgcc_s_dw2-1.dll".
I need two DLLs next to anagrams2.exe program.

And a snippet of GMP stuff looks like.

     uint64_t pflow = 1;   /* multiply buckets */
     uint64_t pfhigh = 1;  /* do most multiply in INTs... */
     uint64_t pftemp = 0;  /* before using GMP for final 128 bit multiply output */

     mpz_t mpzshift;       /* transfer to GMP domain */
     mpz_t mpzaccum;
     mpz_t mpzoutput;

     mpz_init(mpzshift);
     mpz_set_str(mpzshift, "0x0000000100000000", 0); /* 32 bit shift of uint64_t */
     mpz_init(mpzaccum);
     mpz_init(mpzoutput);

     /* this part does the transfer of pflow and pfhigh to a single mpz_t mpzoutput */

     pftemp = pflow >>32;                                 /* MShalf  21B746  32FEAE4C*/
     mpz_set_ui(mpzoutput, pftemp);
     mpz_mul(mpzoutput, mpzshift, mpzoutput);              /*         21B74600000000 */
     mpz_add_ui(mpzoutput, mpzoutput, pflow & 0xFFFFFFFF); /*         21B74632FEAE4C */

     if (pfhigh != 1) { /* multiply to output */
        pftemp = pfhigh >>32;
        mpz_set_ui(mpzaccum, pftemp);
        mpz_mul(mpzaccum, mpzshift, mpzaccum);
        mpz_add_ui(mpzaccum, mpzaccum, pfhigh & 0xFFFFFFFF);

        mpz_mul(mpzoutput, mpzaccum, mpzoutput); /* output is 128bit number */
     }

Then the sorting can use the mpz comparison function,
as crafting my own version directly on pflow and pfhigh
buckets is outside my pay scale.

     int compar;
     compar = mpz_cmp(a->wordpf, b->wordpf);

I won't post the whole thing, for fear of offending the audience.

Oh, yeah, my primes look like this.

int primes[26] = {5,71,41,29,2,47,61,23,11,97,79,31,43,13,7,67,89,19,17,3,37,73,59,83,53,101};

using frequencies from here

http://pi.math.cornell.edu/~mec/2003-2004/cryptography/subs/frequencies.html

The binary search for the first output word looks like...

     int lowindex = 0;
     int highindex = wordcnt - 1;
     int startindex = -1;  /* if anagram present, 0..wordcnt-1 */
     int mid = 0;

     while (lowindex <= highindex) {
         /* printf("low = %6d high = %6d mid = %06d startindex = %06d\n", lowindex, highindex, mid, startindex); */

         mid = (highindex - lowindex) / 2 + lowindex;
         if ( mpz_cmp(wordrec[mid].wordpf, searchpf) > 0 ) {
             highindex = mid - 1;
         } else if ( mpz_cmp(wordrec[mid].wordpf, searchpf) == 0 ) {
             startindex = mid;
             highindex = mid - 1;
         } else {
             lowindex = mid + 1;
         }
     }

You can see I am a fan of the "printf" school of thought.
If at first you don't succeed, printf printf printf.

    Paul

[toc] | [prev] | [next] | [standalone]

#147265

Paul <nospam@needed.invalid> writes:
<cut>
> The binary search for the first output word looks like...
>
>     int lowindex = 0;
>     int highindex = wordcnt - 1;
>     int startindex = -1;  /* if anagram present, 0..wordcnt-1 */
>     int mid = 0;

C has a function for doing this: bsearch.  It's one of the most
overlooked functions in the standard library so this seems like a good
place to give it another shout-out.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#147589

Paul <nospam@needed.invalid> writes:

> DFS wrote:
>
>> On 10/19/2019 7:32 PM, already5chosen@yahoo.com wrote:
>>
>>> On Sunday, October 20, 2019 at 1:27:37 AM UTC+3, DFS wrote:
>>
>>
>>> o.k.  I don't know why, but I read your code.
>>> Turned out, you don't have an array of records.  For some reason,
>>> you decided to build an array of pointers to records.  That's quite
>>> different!
>>> Your comparison function should take that into account and to use
>>> double indirection, like that:
>>>
>>> int comparepf(const void *p1, const void *p2)
>>> {
>>>    const struct words *a = *(const struct words **)p1;
>>>    const struct words *b = *(const struct words **)p2;
>>>    if (a->wordpf == b->wordpf)
>>>      return strcmp(a->word, b->word);
>>>    return a->wordpf < b->wordpf ? -1 : 1;
>>> }
>>
>> The qsort now works.
>
> I took your code and messed around a bit with it.
>
> For the prime number idea, you can assign the primes
> according to letter frequency.  The intention being,
> to reduce the amount of storage to hold the prime products.
> The letter "e" is assigned "2", as it's the most frequent.
>
> dichlorodiphenyltrichloroethane   55812442766843314104001446573936360
>
> And since that "broke" my calculator, I used log2 of all
> the prime numbers and addition, to come up with estimates
> of the storage requirements for the "worst word", the one shown.
> I had to figure out the storage requirements, so I could
> figure out how to store the numbers (I wanted to use uint64_t
> initially, but they weren't big enough).
>
> regmax = 7564585 for string dichlorodiphenyltrichloroethane
>
> The number is fixed point, and needs to be shifted >>16 to get
> the size of register needed.  7564585/65536 = 115.4 or 116 bits,
> so two 64 bit uint64_t would do.  I multiply together the
> primes until one uint64_t is full, then multiply the rest
> into a second unit64_t.
>
> I used GMP, and only transferred my two 64 bit accumulators
> to GMP when "most" of the multiplies were finished.  [...]

With a bit more work you might find a fairly simple encoding that
fits in 64 bits and gives a unique value (or very nearly unique)
for every anagram.  Using the 64-bit encoding as a hash value,
put all the words in a big hash table using open addressing for
the codes, and a linked list for wordes with a given code, so
it's just a few compares on 64-bit values to get to the
appropriate anagram family.

Hint:  one such encoding uses a variation of Ben Bacarisse's idea
of using a "histogram" of the number of occurrences of each
letter in the alphabet.

[toc] | [prev] | [next] | [standalone]

#147148

On Sat, 2019-10-19, already5chosen@yahoo.com wrote:
> On Saturday, October 19, 2019 at 11:27:22 PM UTC+3, DFS wrote:
...
>> Books and tutorials won't help.
>
> How do you know if you never tried? 
> Learning thing on stack overflow only works when you have a basic knowledge.
> Robert Sheckley was absolutely spot on in his classic.
> http://www.gutenberg.org/files/33854/33854-h/33854-h.htm

I'm re-reading a collection of his stories (Shards of Space) right
now.  All of them are spot on!

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#147170

already5chosen@yahoo.com writes:

> [...] floating-point rarely produces an exact equality.

Floating-point often produces an exact equality.  The problem is
it often doesn't produce equality when that is expected, and
sometimes vice versa.

[toc] | [prev] | [next] | [standalone]

#147095

On 19/10/2019 21:26, DFS wrote:
> On 10/19/2019 4:09 PM, already5chosen@yahoo.com wrote:

> =============================================================

> struct words {char *word; double wordpf;};
> struct words **wordrec = NULL;

Some suggestions that may or may not help:

(1) Use a typedef to give the struct its own name, so that you don't 
have to write 'struct words' everywhere, eg:

   typedef struct {char *word; double wordpf;} Words;

Now you can write

   Words **wordrec = NULL;

or sizeof(Words) etc.

(2) Use capitalised names for your typedefs as above, then it might be 
easier to see what is a type, and what is a variable name, which can 
cause confusion.

It also highlights the fact that 'Words' is not a good name for such a 
struct, and 'wordrec' is not a good name for an array of those structs. 
Swapping them is better IMO:

   typedef struct {char *word; double wordpf;} Wordrec;
   Wordrec **words = NULL;

It might be clearer enough now, that you don't need to capitalise the type.

(I haven't looked at the rest of your code, but ** for 'words' doesn't 
look right, assuming this is a one-dimensional list. A pointer to such a 
list only requires '*word'.)

[toc] | [prev] | [next] | [standalone]

#147097

Bart <bc@freeuk.com> writes:
> On 19/10/2019 21:26, DFS wrote:
>> On 10/19/2019 4:09 PM, already5chosen@yahoo.com wrote:
>> =============================================================
>
>> struct words {char *word; double wordpf;};
>> struct words **wordrec = NULL;
>
> Some suggestions that may or may not help:
>
> (1) Use a typedef to give the struct its own name, so that you don't 
> have to write 'struct words' everywhere, eg:
>
>    typedef struct {char *word; double wordpf;} Words;
>
> Now you can write
>
>    Words **wordrec = NULL;
>
> or sizeof(Words) etc.

That's a perfectly valid choice.  It has the advantage that the name of
the type is a single identifier.

Personally, though, I prefer to refer to the type as "struct whatever"
rather than inventing a new name for it.  My point of view is that if
you define a struct with a tag, it already has a perfectly good name.
I don't see much advantage in inventing another name for it.

If you do choose to use a typedef in addition to the tag name, there's
no real reason not to use the same identifier for both.  (Or you can
omit the tag name, but only for structures that don't contain a pointer
to the same type).

And since the type represents a single word, the name "words" or "Words"
is confusing.

I might write:
    struct word {char *str; double wordpf;};
(I don't know what "wordpf" represents).  Note that I've used a
different identifier for the char* member.

Or you could write:
    typedef struct {char *str; double wordpf;} word;
if you prefer a name that's a single identifier.  (And if a word
contains a pointer to a word, you'll need "typedef struct word ...", and
you'll have to refer to it as "struct word" inside the definition.)

> (2) Use capitalised names for your typedefs as above, then it might be 
> easier to see what is a type, and what is a variable name, which can 
> cause confusion.

Not a bad convention, but I haven't seen it used widely.  It could cause
some confusion if you mix code that uses that convention with code that
doesn't.

Picking good and unambiguous names is hard, but it's worth the effort.

[...]

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#147108

On 20/10/2019 00:38, Keith Thompson wrote:
> Bart <bc@freeuk.com> writes:
>> On 19/10/2019 21:26, DFS wrote:
>>> On 10/19/2019 4:09 PM, already5chosen@yahoo.com wrote:
>>> =============================================================
>>
>>> struct words {char *word; double wordpf;};
>>> struct words **wordrec = NULL;
>>
>> Some suggestions that may or may not help:
>>
>> (1) Use a typedef to give the struct its own name, so that you don't
>> have to write 'struct words' everywhere, eg:
>>
>>     typedef struct {char *word; double wordpf;} Words;
>>
>> Now you can write
>>
>>     Words **wordrec = NULL;
>>
>> or sizeof(Words) etc.
> 
> That's a perfectly valid choice.  It has the advantage that the name of
> the type is a single identifier.
> 
> Personally, though, I prefer to refer to the type as "struct whatever"
> rather than inventing a new name for it.  My point of view is that if
> you define a struct with a tag, it already has a perfectly good name.
> I don't see much advantage in inventing another name for it.
> 
> If you do choose to use a typedef in addition to the tag name, there's
> no real reason not to use the same identifier for both.  (Or you can
> omit the tag name, but only for structures that don't contain a pointer
> to the same type).

Bart /did/ omit the struct tag, thus avoiding inventing a new name.

> 
> And since the type represents a single word, the name "words" or "Words"
> is confusing.
> 
> I might write:
>      struct word {char *str; double wordpf;};
> (I don't know what "wordpf" represents).  Note that I've used a
> different identifier for the char* member.
> 
> Or you could write:
>      typedef struct {char *str; double wordpf;} word;
> if you prefer a name that's a single identifier.  (And if a word
> contains a pointer to a word, you'll need "typedef struct word ...", and
> you'll have to refer to it as "struct word" inside the definition.)
> 
>> (2) Use capitalised names for your typedefs as above, then it might be
>> easier to see what is a type, and what is a variable name, which can
>> cause confusion.
> 
> Not a bad convention, but I haven't seen it used widely.  It could cause
> some confusion if you mix code that uses that convention with code that
> doesn't.
> 

That's the trouble with conventions - everyone has their own!

> Picking good and unambiguous names is hard, but it's worth the effort.
> 

It's at least half the battle in writing clear, readable, maintainable 
and correct code - so /definitely/ worth the effort.

[toc] | [prev] | [next] | [standalone]

#147167

On 10/19/2019 6:38 PM, Keith Thompson wrote:
> Bart <bc@freeuk.com> writes:
>> On 19/10/2019 21:26, DFS wrote:
>>> On 10/19/2019 4:09 PM, already5chosen@yahoo.com wrote:
>>> =============================================================
>>
>>> struct words {char *word; double wordpf;};
>>> struct words **wordrec = NULL;
>>
>> Some suggestions that may or may not help:
>>
>> (1) Use a typedef to give the struct its own name, so that you don't
>> have to write 'struct words' everywhere, eg:
>>
>>     typedef struct {char *word; double wordpf;} Words;
>>
>> Now you can write
>>
>>     Words **wordrec = NULL;
>>
>> or sizeof(Words) etc.
> 
> That's a perfectly valid choice.  It has the advantage that the name of
> the type is a single identifier.
> 
> Personally, though, I prefer to refer to the type as "struct whatever"
> rather than inventing a new name for it.  My point of view is that if
> you define a struct with a tag, it already has a perfectly good name.
> I don't see much advantage in inventing another name for it.

+1


> If you do choose to use a typedef in addition to the tag name, there's
> no real reason not to use the same identifier for both.  (Or you can
> omit the tag name, but only for structures that don't contain a pointer
> to the same type).
> 
> And since the type represents a single word, the name "words" or "Words"
> is confusing.
> 
> I might write:
>      struct word {char *str; double wordpf;};
> (I don't know what "wordpf" represents).  Note that I've used a
> different identifier for the char* member.

wordpf contains the product of the prime factors of the word, ie 322 
(which is 2*7*23)


> Or you could write:
>      typedef struct {char *str; double wordpf;} word;
> if you prefer a name that's a single identifier.  (And if a word
> contains a pointer to a word, you'll need "typedef struct word ...", and
> you'll have to refer to it as "struct word" inside the definition.)
> 
>> (2) Use capitalised names for your typedefs as above, then it might be
>> easier to see what is a type, and what is a variable name, which can
>> cause confusion.
> 
> Not a bad convention, but I haven't seen it used widely.  It could cause
> some confusion if you mix code that uses that convention with code that
> doesn't.
> 
> Picking good and unambiguous names is hard, but it's worth the effort.


Yes!  Thanks for the hints.  I didn't do it very well in this instance, 
but good naming makes life easier.

[toc] | [prev] | [next] | [standalone]

#147173

Keith Thompson <kst-u@mib.org> writes:

> Bart <bc@freeuk.com> writes:
>
>> [...] Use a typedef to give the struct its own name, so that you
>> don't have to write 'struct words' everywhere, eg:
>>
>>    typedef struct {char *word; double wordpf;} Words;
>>
>> Now you can write
>>
>>    Words **wordrec = NULL;
>>
>> or sizeof(Words) etc.
>
> That's a perfectly valid choice.  It has the advantage that the
> name of the type is a single identifier.
>
> Personally, though, I prefer to refer to the type as "struct
> whatever" rather than inventing a new name for it.  My point of
> view is that if you define a struct with a tag, it already has a
> perfectly good name.  [...]

If a struct is defined with a tag, there is no doubt that the
type already has a name.  Whether that name is a perfectly good
name is another question altogether.

[toc] | [prev] | [next] | [standalone]

#147175

On 23/10/2019 13:47, Tim Rentsch wrote:
> Keith Thompson <kst-u@mib.org> writes:
> 
>> Bart <bc@freeuk.com> writes:
>>
>>> [...] Use a typedef to give the struct its own name, so that you
>>> don't have to write 'struct words' everywhere, eg:
>>>
>>>     typedef struct {char *word; double wordpf;} Words;
>>>
>>> Now you can write
>>>
>>>     Words **wordrec = NULL;
>>>
>>> or sizeof(Words) etc.
>>
>> That's a perfectly valid choice.  It has the advantage that the
>> name of the type is a single identifier.
>>
>> Personally, though, I prefer to refer to the type as "struct
>> whatever" rather than inventing a new name for it.  My point of
>> view is that if you define a struct with a tag, it already has a
>> perfectly good name.  [...]
> 
> If a struct is defined with a tag, there is no doubt that the
> type already has a name.  Whether that name is a perfectly good
> name is another question altogether.
> 

It doesn't have a name that is a pure identifier, such as T. You have to 
refer to it by the composite 'struct T'.

And given 'struct T', that T could exist in the same scope as an 
unrelated type 'T'. Further, you can choose to do one of:

    struct T T;

or:

    typedef struct T T;

or both:

    struct T T;
    typedef struct U U;

So struct T and the variable T have the same name, sort of; and struct U 
and the type U have the same name, sort of, and here can be used 
interchangeably.

This is why it might be best to forget the possibility of struct tags 
altogether, and always define a typedef for a struct.

Then the name of the struct type will be a regular identifier like other 
user types and the tag cannot clash with either other user types or 
variables

It also helps to make the type more opaque, which in turn means you can 
change the underlying type without having to change 100s of 'struct T' 
to 'struct T*' or 'U'.

[toc] | [prev] | [next] | [standalone]

#147178

Bart <bc@freeuk.com> writes:
> On 23/10/2019 13:47, Tim Rentsch wrote:
>> Keith Thompson <kst-u@mib.org> writes:
>> 
>>> Bart <bc@freeuk.com> writes:
>>>
>>>> [...] Use a typedef to give the struct its own name, so that you
>>>> don't have to write 'struct words' everywhere, eg:
>>>>
>>>>     typedef struct {char *word; double wordpf;} Words;
>>>>
>>>> Now you can write
>>>>
>>>>     Words **wordrec = NULL;
>>>>
>>>> or sizeof(Words) etc.
>>>
>>> That's a perfectly valid choice.  It has the advantage that the
>>> name of the type is a single identifier.
>>>
>>> Personally, though, I prefer to refer to the type as "struct
>>> whatever" rather than inventing a new name for it.  My point of
>>> view is that if you define a struct with a tag, it already has a
>>> perfectly good name.  [...]
>> 
>> If a struct is defined with a tag, there is no doubt that the
>> type already has a name.  Whether that name is a perfectly good
>> name is another question altogether.
>
> It doesn't have a name that is a pure identifier, such as T. You have to 
> refer to it by the composite 'struct T'.

Correct.  And the types `int*` and `char[20]` also don't have names that
are pure identifiers.

Most C type names are not pure identifiers.  Most of them are
keywords (int), or sequences of keywords (unsigned long), or various
combinations of keywords, identifiers, and punctuation symbols
(char **).  In the absence of typedefs and macros, C type names
are *never* pure identifiers.

> And given 'struct T', that T could exist in the same scope as an 
> unrelated type 'T'. Further, you can choose to do one of:
>
>     struct T T;
>
> or:
>
>     typedef struct T T;
>
> or both:
>
>     struct T T;
>     typedef struct U U;
>
> So struct T and the variable T have the same name, sort of; and struct U 
> and the type U have the same name, sort of, and here can be used 
> interchangeably.

Yes, you can create a mess if you use the identifiers "T" and "U" for
everything.  That's why it's a good idea to use more descriptive names.
The problem in your examples isn't the "struct" keyword, it's the short
and non-descriptive names you chose.  (Names like "T" are fine for
non-specific examples, but are rarely a good idea in real life.)

> This is why it might be best to forget the possibility of struct tags 
> altogether, and always define a typedef for a struct.

That requires a little extra work if a struct contains a pointer to
itself.  For example, you can have the typedef *before* the full struct
definition:

typedef struct node node;
struct node {
    int data;
    node *next;
};

Or you can refer to the type as "struct node" inside its definition
and refer to the typedef elsewhere:

typedef struct node {
    int data;
    struct node *next;
} node;

> Then the name of the struct type will be a regular identifier like other 
> user types and the tag cannot clash with either other user types or 
> variables

Again, most other user types don't have names that are single
identifiers, unless you create such names explicitly.

You can use typedef to create such names if you like, and a lot of
programmers do so.  I'm not saying there's anything wrong with that.
If you think it's a great advantage for your types to have names
that are single identifiers, I'm not even saying you're wrong.
It's just not my preference.  And if you're going to be reading C
code written by others, you'll need to cope with both styles.

> It also helps to make the type more opaque, which in turn means you can 
> change the underlying type without having to change 100s of 'struct T' 
> to 'struct T*' or 'U'.

Typedefs are appropriate for types that actually need to be opaque
(see FILE, for example).  But if code that uses your type is going
to be referring to member names, there's no point in trying to hide
the fact that it's a structure.  (If you change it from a struct to
a struct pointer, you'll have to change "." to "->" in client code,
and likely make other changes.)

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#147179

On 23/10/2019 21:51, Keith Thompson wrote:
> Bart <bc@freeuk.com> writes:

>> It doesn't have a name that is a pure identifier, such as T. You have to
>> refer to it by the composite 'struct T'.
> 
> Correct.  And the types `int*` and `char[20]` also don't have names that
> are pure identifiers.

Sure, if you're happy using an actual type constructor, which can be 
used to describe any composite type, and are happy to have to repeat the 
exact same constructor in multiple locations.

My post is about named user-types, where the details of the underlying 
type are given in only one place.

> Most C type names are not pure identifiers.  Most of them are
> keywords (int), or sequences of keywords (unsigned long), or various
> combinations of keywords, identifiers, and punctuation symbols
> (char **).  In the absence of typedefs and macros, C type names
> are *never* pure identifiers.

My post is about naming types. In the case of a struct, C also allows 
the untidy practice of having anonymous structs like struct{int a,b;}, 
and the half-way house of assigning a struct tag like struct T{int a,b;}.

(And, since you appear to have trouble with this, T is not meant to 
represent a meaningful struct tag.)

In my opinion, struct tags are a useless appendage to C, and if they 
didn't exist, would be missed by nobody. They just generate the 
possibility of extra confusion and more errors.

If people actually wanted to write 'struct T', then they can simply call 
the type 'struct_T'.

(As you mention later, at present C may require struct tags in certain 
cases where you are constructing pointers to the struct. That is a 
language limitation (which would not exist if tags didn't exist), and in 
that case tags have to be used, preferably a tag name chosen to indicate 
it is just for that purpose.)

> Yes, you can create a mess if you use the identifiers "T" and "U" for
> everything.  That's why it's a good idea to use more descriptive names.

Um, yes. You do understand that T and U are place holders for actual 
type in a real program? T and U simply represent different identifiers.

> The problem in your examples isn't the "struct" keyword, it's the short
> and non-descriptive names you chose.

No, it isn't. In fact it's completely irrelevant. What talking about 
types in this group, we frequently use T to refer to ANY type (although 
being C, this is likely to be an unmodified type, that is a built-in 
type named or named user, with *, [] or () modifiers, and the syntax 
oddities means those might be placed elsewhere).

In my post, T represents any user-identifier, but used variously as 
struct tag, type tag, or variable in my examples, which is the problem 
as they can all be in the same scope.

   (Names like "T" are fine for
> non-specific examples, but are rarely a good idea in real life.)

Who said that my struct T T illustration should be used in real 
programs? Maybe I should written:

   struct COFF_Reloc_Rec COFF_Reloc_Rec;

Do you think that would have helped me put my point across, or hindered 
it? Are those two identifiers exactly the same (look carefully)? T and T 
are clearly the same.

>> Then the name of the struct type will be a regular identifier like other
>> user types and the tag cannot clash with either other user types or
>> variables
> 
> Again, most other user types don't have names that are single
> identifiers, unless you create such names explicitly.

And again, I'm talking about named types, not anonymous ones. And named 
types (ie. types with associated user-defined identifier) is the context 
I was replying to.

> You can use typedef to create such names if you like, and a lot of
> programmers do so.  I'm not saying there's anything wrong with that.
> If you think it's a great advantage for your types to have names
> that are single identifiers,

Again?

T represents any identifier, and since this is to do with Tags and 
Types, I've called it T rather than W or J.


  I'm not even saying you're wrong.
> It's just not my preference.  And if you're going to be reading C
> code written by others, you'll need to cope with both styles.

As it happens, I don't use single letter type names for real programs, 
ever. Only in posts here, or in test code, where extraneous matters need 
to be minimised.

>> It also helps to make the type more opaque, which in turn means you can
>> change the underlying type without having to change 100s of 'struct T'
>> to 'struct T*' or 'U'.
> 
> Typedefs are appropriate for types that actually need to be opaque
> (see FILE, for example).  But if code that uses your type is going
> to be referring to member names, there's no point in trying to hide
> the fact that it's a structure.  (If you change it from a struct to
> a struct pointer, you'll have to change "." to "->" in client code,
> and likely make other changes.)


Clearly, my example is for when you are not expected to access the 
struct members.

Notice how FILE is defined as FILE, and not 'struct FILE', or 'struct 
FILE*'.

[toc] | [prev] | [next] | [standalone]

#147180

Bart <bc@freeuk.com> writes:
> On 23/10/2019 21:51, Keith Thompson wrote:
>> Bart <bc@freeuk.com> writes:
>>> It doesn't have a name that is a pure identifier, such as T. You have to
>>> refer to it by the composite 'struct T'.
>> 
>> Correct.  And the types `int*` and `char[20]` also don't have names that
>> are pure identifiers.
>
> Sure, if you're happy using an actual type constructor, which can be 
> used to describe any composite type, and are happy to have to repeat the 
> exact same constructor in multiple locations.
>
> My post is about named user-types, where the details of the underlying 
> type are given in only one place.
>
>> Most C type names are not pure identifiers.  Most of them are
>> keywords (int), or sequences of keywords (unsigned long), or various
>> combinations of keywords, identifiers, and punctuation symbols
>> (char **).  In the absence of typedefs and macros, C type names
>> are *never* pure identifiers.
>
> My post is about naming types. In the case of a struct, C also allows 
> the untidy practice of having anonymous structs like struct{int a,b;}, 
> and the half-way house of assigning a struct tag like struct T{int a,b;}.
>
> (And, since you appear to have trouble with this, T is not meant to 
> represent a meaningful struct tag.)

I have no trouble with it.  Apparently you agree with me that T is not
generally a good name for a type or a tag.

One of your examples was
    struct T T;
It could have been
    struct COFF_Reloc_Rec COFF_Reloc_Rec;
Do we agree that using the same identifer for a struct tag and for an
object of the struct type is a bad idea?  Or for a typedef name and an
object of that type?  That's what you did in your example.  Perhaps a
longer name would have made that clearer.

I don't recall anyone suggesting using the same name for a type and
for an object of that type.  You did so in your example.  If that
wasn't your intent, I'll accept that -- but then I'm not sure what point
you were making.

> In my opinion, struct tags are a useless appendage to C, and if they 
> didn't exist, would be missed by nobody. They just generate the 
> possibility of extra confusion and more errors.
> 
> If people actually wanted to write 'struct T', then they can simply call 
> the type 'struct_T'.
> 
> (As you mention later, at present C may require struct tags in certain 
> cases where you are constructing pointers to the struct. That is a 
> language limitation (which would not exist if tags didn't exist), and in 
> that case tags have to be used, preferably a tag name chosen to indicate 
> it is just for that purpose.)

I understand that that's your preference.  I've already acknowledged
that it's a valid preference.  You refuse to do the same for my own
preference.

[...]

> Who said that my struct T T illustration should be used in real 
> programs? Maybe I should written:
>
>    struct COFF_Reloc_Rec COFF_Reloc_Rec;
>
> Do you think that would have helped me put my point across, or hindered 
> it? Are those two identifiers exactly the same (look carefully)? T and T 
> are clearly the same.

Yes, they're exactly the same.  Exactly what point are you making with
that declaration?

>>> Then the name of the struct type will be a regular identifier like other
>>> user types and the tag cannot clash with either other user types or
>>> variables
>> 
>> Again, most other user types don't have names that are single
>> identifiers, unless you create such names explicitly.
>
> And again, I'm talking about named types, not anonymous ones. And named 
> types (ie. types with associated user-defined identifier) is the context 
> I was replying to.

Yes, I understand that.  "int*" is not an anonymous type.  It has a
name, and that name is "int*".  (See the definition of "type-name" in
the C syntax.  It's not just an identifier.)

[...]

> As it happens, I don't use single letter type names for real programs, 
> ever. Only in posts here, or in test code, where extraneous matters need 
> to be minimised.

Great.  In this case, doing so may have unintentionally obscured your
point.

>>> It also helps to make the type more opaque, which in turn means you can
>>> change the underlying type without having to change 100s of 'struct T'
>>> to 'struct T*' or 'U'.
>> 
>> Typedefs are appropriate for types that actually need to be opaque
>> (see FILE, for example).  But if code that uses your type is going
>> to be referring to member names, there's no point in trying to hide
>> the fact that it's a structure.  (If you change it from a struct to
>> a struct pointer, you'll have to change "." to "->" in client code,
>> and likely make other changes.)
>
> Clearly, my example is for when you are not expected to access the 
> struct members.

That wasn't clear at all.  Now that you've stated that assumption, as I
already stated I agree that using a typedef to give a simple name to an
opaque type is a good idea.

> Notice how FILE is defined as FILE, and not 'struct FILE', or 'struct 
> FILE*'.

Yes.  Are you under the impression that that contradicts anything I've
said?  I explicitly stated that FILE is a good example of using a
typedef for an opaque type.

Now let's say we want to define a non-opaque type, for example the type
of a node in a linked list:

    struct node {
        int data;
        struct node *next;
    };

That's how I'd define it.  Client code needs to refer to the "data" and
"next" members, and thus depends on it being a structure.

You'd probably define it something like this:

    typedef struct node_ {
        int data;
        struct node_ *next;
    } node;

with the tag "node_" used to discourage using it outside the struct
definition.  (An alternative is to use "node" both as the typedef name
and the tag name.)

That's fine with me.  It's not my preference, but it's a perfectly valid
style that a lot of programmers use.

Do you, or do you not, acknowledge that the way I do it (no typedef,
referring to the type as "struct node") is also valid?  I'm not asking
whether you like it (I already know you don't).  I'm asking whether you
acknowledge that it's valid.

Note that there are several struct types defined in the C standard
library that have no associated typedefs (struct tm is one example).
In fact, I don't think there's *any* structure type in the standard
library for which the standard specifies both the names of its
members and a typedef for the type.  (No need to say that you dislike
the style used by the standard; I think we're all aware of that.)

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web