How can I do this?

I want to create a linked list data-structure in C, but I do not want to have to malloc any memory. Is it possible to do this in a way that makes it simple to traverse and add to the list?

Regards,

Simon Peyote Joints

yeah, use java.

>>2
Java doesn't support Nomads.

Why would I want to change the infix function to prefix or the other way around? What is the difference between (*) 2 3 and 2 * 3?

>>3

import java.lang.Nomads.IO;

>>1-5
Same person and we have been trolled at the speed of Simon Peyote Joints' quicksort implementation compilerd with the Glasgow Haskell Compiler

>>5
import IO hiding IO

Actually, it's quite simple. Let's say you have your initial linked list statically declared in your source file. When you add an element to the list, your program will just have to edit it's own source file to add the new element, then call gcc and execlp the new executable (don't forget <unistd.h> !).

>>8
Holly shit!

#include <stdio.h>

struct node {
     int item;
     struct node *next;
};

void print_list(struct node *l) {
     while (l) {
          printf("%d\n", l->item);
          l = l->next;
     }
}

void create_list(int i, struct node *prev) {
     struct node n;
     n.item = i;
     n.next = prev;
     if (i > 1) {
          create_list(i - 1, &n);
     } else {
          print_list(&n);
     }
}

int main() {
     int i;
     printf("How many items do you want? ");
     scanf("%d", &i);
     create_list(i, NULL);
     return 0;
}

lol, I just finished writing some data structures in C. Here, have some -

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

static void vector_realloc( Vector* v ) {
    v->data = realloc( v->data, v->capacity * sizeof( void* ) );
}

Vector vector_alloc() {
    Vector ret;
    ret.size = 0;
    ret.capacity = 4;
    ret.data = 0;
    vector_realloc( &ret );
    return ret;
}

Vector vector_copy( Vector* v ) {
    Vector ret;
    ret.size = v->size;
    ret.capacity = v->capacity;
    ret.data = 0;
    vector_realloc( &ret );
    memcpy( ret.data, v->data, v->capacity * sizeof( void* ) );
    return ret;
}

void vector_free( Vector* v ) {
    free( v->data );
    v->data = 0;
}

void vector_push_front( Vector* v, void* d ) {
    int i;

    if ( v->size == v->capacity ) {
        v->capacity *= 2;
        vector_realloc( v );
    }

    for ( i = (int) v->size; i >= 0; --i )
        v->data[i+1] = v->data[i];

    v->data[0] = d;
    v->size++;
}

void vector_push_back( Vector* v, void* d ) {
    if ( v->size == v->capacity ) {
        v->capacity *= 2;
        vector_realloc( v );
    }

    v->data[ v->size++ ] = d;
}

void* vector_pop_front( Vector* v ) {
    void* ret = v->data[0];
    size_t i;

    for ( i = 0; i < v->size; ++i )
        v->data[i] = v->data[i+1];

    v->size--;
    return ret;
}

void* vector_pop_back( Vector* v ) {
    return v->data[ --v->size ];
}

void vector_clear( Vector* v ) {
    v->size = 0;
}

size_t vector_size( Vector* v ) {
    return v->size;
}

void vector_reserve( Vector* v, size_t s ) {
    if ( v->capacity < s ) {
        v->capacity = 0;
        vector_realloc( v );
    }
}

bool vector_empty( Vector* v ) {
    return v->size == 0;
}

void* vector_front( Vector* v ) {
    return v->data[0];
}

void* vector_back( Vector* v ) {
    return v->data[ v->size - 1 ];
}

void* vector_index( Vector* v, size_t s ) {
    return v->data[ s ];
}

#include "HashMap.h"

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

enum EntryState {
    ES_EMPTY = 0,
    ES_SINGLE,
    ES_BUCKET
};

static size_t hash_sdbm( const char *s ) {
    size_t hash = 0, c;
    unsigned char *us = (unsigned char*) s;

    while ( c = *us++ )
        hash = c + ( hash << 6 ) + ( hash << 16 ) - hash;

    return hash;
}

HashMap hashmap_alloc() {
    return hashmap_alloc_size( 1024 );
}

HashMap hashmap_alloc_size( size_t s ) {
    HashMap ret;
    ret.size = s;
    ret.data = calloc( s, sizeof( HashMapEntry ) );
    return ret;
}

HashMap hashmap_copy( HashMap* h ) {
    HashMap ret;
    size_t i, j;

    ret.size = h->size;
    ret.data = malloc( h->size * sizeof( HashMapEntry ) );

    for ( i = 0; i < h->size; ++i ) {
        HashMapEntry *he = &h->data[i], *re = &ret.data[i];
        re->state = he->state;

        if ( he->state == ES_SINGLE ) {
            re->entry.value = he->entry.value;
            re->entry.key = malloc( strlen( he->entry.key ) + 1 );
            strcpy( re->entry.key, he->entry.key );
        }
        else if ( he->state == ES_BUCKET ) {
            re->bucket = vector_alloc();
            for ( j = 0; j < vector_size( &he->bucket ); ++j ) {
                KeyValuePair *kvp = vector_index( &he->bucket, j );
                KeyValuePair *nkvp = malloc( sizeof( KeyValuePair ) );
                nkvp->key = malloc( strlen( kvp->key ) + 1 );
                strcpy( nkvp->key, kvp->key );
                nkvp->value = kvp->value;
                vector_push_back( &re->bucket, nkvp );
            }
        }
    }

    return ret;
}

