Thread: Linked Lists

How would you put a word into a linked list so that the linked list contains each letter of that word...so for example if I want to put "cat" into the linked list I want it to be like this "c" "a" "t" ...so each letter is separately placed in the linked lists

Are you sure you want each node in the list to represent a single character? That is a very wasteful design given that each character has at least the additional overhead of a pointer.

Yes that is the way I would have to write it unfortunately

To be more specific, I will be reading in the word from an input file and then converting that string to a linked list so that I can manipulate the word according to the remaining commands in the file ...So if I have cat in the file and then the next command is to remove the 'a' in cat I can do so within this linked lists

That's a shame. But as far as how to go about it, it is quite simple and essentially nothing changes with how a list of any other type might be managed:

Code:

#include <stdio.h>
#include <stdlib.h>

typedef struct node
    {
    char c;
    struct node *next;
    } node;

node *generate_list(const char *s)
    {
    node *list = NULL;
    node *end = NULL;

    for (; *s != '\0'; s++)
        {
        if (list == NULL)
            {
            list = (node*)malloc(sizeof(node));
            list->c = *s;
            list->next = NULL;
            end = list;
            }
        else
            {
            end->next = (node*)malloc(sizeof(node));
            end = end->next;
            end->c = *s;
            end->next = NULL;
            }
        }

    return list;
    }

int main(void)
    {
    node *list = generate_list("cat");
    node *p;

    for (p = list; p != NULL; p = p->next)
        {
        printf("%c\n", p->c);
        }

    return EXIT_SUCCESS;
    }

You just did his homework for him, sonjared.

It's best to let him at least post his attempt at coding the assignment, and then advise him a bit at a time. Let him or her, work for it, so they learn by practicing and studying, instead of simply copy/pasting your answer.

It is hard to resist answering such - believe me, I know.

Could the OP be looking on how to implement trie type structures? Wiki article:

Trie - Wikipedia, the free encyclopedia

Code:

list = (node*)malloc(sizeof(node));

What if malloc fails?

Originally Posted by Barney McGrew

Code:

list = (node*)malloc(sizeof(node));

What if malloc fails?

Good question. Another good question would be what if the host system does not release allocated memory on process termination. How would you solve those two problems?

Another improvement could be merging the if-else, since there is code duplication in the allocation and initialization of a new node.

How would you solve those two problems?

If it were for an example I'd probably handle the null pointer and just terminate without freeing the memory. That way your program wouldn't invoke undefined behaviour, so it would still be compliant with the C standard.

On the other hand, if I were writing a program for the system that you describe, a simple method might be to wrap my own allocator around malloc.

Another improvement could be merging the if-else, since there is code duplication in the allocation and initialization of a new node.

Yup, I see two good options there. The first is to use a node ** to refer to the current node, and the second is to build the list in reverse, then reverse it manually.

If it were for an example I'd probably handle the null pointer and just terminate without freeing the memory.

This opens up an interesting discussion. If malloc fails and the program has not previously requested sufficient memory to complete execution, what other option is there than to terminate as gracefully as possible? Is it worth trying to recover? Obviously the answer depends somewhat on the application in question, but what to do when malloc fails can be a surprisingly deep problem. Often the best answer is to clean up what is possible and then terminate.

The first is to use a node ** to refer to the current node, and the second is to build the list in reverse, then reverse it manually.

I hadn't considered building the list in reverse, though performance-wise it probably wouldn't be an issue given that the string is unlikely to be excessively long. The solution I had in mind was also a node**.

That way your program wouldn't invoke undefined behaviour, so it would still be compliant with the C standard.

Just so that it is clear, I left checking for errors and freeing memory out of the example intentionally. The kind of scaffolding that should be in production code would obscure the meat of the example, which in this case was the loop over a string and appending of nodes to a list.

I know this is gonna sound nooby but, malloc can fail? O_o

