7
\$\begingroup\$

I'm working on a C library which attempts to bring some of the Python string functions over to C.

This is where my full source is located, but the majority of what I have so far is here.

Are there any places where code efficiency can be improved?

#ifndef OCTO_H
#define OCTO_H

#include <stdlib.h>
#include <string.h>

int len(char* string){

    int i = 0;
    while(*string != '\0'){
        i++;
        *string++;
    }

    return i;

}

char* lstrip(char* string){

    if(!string) 
        return;

    /* Trim off leading whitespace */
    while(*string == ' '){
        string++;
    }

    return string;

}

char* rstrip(char* string){

    /* Trim off trailing whitespace */
    char* end = string + len(string) - 1;
        while (end >= string && *end == ' ')
                end--;
        *(end + 1) = '\0';

    return string;

}

char* strip(char* string){

    /* Trim off both leading and trailing whitespace */
    char* lstring = lstrip(string);
    char* finalString = rstrip(lstring);

    return finalString;

}

char* slice(char* s, int start, int end){

    /* Create a new identical buffer */
    char* buff = (char*) malloc((end - start) + 2);
    strncpy(buff, s + start, (end - start) + 1);
    *(buff + (end - start) + 1) = '\0';
    return buff;
}

char* toUpperCase(char* s){


}

char* toLowerCase(char* s){


}

