Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147558 > unrolled thread
| Started by | DFS <nospam@dfs.com> |
|---|---|
| First post | 2019-11-03 17:39 -0500 |
| Last post | 2019-11-09 02:09 -0500 |
| Articles | 20 on this page of 112 — 21 participants |
Back to article view | Back to comp.lang.c
One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-03 17:39 -0500
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-04 00:20 +0000
Re: One works, the other doesn't? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-04 06:53 +0000
Re: One works, the other doesn't? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-04 09:45 -0500
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 10:34 -0500
Re: One works, the other doesn't? mark.bluemel@gmail.com - 2019-11-05 07:45 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 10:53 -0500
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-05 08:04 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 11:29 -0500
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-05 23:24 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-05 23:06 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-06 12:31 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-05 23:43 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-06 12:54 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 01:35 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-06 15:16 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 11:11 +0000
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 01:59 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 11:35 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 08:57 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 07:24 +1300
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 22:59 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 14:37 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 00:58 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-07 02:08 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 15:43 +0100
Re: One works, the other doesn't? Robert Wessel <robertwessel2@yahoo.com> - 2019-11-07 16:15 -0600
Re: One works, the other doesn't? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-10 20:01 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-11 15:26 +1300
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-11 12:37 +0100
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 07:21 +1300
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 10:39 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 07:47 +1300
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 08:14 +1300
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 12:30 -0800
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 21:04 -0800
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-09 01:37 -0800
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-09 01:38 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-10 08:32 +1300
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 16:09 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-29 11:33 +0100
Re: One works, the other doesn't? Öö Tiib <ootiib@hot.ee> - 2019-11-30 14:20 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-12-01 12:15 +1300
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 10:07 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 10:58 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 10:05 +0100
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 09:52 +0100
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-06 00:56 -0800
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-06 01:00 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 11:32 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 23:11 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 23:22 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 01:04 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 01:13 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 10:22 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 11:51 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 15:58 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 16:34 +0000
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-07 12:40 -0500
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 17:57 +0000
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-07 21:14 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-08 09:45 +0000
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-08 09:56 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-08 19:47 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-09 09:14 +1300
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-08 19:10 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-09 12:24 +0000
Like an old married couple... (Was: One works, the other doesn't?) gazelle@shell.xmission.com (Kenny McCormack) - 2019-11-08 20:25 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 19:58 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 19:31 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-08 08:56 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 20:06 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-08 09:21 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 21:20 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-08 10:28 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 22:35 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-09 09:22 +1300
Re: One works, the other doesn't? jadill33@gmail.com - 2019-11-07 08:37 -0800
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-07 08:52 -0800
Re: One works, the other doesn't? jadill33@gmail.com - 2019-11-07 09:52 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 20:04 +0100
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 19:50 -0800
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 18:05 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-05 09:28 -0800
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 19:02 +0100
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-05 23:21 +0100
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-06 18:36 +0100
Re: One works, the other doesn't? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-05 12:51 -0500
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 18:35 -0500
Re: One works, the other doesn't? Barry Schwarz <schwarzb@delq.com> - 2019-11-05 17:53 -0800
Re: One works, the other doesn't? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-06 09:33 -0500
Re: One works, the other doesn't? Barry Schwarz <schwarzb@delq.com> - 2019-11-05 13:36 -0800
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-07 10:17 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-07 12:19 +0000
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-07 18:59 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-08 00:02 +0000
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-20 10:54 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-20 11:14 +0000
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-20 13:22 +0100
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 15:54 -0800
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-20 08:42 -0800
Re: One works, the other doesn't? Manfred <noname@add.invalid> - 2019-11-21 18:56 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-22 01:07 +0000
Re: One works, the other doesn't? Manfred <noname@add.invalid> - 2019-11-22 15:27 +0100
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 15:47 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-07 18:41 -0500
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 17:39 +0100
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 11:47 -0500
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 17:54 +0100
Re: One works, the other doesn't? luser droog <luser.droog@gmail.com> - 2019-11-05 09:00 -0800
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 21:02 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-09 02:09 -0500
Page 5 of 6 — ← Prev page 1 2 3 4 [5] 6 Next page →
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2019-11-07 20:04 +0100 |
| Message-ID | <qq1pr1$ukp$1@dont-email.me> |
| In reply to | #147721 |
On 07/11/2019 17:37, jadill33@gmail.com wrote: > On Thursday, November 7, 2019 at 9:58:31 AM UTC-5, David Brown wrote: >> On 07/11/2019 12:51, Bart wrote: >>> On 07/11/2019 09:22, David Brown wrote: >>>> On 07/11/2019 02:13, Bart wrote: >>> >>>>> So why was it made fast? >>>> >>>> It doesn't do much (in comparison to bigger compilers), so it can be >>>> small and fast. In particular, as far as I know it doesn't do any kind >>>> of inter-procedural analysis, which is something that takes a lot of >>>> time and resources in a compiler but is very important for both >>>> optimisation and static analysis. It does not handle multiple >>>> languages, multiple targets and multiple devices within a family - so it >>>> does not need the layers of abstraction in between stages. >>> >>> So if using TCC to develop C programs for x86, x64, ARM and ARM64, it's >>> no good because it doesn't support 996 other processors, and it isn't >>> part of a product chain that can also compile C++, Ada and Fortran? >> >> I said the limited features are one of the reasons tcc can be small and >> fast. >> >>> >>> It sounds to me like, if that is how you can streamline a compiler, then >>> what's the problem? >>> >>>> As I have said before, I think it is impressive how much TCC can do in >>>> such a small code space and run time. >>> >>> (For 'impressive', look at LuaJIT, which is a 225KB executable that >>> appears to be a complete Lua implementation with a tracing JIT compiler. >>> C source is a nightmare though...) >>> >>>> But it is not the tool to use for >>>> development. >>> >>> Yes you keep saying that. But not everyone is you with your very >>> exacting requirements. >>> >>>>> TCC compiles so fast that even for big projects Makefiles may not be >>>>> necessary. >>>> >>>> That only applies if you don't know what Makefiles are for, and how >>>> project management works. Or if you only write "hello, world" programs. >>> >>> My projects aren't that big, but they're a long way from being hello, >>> world programs. Yet they don't need makefiles. The biggest one is built >>> like this: >>> >>> C:\qcc>mm qq >>> Compiling qq.m to qq.exe >>> >>> Which processes 56 files totalling 56,000 lines. 'mm.exe' is a bare >>> compiler. While, getting back to C, I can build Seed7 like this: >>> >>> C:\seed79\src>bcc @s7 >>> .... >>> >>> where s7 is simply a list of the modules that are needed. This will also >>> work with gcc and lcc (depending on whether compiler-specific options >>> are inside that @ file). >>> >>> Makefiles are not the only fruit. >> >> We are talking about C, not your private language. Non-negligible >> projects need some kind of build process. Makefiles are one way to >> express these - there are other ways. The point is that "the compiler >> is so fast you don't need a Makefile" is a complete misunderstanding on >> the purpose of Makefiles - they are not just about the efficiency of >> incremental builds. > > You can go even further, non-negligible projects need some kind of > *repeatable* build process, independent of the whims of individual > developers. Bart's perspective appears to be one completely insulated > from the problems that come with multi-staff driven development. In > my work, developers are not the final builders of the end-product, > it's configuration management, and they know nothing of picking > compiler options or IDE configuration, nor do they want to know. We are a small company, so programs are usually written and build by the same person. But I fully agree with repeatable builds. I have programs that I wrote twenty years ago, and several computers and OS's ago, which I can still build on current machines with "make" and get bit-perfect identical binaries. For any major project I work on, when I put together the tools, compilers, libraries, etc., that I will need, I am not ready to start the main coding until I can check out the source and type "make" with identical results on my Windows system, my work Linux system, my home Linux system and my Linux laptop. > > When I came on, the old procedures were a badly formatted document > with a laundry list of manually written commands for source control > and building an application whose components were written in multiple > languages using multiple IDEs. Through a combination of Makefiles and > batch scripts, I was able to reduce the human error component of people > who are not developers to mis-specifying the version number and target > platform. The amount of baby-sitting I have to do now is practically > zero. It typically only breaks when a new version of a compiler or tool > is introduced. > I consider the compiler as part of the project archives. > It wasn't free though, the batch script is about 2000 lines and the > Makefile/Ant configs are couple 100 and it took me about 2-3 months > to create from scratch. Now you rotate in a new configuration > management person, and the time savings are much more real. > > [snip] > > Best regards, > John D. >
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2019-11-08 19:50 -0800 |
| Message-ID | <86sgmxemia.fsf@linuxsc.com> |
| In reply to | #147721 |
jadill33@gmail.com writes: > [N]on-negligible projects need some kind of *repeatable* build > process, independent of the whims of individual developers. > [...] In my work, developers are not the final builders of the > end-product, it's configuration management, [...]. > > When I came on, the old procedures were a badly formatted > document with a laundry list of manually written commands for > source control and building an application whose components > were written in multiple languages using multiple IDEs. [...] Clearly that situation is pretty awful, but a build environment that doesn't accommodate multiple development environments is a sorry excuse for a build environment.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-05 18:05 +0100 |
| Message-ID | <qpsa4t$gn4$1@news.albasani.net> |
| In reply to | #147618 |
>> This was causing my program to fail, and I didn't look closely enough at >> that line. Now I'm golden - I think. >> Thanks for spotting it! > If you use a good modern IDE, it will warn you when the format string > and the arguments don't match. That's rather a matter of the compiler and not of the IDE.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2019-11-05 09:28 -0800 |
| Message-ID | <e46f4981-412b-4ff4-954b-a1354f27110f@googlegroups.com> |
| In reply to | #147625 |
On Tuesday, 5 November 2019 17:05:43 UTC, Bonita Montero wrote: > >> This was causing my program to fail, and I didn't look closely enough at > >> that line. Now I'm golden - I think. > > >> Thanks for spotting it! > > > If you use a good modern IDE, it will warn you when the format string > > and the arguments don't match. > > That's rather a matter of the compiler and not of the IDE. > Modern IDEs parse input as they go, using the results for syntax colouring, and flagging errors or warnings. They also offer autocompletion. I haven't seen how they work under the hood, but I don't believe that they achieve this by invoking the compiler, instead I think it's a cut down independent parser. They also mark errors reported by the compiler, of course, when the user finally runs a build.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-05 19:02 +0100 |
| Message-ID | <qpsdfi$orr$1@news.albasani.net> |
| In reply to | #147627 |
>>>> This was causing my program to fail, and I didn't look closely enough at >>>> that line. Now I'm golden - I think. >>>> Thanks for spotting it! >>> If you use a good modern IDE, it will warn you when the format string >>> and the arguments don't match. >> That's rather a matter of the compiler and not of the IDE. > Modern IDEs parse input as they go, using the results for syntax colouring, > and flagging errors or warnings. They also offer autocompletion. I haven't > seen how they work under the hood, but I don't believe that they achieve > this by invoking the compiler, instead I think it's a cut down independent > parser. They also mark errors reported by the compiler, of course, > when the user finally runs a build. Wich part of the worth "rather" do you not understand?
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2019-11-05 23:21 +0100 |
| Message-ID | <qpsskq$3ee$3@dont-email.me> |
| In reply to | #147629 |
On 05/11/2019 19:02, Bonita Montero wrote: >>>>> This was causing my program to fail, and I didn't look closely >>>>> enough at >>>>> that line. Now I'm golden - I think. > >>>>> Thanks for spotting it! > >>>> If you use a good modern IDE, it will warn you when the format string >>>> and the arguments don't match. > >>> That's rather a matter of the compiler and not of the IDE. > >> Modern IDEs parse input as they go, using the results for syntax >> colouring, >> and flagging errors or warnings. They also offer autocompletion. I >> haven't >> seen how they work under the hood, but I don't believe that they achieve >> this by invoking the compiler, instead I think it's a cut down >> independent >> parser. They also mark errors reported by the compiler, of course, >> when the user finally runs a build. > > Wich part of the worth "rather" do you not understand? > I expect it your misuse of the word "compiler" that he disagreed with. A common tool for IDE's to run in the background as you type (or save) is cppcheck. It is not a compiler, but it will help spot many errors before you even need to compile the code.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2019-11-06 18:36 +0100 |
| Message-ID | <qpv0a2$o2p$1@news.albasani.net> |
| In reply to | #147634 |
>> Wich part of the worth "rather" do you not understand? > I expect it your misuse of the word "compiler" that he disagreed with. I didn't misuse the word "compiler". Most of the complexity recognizing format-string-errors lies in the compiler. Parsing the compiler-output in the IDE is rather simple.
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2019-11-05 12:51 -0500 |
| Message-ID | <qpscqt$g9n$1@dont-email.me> |
| In reply to | #147614 |
On 11/5/19 10:34 AM, DFS wrote:
> On 11/4/2019 9:45 AM, James Kuyper wrote:
>> On 11/3/19 5:39 PM, DFS wrote:
...
>>> Am I allocating memory incorrectly?
>>
>> Quite thoroughly. I'm not sure you did anything correct with regards to
>> your use of dynamically allocated memory.
>
>> Also, there's no need for you to use dynamically allocated memory for
>> this purpose:
>>
>> int cnt=0;
>> for(i=0;i<arrsize;i++) {
>> while (i<arrsize-1 && strcasecmp(randoms3[i],
>> randoms3[i+1])==0)
>> {i++}
>>
>> printf("%d %s ",cnt, randoms3[i]);
>> cnt++;
>> }
>
>
> ? I never wrote that. ...
I wrote nothing to suggest that you had written it.
> ... You concocted it somehow. If you're just
> showing it as an example, ...
I was.
> ... I agree there's no need for dyn alloc mem there.
Which is why I preceded the example with a statement that dynamic
allocation wasn't needed.
> What I wrote was:
>
> printf("%d %s ",cnt,finalarr[cnt]);
>
> so I could see what was copied to finalarr after each loop iteration.
But randoms3[i] IS what was copied to finalarr. The code you wrote
provided no reason for the existence of finalarr. What it did with
finalarr was completely incorrect, but in order to advise you on how it
should be corrected, we need to know how finalarr was intended to be
used. Your code below provides that context.
>> It's possible that the full original context of this code provides a
>> good reasons for dynamically allocating this memory. If so, let us know,
>> and we can give you advice on how to do it properly (which will probably
>> involve the use of realloc()).
>
> Thanks for your assessment James. Before you answered I tried realloc
> in the larger program and it appears to work, in that it copies the
> unique data to the finalarr (whether it's 10 elements or 1000000
> elements), but the program fails and quits after the next to last line.
>
>
> int cnt=0;
> char **finalarr = malloc(sizeof(char*));
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
> finalarr = realloc(finalarr, sizeof(char*) * (cnt+1));
realloc() attempts to allocate the specified amount of space. If that
attempt fails, it returns a null pointer. If that attempt succeeds, it
then copies from the old allocation to the new one, for a number of
bytes equal to the size of the smaller of the two allocations. As a
optimization, it usually tries to allocate the new memory at the same
starting location as the original allocation, if it can, which allows it
to skip the expensive copying step - but the standard says nothing about
this optimization.
This leads to a couple of important points you need to keep in mind when
using realloc().
Like malloc(), realloc() can fail, in which case it returns a null
pointer. If that happens, the previously allocated memory remains
allocated. If you store the result of calling realloc() in the same
place that you stored the only pointer you have to the original
allocation, then if realloc() fails, you will never again be able to
access the data you stored in that location, and you will never be able
to free() it, leading to a memory leak. The right way to use realloc() is:
void *tmp = realloc(finalarr, (cnt+1)*sizeof *finalarr);
if(!tmp)
{
// Error handling
} else {
finalarr = tmp;
}
The second point is that realloc() is a very expensive function to call.
It starts out doing the same thing that malloc() does, searching through
the heap for a block that is big enough (and preferably as small as
possible), which is expensive in itself. On top of that, it also copies
the data over from the previous allocation. Therefore, you should
generally avoid calling it more often than necessary. A common strategy
is to initially call malloc() to allocate significantly more than one
object, and to only call realloc() when you reach the end of the current
allocation and need to add more to it. When it is time to allocate more
memory, increase the total size allocated by a fixed factor (2 is a
popular value for that factor). As a result, the number of calls to
realloc() is proportional to log(N), where N is the final value for the
number of elements used. This will generally leave you with more memory
allocated than is actually needed, but if that's a problem, you can
realloc() back to that actual space needed at the end of the loop, which
might release some of the excess memory.
Refinement 1: on many systems, allocating memory in blocks whose size is
an integer multiple of some particular power of 2 is more efficient than
allocating slightly more or slightly less than that amount. Which power
of two is relevant varies from one system to another. On some systems,
there's multiple different powers of 2 which have corresponding
efficiency advantages. If your initial allocation is for a power of 2
elements, and your growth factor is 2, you're virtually guaranteed to
hit sizes that are particularly efficient.
Refinement 2:
I have vague memories of someone claiming to have seen a study
suggesting that, at least under some common circumstances, the optimal
growth factor is actually sqrt(2). I don't remember what those
circumstances are.
Using sqrt(2) directly would require floating point multiplications and
conversions back to an integer. A better approach is to use the
following: on even steps, set newsize = (oldsize*3)/2; on odd steps use
newsize = (oldsize*4)/3. The average growth factor is exactly sqrt(2),
but the individual expressions only use integer arithmetic.
Refinement 3: on many systems, the malloc() family takes the space you
requested, adds the size of a header, and then rounds up to the next
multiple of a fixed block size. It allocates that much memory, writes
the header at the beginning of the allocation, and returns a pointer
just past the end of the header. Net result: it's the total size,
including the header, that ideally should be an integer multiple of some
particular power of 2. If the requested size is an efficient size, then
the corresponding total size is virtually guaranteed to be a
significantly inefficient size.
Since the size of that header varies from one implementation to another,
portable code has no way of dealing with this complication. Non-portable
code can be designed to take into consideration the size of the header.
> finalarr[cnt] = randoms3[i];
> printf("%d %s \n",cnt,finalarr[cnt]);
> cnt++;
> }
> printf("%d here\n",cnt);
> printf("%.4s remove %d dupes\n",elapsedtime(start),arrsize-cnt);
You've already been informed about the problem with that format string.
[toc] | [prev] | [next] | [standalone]
| From | DFS <nospam@dfs.com> |
|---|---|
| Date | 2019-11-05 18:35 -0500 |
| Message-ID | <iKnwF.65564$P37.23863@fx33.iad> |
| In reply to | #147628 |
On 11/5/2019 12:51 PM, James Kuyper wrote:
> On 11/5/19 10:34 AM, DFS wrote:
>> On 11/4/2019 9:45 AM, James Kuyper wrote:
>>> On 11/3/19 5:39 PM, DFS wrote:
> ...
>>>> Am I allocating memory incorrectly?
>>>
>>> Quite thoroughly. I'm not sure you did anything correct with regards to
>>> your use of dynamically allocated memory.
>>
>>> Also, there's no need for you to use dynamically allocated memory for
>>> this purpose:
>>>
>>> int cnt=0;
>>> for(i=0;i<arrsize;i++) {
>>> while (i<arrsize-1 && strcasecmp(randoms3[i],
>>> randoms3[i+1])==0)
>>> {i++}
>>>
>>> printf("%d %s ",cnt, randoms3[i]);
>>> cnt++;
>>> }
>>
>>
>> ? I never wrote that. ...
>
> I wrote nothing to suggest that you had written it.
>
>> ... You concocted it somehow. If you're just
>> showing it as an example, ...
>
> I was.
>
>> ... I agree there's no need for dyn alloc mem there.
>
> Which is why I preceded the example with a statement that dynamic
> allocation wasn't needed.
>
>> What I wrote was:
>>
>> printf("%d %s ",cnt,finalarr[cnt]);
>>
>> so I could see what was copied to finalarr after each loop iteration.
>
> But randoms3[i] IS what was copied to finalarr. The code you wrote
> provided no reason for the existence of finalarr.
Now I see where you were going. Since all I ever did was copy the
unique elements to finalarr then print them from finalarr, there was no
need for it to even exist. You're right.
My thinking was this:
- two initial arrays of the same size N/2
- combine them into a new array size N
- sort and dedupe and copy the unique elements into a final array of the
exact size N-dupes.
But rather than grow that last array as each element is added, you
pointed out it's better to allocate bigger chunks. Then realloc(arr,0)
will free extra-allocated memory.
> What it did with
> finalarr was completely incorrect, but in order to advise you on how it
> should be corrected, we need to know how finalarr was intended to be
> used. Your code below provides that context.
>
>>> It's possible that the full original context of this code provides a
>>> good reasons for dynamically allocating this memory. If so, let us know,
>>> and we can give you advice on how to do it properly (which will probably
>>> involve the use of realloc()).
>>
>> Thanks for your assessment James. Before you answered I tried realloc
>> in the larger program and it appears to work, in that it copies the
>> unique data to the finalarr (whether it's 10 elements or 1000000
>> elements), but the program fails and quits after the next to last line.
>>
>>
>> int cnt=0;
>> char **finalarr = malloc(sizeof(char*));
>> for(i=0;i<arrsize;i++) {
>> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
>> finalarr = realloc(finalarr, sizeof(char*) * (cnt+1));
>
> realloc() attempts to allocate the specified amount of space. If that
> attempt fails, it returns a null pointer. If that attempt succeeds, it
> then copies from the old allocation to the new one, for a number of
> bytes equal to the size of the smaller of the two allocations. As a
> optimization, it usually tries to allocate the new memory at the same
> starting location as the original allocation, if it can, which allows it
> to skip the expensive copying step - but the standard says nothing about
> this optimization.
>
> This leads to a couple of important points you need to keep in mind when
> using realloc().
>
> Like malloc(), realloc() can fail, in which case it returns a null
> pointer. If that happens, the previously allocated memory remains
> allocated. If you store the result of calling realloc() in the same
> place that you stored the only pointer you have to the original
> allocation, then if realloc() fails, you will never again be able to
> access the data you stored in that location, and you will never be able
> to free() it, leading to a memory leak. The right way to use realloc() is:
>
> void *tmp = realloc(finalarr, (cnt+1)*sizeof *finalarr);
> if(!tmp)
> {
> // Error handling
> } else {
> finalarr = tmp;
> }
https://www.thegeekstuff.com/2010/10/linux-error-codes/
Looking there, it seems ENOMEM (out of memory) is the only error that
would be returned by malloc() or realloc(). If so, would you typically
end the program, or would you try to free unused memory from elsewhere?
> The second point is that realloc() is a very expensive function to call.
> It starts out doing the same thing that malloc() does, searching through
> the heap for a block that is big enough (and preferably as small as
> possible), which is expensive in itself. On top of that, it also copies
> the data over from the previous allocation. Therefore, you should
> generally avoid calling it more often than necessary.
Once I fixed that format spec issue, the program ran fine with this call
to realloc() that was executed once per loop iteration:
finalarr = realloc(finalarr, sizeof(char*) * (cnt+1));
My goal was to size the final array to the exact size needed. But, as
you say above, it's 'very expensive' to call realloc. It doubled the
processing time vs my original (from 2 to 4 seconds, but still).
> A common strategy
> is to initially call malloc() to allocate significantly more than one
> object, and to only call realloc() when you reach the end of the current
> allocation and need to add more to it.
Using that strategy, I have this (seems to work, and very quickly):
int cnt=0, reallocated = 0;
char **finalarr = malloc(sizeof(char*) * (arrsize/2));
for(i=0;i<arrsize;i++) {
while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
finalarr[cnt] = randoms3[i];
cnt++;
if(cnt>=(arrsize/2) && reallocated==0) {
finalarr = realloc(finalarr, sizeof(char*) * (arrsize));
printf("reallocated at cnt = %d\n",cnt);
reallocated = 1;
}
}
realloc(finalarr, 0);
printf("%.4fs to remove %d dupes\n",elapsedtime(start),arrsize-cnt);
It mallocs finalarr to 1/2 the size of the source array, then when
finalarr gets full it reallocs the remaining half.
But it's getting clunky with the 'reallocated' flag. Got any other
methods to know when it's time to reallocate?
So far, 3 versions (array of 1M random elements of random size 8 to 16)
1. 2.4061s to remove 8 dupes
2. 4.8236s to remove 8 dupes
3. 0.1926s to remove 8 dupes
1 = count unique, then separate loop to copy to final array
2 = count and copy in same loop, malloc 1 entry up front then realloc()
1 element each loop
3 = count and copy in same loop, malloc 1/2 up front then realloc() 1/2
during the loop (your 'common strategy')
The last one is 12.6x as fast as the first (and 25x as fast as the
second). So that's nice. Good tip.
> When it is time to allocate more
> memory, increase the total size allocated by a fixed factor (2 is a
> popular value for that factor). As a result, the number of calls to
> realloc() is proportional to log(N), where N is the final value for the
> number of elements used. This will generally leave you with more memory
> allocated than is actually needed, but if that's a problem, you can
> realloc() back to that actual space needed at the end of the loop, which
> might release some of the excess memory.
I would like to free any unused memory right after this 'copy unique
items' operation.
Looks like realloc(finalarr,0) does it.
And that lets me continue to use finalarr afterwards, but then a call to
free(finalarr) at the end of the code throws an error. Which is good, I
think, because it means there is no longer any unused memory allocated
to finalarr, right?
Is there an easy way to measure the amt of memory freed by that command?
> Refinement 1: on many systems, allocating memory in blocks whose size is
> an integer multiple of some particular power of 2 is more efficient than
> allocating slightly more or slightly less than that amount. Which power
> of two is relevant varies from one system to another. On some systems,
> there's multiple different powers of 2 which have corresponding
> efficiency advantages. If your initial allocation is for a power of 2
> elements, and your growth factor is 2, you're virtually guaranteed to
> hit sizes that are particularly efficient.
When you say 'growth factor of 2' do you mean malloc N elements, then
continue to realloc 2N elements as needed?
To work with allocations of power of 2 I'll determine the closest power
of 2 that's greater than 1/2 the size of the source array, and use that
as a starting point.
Also, the number of dupes grows and shrinks inversely to the size of the
random strings. Running my program I see:
* randoms of size 2 to 4 will have a lot of dupes, even when run for
only 1000 elements.
* randoms of size 8 to 16 generate no dupes, even when run for 10M
elements.
> Refinement 2:
> I have vague memories of someone claiming to have seen a study
> suggesting that, at least under some common circumstances, the optimal
> growth factor is actually sqrt(2). I don't remember what those
> circumstances are.
> Using sqrt(2) directly would require floating point multiplications and
> conversions back to an integer. A better approach is to use the
> following: on even steps, set newsize = (oldsize*3)/2; on odd steps use
> newsize = (oldsize*4)/3. The average growth factor is exactly sqrt(2),
> but the individual expressions only use integer arithmetic.
>
> Refinement 3: on many systems, the malloc() family takes the space you
> requested, adds the size of a header, and then rounds up to the next
> multiple of a fixed block size. It allocates that much memory, writes
> the header at the beginning of the allocation, and returns a pointer
> just past the end of the header. Net result: it's the total size,
> including the header, that ideally should be an integer multiple of some
> particular power of 2. If the requested size is an efficient size, then
> the corresponding total size is virtually guaranteed to be a
> significantly inefficient size.
> Since the size of that header varies from one implementation to another,
> portable code has no way of dealing with this complication. Non-portable
> code can be designed to take into consideration the size of the header.
Those are interesting refinements. I'm going to work with Refinement #1
and see if I can get any significant speed increases.
>> finalarr[cnt] = randoms3[i];
>> printf("%d %s \n",cnt,finalarr[cnt]);
>> cnt++;
>> }
>> printf("%d here\n",cnt);
>> printf("%.4s remove %d dupes\n",elapsedtime(start),arrsize-cnt);
>
> You've already been informed about the problem with that format string.
Nice answer, James. Thanks for taking the time. I'm learning a lot
here on clc.
[toc] | [prev] | [next] | [standalone]
| From | Barry Schwarz <schwarzb@delq.com> |
|---|---|
| Date | 2019-11-05 17:53 -0800 |
| Message-ID | <cc54setvt0i8kn89fi629vcm2tnc18k9r9@4ax.com> |
| In reply to | #147642 |
On Tue, 5 Nov 2019 18:35:08 -0500, DFS <nospam@dfs.com> wrote:
<snip>
>Now I see where you were going. Since all I ever did was copy the
>unique elements to finalarr then print them from finalarr, there was no
>need for it to even exist. You're right.
>
>My thinking was this:
>- two initial arrays of the same size N/2
>- combine them into a new array size N
>- sort and dedupe and copy the unique elements into a final array of the
> exact size N-dupes.
>
>But rather than grow that last array as each element is added, you
>pointed out it's better to allocate bigger chunks. Then realloc(arr,0)
>will free extra-allocated memory.
realloc with a zero count will free ALL the memory allocated to that
pointer.
<snip>
>https://www.thegeekstuff.com/2010/10/linux-error-codes/
>
>Looking there, it seems ENOMEM (out of memory) is the only error that
>would be returned by malloc() or realloc(). If so, would you typically
>end the program, or would you try to free unused memory from elsewhere?
The standard (C11) does not require either routine to set errno nor
does it document ENOMEM. This would be an extension provided by
whatever run-time library you are using. The standard error
indication from allocation is a return value of NULL.
What you do after detecting the error depends on your program needs.
<snip>
>Once I fixed that format spec issue, the program ran fine with this call
>to realloc() that was executed once per loop iteration:
>
> finalarr = realloc(finalarr, sizeof(char*) * (cnt+1));
>
>My goal was to size the final array to the exact size needed. But, as
>you say above, it's 'very expensive' to call realloc. It doubled the
>processing time vs my original (from 2 to 4 seconds, but still).
>
>
>> A common strategy
>> is to initially call malloc() to allocate significantly more than one
>> object, and to only call realloc() when you reach the end of the current
>> allocation and need to add more to it.
>
>Using that strategy, I have this (seems to work, and very quickly):
>
>
> int cnt=0, reallocated = 0;
> char **finalarr = malloc(sizeof(char*) * (arrsize/2));
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
> finalarr[cnt] = randoms3[i];
> cnt++;
> if(cnt>=(arrsize/2) && reallocated==0) {
> finalarr = realloc(finalarr, sizeof(char*) * (arrsize));
> printf("reallocated at cnt = %d\n",cnt);
> reallocated = 1;
> }
> }
> realloc(finalarr, 0);
This did not do what you thought.
> printf("%.4fs to remove %d dupes\n",elapsedtime(start),arrsize-cnt);
<snip>
>I would like to free any unused memory right after this 'copy unique
>items' operation.
There is no standard way to free part of an allocation. Calling
realloc with a lesser count than currently allocated MAY accomplish
this if the function decides to reuse the current allocated area but
this is not guaranteed. If memory has become fragmented, realloc may
decide to use a smaller available area and allow the original area to
be joined with an adjacent free area to create a larger free area.
>Looks like realloc(finalarr,0) does it.
No it doesn't. You need to read the description of realloc in the
standard, not in a file that expresses someone's opinion.
>And that lets me continue to use finalarr afterwards, but then a call to
>free(finalarr) at the end of the code throws an error. Which is good, I
>think, because it means there is no longer any unused memory allocated
>to finalarr, right?
If you want finalarr to point to only as much memory as you need, then
call realloc with a count of sizeof *finalarr * cnt.
>Is there an easy way to measure the amt of memory freed by that command?
That command frees ALL the memory!
<snip>
>Those are interesting refinements. I'm going to work with Refinement #1
>and see if I can get any significant speed increases.
It would make more sense to first understand the functions that you
are using and then worry about refinements.
--
Remove del for email
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2019-11-06 09:33 -0500 |
| Message-ID | <qpulkn$htn$1@dont-email.me> |
| In reply to | #147642 |
On 11/5/19 6:35 PM, DFS wrote:
> On 11/5/2019 12:51 PM, James Kuyper wrote:
>> On 11/5/19 10:34 AM, DFS wrote:
>>> On 11/4/2019 9:45 AM, James Kuyper wrote:
>>>> On 11/3/19 5:39 PM, DFS wrote:
...
> But rather than grow that last array as each element is added, you
> pointed out it's better to allocate bigger chunks. Then realloc(arr,0)
> will free extra-allocated memory.
No, that's not what I was suggesting. That frees all of the memory, not
just the excess (or, to place the blame more precisely, that call
falsely tells realloc() that ALL of the memory is excess). What I was
suggesting corresponds to:
temp = realloc(arr, cnt*sizeof *arr);
If the new space requested is sufficiently small compared to the last
request, then this call to realloc() may release some of the excess
space - but it's not guaranteed how much it will release. realloc() will
probably round the total amount requested up to the next multiple of a
fixed block size, and that number might not be any smaller than it was
for the previous call to malloc() or realloc(). It's not even guaranteed
that it will release any memory at all.
...
> https://www.thegeekstuff.com/2010/10/linux-error-codes/
>
> Looking there, it seems ENOMEM (out of memory) is the only error that
> would be returned by malloc() or realloc(). If so, would you typically
> end the program, or would you try to free unused memory from elsewhere?
In most cases, I would end the program. However, if it's important that
the program keeps running (for instance, a heart monitor), and if there
was an alternative approach that used less memory (presumably at the
cost of being slower), I would try to back up and redo the process using
the alternative approach. That situation has never come up in any code
I've ever written, but other people do run into it occasionally.
...
>> A common strategy
>> is to initially call malloc() to allocate significantly more than one
>> object, and to only call realloc() when you reach the end of the current
>> allocation and need to add more to it.
>
> Using that strategy, I have this (seems to work, and very quickly):
>
>
> int cnt=0, reallocated = 0;
> char **finalarr = malloc(sizeof(char*) * (arrsize/2));
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
> finalarr[cnt] = randoms3[i];
> cnt++;
> if(cnt>=(arrsize/2) && reallocated==0) {
> finalarr = realloc(finalarr, sizeof(char*) * (arrsize));
> printf("reallocated at cnt = %d\n",cnt);
> reallocated = 1;
> }
> }
> realloc(finalarr, 0);
> printf("%.4fs to remove %d dupes\n",elapsedtime(start),arrsize-cnt);
>
>
> It mallocs finalarr to 1/2 the size of the source array, then when
> finalarr gets full it reallocs the remaining half.
That's not quite what I was thinking of. Unless you feel the need to
efficiently handle the case where there's lots of duplicates, arrsize
itself will only be a little more than the number of elements you need
in your array, so you should simply allocate that entire space in one
call to malloc():
finalarr = malloc(arrsize * sizeof *finalarr);
Then realloc() at the end if you really need to reduce the allocation.
> But it's getting clunky with the 'reallocated' flag. Got any other
> methods to know when it's time to reallocate?
Yes. In cases where you don't start with a good estimate of the amount
of space needed, the approach I was describing would be written
something like this.
size_t current_allocation = 32; // Judgment call.
finalarr = malloc(current_allocation * sizeof *finalarr);
if(!finalarr)
{
// Error handling
}
Inside the loop:
if(cnt>=current_allocation)
{
current_allocation *= 2;
// If there's any danger of overflow, you
// should check for it here.
void* temp = realloc(finalarr,
current_allocation * sizeof *finalarr);
if(!temp)
{
// Error handling
}
finalarr = temp;
|
[Re: final realloc()]
> Is there an easy way to measure the amt of memory freed by that command?
There is no portable way; some libraries provide tools for inspecting
the heap.
>> Refinement 1: on many systems, allocating memory in blocks whose size is
>> an integer multiple of some particular power of 2 is more efficient than
>> allocating slightly more or slightly less than that amount. Which power
>> of two is relevant varies from one system to another. On some systems,
>> there's multiple different powers of 2 which have corresponding
>> efficiency advantages. If your initial allocation is for a power of 2
>> elements, and your growth factor is 2, you're virtually guaranteed to
>> hit sizes that are particularly efficient.
>
>
> When you say 'growth factor of 2' do you mean malloc N elements, then
> continue to realloc 2N elements as needed?
No, I mean current_allocation *=2, as in the example I provided above.
[toc] | [prev] | [next] | [standalone]
| From | Barry Schwarz <schwarzb@delq.com> |
|---|---|
| Date | 2019-11-05 13:36 -0800 |
| Message-ID | <8nb3se5huvahfiro7lrcdf33f2gvq5b239@4ax.com> |
| In reply to | #147614 |
On Tue, 5 Nov 2019 10:34:36 -0500, DFS <nospam@dfs.com> wrote:
<snip>
>============================================================================
>full code listing
>============================================================================
<snip>
>int main(int argc, char *argv[])
>{
<snip>
>//-------------------------------------------------------------------------------
>//next two sections count unique items and copy to final array
>//I want to combine them, and copy unique items as they're being counted
>//-------------------------------------------------------------------------------
>
>/*
> //count unique items in existing randoms array
> int cnt=0;
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0)
>{i++;}
> cnt++;
> }
>
> //same routine as above, but create a new array
> //to hold unique values, then populate it
> printf("removing dupes... ");
> char **finalarr = malloc(sizeof(char*) * cnt);
> cnt=0;
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
> finalarr[cnt] = randoms3[i];
> cnt++;
> }
> printf("removed %d dupes\n",arrsize-cnt);
>
>*/
>
>
>//-------------------------------------------------------------------------------
>//this is the section we've been talking about.
>//-------------------------------------------------------------------------------
>
> printf("removing dupes... \n");
> QueryPerformanceCounter(&start);
> int cnt=0;
> char **finalarr = malloc(sizeof(char*));
Allocate space for exactly one pointer.
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
> //finalarr = realloc(finalarr, sizeof(char*) * (cnt+1));
> finalarr = malloc(sizeof *finalarr);
Since finalarr is a char**, sizeof *finalarr is the same as
sizeof(char*). So this allocates new space for exactly one pointer.
You commented out the correct code and left the same allocation error
in.
> finalarr[cnt] = randoms3[i];
The only element of finalarr you can access for any purpose is
finalarr[0]. Once cnt exceeds 0, you have buffer overrun and
undefined behavior.
> //printf("%d %s \n",cnt,finalarr[cnt]);
> cnt++;
> }
> printf("%d here\n",cnt);
<snip>
> exit(0);
>}
>============================================================================
--
Remove del for email
[toc] | [prev] | [next] | [standalone]
| From | jak <nospam@please.ty> |
|---|---|
| Date | 2019-11-07 10:17 +0100 |
| Message-ID | <qq0nfg$1hk0$1@gioia.aioe.org> |
| In reply to | #147614 |
Il 05/11/2019 16:34, DFS ha scritto:
> On 11/4/2019 9:45 AM, James Kuyper wrote:
>> On 11/3/19 5:39 PM, DFS wrote:
>>> =========================================================================
>>>
>>> standalone snippet works for small number of array items...
>>> (looks for dupes in an array, copies the unique values to a dynamically
>>> sized array)
>>> =========================================================================
>>>
>>> #include <stdlib.h>
>>> #include <stdio.h>
>>> #include <string.h>
>>>
>>> int main(void) {
>>> char *arr[] =
>>> {"This","array","may","contain","dupe","dupe","values"};
>>> int arrsize = sizeof(arr)/sizeof(arr[0]);
>>>
>>> int cnt = 0;
>>> char **finalarr = malloc(sizeof(char*));
>>> for(int i=0;i<arrsize;i++) {
>>> while (i<arrsize-1 && strcasecmp(arr[i],arr[i+1])==0) {i++;}
>>> finalarr = malloc(sizeof(char*));
>>> finalarr[cnt] = arr[i];
>>> printf("%d %s ",cnt,finalarr[cnt]);
>>> cnt++;
>>> }
>>>
>>> free(finalarr);
>>> }
>>>
>>>
>>> It runs fine - does all six for..loops (seven array items less one dupe)
>>> and reports correct results: unique list of values added to a
>>> dynamically sized array.
>>>
>>> 0 This
>>> 1 array
>>> 2 may
>>> 3 contain
>>> 4 dupe
>>> 5 values
>>>
>>>
>>> =========================================================================
>>>
>>> ... but virtually identical code doesn't work inline of larger program.
>>>
>>> On MSYS2 the program does a few iterations, hangs for a few sections,
>>> then aborts (core dump)
>>>
>>> On Windows after a few iteration of the for..loop it throws an *.exe
>>> quit working.
>>>
>>> =========================================================================
>>>
>>> int cnt=0;
>>> char **finalarr = malloc(sizeof(char*));
>>
>> malloc() can fail, for reasons that aren't under your control. If it
>> does, it returns a null pointer. If your code made any attempt to
>> dereference that pointer, it would have had undefined behavior. Luckily
>> (?) your code never dereferences the value returned by this call to
>> malloc(), so that issue never comes up. That raises the question of why
>> you bothered allocating memory that you never intended to use.
>
> I intended to use it, of course. I thought that was the correct way to
> initialize the array, with memory for one array entry. Then during the
> for..loop add memory for one more entry. I bet the fix is easy, but it
> eludes me.
>
>
>> However, your code does dereference the pointer returned by it's
>> second call to
>> malloc(). You should always check the value returned by malloc() to
>> determine
>> whether it's null, and take appropriate action if it is (what
>> constitutes "appropriate action" is up to you).
>
> "always check"... good practice, I agree, but 90% of the example code
> out there doesn't check.
>
>
>>> for(i=0;i<arrsize;i++) {
>>> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0)
>>> {i++;}
>>
>> As far as I can tell, the only difference between this version and the
>> previous one appears to be that you're replacing arr[] with randoms3[].
>> You should have explicitly mentioned that. Since that is the only
>> difference, you should also have shown us how randoms3[] was declared
>> and initialized, so we could compare with the way arr was declared and
>> initialized, in order to make a guess as to why the difference between
>> the two matters.
>
> randoms3[] was declared and initialized this way:
>
> char **randoms3 = malloc(sizeof(char*) * arrsize);
>
> where arrsize is the value from the command line.
>
>
>
>>> finalarr = malloc(sizeof(char*));
>>
>> The variable finalarr currently holds the only copy, anywhere in your
>> program, of the value returned by a previous call to malloc(). You are
>> replacing that value with a new one. That means that you will never
>> again be able to access the memory allocated by that previous call. You
>> also won't be able to pass that previous value to free(), which makes
>> this a memory leak.
>>
>> The following makes it easy to be certain that you're allocating the
>> right amount of memory, regardless of what the type of finalarr is:
>>
>> finalarr = malloc(sizeof *finalarr);
>>
>>> finalarr[cnt] = randoms3[i];
>>
>> You only allocated enough space for a single pointer to char. Therefore,
>> whenever cnt is greater than 0, you're accessing memory that was not
>> allocated for use by this code. You have the same problem with both
>> versions of your code. If the first version of this code appeared to
>> work, that was purely an unlucky accident. It's unlucky because it left
>> you unaware of the defect in your code.
>
> 'unlucky'... I like it.
>
>
>> I suspect that the difference is due to some data being in different
>> locations in the two different versions of your code. With your previous
>> version, finalarr[cnt] just happened to never refer to a piece of memory
>> which it was unsafe to write to. With this version, it does. That would
>> be a particularly plausible result if randoms3[] refers to dynamically
>> allocated memory.
>>
>>> printf("%d %s ",cnt,finalarr[cnt]);
>>> cnt++;
>>> }
>>>
>>>
>>>
>>> Am I allocating memory incorrectly?
>>
>> Quite thoroughly. I'm not sure you did anything correct with regards to
>> your use of dynamically allocated memory.
>
>
>
>> Also, there's no need for you to use dynamically allocated memory for
>> this purpose:
>>
>> int cnt=0;
>> for(i=0;i<arrsize;i++) {
>> while (i<arrsize-1 && strcasecmp(randoms3[i],
>> randoms3[i+1])==0)
>> {i++}
>>
>> printf("%d %s ",cnt, randoms3[i]);
>> cnt++;
>> }
>
>
> ? I never wrote that. You concocted it somehow. If you're just
> showing it as an example, I agree there's no need for dyn alloc mem there.
>
>
> What I wrote was:
>
> printf("%d %s ",cnt,finalarr[cnt]);
>
> so I could see what was copied to finalarr after each loop iteration.
>
>
>
>> It's possible that the full original context of this code provides a
>> good reasons for dynamically allocating this memory. If so, let us know,
>> and we can give you advice on how to do it properly (which will probably
>> involve the use of realloc()).
>
> Thanks for your assessment James. Before you answered I tried realloc
> in the larger program and it appears to work, in that it copies the
> unique data to the finalarr (whether it's 10 elements or 1000000
> elements), but the program fails and quits after the next to last line.
>
>
> int cnt=0;
> char **finalarr = malloc(sizeof(char*));
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
> finalarr = realloc(finalarr, sizeof(char*) * (cnt+1));
> finalarr[cnt] = randoms3[i];
> printf("%d %s \n",cnt,finalarr[cnt]);
> cnt++;
> }
> printf("%d here\n",cnt);
> printf("%.4s remove %d dupes\n",elapsedtime(start),arrsize-cnt);
>
>
>
> It also fails after the next to last line using your suggestion:
> finalarr = malloc(sizeof *finalarr);
>
>
> int cnt=0;
> char **finalarr = malloc(sizeof(char*));
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
> finalarr = malloc(sizeof *finalarr);
> finalarr[cnt] = randoms3[i];
> cnt++;
> }
> printf("%d here\n",cnt);
> printf("%.4s remove %d dupes\n",elapsedtime(start),arrsize-cnt);
>
>
>
>
> ============================================================================
>
> full code listing
> ============================================================================
>
> #include <stdlib.h>
> #include <stdio.h>
> #include <string.h>
> #include <time.h>
> #include <Windows.h>
>
>
> //usage
> //progname N L H
> //N = number of array elements to be created
> //L = low end of length of random string
> //H = high end of length of random string
> //usage example: ./rand 500 4 8
>
> //vars
> int i=0, j=0, k=0;
> char charset[62] =
> "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
> short charsetLen = 62;
>
> //program timing
> LARGE_INTEGER frequency,master,start,end;
> double elapsedtime(LARGE_INTEGER startingtimer)
> {
> QueryPerformanceCounter(&end);
> return (end.QuadPart - startingtimer.QuadPart) /
> (double)frequency.QuadPart;
> }
>
> //string compare function for qsort
> int comparechar( const void *a, const void *b){
> const char **chara = (const char **)a;
> const char **charb = (const char **)b;
> return strcasecmp(*chara, *charb);
> }
>
> //get random number from within range
> int randNbr(int low, int high) {
> return (low + rand() / (RAND_MAX / (high - low + 1) + 1));
> }
>
> //build random string of random length
> char *randStr(int randLen) {
> char *randStr = malloc(sizeof(char) * (randLen + 1));
> for(i=0; i<randLen; i++) {
> randStr[i] = charset[randNbr(0,charsetLen-1)];
> }
> randStr[randLen] = '\0';
> return randStr;
> }
>
> //copy elements of arrays a and b into existing array c
> void combinearrays(int lenA, int lenB, char *a[], char *b[], char *c[]) {
> printf("combining... ");
> memcpy(c , a, sizeof(char*) * lenA);
> memcpy(c+lenA, b, sizeof(char*) * lenB);
> printf("combined arrays 1 and 2\nnew unsorted array contains %d
> elements\n",lenA+lenB);
> }
>
>
> int main(int argc, char *argv[])
> {
> char *dupes[] =
> {"These","are","the","dupe","values","for","each","array"};
> int dupecnt = sizeof(dupes)/sizeof(dupes[0]);
>
> //size of array (including dupes)
> int arrsize = atoi(argv[1]) + (2*dupecnt);
>
> //size of random strings.
> int lo = atoi(argv[2]);
> int hi = atoi(argv[3]);
>
> //begin timer
> QueryPerformanceFrequency(&frequency);
> QueryPerformanceCounter(&master);
> QueryPerformanceCounter(&start);
>
> //create and size 3 arrays
> //first 2 are half the size of the 3rd
> //they will later be combined into the 3rd
> char **randoms1 = malloc(sizeof(char*) * arrsize/2);
> char **randoms2 = malloc(sizeof(char*) * arrsize/2);
> char **randoms3 = malloc(sizeof(char*) * arrsize);
>
> //seed
> srand(time(NULL));
>
> //populate 2 arrays with random strings of random lengths
> for(j=0;j<arrsize/2-dupecnt;j++) {
> randoms1[j] = randStr(randNbr(lo,hi));
> randoms2[j] = randStr(randNbr(lo,hi));
> }
>
> //add dupes to each array
> for(i=0;i<dupecnt;i++) {
> k = (arrsize/2)+i-dupecnt;
> randoms1[k] = dupes[i];
> randoms2[k] = dupes[i];
> }
>
>
> //show top and bottom 10
> printf("\n\nItem Array 1 Array2\n");
> printf("-------------------------------------------------\n");
> for(i=0;i<arrsize/2;i++) {
> if (i<10 || i>(arrsize/2-11)) {
> printf("%-7d %-18s %-18s \n",i+1, randoms1[i], randoms2[i]);
> }
> }
>
> printf("\n%.4fs to create %d random string elements (+ add
> dupes)\n",elapsedtime(start),arrsize-(2*dupecnt));
>
>
> //sort - combine the unsorted arrays into one, then qsort large array
> combinearrays(arrsize/2, arrsize/2, randoms1, randoms2, randoms3);
> QueryPerformanceCounter(&start);
> printf("qsorting... ");
> qsort(randoms3, arrsize, sizeof(char*), comparechar);
> printf("%.4fs\n",elapsedtime(start));
>
>
> //-------------------------------------------------------------------------------
>
> //next two sections count unique items and copy to final array
> //I want to combine them, and copy unique items as they're being counted
> //-------------------------------------------------------------------------------
>
>
> /*
> //count unique items in existing randoms array
> int cnt=0;
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0)
> {i++;}
> cnt++;
> }
>
> //same routine as above, but create a new array
> //to hold unique values, then populate it
> printf("removing dupes... ");
> char **finalarr = malloc(sizeof(char*) * cnt);
> cnt=0;
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 &&
> strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
> finalarr[cnt] = randoms3[i];
> cnt++;
> }
> printf("removed %d dupes\n",arrsize-cnt);
>
> */
>
>
> //-------------------------------------------------------------------------------
>
> //this is the section we've been talking about.
> //-------------------------------------------------------------------------------
>
>
> printf("removing dupes... \n");
> QueryPerformanceCounter(&start);
> int cnt=0;
> char **finalarr = malloc(sizeof(char*));
> for(i=0;i<arrsize;i++) {
> while (i<arrsize-1 && strcasecmp(randoms3[i],randoms3[i+1])==0) {i++;}
> //finalarr = realloc(finalarr, sizeof(char*) * (cnt+1));
> finalarr = malloc(sizeof *finalarr);
> finalarr[cnt] = randoms3[i];
> //printf("%d %s \n",cnt,finalarr[cnt]);
> cnt++;
> }
> printf("%d here\n",cnt);
> printf("%.4s remove %d dupes\n",elapsedtime(start),arrsize-cnt);
> -------------------------------------------------------------------------------
>
>
>
>
> //print top and bottom data
> printf("\ncombined data\ndeduped and sorted
> lowercase\n---------------------------------\n");
> for(i=0;i<cnt;i++) {
> if (i<10 || i>(cnt-11)) {
> printf("%-6d %s\n",i+1, finalarr[i]);
> }
> }
>
> printf("program ran in %.4fs seconds\n",elapsedtime(master));
>
> //finish
> free(randoms1);
> free(randoms2);
> free(randoms3);
> free(finalarr);
> printf("Done");
> exit(0);
> }
> ============================================================================
>
>
I'm sorry, don't you think it's better to approach it using orderly
entry lists?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
unsigned int rndNum(int min, int max)
{
int hi = 0;
int rnd;
if (min < max)
hi = max;
else
hi = min;
do
{
rnd = rand() % hi;
}
while(rnd < min);
return rnd;
}
char *rndStr()
{
static char charset[] = "AaBbCcDdEeFfGgHhIiLlMmNnOoPpQqRrSsTtUuVvZz";
int charsetLen = strlen(charset);
int i, rndLen = rndNum(3, 30);
static char *rndStr;
if((rndStr = malloc(sizeof(char) * (rndLen + 1))) != NULL)
{
for(i = 0; i < rndLen; i++)
rndStr[i] = charset[rndNum(0, charsetLen)];
rndStr[rndLen] = '\0';
}
return rndStr;
}
typedef struct LIST
{
char *str;
int count;
struct LIST *next;
} Lista;
Lista *BuildList(char *str)
{
Lista *lRet = malloc(sizeof(Lista));
if(lRet != NULL)
{
lRet->str = malloc((strlen(str) + 1) * sizeof(str[0]));
if(lRet->str != NULL)
{
strcpy(lRet->str, str);
lRet->count = 1;
lRet->next = NULL;
}
else
{
free(lRet);
lRet = NULL;
}
}
return lRet;
}
int InsertList(Lista **next, char *str)
{
static Lista *iNxt, *tmp;
static int cmp;
iNxt = *next;
if(iNxt == NULL)
cmp = -1;
else
cmp = strcmp(str, iNxt->str);
if(cmp < 0)
{
tmp = BuildList(str);
if(tmp == NULL)
return NULL;
tmp->next = iNxt;
(*next) = tmp;
}
else
{
if(cmp > 0)
{
return InsertList(&iNxt->next, str);
}
else
{
iNxt->count++;
*next = iNxt;
}
}
return 1;
}
int main(int argc, char *argv[])
{
char *str;
int i;
Lista *root = NULL, *itp, *tmp;
for(i = 0; i < 10000; i++)
{
if((str = rndStr()) == NULL)
{
perror("Allocation failure!");
exit(1);
}
if(str[0] != '\0')
if(!InsertList(&root, str))
{
printf("Error adding list\n");
exit(1);
}
free(str);
}
for(i = 1, itp = root; itp != NULL; i++)
{
/* print first last and duplicates */
if(itp->count > 1 || i == 1 || itp->next == NULL)
printf("\n%5d: %5d: %s", i, itp->count, itp->str);
tmp = itp;
itp = itp->next;
free(tmp->str);
free(tmp);
}
exit(0);
}
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-11-07 12:19 +0000 |
| Message-ID | <87imnvj2v6.fsf@bsb.me.uk> |
| In reply to | #147701 |
jak <nospam@please.ty> writes:
<cut>
> unsigned int rndNum(int min, int max)
> {
> int hi = 0;
> int rnd;
> if (min < max)
> hi = max;
> else
> hi = min;
> do
> {
> rnd = rand() % hi;
> }
> while(rnd < min);
> return rnd;
> }
This is a very odd function. What problem are you trying to solve by
writing is this way? The usual reason to have a loop in such a function
is to remove the bias that can occur when RAND_MAX is small and not a
multiple of the length of the range of values being chosen. But here
you could simply add a number in the right range to min and have no loop
at all.
IIRC the comp.lang.c FAQ has a reasonable discussion on the bias
problem.
Note also that the OP's function could generate a value of max. In your
version, the range of returned results is min to max-1. Nothing wrong
with that, but it's a non-obvious change that can trip up the unwary.
On the plan of maintaining a sorted list, it's likely to be costly. You
will be doing, in effect, a quadratic sort. You could, instead, just
all every string to the list and do an O(n log n) merge sort, followed
by a count of equal strings. Even then, the cost of all the small
allocations might be significant.
<cut>
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | jak <nospam@please.ty> |
|---|---|
| Date | 2019-11-07 18:59 +0100 |
| Message-ID | <qq1m1g$55b$1@gioia.aioe.org> |
| In reply to | #147708 |
Il 07/11/2019 13:19, Ben Bacarisse ha scritto:
> This is a very odd function. What problem are you trying to solve by
> writing is this way? The usual reason to have a loop in such a function
> is to remove the bias that can occur when RAND_MAX is small and not a
> multiple of the length of the range of values being chosen. But here
> you could simply add a number in the right range to min and have no loop
> at all.
>
> IIRC the comp.lang.c FAQ has a reasonable discussion on the bias
> problem.
>
> Note also that the OP's function could generate a value of max. In your
> version, the range of returned results is min to max-1. Nothing wrong
> with that, but it's a non-obvious change that can trip up the unwary.
>
> On the plan of maintaining a sorted list, it's likely to be costly. You
> will be doing, in effect, a quadratic sort. You could, instead, just
> all every string to the list and do an O(n log n) merge sort, followed
> by a count of equal strings. Even then, the cost of all the small
> allocations might be significant.
You're right about the sort. I had already changed the algorithm with
unbalanced btree.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
unsigned int rndNum(int min, int max)
{
int hi = 0;
int rnd;
if (min < max)
hi = max;
else
hi = min;
do
{
rnd = rand() % hi;
}
while(rnd < min);
return rnd;
}
char *rndStr()
{
static char charset[] = "AaBbCcDdEeFfGgHhIiLlMmNnOoPpQqRrSsTtUuVvZz";
int charsetLen = strlen(charset);
int i, rndLen = rndNum(3, 30);
static char *rndStr;
if((rndStr = malloc(sizeof(char) * (rndLen + 1))) != NULL)
{
for(i = 0; i < rndLen; i++)
rndStr[i] = charset[rndNum(0, charsetLen)];
rndStr[rndLen] = '\0';
}
return rndStr;
}
typedef struct LIST
{
char *str;
int count;
struct LIST *pMin, *pMaj;
} Lista;
Lista *BuildList(char *str)
{
Lista *lRet = malloc(sizeof(Lista));
if(lRet != NULL)
{
lRet->str = malloc((strlen(str) + 1) * sizeof(str[0]));
if(lRet->str != NULL)
{
strcpy(lRet->str, str);
lRet->count = 1;
lRet->pMin = lRet->pMaj = NULL;
}
else
{
free(lRet);
lRet = NULL;
}
}
return lRet;
}
int InsertList(Lista **next, char *str)
{
static Lista *iNxt;
static int cmp;
if(*next == NULL)
{
if(!(*next = BuildList(str)))
return 0;
}
else
{
iNxt = *next;
cmp = strcmp(str, iNxt->str);
if(cmp < 0)
{
return InsertList(&(iNxt->pMin), str);
}
else if(cmp > 0)
{
return InsertList(&(iNxt->pMaj), str);
}
else
{
iNxt->count++;
}
}
return 1;
}
int PrintList(Lista *l)
{
static unsigned int i = 0;
if(l == NULL)
return 1;
PrintList(l->pMin);
i++;
// if(l->count > 1) /* print duplicates */
printf("%5d: %5d: %s\n", i, l->count, l->str);
PrintList(l->pMaj);
return 0;
}
void KillList(Lista *l)
{
if(l != NULL)
{
KillList(l->pMin);
KillList(l->pMaj);
free(l);
}
}
int main(int argc, char *argv[])
{
char *str;
int i;
Lista *root = NULL;
srand(time(0));
for(i = 0; i < 3000; i++)
{
if((str = rndStr()) == NULL)
{
perror("Allocation failure!");
exit(1);
}
if(str[0] != '\0')
if(!InsertList(&root, str))
{
printf("Error adding list\n");
exit(1);
}
free(str);
}
PrintList(root);
KillList(root);
exit(0);
}
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-11-08 00:02 +0000 |
| Message-ID | <87y2wrgrr3.fsf@bsb.me.uk> |
| In reply to | #147731 |
jak <nospam@please.ty> writes:
> Il 07/11/2019 13:19, Ben Bacarisse ha scritto:
>> This is a very odd function. What problem are you trying to solve by
>> writing is this way? The usual reason to have a loop in such a function
>> is to remove the bias that can occur when RAND_MAX is small and not a
>> multiple of the length of the range of values being chosen. But here
>> you could simply add a number in the right range to min and have no loop
>> at all.
>>
>> IIRC the comp.lang.c FAQ has a reasonable discussion on the bias
>> problem.
>>
>> Note also that the OP's function could generate a value of max. In your
>> version, the range of returned results is min to max-1. Nothing wrong
>> with that, but it's a non-obvious change that can trip up the unwary.
>>
>> On the plan of maintaining a sorted list, it's likely to be costly. You
>> will be doing, in effect, a quadratic sort. You could, instead, just
>> all every string to the list and do an O(n log n) merge sort, followed
>> by a count of equal strings. Even then, the cost of all the small
>> allocations might be significant.
>
> You're right about the sort. I had already changed the algorithm with
> unbalanced btree.
A merge sort will be O(n log n) but an unbalanced tree can still be
O(n^2). On average it will be better, but not in the worst case.
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <time.h>
>
> unsigned int rndNum(int min, int max)
> {
> int hi = 0;
> int rnd;
> if (min < max)
> hi = max;
> else
> hi = min;
> do
> {
> rnd = rand() % hi;
> }
> while(rnd < min);
> return rnd;
> }
This is still an odd function. See my comments above.
> char *rndStr()
> {
> static char charset[] = "AaBbCcDdEeFfGgHhIiLlMmNnOoPpQqRrSsTtUuVvZz";
> int charsetLen = strlen(charset);
> int i, rndLen = rndNum(3, 30);
> static char *rndStr;
>
> if((rndStr = malloc(sizeof(char) * (rndLen + 1))) != NULL)
> {
> for(i = 0; i < rndLen; i++)
> rndStr[i] = charset[rndNum(0, charsetLen)];
> rndStr[rndLen] = '\0';
> }
> return rndStr;
> }
I'd write a function with this prototype:
char *rndStr(char *str_buffer, int min_len, int max_len, const char *alphabet);
so as to avoid allocating and freeing every string twice. The main
function can then call this function to fill a buffer with a random
string and the buffer can be reused. Of course if you need this
function for other things, then it's a good idea to return an allocated
string, but it looks like a special-case function with it's hard-wired
alphabet and sizes.
> typedef struct LIST
> {
> char *str;
> int count;
> struct LIST *pMin, *pMaj;
> } Lista;
>
> Lista *BuildList(char *str)
> {
> Lista *lRet = malloc(sizeof(Lista));
> if(lRet != NULL)
> {
> lRet->str = malloc((strlen(str) + 1) * sizeof(str[0]));
You could avoid doing two allocation by using a C99 flexible array
member:
typedef struct LIST
{
int count;
struct LIST *pMin, *pMaj;
char str[];
} Lista;
You then
lRet = malloc(sizeof *lRet + strlen(str) + 1);
> if(lRet->str != NULL)
> {
> strcpy(lRet->str, str);
> lRet->count = 1;
> lRet->pMin = lRet->pMaj = NULL;
> }
> else
> {
> free(lRet);
> lRet = NULL;
> }
> }
> return lRet;
> }
>
> int InsertList(Lista **next, char *str)
> {
> static Lista *iNxt;
> static int cmp;
Eek! When I see static data I start to worry. But in fact, neither of
these needs to be static. If you are worried about the stack usage, a
good compiler (like gcc) will turn this function into a loop. If you
are worried about other compilers, it's very simple to write it as a
loop.
> if(*next == NULL)
> {
> if(!(*next = BuildList(str)))
> return 0;
> }
> else
> {
> iNxt = *next;
> cmp = strcmp(str, iNxt->str);
> if(cmp < 0)
> {
> return InsertList(&(iNxt->pMin), str);
> }
> else if(cmp > 0)
> {
> return InsertList(&(iNxt->pMaj), str);
> }
> else
> {
> iNxt->count++;
> }
> }
> return 1;
> }
>
> int PrintList(Lista *l)
> {
> static unsigned int i = 0;
> if(l == NULL)
> return 1;
> PrintList(l->pMin);
> i++;
> // if(l->count > 1) /* print duplicates */
> printf("%5d: %5d: %s\n", i, l->count, l->str);
> PrintList(l->pMaj);
> return 0;
> }
>
> void KillList(Lista *l)
> {
> if(l != NULL)
> {
> KillList(l->pMin);
> KillList(l->pMaj);
You don't free l->str. Not that it matters in this case, but you are
careful about freeing storage so you probably want to to free it all.
If you didn't free it here because the tree does not "own" the string,
then I would argue that the tree insert function should not have taken a
copy.
> free(l);
> }
> }
>
> int main(int argc, char *argv[])
> {
> char *str;
> int i;
> Lista *root = NULL;
> srand(time(0));
> for(i = 0; i < 3000; i++)
> {
> if((str = rndStr()) == NULL)
> {
> perror("Allocation failure!");
> exit(1);
> }
> if(str[0] != '\0')
> if(!InsertList(&root, str))
> {
> printf("Error adding list\n");
> exit(1);
> }
> free(str);
> }
> PrintList(root);
> KillList(root);
> exit(0);
> }
>
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | jak <nospam@please.ty> |
|---|---|
| Date | 2019-11-20 10:54 +0100 |
| Message-ID | <qr32g1$psg$1@gioia.aioe.org> |
| In reply to | #147755 |
Il 08/11/2019 01:02, Ben Bacarisse ha scritto:
> jak <nospam@please.ty> writes:
>
>> Il 07/11/2019 13:19, Ben Bacarisse ha scritto:
>>> This is a very odd function. What problem are you trying to solve by
>>> writing is this way? The usual reason to have a loop in such a function
>>> is to remove the bias that can occur when RAND_MAX is small and not a
>>> multiple of the length of the range of values being chosen. But here
>>> you could simply add a number in the right range to min and have no loop
>>> at all.
>>>
>>> IIRC the comp.lang.c FAQ has a reasonable discussion on the bias
>>> problem.
>>>
>>> Note also that the OP's function could generate a value of max. In your
>>> version, the range of returned results is min to max-1. Nothing wrong
>>> with that, but it's a non-obvious change that can trip up the unwary.
>>>
>>> On the plan of maintaining a sorted list, it's likely to be costly. You
>>> will be doing, in effect, a quadratic sort. You could, instead, just
>>> all every string to the list and do an O(n log n) merge sort, followed
>>> by a count of equal strings. Even then, the cost of all the small
>>> allocations might be significant.
>>
>> You're right about the sort. I had already changed the algorithm with
>> unbalanced btree.
>
> A merge sort will be O(n log n) but an unbalanced tree can still be
> O(n^2). On average it will be better, but not in the worst case.
>
Forgive me if I'm late. I have little free time for myself.
Now I have again changed the algorithm to a balanced AVL tree.
>> #include <stdio.h>
>> #include <stdlib.h>
>> #include <string.h>
>> #include <time.h>
>>
>> unsigned int rndNum(int min, int max)
>> {
>> int hi = 0;
>> int rnd;
>> if (min < max)
>> hi = max;
>> else
>> hi = min;
>> do
>> {
>> rnd = rand() % hi;
>> }
>> while(rnd < min);
>> return rnd;
>> }
>
> This is still an odd function. See my comments above.
>
I know and you're right but I have an excuse: I wrote this function like
this because I wanted to focus on research. Originally I copied the
function from the OP and found that it repeated the same dimensions too
many times so I retouched it distractedly.
>> char *rndStr()
>> {
>> static char charset[] = "AaBbCcDdEeFfGgHhIiLlMmNnOoPpQqRrSsTtUuVvZz";
>> int charsetLen = strlen(charset);
>> int i, rndLen = rndNum(3, 30);
>> static char *rndStr;
>>
>> if((rndStr = malloc(sizeof(char) * (rndLen + 1))) != NULL)
>> {
>> for(i = 0; i < rndLen; i++)
>> rndStr[i] = charset[rndNum(0, charsetLen)];
>> rndStr[rndLen] = '\0';
>> }
>> return rndStr;
>> }
>
> I'd write a function with this prototype:
>
> char *rndStr(char *str_buffer, int min_len, int max_len, const char *alphabet);
>
You're right here too, but the excuse is the same: I was just looking
for a function that would produce random words and I wanted to focus on
sorting.
> so as to avoid allocating and freeing every string twice. The main
> function can then call this function to fill a buffer with a random
> string and the buffer can be reused. Of course if you need this
> function for other things, then it's a good idea to return an allocated
> string, but it looks like a special-case function with it's hard-wired
> alphabet and sizes.
>
>> typedef struct LIST
>> {
>> char *str;
>> int count;
>> struct LIST *pMin, *pMaj;
>> } Lista;
>>
>> Lista *BuildList(char *str)
>> {
>> Lista *lRet = malloc(sizeof(Lista));
>> if(lRet != NULL)
>> {
>> lRet->str = malloc((strlen(str) + 1) * sizeof(str[0]));
>
> You could avoid doing two allocation by using a C99 flexible array
> member:
I know but unfortunately I can't afford to choose which compiler to use
and during my work I meet really old compilers, so I tend to ignore the
new features.
>
> typedef struct LIST
> {
> int count;
> struct LIST *pMin, *pMaj;
> char str[];
> } Lista;
>
> You then
>
> lRet = malloc(sizeof *lRet + strlen(str) + 1);
>
>> if(lRet->str != NULL)
>> {
>> strcpy(lRet->str, str);
>> lRet->count = 1;
>> lRet->pMin = lRet->pMaj = NULL;
>> }
>> else
>> {
>> free(lRet);
>> lRet = NULL;
>> }
>> }
>> return lRet;
>> }
>>
>> int InsertList(Lista **next, char *str)
>> {
>> static Lista *iNxt;
>> static int cmp;
>
> Eek! When I see static data I start to worry. But in fact, neither of
> these needs to be static. If you are worried about the stack usage, a
> good compiler (like gcc) will turn this function into a loop. If you
> are worried about other compilers, it's very simple to write it as a
> loop.
>
Yes, I was worried about the use of the stack. For the same reason as
above: I rarely meet modern compilers.
>> if(*next == NULL)
>> {
>> if(!(*next = BuildList(str)))
>> return 0;
>> }
>> else
>> {
>> iNxt = *next;
>> cmp = strcmp(str, iNxt->str);
>> if(cmp < 0)
>> {
>> return InsertList(&(iNxt->pMin), str);
>> }
>> else if(cmp > 0)
>> {
>> return InsertList(&(iNxt->pMaj), str);
>> }
>> else
>> {
>> iNxt->count++;
>> }
>> }
>> return 1;
>> }
>>
>> int PrintList(Lista *l)
>> {
>> static unsigned int i = 0;
>> if(l == NULL)
>> return 1;
>> PrintList(l->pMin);
>> i++;
>> // if(l->count > 1) /* print duplicates */
>> printf("%5d: %5d: %s\n", i, l->count, l->str);
>> PrintList(l->pMaj);
>> return 0;
>> }
>>
>> void KillList(Lista *l)
>> {
>> if(l != NULL)
>> {
>> KillList(l->pMin);
>> KillList(l->pMaj);
>
> You don't free l->str. Not that it matters in this case, but you are
> careful about freeing storage so you probably want to to free it all.
> If you didn't free it here because the tree does not "own" the string,
> then I would argue that the tree insert function should not have taken a
> copy.
>
That's my bad, thank you.
>> free(l);
>> }
>> }
>>
>> int main(int argc, char *argv[])
>> {
>> char *str;
>> int i;
>> Lista *root = NULL;
>> srand(time(0));
>> for(i = 0; i < 3000; i++)
>> {
>> if((str = rndStr()) == NULL)
>> {
>> perror("Allocation failure!");
>> exit(1);
>> }
>> if(str[0] != '\0')
>> if(!InsertList(&root, str))
>> {
>> printf("Error adding list\n");
>> exit(1);
>> }
>> free(str);
>> }
>> PrintList(root);
>> KillList(root);
>> exit(0);
>> }
>>
>
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2019-11-20 11:14 +0000 |
| Message-ID | <87v9re7qbi.fsf@bsb.me.uk> |
| In reply to | #148068 |
jak <nospam@please.ty> writes:
> Il 08/11/2019 01:02, Ben Bacarisse ha scritto:
>> jak <nospam@please.ty> writes:
<cut>
>>> typedef struct LIST
>>> {
>>> char *str;
>>> int count;
>>> struct LIST *pMin, *pMaj;
>>> } Lista;
>>>
>>> Lista *BuildList(char *str)
>>> {
>>> Lista *lRet = malloc(sizeof(Lista));
>>> if(lRet != NULL)
>>> {
>>> lRet->str = malloc((strlen(str) + 1) * sizeof(str[0]));
>>
>> You could avoid doing two allocation by using a C99 flexible array
>> member:
>
> I know but unfortunately I can't afford to choose which compiler to
> use and during my work I meet really old compilers, so I tend to
> ignore the new features.
There's a very old trick to do the same thing:
typedef struct LIST
{
int count;
struct LIST *pMin, *pMaj;
char str[1];
} Lista;
Then you over-allocate the struct and store the string in-place, so to
speak. Of course it is technically undefined to access elements of the
str member with indexes > 1, but it was (and is) such a widely-used hack
that I would be surprised if any compiler did not take the possibility
into account.
<cut>
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | jak <nospam@please.ty> |
|---|---|
| Date | 2019-11-20 13:22 +0100 |
| Message-ID | <qr3b6l$3oe$1@gioia.aioe.org> |
| In reply to | #148071 |
Il 20/11/2019 12:14, Ben Bacarisse ha scritto:
> jak <nospam@please.ty> writes:
>
>> Il 08/11/2019 01:02, Ben Bacarisse ha scritto:
>>> jak <nospam@please.ty> writes:
> <cut>
>>>> typedef struct LIST
>>>> {
>>>> char *str;
>>>> int count;
>>>> struct LIST *pMin, *pMaj;
>>>> } Lista;
>>>>
>>>> Lista *BuildList(char *str)
>>>> {
>>>> Lista *lRet = malloc(sizeof(Lista));
>>>> if(lRet != NULL)
>>>> {
>>>> lRet->str = malloc((strlen(str) + 1) * sizeof(str[0]));
>>>
>>> You could avoid doing two allocation by using a C99 flexible array
>>> member:
>>
>> I know but unfortunately I can't afford to choose which compiler to
>> use and during my work I meet really old compilers, so I tend to
>> ignore the new features.
>
> There's a very old trick to do the same thing:
>
> typedef struct LIST
> {
> int count;
> struct LIST *pMin, *pMaj;
> char str[1];
> } Lista;
>
> Then you over-allocate the struct and store the string in-place, so to
> speak. Of course it is technically undefined to access elements of the
> str member with indexes > 1, but it was (and is) such a widely-used hack
> that I would be surprised if any compiler did not take the possibility
> into account.
>
> <cut>
>
I guess I have to declare the string at the end of the struct. I'll try
this hack, I have just the right compiler :) (an old compiler that comes
from 'Green Hills' on Unix). I'll relate to you.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2019-11-28 15:54 -0800 |
| Message-ID | <86v9r38sm0.fsf@linuxsc.com> |
| In reply to | #148076 |
jak <nospam@please.ty> writes:
> Il 20/11/2019 12:14, Ben Bacarisse ha scritto:
>
>> jak <nospam@please.ty> writes:
>>
>>> Il 08/11/2019 01:02, Ben Bacarisse ha scritto:
>>>
>>>> jak <nospam@please.ty> writes:
>>
>> <cut>
>>
>>>>> typedef struct LIST
>>>>> {
>>>>> char *str;
>>>>> int count;
>>>>> struct LIST *pMin, *pMaj;
>>>>> } Lista;
>>>>>
>>>>> Lista *BuildList(char *str)
>>>>> {
>>>>> Lista *lRet = malloc(sizeof(Lista));
>>>>> if(lRet != NULL)
>>>>> {
>>>>> lRet->str = malloc((strlen(str) + 1) * sizeof(str[0]));
>>>>
>>>> You could avoid doing two allocation by using a C99 flexible array
>>>> member:
>>>
>>> I know but unfortunately I can't afford to choose which compiler to
>>> use and during my work I meet really old compilers, so I tend to
>>> ignore the new features.
>>
>> There's a very old trick to do the same thing:
>>
>> typedef struct LIST
>> {
>> int count;
>> struct LIST *pMin, *pMaj;
>> char str[1];
>> } Lista;
>>
>> Then you over-allocate the struct and store the string in-place, so to
>> speak. Of course it is technically undefined to access elements of the
>> str member with indexes > 1, but it was (and is) such a widely-used hack
>> that I would be surprised if any compiler did not take the possibility
>> into account.
>>
>> <cut>
>
> I guess I have to declare the string at the end of the struct. [...]
You could use the original structure definition, and simply
point the 'str' member at the end of the struct (disclaimer:
not compiled):
size_t extra = strlen( str ) + 1;
Lista *p = malloc( sizeof *p + extra );
// check for allocation failure
p->str = (char*)p + sizeof *p;
No hack required.
[toc] | [prev] | [next] | [standalone]
Page 5 of 6 — ← Prev page 1 2 3 4 [5] 6 Next page →
Back to top | Article view | comp.lang.c
csiph-web