双链表实现HBASE表（2）
#
在第一版<>的基础上，用双链表实现了HBASE单个表的基本算法。进行进一步扩展，实现rowkey的排序插入，实现rowkey的分片，实现分片和磁盘文件的关联。再用C语言编写一个nginx的负载均衡和控制元数据功能，利用socket通信实现多节点协作，多副本实现。封装访问接口。完全可以创建一个C语言版的分布式HBASE数据库。
代码如下：
/***************************************************** Linux下因为字符集原因，需要使用命令 iconv -f UTF-16 -t UTF-8 linktable2.c > linktab2.c 重新生成正确字符集UTF-8 ，否则报空字符错 编译：gcc -o linktable2 linktab2.c -std=c99 *****************************************************/ //#include <pthread.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <time.h> #include <sys/time.h> //#include <unistd.h> /*链表列节点*/ typedef struct XYTableCell { struct XYTableCell* pPrev; struct XYTableCell* pNext; long colIndex; long timeStamp; /*其它数据域*/ char data[20]; } XYTableCell; /*链表行节点*/ typedef struct XYLinkTable { struct XYLinkTable* pPrev; struct XYLinkTable* pNext; long rowIndex; long timeStamp; /* 列数据链表 */ XYTableCell* pColumnCell; } XYLinkTable; XYLinkTable* myLinkTable; /*释放节点的列资源*/ long freeTableRow(XYLinkTable* myTable) { if (myTable != NULL) { long nodes = 0; XYTableCell* pNextCell = myTable->pColumnCell; /*向后tail删除*/ while (pNextCell != NULL) { XYTableCell* tmp = pNextCell->pNext; free(pNextCell); pNextCell = tmp; nodes++; } return nodes; } else { return 0; } } /*向后追加节点，返回最后的节点*/ XYLinkTable* appendNode(XYLinkTable* myTable, long row, long tm, XYTableCell* firstCell) { if (myTable == NULL) { myTable = (XYLinkTable*)malloc(sizeof(XYLinkTable)); myTable->pPrev = NULL; myTable->pNext = NULL; myTable->pColumnCell = firstCell;/*列数据暂时置空*/ myTable->rowIndex = row; myTable->timeStamp = tm; return myTable; } else { myTable->pNext = (XYLinkTable*)malloc(sizeof(XYLinkTable)); if (myTable->pNext == NULL) { printf("==ERR：分配第 %ld 空间 %zd byte 失败\n", row, sizeof(XYLinkTable)); return myTable; } myTable->pNext->pPrev = myTable; myTable = myTable->pNext; myTable->pNext = NULL; myTable->pColumnCell = firstCell;/*列数据暂时置空*/ myTable->rowIndex = row; myTable->timeStamp = tm; return myTable; } } /*释放行资源*/ long freeLinkTable(XYLinkTable* myTable) { if (myTable != NULL) { long nodes = 0; XYLinkTable* pNextNode = myTable->pNext; /*向前head删除*/ while (myTable != NULL) { XYLinkTable* tmp = myTable->pPrev; freeTableRow(myTable);/*先释放行的所有列*/ free(myTable); myTable = tmp; nodes++; } myTable = pNextNode; /*向后tail删除*/ while (myTable != NULL) { XYLinkTable* tmp = myTable->pNext; freeTableRow(myTable);/*先释放行的所有列*/ free(myTable); myTable = tmp; nodes++; } return nodes; } else { return 0; } }
Windows服务器实时监控系统
4800
/*查找到指定的数据*/ XYLinkTable* getAt(XYLinkTable* myTable, long row) { if (myTable != NULL) { XYLinkTable* pNextNode = myTable->pNext; /*向前head删除*/ while (myTable != NULL) { XYLinkTable* tmp = myTable->pPrev; if (myTable->rowIndex == row) { return myTable; } myTable = tmp; } myTable = pNextNode; /*向后tail删除*/ while (myTable != NULL) { XYLinkTable* tmp = myTable->pNext; if (myTable->rowIndex == row) { return myTable; } myTable = tmp; } return NULL; } else { return NULL; } } /*显示行数据*/ void printNode(XYLinkTable* myTable) { printf("======================================\n"); printf("==XYLinkTable双向链表：\n"); printf("==XYLinkTable->pPrev ：0X%p\n" , myTable->pPrev); printf("==XYLinkTable->pNext ：0X%p\n" , myTable->pNext); printf("==XYLinkTable->rowIndex ：%ld\n" , myTable->rowIndex); printf("==XYLinkTable->timeStamp：%ld\n" , myTable->timeStamp); XYTableCell* myCell = myTable->pColumnCell; while (myCell != NULL) { XYTableCell* tmp = myCell->pNext; printf("列=%ld , %s / ", myCell->colIndex, myCell->data); myCell = tmp; } printf("\n"); printf("======================================\n"); } /*向后追加节点，返回最后的节点*/ XYTableCell* addCell(XYTableCell* myCell, long col) { if (myCell == NULL) { myCell = (XYTableCell*)malloc(sizeof(XYTableCell)); myCell->pPrev = NULL; myCell->pNext = NULL; snprintf(myCell->data, sizeof(myCell->data), "值=%ld", col * 3); myCell->colIndex = col; myCell->timeStamp = col+ col; return myCell; } else { myCell->pNext = (XYTableCell*)malloc(sizeof(XYTableCell)); if (myCell->pNext == NULL) { printf("==ERR：分配第 %ld 空间 %zd byte 失败\n", col, sizeof(XYTableCell)); return myCell; } myCell->pNext->pPrev = myCell; myCell = myCell->pNext; myCell->pNext = NULL; snprintf(myCell->data, sizeof(myCell->data), "值=%ld", col * 3); myCell->colIndex = col; myCell->timeStamp = col + col; return myCell; } } int main() { /*初始化*/ myLinkTable = NULL; //struct timeval //{ // time_t tv_sec; /* seconds */ // suseconds_t tv_usec; /* microseconds ,即10-6秒,而不是毫秒（millisecond），10-3秒*/ //}; struct timeval startTime; gettimeofday(&startTime, NULL); /*添加元素*/ int minRand = 10; int maxRand = 99; int MAX_ROWS = 50000; int MIN_ROWS = 0; /*范围：(rand() % (max - min + 1)) + min = [10,99]*/ int min_cols = 0; int max_cols = 10; srand((int)time(NULL)); for (long r = 1; r <= MAX_ROWS; r++) { /*1, 构建列链表[0,10]的随机列数*/ // XYTableCell* addCell(XYTableCell* myCell, long col) XYTableCell* firstCell = NULL; XYTableCell* lastCell = NULL; for (int c = 0; c < ((rand() % (max_cols - min_cols + 1)) + min_cols); c++) { lastCell = addCell(lastCell , c); if (c == 0) { firstCell = lastCell; } } /*2, 构建行数据，同时传入列链表的首指针*/ myLinkTable = appendNode(myLinkTable, r , ((rand() % (maxRand - minRand + 1)) + minRand), firstCell); }
struct timeval endTime; gettimeofday(&endTime, NULL); unsigned long microseconds = 1000000 * (endTime.tv_sec - startTime.tv_sec) + endTime.tv_usec - startTime.tv_usec ; printf("初始哈耗时 = %ld us微秒\n",microseconds); /*随机查询一个*/ XYLinkTable* myNode = getAt(myLinkTable, ( (rand() % (MAX_ROWS - MIN_ROWS + 1) ) + MIN_ROWS) ); printNode(myNode); /*释放资源*/ freeLinkTable(myLinkTable); myLinkTable = NULL; return 0; } |
运行结果如下：
接下来，先实现链表的告诉检索算法（比如：二级索引，三级索引，归并搜索，平衡树/红黑树等）。然后继续HBASE实现。
（End）