Untitled
unknown
c_cpp
10 months ago
3.8 kB
3
Indexable
#include <stdio.h> #include <stdlib.h> #include <string.h> // MurmurOAAT32 hash function unsigned int MurmurOAAT32(char *key) { unsigned int h = 3323198485u; for (; *key; ++key) { h ^= *key; h *= 0x5bd1e995; h ^= h >> 15; } return h; } // Function to convert unsigned int to string void unsigned_int_to_string(unsigned int num, char *str) { sprintf(str, "%u", num); } // Function to merge and hash two values in the binary tree unsigned int merge_and_hash(unsigned int a, unsigned int b) { unsigned int sum = a + b; char buffer[11]; // enough to hold a 32-bit unsigned int unsigned_int_to_string(sum, buffer); return MurmurOAAT32(buffer); } // Definition of tree node typedef struct Node { unsigned int data; struct Node *left; struct Node *right; } Node; // Function to create a new tree node Node* create_tree_node(unsigned int data) { Node *new_node = (Node *)malloc(sizeof(Node)); new_node->data = data; new_node->left = NULL; new_node->right = NULL; return new_node; } // Recursive function to build the Merkle tree and collect hash values Node* build_merkle_tree(unsigned int *hashes, int n) { if (n == 1) { return create_tree_node(hashes[0]); } int new_n = (n + 1) / 2; unsigned int *new_hashes = (unsigned int *)malloc(new_n * sizeof(unsigned int)); Node **nodes = (Node **)malloc(n * sizeof(Node*)); for (int i = 0; i < n; i++) { nodes[i] = create_tree_node(hashes[i]); } for (int i = 0; i < new_n; i++) { if (2 * i + 1 < n) { new_hashes[i] = merge_and_hash(hashes[2 * i], hashes[2 * i + 1]); Node *parent = create_tree_node(new_hashes[i]); parent->left = nodes[2 * i]; parent->right = nodes[2 * i + 1]; nodes[i] = parent; } else { char buffer[11]; unsigned_int_to_string(hashes[2 * i] * 2, buffer); new_hashes[i] = MurmurOAAT32(buffer); nodes[i] = create_tree_node(new_hashes[i]); nodes[i]->left = nodes[2 * i]; } } Node *root = build_merkle_tree(new_hashes, new_n); free(new_hashes); free(nodes); return root; } // Function to print the Merkle tree by level void print_merkle_tree(Node* root) { if (!root) return; Node** currentLevel = (Node**)malloc(sizeof(Node*)); currentLevel[0] = root; int count = 1; while (count > 0) { int nextCount = 0; Node** nextLevel = (Node**)malloc(2 * count * sizeof(Node*)); for (int i = 0; i < count; i++) { printf("%-15u", currentLevel[i]->data); if (currentLevel[i]->left) { nextLevel[nextCount++] = currentLevel[i]->left; } if (currentLevel[i]->right) { nextLevel[nextCount++] = currentLevel[i]->right; } } printf("\n"); free(currentLevel); currentLevel = nextLevel; count = nextCount; } free(currentLevel); } int main() { int n; scanf("%d", &n); char **strings = (char **)malloc(n * sizeof(char *)); unsigned int *hashes = (unsigned int *)malloc(n * sizeof(unsigned int)); for (int i = 0; i < n; i++) { strings[i] = (char *)malloc(101 * sizeof(char)); // 100 chars + null terminator scanf("%s", strings[i]); hashes[i] = MurmurOAAT32(strings[i]); } Node *root = build_merkle_tree(hashes, n); // Print the last layer (all leaves) for (int i = 0; i < n; i++) { printf("%-15u", hashes[i]); } printf("\n"); // Print the Merkle tree by level print_merkle_tree(root); for (int i = 0; i < n; i++) { free(strings[i]); } free(strings); free(hashes); return 0; }
Editor is loading...
Leave a Comment