sortedlist.c

基于beeo标准的数据加解密算法

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "beeo_define.h"	//for sl_malloc & sl_free

#include "sortedList.h"

#ifndef ASSERT
#define ASSERT(x)
#endif

typedef struct tagSortedListItem
{
	unsigned long	dwIndex1;
	unsigned long	dwIndex2;
	unsigned long	dwIndex3;
	unsigned long	dwIndex4;
	void*			pContent;
} SORTED_LIST_ITEM;

typedef struct tagSortedList
{
	long				dwCanBuffItems;
	long				dwBuffedItems;
	SORTED_LIST_ITEM**	itemList;
} SORTED_LIST;

//分配一个排序列表
//参数为两个函数指针，分别用于自动保存和释放子项内容，
//这两个指针可以都为0，这样，在增加子项的时候就不会分配内存保存子项内容，也不会在删除子项的时候释放内容
void* PASCAL slAllocList()
{
	SORTED_LIST * sl;

	sl = (SORTED_LIST*)sl_malloc(sizeof(SORTED_LIST));
	if(0==sl) return 0;

	memset(sl, 0, sizeof(SORTED_LIST));
	sl->itemList = (SORTED_LIST_ITEM**)sl_malloc((sl->dwCanBuffItems+32)*sizeof(SORTED_LIST_ITEM**));
	if(0==sl->itemList)
	{
		sl_free(sl);
		return 0;
	}
	memset(sl->itemList+sl->dwCanBuffItems, 0, 32*sizeof(SORTED_LIST_ITEM**));
	sl->dwCanBuffItems += 32;
#if 0
	{//test
		void* c;
		slInsertItem(sl, (void*)1, 1,2,3,0);
		slInsertItem(sl, (void*)2, 1,3,2,0);
		slInsertItem(sl, (void*)3, 2,1,3,0);
		slInsertItem(sl, (void*)4, 2,3,1,0);
		slInsertItem(sl, (void*)5, 3,1,2,0);
		slInsertItem(sl, (void*)6, 3,2,1,0);
		c = slFindContent(sl,1,2,3,0);
		c = slFindContent(sl,1,3,2,0);
		c = slFindContent(sl,2,1,3,0);
		c = slFindContent(sl,2,3,1,0);
		c = slFindContent(sl,3,1,2,0);
		c = slFindContent(sl,3,2,1,0);
	}
#endif
	return sl;
}

//删除一个排序列表，并且自动释放自动分配的内存
void PASCAL slReleaseList(void* p)
{
	SORTED_LIST* sl;
	SORTED_LIST_ITEM* item;

	sl=(SORTED_LIST*)p;
	if(!sl) return;

	if(sl->itemList)
	{
		while(sl->dwBuffedItems)
		{
			item = sl->itemList[sl->dwBuffedItems-1];
			sl_free(item);
			item --;
			sl->dwBuffedItems --;
		}
		sl_free(sl->itemList);
	}

	sl_free(sl);
}

#define Compare2DW(d1,d2,b)					\
	tmp = d1-d2;							\
	sum |= tmp;								\
	less += ((d1^d2^tmp)&0x80000000)>>b;	\
	tmp = d2-d1;							\
	large += ((d1^d2^tmp)&0x80000000)>>b;

