c语言开发之广义巨型数组

作者在某软件项目中，需要用到巨型数组，用来存储超过上千万乃至上亿的指针，因为只需要根据索引下标进行访问，利用数组可以连续存放数据，大大节省内存，通过下标可以访问到数据。但是传统意义上的数组，受限于栈(stack)空间和堆(stack)空间的限制无法满足业务需求。所以作者设计广义上的数组概念，用来支持超大巨型数组。

传统数组(静态数组)

C语言数组定义如下:

1、数组是相同数据类型的元素的集合。

2、数组中的各元素的存储按先后顺序连续存放。

3、数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如：a[0]表示

名字为a的数组中的第一个元素，a[1]代表数组a的第二个元素，以此类推。

示例如下：

    int a[5];
    a[0] = 10;
	a[1] = 11;
	a[2] = 12;
	a[3] = 13;
    a[4] = 14;

    int i;
    for(i = 0; i < 4, i++)
    {
	    printf(“%d\r\n”, i);
    }

静态数组的限制：

静态数组占用程序的栈空间，windows的栈缺省是2M字节，程序的使用的栈超过这

个值，就会异常，所以静态数组的大小是受限制的。

2、c语言声明数组时，数组的元素数量是固定的。

因为上述的2个限制，才会有下面动态数组的概念。

动态数组

动态数组就是在通过mallo函数或new操作符在堆空间中分配指定大小的内存空间，用来连续存储指定数据类型的数据，动态数组也是可以通过下标来访问数组元素。

c示例如下：

    int* a;
	a = (int *)malloc(5*sizeof(int));

    a[0] = 10;
	a[1] = 11;
	a[2] = 12;
	a[3] = 13;
    a[4] = 14;

    int i;
    for(i = 0; i < 4, i++)
    {
	    printf(“%d\r\n”, i);
    }

    free(a);

c++示例如下：

    int* a;
	a = new int[5];

    a[0] = 10;
	a[1] = 11;
	a[2] = 12;
	a[3] = 13;
    a[4] = 14;

    int i;
    for(i = 0; i < 4, i++)
    {
	    printf(“%d\r\n”, i);
    }

    delete[] a;

该机制相对静态数组优点是：

1、数组元素数量可以是变量。

2、数组占用的连续空间可以很大，可以远大于栈空间。

但是具体到特殊应用场景，动态数组还是受限。动态数组是从程序的堆空间分配连续内存，

如果需要数组元素数量很大，就需要分配很大连续空间，再如果程序需要频繁的生成和释放大型动态数组，对内存管理势必造成很大压力，对程序的稳定性造成威胁。据此作者提出并推荐试用广义巨型数组。

广义巨型数组

之所以成为广义，是因为不是通过[下标]方位，而是通过广义巨型数组提供的函数和下

标访问，还之所以称为数组，是因为广义巨型数组是多级分段连续存储，每段连续存储

有限数量的元素，例如：256问广义巨型数组也是通过下标，访问速度也很快。

技术特点

1、可以存储超大数量数组元素，可以存储上千万、上亿、上十亿的数量。作者提供的

源码理论上支持0xFFFFFFFFFFFFFF数量的元素。

2、采用多级分段存储，每段存储256元素，每段占用的空间都不大，一般占用

从1K 、2K、4K 、8K等。

3、访问速度会比静态和动态数组要慢点，但是具体到特殊的应用场景还是可以接受的。

1. 应用场景

1、数组元素数量超大，上千万、亿、十亿、百亿级别。

源码文件

HugeArray.h

#ifndef HUGEARRAY_H
#define HUGEARRAY_H

typedef void* HANDLE;

class CHugeArrayU;

class CTinyArrayU
{
public:
	unsigned char m_nLevel;
	unsigned short m_nArraySize;
	CHugeArrayU* m_pHugeArray;
	void* m_pData;
public:
	CTinyArrayU();
	~CTinyArrayU();
	void Constructor();
	void Destructor();
public:
	int Init(CHugeArrayU* pHugeArray, int nLevel, int nArraySize);
	int Destroy();
public:	
	void* GetAddr(size_t nIndex);
};

