Trying to create a linked list in C: can I just import a C++ header file?

Right now I'm working on an implementation of malloc(), and would like to keep track of free blocks using a linked list. Except, I don't know if the standard C libraries provide the programmer a "linked list", but apparently C++ does.

Otherwise, c开发者_如何学Can anyone lend a few pointers as to how a linked list should be implemented?

There isn't a standard linked list in C; see Wikipedia if you're determined to roll your own, but I don't recommend it.

BSDs and Linux will give you sys/queue.h; see man 3 queue. It's not standard, though.

Personally, I usually use Glib if I'm working in C and need standard data structures. (http://developer.gnome.org/glib)

No, you really can't.

C++ comes with certain headers that map to some of the C ones (both as XYZ.h and cXYZ) and it can use and link to C code that's been properly marked (see extern "C").

But you can't go the other way. C++ headers will have all sorts of wonderful C++ things in them that will not be understood by your C compiler (and, if they are understood, then they're really C headers).

If you want to implement a linked list, there are literally thousands of samples available on the web for pure C.

Or here's a very simple one to start with (no error checks on malloc, simple FIFO queue):

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

typedef struct sNode {
    int payload;
    struct sNode *next;
} tNode;

void listAppend (tNode **pFirst, tNode **pLast, int val) {
    tNode *node;

    node = malloc (sizeof (tNode));
    node->payload = val;
    node->next = NULL;

    printf ("Append %d: ", val);

    if (*pFirst == NULL) {
        *pFirst = node;
        *pLast = node;
        return;
    }

    (*pLast)->next = node;
    *pLast = node;
}

int listRemove (tNode **pFirst, tNode **pLast) {
    int val;
    tNode *node;

    if (*pFirst == NULL)
        return -999;

    node = *pFirst;
    *pFirst = (*pFirst)->next;
    if (*pFirst == NULL)
        *pLast = NULL;

    val = node->payload;
    printf ("Remove %d: ", val);

    free (node);
    return val;
}

void dump (tNode* n) {
    printf ("list = [");
    while (n != NULL) {
        printf (" %d", n->payload);
        n = n->next;
    }
    printf (" ]\n");
}

int main (int argc, char *argv[]) {
    int val;
    tNode *first = NULL;
    tNode *last = NULL;
    while (argv[1] != NULL) {
        if (*argv[1] == '-')
            val = listRemove (&first, &last);
        else
            listAppend (&first, &last, atoi (argv[1]));
        dump (first);
        argv++;
    }
    return 0;
}

When run with:

pax$ ./testprog 10 20 30 15 25 - - - - - -

the output is:

Append 10: list = [ 10 ]
Append 20: list = [ 10 20 ]
Append 30: list = [ 10 20 30 ]
Append 15: list = [ 10 20 30 15 ]
Append 25: list = [ 10 20 30 15 25 ]
Remove 10: list = [ 20 30 15 25 ]
Remove 20: list = [ 30 15 25 ]
Remove 30: list = [ 15 25 ]
Remove 15: list = [ 25 ]
Remove 25: list = [ ]
list = [ ]

One can include a C++ header file, and it will work as long as the contents of such file is written in the subset that is supported by both C and C++ (that is most but not all of C). If you are thinking about C++ std::list then you are out of luck, it won't work from C.

You will have to create a linked list yourself. A forward list should be enough for your use case (as opposed to a double-linked list). You can embedd the next pointers within the same block that you are allocating, making it an intrusive list.

Update:

Here is in pseudo-code how you handle a malloc( N )

struct bookkeeping {
    std::size_t size;
    void* next;
};

void* malloc( std::size_t N )
{
    unsigned char* ptr = ...get ahold of a memory block of size N + sizeof( bookkeeping )...

    bookkeeping* info = ptr;
    info->size = N;
    ...fill the bookkeeping information...

    return ptr + sizeof(bookkeeping);
}

void free( void* ptr )
{
    bookkeeping* info = (unsigned char*)ptr - sizeof( bookkeeping );

    ...free the block pointed to by `info`...
}

Remember to account for alignment as well.

You can't include a C++ header from a C file. But you can make use of C++ code from C.

mymodule.c wants to include C++ utility.h, but it can't.

You write C_utility.h and C_utility.cpp. C_utility.h uses only C language features. It declares some functions and usually some opaque types that are presented to C basically as void pointers. (There are some better techniques that will let the C compiler at least check that the type matches, but not give it any information about the type.) The opaque types are actually pointers to C++ objects, but C doesn't know that. You get the pointers out of the functions declared in the header, and you send them back in.

C_utility.cpp includes utility.h. C_utility.cpp contains C++ code. You can define classes. Only the function signatures from C_utility,h are limited to be C syntax. The function bodies can construct C++ classes and stuff.

mymodule.c includes C_utility.h.

You compile C_utility.cpp with the C++ compiler and mymodule.c with the C compiler. Both compilers produce .o files, and the linker is able to combine both kinds of .o file together.

For your purpose, you can make a C_linkedlist.h and C_linkedlist.cpp that expose a C interface for a linked list. Then you can make malloc.c that includes C_linkedlist.h. Or you can make C_malloc.h and C_malloc.cpp, with C_malloc.h only containing C syntax but C_malloc.cpp freely using C++.

By the way, I don't think using the C++ linked list for malloc is a great idea. malloc can impact performance. It should really be tuned for really fast speed. C++ is pretty fast but adds a little bit of overhead because it does a few things for "niceness" that you might not need in a particular case.

There is no standard header file in C which provides linked list implementation.

The standard way to implement linked lists (atleast the way i've learnt), is 1. declare a structure,

struct node{
    <datatype> data;
    struct node *next;
    struct node *prev; //if you want a doubly linked list
}

1. Have a start/head pointer to point to the first element in the node.

2. dynamically allocate the memory as required. For the first node created, the start/head pointer should point to it. Thereafter the next pointer of the last block(node) points to the newly created node.

You can take a look at this or this for further info.