//从大到小排列
static int PASCAL slFindIndexPos(long* pos, SORTED_LIST* sl, unsigned long dwIndex1, unsigned long dwIndex2, unsigned long dwIndex3, unsigned long dwIndex4)
{
	long dis,begin,end,cen;
	SORTED_LIST_ITEM* item;
	SORTED_LIST_ITEM** itemList=sl->itemList;
	unsigned long dwItems= sl->dwBuffedItems;
	unsigned long large, less, sum, tmp;

	begin = 0;
	end = dwItems-1;
	dis = dwItems;
	while(dis>1)
	{
		cen=(end+begin+1)>>1;
		item = itemList[cen];
		ASSERT(item);

		large=less=sum = 0;
		Compare2DW(item->dwIndex1,dwIndex1, 1);
		Compare2DW(item->dwIndex2,dwIndex2, 2);
		Compare2DW(item->dwIndex3,dwIndex3, 3);
		Compare2DW(item->dwIndex4,dwIndex4, 4);
		
		if(!sum)		{pos[0]=cen;return 0;}	//找到了
		if(large<less)	end = cen;
		else			begin = cen;
		dis = end-begin;
	}

	if(end<0) {pos[0]=0; return 1;}// No any items
	ASSERT(itemList[end]);
	item = itemList[end];
	{
		large=less=sum = 0;
		Compare2DW(item->dwIndex1,dwIndex1, 1);
		Compare2DW(item->dwIndex2,dwIndex2, 2);
		Compare2DW(item->dwIndex3,dwIndex3, 3);
		Compare2DW(item->dwIndex4,dwIndex4, 4);
		if(!sum)		{pos[0]=end;return 0;}	//找到了
		if(large>less)	{pos[0]=end;return 2;}	 //没有找到，增加的Item在end之后
	}

	ASSERT(itemList[begin]);
	item = itemList[begin];
	{
		large=less=sum = 0;
		Compare2DW(item->dwIndex1,dwIndex1, 1);
		Compare2DW(item->dwIndex2,dwIndex2, 2);
		Compare2DW(item->dwIndex3,dwIndex3, 3);
		Compare2DW(item->dwIndex4,dwIndex4, 4);
		if(!sum)		{pos[0]=begin;return 0;}	//找到了
		if(large>less)	{pos[0]=begin;return 2;}	 //没有找到，增加的Item在begin之后
		else 			{pos[0]=begin;return 1;}	 //没有找到，增加的Item在begin之前
	}
}

//在一个排序列表中添加一子项
int PASCAL slInsertItem(void* p, void* content, unsigned long dwIndex1, unsigned long dwIndex2, unsigned long dwIndex3, unsigned long dwIndex4)
{
	SORTED_LIST* sl;
	SORTED_LIST_ITEM* item;
	long pos=0x0;
	int ret;
	
	sl=(SORTED_LIST*)p;
	ASSERT(sl);
	ASSERT(content);
	
	if((sl->dwBuffedItems+1)>=sl->dwCanBuffItems)
	{
		p = sl_malloc((sl->dwCanBuffItems+32)*sizeof(SORTED_LIST_ITEM**));
		if(0==p) return 0;
		if(sl->itemList)
		{
			memcpy(p, sl->itemList, sl->dwBuffedItems*sizeof(SORTED_LIST_ITEM**));
			sl_free(sl->itemList);
		}
		sl->itemList = (SORTED_LIST_ITEM**)p;
		memset(sl->itemList+sl->dwCanBuffItems, 0, 32*sizeof(SORTED_LIST_ITEM**));
		sl->dwCanBuffItems += 32;
	}
	
	ret = slFindIndexPos(&pos, sl, dwIndex1, dwIndex2, dwIndex3, dwIndex4);
	if(!ret) return 0;//这个索引值已经存在，无法添加
	pos += ret-1;
	item = (SORTED_LIST_ITEM*)sl_malloc(sizeof(SORTED_LIST_ITEM));
	if(0==item) return 0;
	memmove(sl->itemList+pos+1, sl->itemList+pos, (sl->dwBuffedItems-pos)*sizeof(SORTED_LIST_ITEM**));
	
	item->dwIndex1 = dwIndex1;
	item->dwIndex2 = dwIndex2;
	item->dwIndex3 = dwIndex3;
	item->dwIndex4 = dwIndex4;
	item->pContent = content;
	sl->itemList[pos]=item;
	sl->dwBuffedItems++;
	
	return ret;
}

