ha0ha.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:8k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /************************************************************************
  2. The hash table with external chains
  3. (c) 1994-1997 Innobase Oy
  4. Created 8/22/1994 Heikki Tuuri
  5. *************************************************************************/
  6. #include "ha0ha.h"
  7. #ifdef UNIV_NONINL
  8. #include "ha0ha.ic"
  9. #endif
  10. #include "buf0buf.h"
  11. /*****************************************************************
  12. Creates a hash table with >= n array cells. The actual number of cells is
  13. chosen to be a prime number slightly bigger than n. */
  14. hash_table_t*
  15. ha_create(
  16. /*======*/
  17. /* out, own: created table */
  18. ibool in_btr_search, /* in: TRUE if the hash table is used in
  19. the btr_search module */
  20. ulint n, /* in: number of array cells */
  21. ulint n_mutexes, /* in: number of mutexes to protect the
  22. hash table: must be a power of 2, or 0 */
  23. ulint mutex_level) /* in: level of the mutexes in the latching
  24. order: this is used in the debug version */
  25. {
  26. hash_table_t* table;
  27. ulint i;
  28. table = hash_create(n);
  29. if (in_btr_search) {
  30. table->adaptive = TRUE;
  31. } else {
  32. table->adaptive = FALSE;
  33. }
  34. if (n_mutexes == 0) {
  35. if (in_btr_search) {
  36. table->heap = mem_heap_create_in_btr_search(4096);
  37. } else {
  38. table->heap = mem_heap_create_in_buffer(4096);
  39. }
  40. return(table);
  41. }
  42. hash_create_mutexes(table, n_mutexes, mutex_level);
  43. table->heaps = mem_alloc(n_mutexes * sizeof(void*));
  44. for (i = 0; i < n_mutexes; i++) {
  45. if (in_btr_search) {
  46. table->heaps[i] = mem_heap_create_in_btr_search(4096);
  47. } else {
  48. table->heaps[i] = mem_heap_create_in_buffer(4096);
  49. }
  50. }
  51. return(table);
  52. }
  53. /*****************************************************************
  54. Inserts an entry into a hash table. If an entry with the same fold number
  55. is found, its node is updated to point to the new data, and no new node
  56. is inserted. */
  57. ibool
  58. ha_insert_for_fold(
  59. /*===============*/
  60. /* out: TRUE if succeed, FALSE if no more
  61. memory could be allocated */
  62. hash_table_t* table, /* in: hash table */
  63. ulint fold, /* in: folded value of data; if a node with
  64. the same fold value already exists, it is
  65. updated to point to the same data, and no new
  66. node is created! */
  67. void* data) /* in: data, must not be NULL */
  68. {
  69. hash_cell_t* cell;
  70. ha_node_t* node;
  71. ha_node_t* prev_node;
  72. buf_block_t* prev_block;
  73. ulint hash;
  74. ut_ad(table && data);
  75. #ifdef UNIV_SYNC_DEBUG
  76. ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
  77. #endif /* UNIV_SYNC_DEBUG */
  78. hash = hash_calc_hash(fold, table);
  79. cell = hash_get_nth_cell(table, hash);
  80. prev_node = cell->node;
  81. while (prev_node != NULL) {
  82. if (prev_node->fold == fold) {
  83. if (table->adaptive) {
  84. prev_block = buf_block_align(prev_node->data);
  85. ut_a(prev_block->n_pointers > 0);
  86. prev_block->n_pointers--;
  87. buf_block_align(data)->n_pointers++;
  88. }
  89. prev_node->data = data;
  90. return(TRUE);
  91. }
  92. prev_node = prev_node->next;
  93. }
  94. /* We have to allocate a new chain node */
  95. node = mem_heap_alloc(hash_get_heap(table, fold), sizeof(ha_node_t));
  96. if (node == NULL) {
  97. /* It was a btr search type memory heap and at the moment
  98. no more memory could be allocated: return */
  99. ut_ad(hash_get_heap(table, fold)->type & MEM_HEAP_BTR_SEARCH);
  100. return(FALSE);
  101. }
  102. ha_node_set_data(node, data);
  103. if (table->adaptive) {
  104. buf_block_align(data)->n_pointers++;
  105. }
  106. node->fold = fold;
  107. node->next = NULL;
  108. prev_node = cell->node;
  109. if (prev_node == NULL) {
  110. cell->node = node;
  111. return(TRUE);
  112. }
  113. while (prev_node->next != NULL) {
  114. prev_node = prev_node->next;
  115. }
  116. prev_node->next = node;
  117. return(TRUE);
  118. }
  119. /***************************************************************
  120. Deletes a hash node. */
  121. void
  122. ha_delete_hash_node(
  123. /*================*/
  124. hash_table_t* table, /* in: hash table */
  125. ha_node_t* del_node) /* in: node to be deleted */
  126. {
  127. if (table->adaptive) {
  128. ut_a(buf_block_align(del_node->data)->n_pointers > 0);
  129. buf_block_align(del_node->data)->n_pointers--;
  130. }
  131. HASH_DELETE_AND_COMPACT(ha_node_t, next, table, del_node);
  132. }
  133. /*****************************************************************
  134. Deletes an entry from a hash table. */
  135. void
  136. ha_delete(
  137. /*======*/
  138. hash_table_t* table, /* in: hash table */
  139. ulint fold, /* in: folded value of data */
  140. void* data) /* in: data, must not be NULL and must exist
  141. in the hash table */
  142. {
  143. ha_node_t* node;
  144. #ifdef UNIV_SYNC_DEBUG
  145. ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
  146. #endif /* UNIV_SYNC_DEBUG */
  147. node = ha_search_with_data(table, fold, data);
  148. ut_a(node);
  149. ha_delete_hash_node(table, node);
  150. }
  151. /*************************************************************
  152. Looks for an element when we know the pointer to the data, and updates
  153. the pointer to data, if found. */
  154. void
  155. ha_search_and_update_if_found(
  156. /*==========================*/
  157. hash_table_t* table, /* in: hash table */
  158. ulint fold, /* in: folded value of the searched data */
  159. void* data, /* in: pointer to the data */
  160. void* new_data)/* in: new pointer to the data */
  161. {
  162. ha_node_t* node;
  163. #ifdef UNIV_SYNC_DEBUG
  164. ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
  165. #endif /* UNIV_SYNC_DEBUG */
  166. node = ha_search_with_data(table, fold, data);
  167. if (node) {
  168. if (table->adaptive) {
  169. ut_a(buf_block_align(node->data)->n_pointers > 0);
  170. buf_block_align(node->data)->n_pointers--;
  171. buf_block_align(new_data)->n_pointers++;
  172. }
  173. node->data = new_data;
  174. }
  175. }
  176. /*********************************************************************
  177. Removes from the chain determined by fold all nodes whose data pointer
  178. points to the page given. */
  179. void
  180. ha_remove_all_nodes_to_page(
  181. /*========================*/
  182. hash_table_t* table, /* in: hash table */
  183. ulint fold, /* in: fold value */
  184. page_t* page) /* in: buffer page */
  185. {
  186. ha_node_t* node;
  187. #ifdef UNIV_SYNC_DEBUG
  188. ut_ad(!table->mutexes || mutex_own(hash_get_mutex(table, fold)));
  189. #endif /* UNIV_SYNC_DEBUG */
  190. node = ha_chain_get_first(table, fold);
  191. while (node) {
  192. if (buf_frame_align(ha_node_get_data(node)) == page) {
  193. /* Remove the hash node */
  194. ha_delete_hash_node(table, node);
  195. /* Start again from the first node in the chain
  196. because the deletion may compact the heap of
  197. nodes and move other nodes! */
  198. node = ha_chain_get_first(table, fold);
  199. } else {
  200. node = ha_chain_get_next(node);
  201. }
  202. }
  203. #ifdef UNIV_DEBUG
  204. /* Check that all nodes really got deleted */
  205. node = ha_chain_get_first(table, fold);
  206. while (node) {
  207. ut_a(buf_frame_align(ha_node_get_data(node)) != page);
  208. node = ha_chain_get_next(node);
  209. }
  210. #endif
  211. }
  212. /*****************************************************************
  213. Validates a hash table. */
  214. ibool
  215. ha_validate(
  216. /*========*/
  217. /* out: TRUE if ok */
  218. hash_table_t* table) /* in: hash table */
  219. {
  220. hash_cell_t* cell;
  221. ha_node_t* node;
  222. ibool ok = TRUE;
  223. ulint i;
  224. for (i = 0; i < hash_get_n_cells(table); i++) {
  225. cell = hash_get_nth_cell(table, i);
  226. node = cell->node;
  227. while (node) {
  228. if (hash_calc_hash(node->fold, table) != i) {
  229. ut_print_timestamp(stderr);
  230. fprintf(stderr,
  231. "InnoDB: Error: hash table node fold value %lu does notn"
  232. "InnoDB: match with the cell number %lu.n",
  233. (ulong) node->fold, (ulong) i);
  234. ok = FALSE;
  235. }
  236. node = node->next;
  237. }
  238. }
  239. return(ok);
  240. }
  241. /*****************************************************************
  242. Prints info of a hash table. */
  243. void
  244. ha_print_info(
  245. /*==========*/
  246. FILE* file, /* in: file where to print */
  247. hash_table_t* table) /* in: hash table */
  248. {
  249. hash_cell_t* cell;
  250. ulint cells = 0;
  251. ulint n_bufs;
  252. ulint i;
  253. for (i = 0; i < hash_get_n_cells(table); i++) {
  254. cell = hash_get_nth_cell(table, i);
  255. if (cell->node) {
  256. cells++;
  257. }
  258. }
  259. fprintf(file,
  260. "Hash table size %lu, used cells %lu",
  261. (ulong) hash_get_n_cells(table), (ulong) cells);
  262. if (table->heaps == NULL && table->heap != NULL) {
  263. /* This calculation is intended for the adaptive hash
  264. index: how many buffer frames we have reserved? */
  265. n_bufs = UT_LIST_GET_LEN(table->heap->base) - 1;
  266. if (table->heap->free_block) {
  267. n_bufs++;
  268. }
  269. fprintf(file, ", node heap has %lu buffer(s)n", (ulong) n_bufs);
  270. }
  271. }