class CHugeArrayU
{
public:	
	size_t m_nArraySize;		// 数组元素数量
	int m_nLevel;			// 通过计算数组的最大级数
	int m_nUnitSize;		// 数组每个元素的字节大小
	CTinyArrayU m_pRoot;		// 根节点
public:
	CHugeArrayU();
	~CHugeArrayU();
	void Constructor();
	void Destructor();
public:
	int Init(size_t nArraySize, size_t nUnitSize);
	int Destroy();
public:	
	void* GetAddr(size_t nIndex);
};

HANDLE CreateHugeArray(size_t nArraySize, size_t nUnitSize, size_t nHeapSize);
void DeleteHugeArray(HANDLE hArray);
void* HAGetAddrByIndex(HANDLE hArray, size_t nIndex);

#endif

HugeArray.cpp

#include "HugeArray.h"

CTinyArrayU :: CTinyArrayU()
{
	Constructor();
}

CTinyArrayU :: ~CTinyArrayU()
{
	Destructor();
}

void CTinyArrayU :: Constructor()
{
	m_pData = NULL;
}
	
void CTinyArrayU :: Destructor()
{	
	Destroy();
}

int CTinyArrayU :: Init(CHugeArrayU* pHugeArray, int nLevel, int nArraySize)
{	
	m_pHugeArray = pHugeArray;
	m_nLevel = nLevel;

	m_nArraySize = nArraySize;

	if(m_nLevel == m_pHugeArray->m_nLevel)
	{					
		m_pData = (char *) malloc(m_nArraySize*m_pHugeArray->m_nUnitSize);
	}
	else
	{		
		m_pData = (CTinyArrayU *) malloc(m_nArraySize*sizeof(CTinyArrayU));
		
		int i;
		for (i = 0; i < m_nArraySize; i++)
		{
			((CTinyArrayU *)m_pData)[i].Constructor();
			((CTinyArrayU *)m_pData)[i].Init(m_pHugeArray, m_nLevel + 1, 0x100);
		}	
	}

	return 0;
}

int CTinyArrayU :: Destroy()
{
	if(m_pData != NULL)
	{
		if(m_nLevel != m_pHugeArray->m_nLevel)
		{
			int i;
			for (i = 0; i < m_nArraySize; i++)
			{
				((CTinyArrayU *)m_pData)[i].Destroy();
			}	
		}
		
		free(m_pData);
		m_pData = NULL;
	}
	return 0;
}

void* CTinyArrayU :: GetAddr(size_t nIndex)
{	
	int nByte;
	nByte = m_pHugeArray->m_nLevel - m_nLevel;

	unsigned char nID;
	nID = ((unsigned char *)(&nIndex))[nByte];

	if(m_nLevel == m_pHugeArray->m_nLevel)
	{
		return (char *)m_pData + nID*(m_pHugeArray->m_nUnitSize);
	}

	CTinyArrayU* pNext;
	pNext = &(((CTinyArrayU *)m_pData)[nID]);
	return pNext->GetAddr(nIndex);
}

CHugeArrayU :: CHugeArrayU()
{
	Constructor();
}

CHugeArrayU :: ~CHugeArrayU()
{
	Destructor();
}

void CHugeArrayU :: Constructor()
{
	m_pRoot.Constructor();
}	

void CHugeArrayU :: Destructor()
{
	Destroy();
}

