OSDev.org

Code: Select all

struct RBTreeNode_t *rbTreeGrandparent(struct RBTreeNode_t *node) {
	return node->parent->parent;
}

struct RBTreeNode_t *rbTreeUncle(struct RBTreeNode_t *node) {
	return (node->parent == rbTreeGrandparent(node)->left) ? rbTreeGrandparent(node)->right : rbTreeGrandparent(node)->left;
}

void rbTreeRotateLeft(struct RBTreeNode_t *node) {
	struct RBTreeNode_t *ptr1= node->right->left, *ptr2= node->right;
	
	if(likely(node->parent != 0)) {
		if(node->parent->left == node) {
			node->parent->left= ptr2;
		} else {
			node->parent->right= ptr2;
		}
	}
	ptr2->parent= node->parent;
	ptr2->left= node;
	node->right= ptr1;
	if(node->right != 0)
		node->right->parent= node;
	node->parent= ptr2;
	
	if(unlikely(node == kernelArgs.kernelSymTab)) {
		kernelArgs.kernelSymTab= ptr2;
	}
}

void rbTreeRotateRight(struct RBTreeNode_t *node) {
	struct RBTreeNode_t *ptr1= node->left->right, *ptr2= node->left;
	
	if(likely(node->parent != 0)) {
		if(node->parent->left == node) {
			node->parent->left= ptr2;
		} else {
			node->parent->right= ptr2;
		}
	}
	ptr2->parent= node->parent;
	ptr2->right= node;
	node->left= ptr1;
	if(node->left != 0)
		node->left->parent= node;
	node->parent= ptr2;
	
	if(unlikely(node == kernelArgs.kernelSymTab)) {
		kernelArgs.kernelSymTab= ptr2;
	}
}

void rbTreeInsertCheck(struct RBTreeNode_t *node) {
	if(unlikely(node->parent == 0)) {
		node->color= RBTREE_BLACK;
	} else {
		if(unlikely(node->parent->color == RBTREE_BLACK)) {
			return;
		} else {
			if(unlikely(rbTreeUncle(node) != 0 && rbTreeUncle(node)->color == RBTREE_RED)) {
				node->parent->color= RBTREE_RED;
				rbTreeUncle(node)->color= RBTREE_BLACK;
				rbTreeGrandparent(node)->color= RBTREE_RED;
				rbTreeInsertCheck(rbTreeGrandparent(node));
			} else {
				if(node == node->parent->right && node->parent == rbTreeGrandparent(node)->left) {
					rbTreeRotateLeft(node->parent);
					node= node->left;
				} else if (node == node->parent->left && node->parent == rbTreeGrandparent(node)->right) {
					rbTreeRotateRight(node->parent);
					node= node->right;
				}
				node->parent->color= RBTREE_BLACK;
				rbTreeGrandparent(node)->color= RBTREE_RED;
				if(node == node->parent->left && node->parent == rbTreeGrandparent(node)->left) {
					rbTreeRotateRight(rbTreeGrandparent(node));
				} else {
					rbTreeRotateLeft(rbTreeGrandparent(node));
				}
			}
		}
	}
}

void rbTreeInsert(struct RBTreeNode_t *startNode, struct RBTreeNode_t *insertNode) {
	uint32t res;
	
	if(unlikely(startNode == 0)) {
		insertNode->left= 0;
		insertNode->right= 0;
		insertNode->parent= 0;
		insertNode->color= RBTREE_BLACK;
		kernelArgs.kernelSymTab= insertNode;
	}
	
	if(unlikely(!(res= strcmp(startNode->str,insertNode->str))))
		return;
	if(res > 0) {
		if(likely(startNode->right != 0)) {
			rbTreeInsert(startNode->right,insertNode);
		} else {
			insertNode->left= 0;
			insertNode->right= 0;
			insertNode->parent= startNode;
			insertNode->color= RBTREE_RED;
			startNode->right= insertNode;
			rbTreeInsertCheck(insertNode);
		}
	} else {
		if(likely(startNode->left != 0)) {
			rbTreeInsert(startNode->left,insertNode);
		} else {
			insertNode->left= 0;
			insertNode->right= 0;
			insertNode->parent= startNode;
			insertNode->color= RBTREE_RED;
			startNode->left= insertNode;
			rbTreeInsertCheck(insertNode);
		}
	}
}

