Thread: Determining length needed for string

  1. #16
    Registered User
    Join Date
    Mar 2010
    Your code is leaking memory -- you have calls to malloc but no corresponding calls to free. You should free the memory once you no longer need the temporary expansion.

    Anyway - your question --
    It looks like you can't know how long the buffer needs to be until you've expanded stuff. One option would be to do a 'dry run' of the expansion that just counts the number of characters in the string, then malloc that amount then expand into there. To be honest I haven't looked at what you're doing closely enough to know if you could calculate the needed size upfront somehow, or at least make a conservative estimate. I assume if you could do this you would have done it already

    I'd probably go for dynamically resizing your buffer with realloc (realloc - C++ Reference).
    First decide on an initial buffer size -- for testing, best pick a pathetically small size to make sure your reallocation is working. But after testing, just go for a buffer size that feels like it'll probably fit most cases.

    I'd suggest writing another helper function for concatenating the expansion into the main buffer. Before you copy anything into the buffer, you will need to check that there is enough space remaining for the string. Unfortunately I think this means you'll have to pass around a buffer_size variable.
    If there isn't enough space in the buffer, increase it by some amount and try again until you have enough space.

       while (not enough space in buffer0
            increase buffer size var
            realloc buffer with bigger size
        concat string to buffer
    Read the docs about realloc -- in particular, beware that it might return a different block of memory, so you'll need to return the pointer from the function.

    You could of course realloc for every single expansion, just allocating as much as you need, but that would impact performance, especially if realloc needs to copy the string to a new place often. On your average desktop machine I doubt you'd ever observe any actual slowdown, but it's good to be considerate of such things and consider the tradeoff you're making (size of upfront memory allocation vs frequency of calls to realloc).

    You could also do it with some dynamic data structure like a linked list of strings. You could traverse it at the end and turn it back into a string. I really don't think that's the right solution though, overkill.

    Not sure if other people will suggest better ideas -- I've not used realloc a lot in real code, so not sure if it's actually a good way. Better than allocated a huge fixed length buffer and hoping for the best..... which I see all the time in production code!

  2. #17
    Registered User
    Join Date
    May 2012
    Arizona, USA
    /* Write a function expand(s1,s2) that expands shorthand notations like
    a-z in the string s1 into the equivalent complete list in s2.
    Allow for letters of either case and digits, and be prepared to handle
    cases like a-b-c and a-z0-9 and -a-z. Arrange that a leading or
    trailing - is taken literally. */
    I think most of us missed this part. Your assignment is to store the expanded string in the buffer pointed to by s2, which is passed to your function. The caller of the expand function has to ensure that the buffer pointed to by s2 is large enough to hold the expanded results. I think you're trying to do more than is asked of you in this assignment and making it more complicated than it has to be.

    It is certainly a good idea to dynamically allocate the result string if this were to go into a real-world application, but homework assignments are not exactly real-world applications. It's a good thing that you're thinking about this issue now, even when it's not required in this specific case.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 20
    Last Post: 03-08-2011, 05:16 PM
  2. Determining external path length of a tree
    By kolistivra in forum C Programming
    Replies: 11
    Last Post: 09-01-2006, 10:22 AM
  3. Determining Length of Keypress
    By Nascent in forum C++ Programming
    Replies: 3
    Last Post: 11-30-2005, 03:37 PM
  4. String length
    By Kokila in forum C++ Programming
    Replies: 4
    Last Post: 12-19-2001, 12:42 AM
  5. length of string etc.
    By Peachy in forum C Programming
    Replies: 5
    Last Post: 09-27-2001, 12:04 PM

Tags for this Thread