#endif /* OCTO_H */
\$\endgroup\$
  • 2
    \$\begingroup\$ It is not a header file so your multiple-inclusion barrier is unnecessary (#ifndef OCTO_H etc) \$\endgroup\$ – William Morris Aug 15 '13 at 20:30
  • \$\begingroup\$ @WilliamMorris: Do we call these multiple-inclusion barrier as Header Guards? \$\endgroup\$ – user26703 Aug 16 '13 at 4:29
  • \$\begingroup\$ @WedaPashi: Yes, header guards are there to prevent the header from being included more than once. \$\endgroup\$ – Jamal Aug 16 '13 at 6:28
  • \$\begingroup\$ Note that the identifier string is reserved for the standard library, so you shouldn't use it. \$\endgroup\$ – Paul Griffiths Aug 25 '13 at 20:55
5
\$\begingroup\$

Well efficiency can be improved by using the built-in string functions.
They have been optimized at the assembly level for most implementations.

Assuming you were writing len() in C rather than using some optimal assemble instructions. The canonical form looks more like this (though I am sure it can be done better). Though there is strlen() which does the same thing.

int len(char* string)
{
    char *end = string;
    for(;*end;++end)  /* Notice nothing here */;
    return end-string;
}

Looking at this:

char* lstrip(char* string){


    /* This makes it non optimal for strings we already know are good.
     * If I already know my string is fine I would want a function that
     * did not do this test.
     *
     * Of course you can then have a second function that does the test
     * then calls the non checked version (and if it is short the compiler
     * will inline
     */
    if(!string)
        /* Not returning a value from a function expecting a value is an error
         * Check the warning messages generated by the compiler
         */      
        return;

    /*
     * ' ' is not white space it is just a space character
     *    What you are looking for is isspace(c)
     */    
    while(*string == ' '){
        string++;
    }

    return string;
}

I would have written like this:

char* lstripNT(char* string){ return string?lstrip(string):NULL;}
char* lstrip(char* string){
    for(;isspace(string);++string) /*Nothing here*/;
    return string;

    // NOTE: there is an issue with this technique in that you
    //       are not returning the original string.
    //       If the string was dynamically allocated
    //       you now have issues with freeing it. Which means you
    //       specifically need to keep a copy of the original pointer
    //       for the purpose of freeing it when you are finished.
    //       This is NOT a good idea.
}

Because of the problem with dynamic allocation I would probably write like this:

char* lstrip(char* string)
{
    size_t  move = 0;
    char*   start= string;
    for(;isspace(start);++start,++move)
    {}
    if (move)
    {
        // Move all the characters down.
        // So we basically squish the white space.
        for(;*start;++start)
        {
            *(start-move) = *start;
        }
    }
    return string;
}

Right trim. Is not really optimal because you scan to the end (using len). Then you then scan backwards until you find a non space character. You can do this in a single traverse. Also you are not being consistent. lstrip() checks for NULL while this does not.

char* rstripNT(char* string){ return string?rstrip(string):NULL;}
char* rstrip(char* string){

      char* loop    = string;
      char* last    = NULL;
      int   isSpace = false;
      while(*loop)
      {
          isSpace = TRUE;
          last    = loop;
          for(;*loop && isspace(*loop);++loop)
          {}
          if (*loop)
          {
              isSpace = FALSE;
              for(;*loop && !isspace(*loop);++loop)
              {}
          }
      }
      if (isSpace)
      {
          *last = '\0';
      }
      return string;
}

The strip.

char* strip(char* string){

    /* Trim off both leading and trailing whitespace */
    char* lstring = lstrip(string);
    char* finalString = rstrip(lstring);

    return finalString;

}

This is conceptually what you want to do.
But I don't think that will be optimal way to do it. I would write this as a single pass.

\$\endgroup\$
  • \$\begingroup\$ I think for(;*end;++end) /* Notice nothing here */; should be for(;*end;++end){} /* Notice nothing here */; \$\endgroup\$ – Cygwinnian Aug 15 '13 at 20:13
  • 2
    \$\begingroup\$ @Cygwinnian: Those are both the same. The standard is for(<init>;<test>;<inc>)<statement>. Statement can be the empty statement ; or it can be Block {} both work the same way. \$\endgroup\$ – Martin York Aug 15 '13 at 21:09
  • \$\begingroup\$ @LokiAstari Sorry didn't see the semicolon at the end of the comment. \$\endgroup\$ – Cygwinnian Aug 15 '13 at 21:57
  • \$\begingroup\$ To expand on the point about using built-in functions, strlen() in particular is likely to have an built-in implementation that is faster than you’d be able to hand code in C. \$\endgroup\$ – microtherion Aug 16 '13 at 7:07
  • \$\begingroup\$ @microtherion: I though I said that in the first sentence. \$\endgroup\$ – Martin York Aug 16 '13 at 16:34
4
\$\begingroup\$

Efficiency is just one of the issues with your library. Here are some other concerns.

Implementation as a header file. Most libraries are linked in to the code that uses it; yours is compiled in, by being #included as a header file. What happens if file1.c and file2.c each uses octo.h? Then when you try to link file1.o and file2.o together, each of your functions would be defined twice, which is a linking error.

Incomplete Python emulation. String libraries can actually be quite complicated. For example, which characters are considered whitespace? Traditionally, the whitespace characters are Tab, Newline, Vertical tab, Form feed, Carriage return, and Space, but Unicode defines many more whitespace characters, so the answer may vary by locale. Should len() count bytes, or should it count Unicode characters, assuming that its argument is a string encoded in UTF-8? If your library is inspired by Python, people may have an expectation that it behaves like Python.

Memory handling. Your rstrip() function clobbers the input string. C programmers sometimes tolerate such behaviour, if it's documented. However, the fact that your rstrip() returns a char * rather than void suggests that it returns the stripped string as a copy, rather than modifying the original. On the other hand, your slice() function returns a copy and leaves the original unmolested. In short, your library has no consistent memory-management policy, which is essential for any cohesive C library. As a result, anyone who uses it is likely to get segfaults and/or memory leaks.

Stray pointer dereference in len(). Your len() function has a statement *string++; that should be just string++;. By the way, if you had written (*string)++; instead, you would have implemented a Caesar cipher shifting by 1.

You could use C library functions. Your len() is just strlen() (but returning a signed rather than unsigned int). Your lstrip() could use strspn() or isspace(). In short, get familiar with the C library's built-in functions before you write your own.

\$\endgroup\$
4
\$\begingroup\$

These points are mostly designed-oriented:

  • I'd recommend having len() return a size_t with i as the same type. This type is preferred for size functions and is also used in libraries.

  • Although just another form, lstrip() can be done this way:

    char* lstrip (char* string) {
    
        // skip and return right away if condition is not met
        if (string) {
            /* Trim off leading whitespace */
            while (*string == ' ') {
                string++;
            }
        }
    
        return string;
    }
    

    Also, your plain return won't work because the function is supposed to return a char*.

\$\endgroup\$
3
\$\begingroup\$

Here's another variant on these functions. I've passed in a character set, cset, that is to be stripped instead of assuming we are stripping just spaces or using isspace. So you might pass in

" \t\n\r"

as cset, for example.

size_t lstrip(char * restrict s, const char * restrict cset)
{
    const char *t = s + strspn(s, cset);
    size_t len = strlen(t);

    if (s != t) {
        memmove(s, t, len + 1); // +1 to capture the \0
    }
    return len;
}

Here is rstrip

size_t rstrip(char * restrict s, const char * restrict cset)
{
    char *end = s + strlen(s);

    while (end > s && strchr(cset, *end)) {
        --end;
    }
    end[1] = '\0';
    return (size_t) (end - s);
}

These functions are reasonably efficient.

Implementing slice is much more complicated if you want to emulate Python well because Python (as far as I remember) allows negative values in start/end so that you can slice relative to the end rather than the start. Your version doesn't handle such things.

\$\endgroup\$
0
\$\begingroup\$

One way to improve time-efficiency for certain operations would be to package the string in a struct. If you make the char* the first member, then the struct can be cast to a char* and used normally. But it lets you stash a length member and avoid recalculating.

struct mystr {
    char *ptr;
    size_t len;
};
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.