void rbTreeDebug(struct RBTreeNode_t *node) {
	if(likely(node != 0)) {
		rbTreeDebug(node->left);
		printf("str: %s, val: %#X, left: %#X, right: %#X\n",node->str,node->value,node->left,node->right);
		rbTreeDebug(node->right);
	}
}

Code: Select all

#define RBTREE_BLACK 0
#define RBTREE_RED !RBTREE_BLACK

#pragma pack(1)

struct RBTreeNode_t {
	struct RBTreeNode_t *left;
	struct RBTreeNode_t *right;
	uint32t color;
	uint32t value;
	char *str;
};

static struct RBTreeNode_t *rbTreeRotateLeft(struct RBTreeNode_t *node);
static struct RBTreeNode_t *rbTreeRotateRight(struct RBTreeNode_t *node);
static void rbTreeColorFlip(struct RBTreeNode_t *node);

struct RBTreeNode_t *rbTreeRotateLeft(struct RBTreeNode_t *node) {
	struct RBTreeNode_t *ptr= node->right;
	
	node->right= ptr->left;
	ptr->left= node;
	ptr->color= ptr->left->color;
	ptr->left->color= RBTREE_RED;
	
	return ptr;
}

struct RBTreeNode_t *rbTreeRotateRight(struct RBTreeNode_t *node) {
	struct RBTreeNode_t *ptr= node->left;
	
	node->left= ptr->right;
	ptr->right= node;
	ptr->color= ptr->right->color;
	ptr->right->color= RBTREE_RED;
	
	return ptr;
}

void rbTreeColorFlip(struct RBTreeNode_t *node) {
	node->color= !node->color;
	node->left->color= !node->left->color;
	node->right->color= !node->right->color;
}

struct RBTreeNode_t *rbTreeInsert(struct RBTreeNode_t *startNode, struct RBTreeNode_t *node) {
	uint32t res;
	
	if(unlikely(startNode == 0))
		return node;
	
	res= strcmp(startNode->str,node->str);
	
	if(res < 0)
		startNode->left= rbTreeInsert(startNode->left,node);
	else
		startNode->right= rbTreeInsert(startNode->right,node);
	
	if(startNode->right->color == RBTREE_RED)
		startNode= rbTreeRotateLeft(startNode);
	if((startNode->left->color == RBTREE_RED) && (startNode->left->left->color == RBTREE_RED))
		startNode= rbTreeRotateRight(startNode);
	if((startNode->left->color == RBTREE_RED) && (startNode->right->color == RBTREE_RED))
		rbTreeColorFlip(startNode);
	
	return startNode;
}

Code: Select all

struct
{
    uint32_t a;
    uint8_t b;
    uint32_t c;
    uint8_t d;
}

Code: Select all

struct
{
    uint32_t a;
    uint8_t b;
    uint8_t d;
    uint32_t c;
}

Code: Select all

struct
{
    uint32_t a; //Starts on a 32-bit boundary. For example 'bit 0'.
    uint8_t b; //Starts on an 8-bit boundary. Following the previous variable: 'bit 32'.  
    uint32_t c; //Wants to start at a 32-bit boundary, but is at bit '40' so it is padded with 24 bits so it is on 'bit 64' (next 32-bit boundary).
    uint8_t d; //Starts on an 8-bit boundary. Lies on 'Bit 96'.
}

Code: Select all

struct
{
    uint32_t a; //Starts on a 32-bit boundary. For example 'bit 0'.
    uint8_t b; //Starts on an 8-bit boundary. Following the previous variable: 'bit 32'.  
    uint8_t d; //Starts on an 8-bit boundary. Lies on 'Bit 40'.
    uint32_t c; //Wants to start at a 32-bit boundary, but is at bit '48' so it is padded with 16 bits so it is on 'bit 64' (next 32-bit boundary).  
}