hi there!

i just thought with all this asking about arrays i could post a "kind of"-solution. it's a completely working (well, at least it's ansi c, didn't try it with lite-c) linked list with adding and removal &c. &c. see for yourself.

Code:

---

struct llink {
	struct llink *prev, *next;
	void *p;
};
struct llist {
	struct llink *start;
};

llist* new_llist(void)
{
	llist* list = (llist*)malloc(sizeof(llist));
	if (list == NULL) {
		return (llist*)NULL;
	}
	list->start = NULL;
	return list;
}

llink* llist_add(llist *list, void *p)
{
	llink *link;
    if (list == NULL) {
		return (llink*)NULL;
	}

	link = (llink*)malloc(sizeof(llink));
	if (link == NULL) {
		return (llink*)NULL;
	}

	link->p = p;
	
	if (list->start == NULL) {
		list->start = link->next = link->prev = link;
	} else {
		// reassign left side
		link->prev = list->start->prev;
		list->start->prev->next = link;

		// reassign right side
		link->next = list->start;
		list->start->prev = link;
	}
	
	return link;
}

size_t llist_size(llist *list)
{
	size_t i = 1;
	llink *start, *current;
    if ( (list == NULL) || (list->start == NULL) ) {
		return 0;
	}

	current = start = list->start;
	while ( (current = current->next, current) != start ) {
		i ++;
	}

	return i;
}

llink* llist_get_link(llist *list, size_t offset)
{
	size_t c_offset;
	llink *current;
    if ( (list == NULL) || (list->start == NULL) ) {
		return NULL;
	}

	c_offset = offset%llist_size(list);
	current = list->start;
	for (c_offset; c_offset > 0; c_offset --) {
		current = current->next;
	}

	return current;
}

void* llist_get(llist *list, size_t offset)
{
	llink *current = llist_get_link(list, offset);
	return (current == NULL) ? NULL : current->p;
}

bool llist_delete(llist *list, size_t offset)
{
	llink *victim;
	if ( (victim = llist_get_link(list, offset)) == NULL ) {
		return false;
	}

	if (llist_size(list) == 1) {
		free(victim);
		list->start = NULL;
		return true;
	}

	if (offset == 0) {
		list->start = victim->next;
	}

	// reclose list
	victim->prev->next = victim->next;
	victim->next->prev = victim->prev;
	free(victim);
	return true;
}

signed long int llist_index_of(llist *list, void *p)
{
	size_t i = llist_size(list);
	llink *current;
	if (i == 0) { // implies list->start == NULL
		return -1;
	}

	current = list->start;
	for (i; i > 0; i --) {
		if (current->p == p) {
			return (signed long int)i;
		}
		current = current->next;
	}

	return -1;
}

---

if you want any function added, just tell me.

greetings, joey.

woohops, just noticed that there's a lite-c contributions thread-containing-thingy... well, could someone move the thread?

anyway, here's a usage example:

Code:

---

	llist *list = new_llist();
	char foo[] = "test", fuzz[] = "schnarch";
	int *arr = (int*)malloc(20000*sizeof(int));

	llist_add(list, &foo);
	llist_add(list, &fuzz);
	llist_add(list, &arr);

	size_t size = llist_size(list); // returns 3
	char *test = (char*)llist_get(list, 0); // returns "test"

	signed long int v = llist_index_of(list, &fuzz); // returns 1

	llist_delete(list, 0); // returns true
	size = llist_size(list); // returns 2

	int *test2 = (int*)llist_get(list, llist_index_of(list, &arr)); // returns the allocated memory

	free(list);

---

I suppose...a list here could store it's count internally as a member. It might modify or update its count as elements are added and deleted. Some overhead of counting elements through iteration might be reduced.
Actually, to be honest, I'd much rather view a C-Lite "map" or "hashtable" implementation, ...but this is nice.

well, yes, for big list it has definately some overhead.

i've written a map/hashtable, if someone is interested...

Although I have currently no need for it, I am interested in how it looks like. I have been wondering, could this be used in combination with a linked list to keep track of the datatypes in the list?

i'm using two lists of the above example, one for storing the key and the other for the value. the map type is defined as follows:



implementation of the functins new/add/remove/delete is like above.



note that it doesn't work for hardcoded values since it also works with pointers for the keys. the advantage is that you can simply add a hashmap to an entity, a panel or whatever else you can imagine.

joey.

Ah I see, somewhat like a two-dimensional array, but then with a linked list.
Well, for datatype recognition you would still require a list of all known types and userdefined structs can not be recognised anyway, of course. So nevermind that idea.

Thanx nonetheless !

I didn´t go through your code in detail but isn´t your hash map implementation very slow? I always thought that one of the main points of hash maps is very fast look-up of keys? They often use some kind of tree structure for that.

it's a very simple approach and not the fastest, but it's not that slow. the only bottleneck is the llist_index_of-function. furthermore it's not a hashmap but only a simple map. there are c-compatible hashmaps out there, and if you're willing to spend the time you could simply make a wrapper for the std::map or std::multimap classes.
i also just noted that i've changed the list functions' names a bit, but it should not be hard for you to alter them accordingly.

joey.