Well, I guess you can run out of available memory but can malloc fail in any other case?

And on a slightly related note, I heard about the memory manager Hoard. They claim the command to use it is "LD_PRELOAD=/path/libhoard.so" but how do I actually check if Hoard's libraries are being used instead of the standard malloc one?

Originally Posted by MutantJohn

Well, I guess you can run out of available memory but can malloc fail in any other case?

Yes. Most operating systems can impose per-process limits the processes are not allowed to exceed, even if there is technically more memory available. For example, in Linux these can be queried using getrlimit().

Originally Posted by MutantJohn

They claim the command to use it is "LD_PRELOAD=/path/libhoard.so" but how do I actually check if Hoard's libraries are being used instead of the standard malloc one?

Using the dynamic linker (include <dlfcn.h>, and link using -ldl). For example:

Code:

#define  _GNU_SOURCE
#include <stdio.h>
#include <dlfcn.h>

#ifndef   LIBC_NAME
#define   LIBC_NAME "libc.so.6"
#endif

#ifndef   LIBHOARD_NAME
#define   LIBHOARD_NAME "libhoard.so"
#endif

int main(void)
{
    void    *libhoard_handle, *libhoard_malloc;
    void    *libc_handle, *libc_malloc;
    void    *current_malloc;

    libc_handle = dlopen(LIBC_NAME, RTLD_NOW | RTLD_NOLOAD | RTLD_GLOBAL);
    if (!libc_handle) {
        fprintf(stderr, "%s\n", dlerror());
        return 1;
    }

    current_malloc = dlsym(RTLD_DEFAULT, "malloc");
    libc_malloc = dlsym(libc_handle, "malloc");
    if (current_malloc == libc_malloc) {

        fprintf(stderr, "malloc() is from standard C library (%s)\n", LIBC_NAME);

    } else {

        libhoard_handle = dlopen(LIBHOARD_NAME, RTLD_NOW | RTLD_NOLOAD | RTLD_GLOBAL);
        if (libhoard_handle) {

            libhoard_malloc = dlsym(libhoard_handle, "malloc");
            if (current_malloc == libhoard_malloc) {

                fprintf(stderr, "malloc() is from Hoard library (%s)\n", LIBHOARD_NAME);

            } else {

                fprintf(stderr, "malloc() is from an unknown library.\n");
            }

            dlclose(libhoard_handle);

        } else {

            fprintf(stderr, "%s: Hoard library not loaded.\n", LIBHOARD_NAME);

        }
    }

    dlclose(libc_handle);

    return 0;
}

But really, you normally just want to know if the Hoard library is loaded or not. Here is a simple function, library_loaded(), that will return nonzero if the named library (say, "libhoard.so" or "libc.so.6") is loaded, zero if not loaded.

Code:

#include <stdio.h>
#include <string.h>
#include <dlfcn.h>

int library_loaded(const char *const name)
{
    void *handle;
    int   retval;

    if (!name || !*name)
        return 0;

    handle = dlopen(name, RTLD_NOW | RTLD_NOLOAD | RTLD_GLOBAL);
    if (handle != NULL) {
        retval = 1;
        dlclose(handle);
    } else
        retval = 0;

    return retval;
}

int main(int argc, char *argv[])
{
    int arg;

    if (argc < 2 || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
        fprintf(stderr, "\nUsage: %s LIBRARY ...\n\n", argv[0]);
        return 1;
    }

    for (arg = 1; arg < argc; arg++)
        if (library_loaded(argv[arg]))
            printf("%s: Loaded\n", argv[arg]);
        else
            printf("%s: Not loaded\n", argv[arg]);

    return 0;
}

If you save the above as libtest.c, you can compile and run it using

Code:

gcc -W -Wall libtest.c -ldl -o libtest
./libtest libc.so.6 libhoard.so
env LD_PRELOAD=/path/libhoard.so ./libtest libc.so.6 libhoard.so