int CHugeArrayU :: Init(size_t nArraySize, size_t nUnitSize)
{	
	size_t nInitCount;

#ifdef OS_32_BIT
	//if(sizeof(size_t) == 4)
	//{	// 32 位操作系统
		if(nArraySize <= 0xFF)
		{
			m_nLevel = 1;
			nInitCount = nArraySize;
		}
		else if(nArraySize <= 0xFFFF)
		{
			m_nLevel = 2;
			nInitCount = nArraySize/0x100;
			if(nArraySize%0x100 > 0)
			{
				nInitCount++;
			}
		}
		else if(nArraySize <= 0xFFFFFF)
		{
			m_nLevel = 3;
			nInitCount = nArraySize/0x10000;
			if(nArraySize%0x10000 > 0)
			{
				nInitCount++;
			}
		}
		else
		{
			m_nLevel = 4;
			nInitCount = nArraySize/0x1000000;
			if(nArraySize%0x1000000 > 0)
			{
				nInitCount++;
			}
		}	
	//}
#endif
#ifdef OS_64_BIT
	//else
	//{	// 64位操作系统
		if(nArraySize <= 0xFF)
		{
			m_nLevel = 1;
			nInitCount = nArraySize;
		}
		else if(nArraySize <= 0xFFFF)
		{
			m_nLevel = 2;
			nInitCount = nArraySize/0x100;
			if(nArraySize%0x100 > 0)
			{
				nInitCount++;
			}
		}
		else if(nArraySize <= 0xFFFFFF)
		{
			m_nLevel = 3;
			nInitCount = nArraySize/0x10000;
			if(nArraySize%0x10000 > 0)
			{
				nInitCount++;
			}
		}
		else if(nArraySize <= 0xFFFFFFFF)
		{
			m_nLevel = 4;
			nInitCount = nArraySize/0x100000000;
			if(nArraySize%0x100000000 > 0)
			{
				nInitCount++;
			}
		}	
		else if(nArraySize <= 0xFFFFFFFFFF)
		{
			m_nLevel = 5;
			nInitCount = nArraySize/0x10000000000;
			if(nArraySize%0x10000000000 > 0)
			{
				nInitCount++;
			}
		}
		else if(nArraySize <= 0xFFFFFFFFFFFF)
		{
			m_nLevel = 6;
			nInitCount = nArraySize/0x1000000000000;
			if(nArraySize%0x1000000000000 > 0)
			{
				nInitCount++;
			}
		}
		else if(nArraySize <= 0xFFFFFFFFFFFFFF)
		{
			m_nLevel = 7;
			nInitCount = nArraySize/0x100000000000000;
			if(nArraySize%0x100000000000000 > 0)
			{
				nInitCount++;
			}
		}
		else
		{
			//m_nLevel = 8;
			//nInitCount = nArraySize/0x100000000000000;
			//nInitCount = 

			//if(nArraySize%0x100000000000000 > 0)
			//{
			//	nInitCount++;
			//}
		}
	//}
#endif
	m_nArraySize = nArraySize;
	m_nUnitSize = nUnitSize;

	m_pRoot.Init(this, 1, nInitCount);

	return 0;
}

int CHugeArrayU :: Destroy()
{
	m_pRoot.Destroy();
	return 0;
}

void* CHugeArrayU :: GetAddr(size_t nIndex)
{
	return m_pRoot.GetAddr(nIndex);
}

HANDLE CreateHugeArray(size_t nArraySize, size_t nUnitSize, size_t nHeapSize)
{
	CHugeArray* pHugeArray;
	pHugeArray = (CHugeArray *)MMAlloc(sizeof(CHugeArray));
	pHugeArray->Constructor();
	pHugeArray->Init(nArraySize, nUnitSize, nHeapSize);
	return pHugeArray;
}

void DeleteHugeArray(HANDLE hArray)
{
	((CHugeArray *)hArray)->Destructor();
	MMFree(hArray, 0);
}

void* HAGetAddrByIndex(HANDLE hArray, size_t nIndex)
{
	return ((CHugeArray *)hArray)->GetAddr(nIndex);
}

1、功能说明

此函数用来生成一个巨型数组的数据结构，执行成功后返回一个句柄，之后对巨型数组的操作都引用此句柄。

2、函数原型

HANDLE CreateHugeArray(size_t nArraySize, size_t nUnitSize);

3、参数说明

size_t nArraySize

输入参数。数组的最大元素数量, nArraySize必须大于0。

size_t nUnitSize

输入参数。单个数组元素的大小，单位字节, nUnitSize必须大于0。

4、返回值

执行成功返回非NULL的句柄，执行失败时返回NULL。

5、相关函数

DeleteHugeArray(HANDLE hArray)

示例：

#include “HugeArray.h"

int main(int argc, char* argv[])
{
    HANDLE hArray;
    hArray = CreateHugeArray(1024, sizeof(int));
    if(hArray == NULL)
    {	
	    return 0;
    }
    DeleteHugeArray(hArray);
	return 0;
}

DeleteHugeArray()

1、功能说明

此函数用来释放指定的HugeArray数据结构以及占用的内存。

