From e12753d2ec9db83ec08bb9db63902a82fb245cdd Mon Sep 17 00:00:00 2001
From: "Tomas Chvatal (scarabeus)" <tomas.chvatal@gmail.com>
Date: Wed, 22 Oct 2008 22:50:54 +0200
Subject: X

---
 src/base/index.c~ | 289 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 289 insertions(+)
 create mode 100644 src/base/index.c~

(limited to 'src/base/index.c~')

diff --git a/src/base/index.c~ b/src/base/index.c~
new file mode 100644
index 0000000..77b0eac
--- /dev/null
+++ b/src/base/index.c~
@@ -0,0 +1,289 @@
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include "main.h"
+#include "list.h"
+#include "index.h"
+
+#define DEBUG_INDEX
+
+static index_item_t* newIndexItem(int key, void *data)
+{
+	index_item_t *new;
+
+	new = malloc( sizeof(index_item_t) );
+	new->key = key;
+	new->data = data;
+
+	return new;
+}
+
+#ifdef DEBUG_INDEX
+static void printIndexItem(index_item_t *p)
+{
+	printf("key = %d data = %p\n", p->key, p->data);
+}
+
+static void printListIndexItem(list_t *list)
+{
+	int i;
+
+	printf("list :\n");
+	printf("------------------\n");
+
+	for( i = 0 ; i < list->count ; i++ )
+	{
+		index_item_t *this;
+
+		this = (index_item_t *)list->list[i];
+		printIndexItem(this);
+	}
+}
+
+static void checkList(list_t *list)
+{
+	int i;
+	int prev;
+	int this;
+
+	//return;
+
+	if( list->count == 0 )
+	{
+		printf("nothing\n");
+		return;	
+	}
+
+	prev = ( (index_item_t *) list->list[0] )->key;
+
+	for( i = 1 ; i < list->count ; i++ )
+	{
+		this = ( (index_item_t *) list->list[i] )->key;
+
+		if( prev >= this )
+		{
+			printListIndexItem(list);
+			assert( ! "error" );
+		}
+
+		prev = this;
+	}
+}
+#endif
+
+static void destroyIndexItem(index_item_t *p)
+{
+	free(p);
+}
+
+list_t* newIndex()
+{
+	return newList();
+}
+
+void addToIndex(list_t *list, int key, void *data)
+{
+#ifdef DEBUG_INDEX
+	int count = 0;
+#endif
+
+	index_item_t *item;
+	index_item_t *this;
+	int min, max, point;
+	int len;
+
+	item = newIndexItem(key, data);
+	len = list->count;
+
+	min = 0;
+	max = len-1;
+
+	for(;;)
+	{
+		point = min + ( max - min ) / 2;
+
+#ifdef DEBUG_INDEX
+		if( ++count == len*5 )
+		{
+			printf("CICLIC ERROR\n");
+			printIndexItem(item);
+			printf("-------------------\n");
+			printListIndexItem(list);
+			assert( 0 );
+		}
+#endif
+
+		if( max < 0 )
+		{
+			insList(list, 0, item);
+#ifdef DEBUG_INDEX
+			checkList(list);
+#endif
+			return;
+		}
+
+		if( min >= len )
+		{
+			addList(list, item);
+#ifdef DEBUG_INDEX
+			checkList(list);
+#endif
+			return;
+		}
+		
+		this = (index_item_t *)list->list[point];
+
+/*
+		printf("min = %d max = %d point = %d len = %d offset = %d\n",
+			min, max, point, len, offset);
+
+*/
+		if( min > max )
+		{
+			insList(list, point, item);
+#ifdef DEBUG_INDEX
+			checkList(list);
+#endif
+			return;
+		}
+
+		if( item->key > this->key )
+		{
+			min = point + 1;
+			continue;
+		}
+
+		if( item->key < this->key )
+		{
+			max = point - 1;
+			continue;
+		}
+	}
+}
+
+static int getOffsetFromIndex(list_t *list, int key)
+{
+	index_item_t *this;
+	int min, max, point, len;
+
+	len = list->count;
+
+	if( len == 0 )
+	{
+		return -1;
+	}
+
+	min = 0;
+	max = len-1;
+
+	for(;;)
+	{
+		point = min + ( max - min ) / 2;
+
+		if(  max < 0 || point >= len || max < min )
+		{
+			return -1;
+		}
+		
+		this = (index_item_t *)list->list[point];
+/*
+		printf("min = %d max = %d point = %d len = %d offset = %d\n",
+			min, max, point, len, offset);
+*/
+		if( key == this->key )
+		{
+			return point;
+		}
+
+		if( key > this->key )
+		{
+			min = point + 1;
+			continue;
+		}
+
+		if( key < this->key )
+		{
+			max = point - 1;
+			continue;
+		}
+	}
+}
+
+void* getFromIndex(list_t *list, int key)
+{
+	int offset;
+
+	offset = getOffsetFromIndex(list, key);
+
+	if( offset != -1 )
+	{
+		index_item_t *this;
+
+		this = list->list[offset];
+		return this->data;
+	}
+
+	return NULL;
+}
+
+void delFromIndex(list_t *list, int key)
+{
+	int offset;
+
+	offset = getOffsetFromIndex(list, key);
+
+	if( offset != -1 )
+	{
+		delListItem(list, offset, destroyIndexItem);
+	}
+}
+
+void delFromIndexWithObject(list_t *list, int key, void *f)
+{
+	int offset;
+
+	offset = getOffsetFromIndex(list, key);
+
+	if( offset != -1 )
+	{
+		index_item_t *this;
+		void (*fce)(void *p);
+
+		this = list->list[offset];
+
+		fce = f;
+		fce(this);
+
+		delListItem(list, offset, destroyIndexItem);
+	}
+}
+
+void actionIndexWithObject(list_t *list, void *f)
+{
+	int i;
+
+	for( i = 0 ; i < list->count ; i++)
+	{
+		index_item_t *this;
+		void (*fce)(void *p);
+
+		this = list->list[i];
+
+		fce = f;
+		fce(this);
+	}
+}
+
+void destroyIndex(list_t *list)
+{
+	destroyListItem(list, destroyIndexItem);
+}
+
+void destroyIndexWithObject(list_t *list, void *f)
+{
+	actionIndexWithObject(list, f);
+	destroyListItem(list, destroyIndexItem);
+}
-- 
cgit v1.2.3