【C语言数据结构】对Lua Table源码的一次劣质学习-526互联

/* new_key */

KLcBool KLcmCreateMapKeyValue(KLCMAP_PTR pTag, KLCTVALUE_PTR pKv)
{
	KLcBool kbRet					= KL_FALSE;
	KLcBool kbIsKvLegal				= KL_FALSE;
	DWORD dwInsertPos				= 0;
	DWORD dwFreePos					= 0;
	DWORD dwCollisionPos			= 0;
	KLCTVALUE_PTR ptMainNode		= NULL;
	KLCTVALUE_PTR ptCollisionNode	= NULL;

	kbRet = KLcmGetIsLegalKv(pKv);
	KL_PROCESS_ERROR(kbRet && kbIsKvLegal);

	/* 获取 pkv 应该插入的位置，下述 '插入位置'. */
	kbRet = KLcmGetHashKeyPosition(pTag, pKv, &dwInsertPos);
	KL_PROCESS_ERROR(kbRet);
	/* 预期节点，主位置节点. */
	ptMainNode = pTag->parrNode[dwInsertPos];

	/* 判断插入位置是否被占用. */
	if (NULL != KLCMAP_CHECKNULL(ptMainNode))
	{
		/* 插入位置被占用. */
		/* 获取新的插入位置，下述 '新位置'，这个位置一定是空的. */
		kbRet = KLcmGetHashKeyFreePosition(pTag, &dwFreePos);
		KL_PROCESS_ERROR(kbRet);

		/* 判断是否还有 map 结构空间，有则继续，无则扩容. */
		if (KLCMAP_LACKOFSPACE != dwFreePos)
		{
			/* 还有空间，不需要扩容 Map 结构. */
			/* 获取被占用的预期节点的原属地位置. */
			kbRet = KLcmGetHashKeyPosition(pTag, ptMainNode, &dwCollisionPos);
			KL_PROCESS_ERROR(kbRet);
			/* 预期节点（原属地）. */
			ptCollisionNode = pTag->parrNode[dwCollisionPos];

			/* 判断冲突节点是否真正属于这个目前所占用的位置 */
			/* 即判断是否为主位置节点. */
			if (dwInsertPos != dwCollisionPos)
			{
				/* 冲突节点现在所占的这个位置不属于它，也是通过碰撞被临时放在这的. */
				/* 移动占据这里的kv结构，将占据这里的kv结构放在第一个空闲位置，需要存储的结构放在这. */
				while (KLCMAP_GETNEXT(ptCollisionNode) != ptMainNode)
				{
					/* 获取预期位置的上一个节点. */
					ptCollisionNode = KLCMAP_GETNEXT(ptCollisionNode);
				}
				/*
				* 1. 把这个冲突节点移动到新找的空位.
				* 2. 把 预期节点（冲突节点）前一个节点的指针重新指向新的位置.
				* 3. 把 pkv 插入到现在这个节点成为主位置节点.
				*/
				ptCollisionNode->uKey.pNext = pTag->parrNode[dwFreePos];
				*(pTag->parrNode[dwFreePos]) = *ptMainNode;
				ptMainNode->uKey.pNext = NULL;
				kbRet = KLcmSetNullKV(ptMainNode);
				KL_PROCESS_ERROR(kbRet);
			}
			else
			{
				/* 冲突节点现在所占的位置属于它，本次插入发生碰撞. */
				/* 把 pkv 插入到新节点里去，然后预期节点链接此. */
				KLCMAP_GETNEXT(pTag->parrNode[dwFreePos]) = KLCMAP_GETNEXT(ptMainNode);
				KLCMAP_GETNEXT(ptMainNode) = pTag->parrNode[dwFreePos];
				/* 这里只是交换了指针，方便下面的插入，不是交换指针内的数据. */
				ptMainNode = pTag->parrNode[dwFreePos];
			}
		}
		else
		{
			/* 需要开辟新空间. */
		}
	} 

	/* 上面的操作只是进行了数据结构内的位置交换，没有数据的插入逻辑. */
	/* 以下才是数据插入的逻辑. */
	ptMainNode->uKey.sVk.uValue = pKv->ktValue.uValue;
	ptMainNode->uKey.sVk.emType = pKv->ktValue.emType;

	kbRet = KL_TRUE;
Exit0:
	return kbRet;
}