2、函数原型

void DeleteHugeArray(HANDLE hArray);

3、参数说明

1）HANDLE hArray

输入参数，hArray是执行CreateHugeArray函数返回的句柄。

4、返回值

无。

5、相关函数

CreateHugeArray()

#include “HugeArray.h"

int main(int argc, char* argv[])
{
    HANDLE hArray;
    hArray = CreateHugeArray(1024, sizeof(int), 8*1024);
    if(hArray == NULL)
    {
	    Return 0;
    }

    DeleteHugeArray (hArray);
    return 0;
}

HAGetAddrByIndex()

1、功能说明

此函数用来根据数组索引下标获指定取数组元素地址。

2、函数原型

Void* HAGetAddrByIndex(HANDLE hArray, size_t nIndex);

3、参数说明

1）HANDLE hArray

输入参数，hArray是执行CreateHugeArray函数返回的句柄。

2）size_t nIndex

输入参数，数组下标，从0开始。

4、返回值

地址指针

5、相关函数

示例：


#include "HugeArray.h"

typedef struct _PERSONINFO
{
	char sCardID[19];
    int nSex;
	char sName[32];
	int nAge;
	char sAddress[128];
	char sEmail[128];
}PERSONINFO;
typedef PERSONINFO* LPPERSONINFO;

int main(int argc, char* argv[])
{
	HANDLE pArray;
	pArray = CreateHugeArray(0xFFFFF, sizeof(PERSONINFO));

	int i;
	for (i = 0; i < 0xFFFFF; i++)
	{
		LPPERSONINFO pInfo;
		pInfo = (LPPERSONINFO)HAGetAddrByIndex(pArray, i);
		sprintf(pInfo->sCardID, "CardID: %d", i);
		pInfo->nSex = i;
		sprintf(pInfo->sName, "Name: %d", i);
		pInfo->nAge = i;
		sprintf(pInfo->sAddress, "Address: %d", i);
		sprintf(pInfo->sEmail, "Email: %d", i);
	}

	for (i = 0; i < 0xFFFFF; i++)
	{			
		LPPERSONINFO pInfo;
		pInfo = (LPPERSONINFO)HAGetAddrByIndex(pArray, i);
	
		printf("%s\r\n", pInfo->sCardID);	
		printf("%d\r\n", pInfo->nSex);	
		printf("%s\r\n", pInfo->sName);
		printf("%d\r\n", pInfo->nAge);
		printf("%s\r\n", pInfo->sAddress);
		printf("%s\r\n", pInfo->sEmail);		
	}
	
	DeleteHugeArray(pArray);

	return 0;
}

相关标签：开源计划 c++ 数组源码数据结构

上一篇： NPM包发布流程

下一篇： Debian系统编译FreeSwitch找不到libavformat的问题

c语言开发之广义巨型数组

C语言开发之理解指针数组、数组指针、函数指针

程序开发之C++语言基础

C语言入门之C语言开发环境搭建

C语言数据结构之数组模拟实现顺序表流程详解

C语言学习之将一个数组中的值按逆序重新存放。例如,原来顺序为8,6,5,4,1. 要求改为1,4,5,6,8。

C语言基础学习之指针，数组和内存杂讲

c语言指针基础之指针和数组的关系

C语言学习之指针类型_空指针_二级指针_指针运算_指针与数组实例讲解

数据结构之---C语言实现图的数组（邻接矩阵）存储表示

C语言实验之数组逆序代码实例

c语言开发之广义巨型数组

C语言开发之理解指针数组、数组指针、函数指针

程序开发之C++语言基础

C语言入门之C语言开发环境搭建

C语言 数据结构之数组模拟实现顺序表流程详解

C语言学习之将一个数组中的值按逆序重新存放。例如,原来顺序为8,6,5,4,1. 要求改为1,4,5,6,8。

C语言基础学习之指针，数组和内存杂讲

c语言指针基础之指针和数组的关系

C语言学习之指针类型_空指针_二级指针_指针运算_指针与数组实例讲解

数据结构之---C语言实现图的数组（邻接矩阵）存储表示

C语言实验之数组逆序代码实例

C语言数据结构之数组模拟实现顺序表流程详解