Why does strcat mess up the tokens in strtok (and strtok_r)?

Discussion in 'C Programming' started by DFS, Jun 11, 2014.

  1. DFS

    DFS Guest

    The only thing I would change is moving the initialization of l out of
    the while loop. And for my own style, add some brackets to the str += line:

    int getMaxWordLength(const char *str, const char *delim)
    size_t max = 0, l;
    while (*str) {
    l = strcspn(str, delim);
    if (l > max) max = l;
    str += (l + strspn(str, delim));
    return max;

    I doubt that's the right answer, though. My guess is it has something
    to do with strcspn and strspn.
    DFS, Jun 14, 2014
    1. Advertisements

  2. DFS

    DFS Guest

    Looks more than subtle to me!

    That's worrisome.

    I may not have posted it, but in my example main() from which I called
    the routine I always set char delim[N] = "space and/or some characters"
    DFS, Jun 14, 2014
    1. Advertisements

  3. DFS

    DFS Guest

    And here's a visual display of why it doesn't matter:

    [dfs@home files]$ ./temp
    String: The titanosaur remains were eaten up.
    Delimiter(s): | |
    word lengths: 3,0,10,0,7,0,4,0,5,0,3, (max 10)
    DFS, Jun 14, 2014
  4. DFS

    DFS Guest

    That's a good way of thinking about it.

    I don't get you. Isn't it 'special' (ie powerful, intelligent) to
    generate a machine-ish object file from C code?

    I've seen a few people online praise Haskell.

    Nice post. Thanks for the good info.
    DFS, Jun 14, 2014
  5. Yes, I intended the "str + l" to be in the strspn call but having written
    something a bit like "str + l" I probably forgot that I hadn't (if you
    see what I mean).

    Ben Bacarisse, Jun 14, 2014
  6. DFS

    James Kuyper Guest

    On 06/14/2014 01:30 AM, Barry Schwarz wrote:
    'tgt' and 'src' are supposed to be restrict-qualified (C99 and later).
    James Kuyper, Jun 14, 2014
  7. DFS

    James Kuyper Guest

    On 06/14/2014 11:03 AM, DFS wrote:
    You haven't moved the initialization of 'l' out of the loop; 'l' is
    still uninitialized at this point.

    This code makes no use of 'l' anywhere except inside the body of the
    while() loop, and the value at the end of a given pass through the loop
    gets overwritten at the start of the very next pass. Why give 'l' a
    wider scope than necessary?
    'l' doesn't become initialized until the first time the following line
    gets executed:
    James Kuyper, Jun 14, 2014
  8. DFS

    DFS Guest

    I want to try those exercises you talk about below, but you snipped my
    post (all of main()), so I can't tell what you're talking about:

    Are you referring to the elapsed time calculations in main()?

    int main(void) {
    int i,j;
    struct timespec start, end;
    double et;

    for (i = 30; i <= 44; i++) {
    clock_gettime(CLOCK_MONOTONIC_RAW, &start);
    j = Fib(i);
    clock_gettime(CLOCK_MONOTONIC_RAW, &end);
    et = (end.tv_sec-start.tv_sec) + ((end.tv_nsec-start.tv_nsec) /
    printf("Fibonacci %d = %d (%.2f seconds)\n", i, j, et);

    Integer versions of what?
    DFS, Jun 15, 2014
  9. DFS

    BartC Guest

    I think this is about FibBinet() function which might not give an exact
    result (and that it can't represent every whole number which needs 52 to 64
    bits or thereabouts, whereas a 64-bit int type can).
    Presumably of a Fibonacci function. For example, this simple iterative

    unsigned long long int myfib(int num) {
    unsigned long long int a,b,t;
    int i;
    for (i=0; i<num; ++i){
    return a;

    calculates myfib(44) more than 10 times faster than FibBinet(), and handles
    values up 64 bits exactly, despite using a loop.
    BartC, Jun 15, 2014
  10. DFS

    Jorgen Grahn Guest

    Perhaps I'm missing some contect (the declaration of 'str' isn't shown
    above) but if the compiler cannot prove that the 'const char* str'
    isn't modified inside the loop through some alias, the 'const' doesn't
    Jorgen Grahn, Jun 15, 2014
  11. DFS

    DFS Guest

    I think I got it (simple iteration)! I took another look at my orig
    code/output and noticed you don't have to calculate Fib(N) recursively
    each iteration, you just have to keep track of the previous 2 numbers
    and add them together.

    No wonder it was so slow: by the time it got to Fib(40) it had done
    Fib(1) through Fib(39) up to thirty-nine times each.

    New version:

    long long Fib(int num) {
    long long a=0,b=1,F;int i=0;
    return F;

    But I notice Fib(72) and up are slightly different from the FibBinet()

    long long FibBinet(int num) {
    long long FB = (pow(1+sqrt(5),num) - pow(1-sqrt(5),num)) /
    (pow(2,num) * sqrt(5));
    return FB;

    int main(void) {
    long long a,b;
    for (int i=0;i<=100;i++) {
    a = Fib(i);
    b = FibBinet(i);
    if(a != b) {
    printf("Fib(%d) = %-*llu Binet = %llu\n", i,22,a,b);

    [dfs@home misc]$ ./Fibonacci
    Fib(72) = 498454011879264 Binet = 498454011879265
    Fib(73) = 806515533049393 Binet = 806515533049395
    Fib(74) = 1304969544928657 Binet = 1304969544928660
    Fib(75) = 2111485077978050 Binet = 2111485077978055
    Fib(76) = 3416454622906707 Binet = 3416454622906715
    Fib(77) = 5527939700884757 Binet = 5527939700884771
    Fib(78) = 8944394323791464 Binet = 8944394323791488
    Fib(79) = 14472334024676221 Binet = 14472334024676260
    Fib(80) = 23416728348467685 Binet = 23416728348467744
    Fib(81) = 37889062373143906 Binet = 37889062373144008
    Fib(82) = 61305790721611591 Binet = 61305790721611752
    Fib(83) = 99194853094755497 Binet = 99194853094755776
    Fib(84) = 160500643816367088 Binet = 160500643816367552
    Fib(85) = 259695496911122585 Binet = 259695496911123328
    Fib(86) = 420196140727489673 Binet = 420196140727490880
    Fib(87) = 679891637638612258 Binet = 679891637638614272
    Fib(88) = 1100087778366101931 Binet = 1100087778366105088
    Fib(89) = 1779979416004714189 Binet = 1779979416004719360
    Fib(90) = 2880067194370816120 Binet = 2880067194370824704
    Fib(91) = 4660046610375530309 Binet = 4660046610375544832
    Fib(92) = 7540113804746346429 Binet = 7540113804746369024

    Fib(93) = 12200160415121876738 Binet = 9223372036854775808
    Fib(94) = 1293530146158671551 Binet = 9223372036854775808
    Fib(95) = 13493690561280548289 Binet = 9223372036854775808
    Fib(96) = 14787220707439219840 Binet = 9223372036854775808
    Fib(97) = 9834167195010216513 Binet = 9223372036854775808
    Fib(98) = 6174643828739884737 Binet = 9223372036854775808
    Fib(99) = 16008811023750101250 Binet = 9223372036854775808
    Fib(100) = 3736710778780434371 Binet = 9223372036854775808

    Also, from (93) onward the Fib() results look random, while the
    FibBinet() result is always 9223372036854775808 (highest 64-bit number+1).

    I couldn't find much on the web about d'Ocagne's identity, other than a
    description and this page.


    So far all I've been able to do is prove the identity holds (sometimes
    - it seems to hold where m>=n for integers >=0):

    int docagne(int m, int n) {
    printf("docagne %d,%d: ", m,n);
    if((Fib(m)*Fib(n+1))-(Fib(n)*Fib(m+1))==pow(-1,n)*Fib(m-n)) {
    printf("identity holds\n");
    } else {
    printf("identity (or DFS) fails\n");
    return 0;

    int main(void) {
    int a=-10,b=10;
    printf("\nd'Ocagne identity =
    for (int i=a;i<=b;i++) {
    for (int j=a;j<=b;j++) {

    Cool exercises!

    I'm stuck on using docagne to generate the Fib series, and on the
    recursive stuff. I do like the idea of recursive functions - they seem
    tidier or something.
    DFS, Jun 15, 2014
  12. DFS

    DFS Guest

    I meant 'move the declaration'.

    So you recommend declaring and initializing it inside the loop?

    I figured it used more resources that way, than declaring it outside and
    initializing it inside.
    DFS, Jun 15, 2014
  13. DFS

    Kaz Kylheku Guest

    But it creates an opportunity to demonstrate memoization. :)
    Kaz Kylheku, Jun 15, 2014
  14. DFS

    BartC Guest

    Suppose you wanted to test how well a language implemention handled lots of
    function calls. Fib(44) using the recursive method requires over two billion
    calls. An iterative version requires at most one call. Which one is a better

    (And ultimately both are pointless for actually delivering a Fibonacci
    number; there are so few that will fit into even 64-bits, that a function
    might just as well use a pre-calculated lookup-table.)
    BartC, Jun 15, 2014
  15. DFS

    James Kuyper Guest

    Not in the sense he meant. Object files are just ordinary files in a
    tightly specified format. No special permissions or abilities are needed
    to write them, just a sufficiently good understanding of that format.
    James Kuyper, Jun 16, 2014
  16. DFS

    James Kuyper Guest

    I do, strongly. Other people disagree with me, equally strongly,
    recommending that automatic variables should be declared only at the top
    of each function. You'll have to read our arguments and make your own
    decision. There's nothing horribly wrong with the other approach, I just
    think mine is better.
    I'm curious - why? It must be set to a value at the start of each pass
    through the loop, regardless of whether it's declared inside the loop or
    outside of it.

    If anything, it might use less resources, in some cases. By declaring
    the variable inside the loop, it's lifetime ends when the body of the
    loop completes. That means that the memory it occupied could be
    available for some other variable declared later in the same function.
    This isn't a particularly significant effect - any such variable can be
    trivially analyzed to determine it will never be in use at the same time
    as the first variable, and the two variables can therefore both be given
    the same location in memory (unless your program takes the address of
    both variables while they are in scope, which might force it to give
    them distinct addresses).

    There are three main reasons why I prefer declaring each identifier with
    the tightest possible scope. Firstly, it reduces the likelihood of two
    things being accidentally being given the same name in overlapping
    scopes. Secondly, it means that you don't have to search as far from the
    point of use to find the definition. Finally, if you delay definition of
    a variable long enough, it's often possible to give it the only value it
    will ever have, as part of the initialization. That allows you to define
    it to be 'const', which often can enable warnings that would not
    otherwise occur, and optimizations that would otherwise not be permitted.
    In C90, declarations can occur only at the start of a block; but in
    later versions of C, they can be mixed in with statements. Since the
    scope of a variable name starts at the point of declaration, "tightest
    possible scope" implies taking advantage of that fact to delay
    definition even further - unless C90 compatibility is important.

    Note: in principle, "tightest possible scope" could be taken as implying
    the creation of a separate compound-statement block for each variable.
    That would be ridiculous - it's not what I mean. I create
    compound-statement blocks only as needed for other purposes, and define
    each variable in the innermost of those blocks that gives it sufficient
    scope for it's intended use.
    James Kuyper, Jun 16, 2014
  17. DFS

    DFS Guest

    Interesting. And given that 'naive' code, the times to calculate
    follows the same pattern:

    Fibonacci 30 = 832040 (0.03 seconds)
    Fibonacci 31 = 1346269 (0.05 seconds)
    Fibonacci 32 = 2178309 (0.08 seconds)
    Fibonacci 33 = 3524578 (0.12 seconds)
    Fibonacci 34 = 5702887 (0.20 seconds)
    Fibonacci 35 = 9227465 (0.32 seconds)
    Fibonacci 36 = 14930352 (0.52 seconds)
    Fibonacci 37 = 24157817 (0.84 seconds)
    Fibonacci 38 = 39088169 (1.36 seconds)
    Fibonacci 39 = 63245986 (2.19 seconds)
    Fibonacci 40 = 102334155 (3.55 seconds)
    Fibonacci 41 = 165580141 (5.75 seconds)
    Fibonacci 42 = 267914296 (9.30 seconds)
    Fibonacci 43 = 433494437 (15.04 seconds)
    Fibonacci 44 = 701408733 (24.34 seconds)

    I used a global variable (I don't know any other way) to keep track of
    how many calls to Fib() were made:

    int Fib(int num) {
    int i=0;
    FibCounter++; //global
    if(num==0) {i = 0;}
    else if(num==1) {i = 1;}
    else if(num>=2) {i = Fib(num-1) + Fib(num-2);}
    return i;

    The # of calls Fib(0) thru Fib(40) is 866,988,831.
    DFS, Jun 16, 2014
  18. DFS

    DFS Guest

    I get strange numbers above Fib(92)

    Fib(84) = 160500643816367088
    Fib(85) = 259695496911122585
    Fib(86) = 420196140727489673
    Fib(87) = 679891637638612258
    Fib(88) = 1100087778366101931
    Fib(89) = 1779979416004714189
    Fib(90) = 2880067194370816120
    Fib(91) = 4660046610375530309
    Fib(92) = 7540113804746346429

    Fib(93) = 12200160415121876738
    Fib(94) = 1293530146158671551
    Fib(95) = 13493690561280548289
    Fib(96) = 14787220707439219840
    Fib(97) = 9834167195010216513
    Fib(98) = 6174643828739884737
    Fib(99) = 16008811023750101250
    Fib(100) = 3736710778780434371

    unsigned long long int myfib(int num) {
    unsigned long long int a,b,t;
    int i;
    for (i=0; i<num; ++i){
    return a;

    int main(void) {
    for (int i=0;i<=100;i++) {
    unsigned long long int j = myfib(i);
    printf("Fib(%d) = %llu\n",i,j);
    DFS, Jun 16, 2014
  19. DFS

    Ike Naar Guest

    One type of system where compilers *were* (or still are?) special
    programs is the Burroughs large system series (later Unisys).
    Executables were not ordinary files but has a special bit that
    marked them as such, this bit could only be set by a program that
    was declared a "compiler" by the system operator (I believe the
    console command to achieve this was "MC" for "make compiler").
    Ike Naar, Jun 16, 2014
  20. DFS

    Ike Naar Guest

    Apparently unsigned long long int is a 64-bit type on your computer,
    so it cannot store numbers larger than 18446744073709551615.
    Ike Naar, Jun 16, 2014
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.