void hashmap_free( HashMap* h ) {
    size_t i, j;

    for ( i = 0; i < h->size; ++i ) {
        HashMapEntry *he = &h->data[i];

        if ( he->state == ES_SINGLE ) {
            free( he->entry.key );
        }
        else if ( he->state == ES_BUCKET ) {
            for ( j = 0; i < vector_size( &he->bucket ); ++j ) {
                KeyValuePair *kvp = vector_index( &he->bucket, j );
                free( kvp->key );
                free( kvp );
            }
            vector_free( &he->bucket );
        }
    }

    /* free the data */
    free( h->data );
}

bool hashmap_haskey( HashMap* h, const char* k ) {
    return hashmap_get( h, k ) != 0;
}

static HashMapEntry* hashmap_getentry( HashMap* h, const char* k ) {
    size_t index = hash_sdbm( k ) % h->size;
    return &h->data[ index ];
}

void* hashmap_get( HashMap* h, const char* k ) {
    HashMapEntry *e = hashmap_getentry( h, k );   
    size_t i;

    if ( e->state == ES_SINGLE ) {
        if ( !strcmp( e->entry.key, k ) )
            return e->entry.value;
        return 0;
    }
    else if ( e->state == ES_BUCKET ) {
        Vector *v = &e->bucket;
        for ( i = 0; i < v->size; ++i ) {
            KeyValuePair *kvp = vector_index( v, i );
            if ( !strcmp( kvp->key, k ) )
                return kvp->value;
        }
        return 0;
    }

    return 0;
}

void hashmap_insert( HashMap* h, const char* k, void* v ) {
    HashMapEntry *e = hashmap_getentry( h, k );

    if ( e->state == ES_EMPTY ) {
        e->state = ES_SINGLE;
        e->entry.key = malloc( strlen( k ) + 1 );
        strcpy( e->entry.key, k );
        e->entry.value = v;
    }
    else if ( e->state == ES_SINGLE ) {
        KeyValuePair kvp = e->entry;
        KeyValuePair *pkvp;

        e->state = ES_BUCKET;
        e->bucket = vector_alloc();

        pkvp = malloc( sizeof( KeyValuePair ) );
        pkvp->key = kvp.key;
        pkvp->value = kvp.value;
        vector_push_back( &e->bucket, pkvp );
    }

    if ( e->state == ES_BUCKET ) {
        KeyValuePair *pkvp;
        pkvp = malloc( sizeof( KeyValuePair ) );
        pkvp->key = malloc( strlen( k ) + 1 );
        strcpy( pkvp->key, k );
        pkvp->value = v;
        vector_push_back( &e->bucket, pkvp );
    }
}

void hashmap_remove( HashMap* h, const char* k ) {
    HashMapEntry *e = hashmap_getentry( h, k );
    size_t i;

    if ( e->state == ES_SINGLE ) {
        free( e->entry.key );
        e->state = ES_EMPTY;
    }
    else if ( e->state == ES_BUCKET ) {
        Vector cv = vector_copy( &e->bucket );
        vector_clear( &e->bucket );

        for ( i = 0; i < vector_size( &cv ); ++i ) {
            KeyValuePair *kvp = vector_index( &cv, i );
           
            if ( !strcmp( kvp->key, k ) ) {
                free( kvp->key );
                free( kvp );
            }
            else {
                vector_push_back( &e->bucket, kvp );
            }
        }

        vector_free( &cv );

        if ( vector_empty( &e->bucket ) ) {
            vector_free( &e->bucket );
            e->state = ES_EMPTY;
        }
    }
}

I just finished doing sponge testing on both of these, and they don't leak any memory. Only tested the insert/remove and push_back/pop_front functions, though those arguably are the most important ones.

lol.

>>12
Actually, there's a bug in hashmap_free -

            for ( j = 0; [b]i[/b] < vector_size( &he->bucket ); ++j ) {

Should be a "j".

I couldn't help but notice you pre-incremented your variable in the for-loop. EXPERT PROGRAMMER

BTW, Please for the love of god don't use capitals in your C code. It makes you look like a Seppler.

And by capitals, I mean CamelCase.

>>16-17
It's a bad habit I've picked up from being a Seppler in the past. I'm trying to shake off the bits and pieces of bad habits; even caught myself typing delete a couple of times, and once wishing for some kind of RAII. And some namespaces.

Then I remembered all that bullshit was just excess bloat.

>>18
<3

The objects contains given.

Newer Posts

---

Don't change these.

Name:		Email:
Entire Thread Thread List