//删除索引号为dwIndex的子项
//如果bDeleteContent=0，将不会自动释放content的内存，并返回这个子项中的content
//如果bDeleteContent!=0，将自动释放content的内存，返回0
void* PASCAL slReleaseItem(void* p, unsigned long dwIndex1, unsigned long dwIndex2, unsigned long dwIndex3, unsigned long dwIndex4)
{
	SORTED_LIST* sl;
	SORTED_LIST_ITEM* item;
	long pos=0x0;
	void* content;

	sl=(SORTED_LIST*)p;
	ASSERT(sl);

	if(!sl->dwBuffedItems) return 0;
	if(slFindIndexPos(&pos, sl, dwIndex1, dwIndex2, dwIndex3, dwIndex4))
		return 0;

	item = sl->itemList[pos];
	ASSERT(item);

	content = item->pContent;
	sl_free(item);
	sl->dwBuffedItems --;
	if(pos<sl->dwBuffedItems)
		memcpy(sl->itemList+pos, sl->itemList+pos+1, (sl->dwBuffedItems-pos)*sizeof(SORTED_LIST_ITEM**));
	sl->itemList[sl->dwBuffedItems]=0;
	
	return content;
}

void* PASCAL slReleaseItembyPos(void* p, long pos)
{
	SORTED_LIST* sl;
	SORTED_LIST_ITEM* item;
	void* content;
	
	sl=(SORTED_LIST*)p;
	ASSERT(sl);
	
	item = sl->itemList[pos];
	if(!item) return 0;
	
	content = item->pContent;
	
	sl_free(item);
	sl->dwBuffedItems --;
	if(pos<sl->dwBuffedItems)
		memcpy(sl->itemList+pos, sl->itemList+pos+1, (sl->dwBuffedItems-pos)*sizeof(SORTED_LIST_ITEM**));
	sl->itemList[sl->dwBuffedItems]=0;
	
	return content;
}

void* PASCAL slFindContent(void* p, unsigned long dwIndex1, unsigned long dwIndex2, unsigned long dwIndex3, unsigned long dwIndex4)
{
	SORTED_LIST* sl;
	SORTED_LIST_ITEM* item;
	long pos=0x0;
	
	sl=(SORTED_LIST*)p;
	ASSERT(sl);
	
	if(slFindIndexPos(&pos, sl, dwIndex1, dwIndex2, dwIndex3, dwIndex4))
		return 0;
	
	item = sl->itemList[pos];
	ASSERT(item);

	return item->pContent;
}

long PASCAL slGetItemCount(void* p)
{
	SORTED_LIST* sl;
	
	sl=(SORTED_LIST*)p;
	ASSERT(sl);
	return sl->dwBuffedItems;
}

void* PASCAL slGetItem(void* p, long pos)
{
	SORTED_LIST* sl;
	SORTED_LIST_ITEM* item;

	sl=(SORTED_LIST*)p;
	ASSERT(sl);

	ASSERT(sl->itemList);
	if(sl->dwBuffedItems > pos)
	{
		item = sl->itemList[pos];
		return item->pContent;
	}
	return 0;
}

int PASCAL slAppendItemRandom(void* p, void* content)
{
	unsigned long dwIndex=0x80000000;
	SORTED_LIST* sl;
	SORTED_LIST_ITEM* item;
	
	sl=(SORTED_LIST*)p;
	ASSERT(sl);
	
	if(!sl->dwBuffedItems)
	{
		return slInsertItem(sl, content, dwIndex, 0, 0,0);
	}

	item=sl->itemList[sl->dwBuffedItems-1];
	ASSERT(item);
	if(item->dwIndex1)
	{
		dwIndex = item->dwIndex1-1;
		return slInsertItem(sl, content, dwIndex, 0, 0,0);
	}

	item=sl->itemList[0];
	ASSERT(item);
	dwIndex=item->dwIndex1+1;
	return slInsertItem(sl, content, dwIndex, 0, 0,0);
}

void PASCAL slModifyIndex(void* p, long pos, unsigned long dwIndex1, unsigned long dwIndex2, unsigned long dwIndex3, unsigned long dwIndex4)
{
	SORTED_LIST* sl;
	SORTED_LIST_ITEM* item;
	void * content;

	sl=(SORTED_LIST*)p;
	ASSERT(sl);
	ASSERT(pos<sl->dwBuffedItems);

	item = sl->itemList[pos];
	content = item->pContent;
	slReleaseItem(sl, item->dwIndex1, item->dwIndex2, item->dwIndex3, item->dwIndex4);
	slInsertItem(sl, content, dwIndex1, dwIndex2, dwIndex3, dwIndex4);
}