This repository has been archived by the owner on Aug 3, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 36
/
db_debug.c
132 lines (106 loc) · 2.75 KB
/
db_debug.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/**
* @file db_debug.c
* Debug routines for libdb
*
* @remark Copyright 2002 OProfile authors
* @remark Read the file COPYING
*
* @author Philippe Elie
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "odb.h"
static int check_circular_list(odb_data_t const * data)
{
odb_node_nr_t pos;
int do_abort = 0;
unsigned char * bitmap = malloc(data->descr->current_size);
memset(bitmap, '\0', data->descr->current_size);
for (pos = 0 ; pos < data->descr->size * BUCKET_FACTOR ; ++pos) {
odb_index_t index = data->hash_base[pos];
if (index && !do_abort) {
while (index) {
if (bitmap[index])
do_abort = 1;
bitmap[index] = 1;
index = data->node_base[index].next;
}
}
if (do_abort) {
printf("circular list detected size: %d\n",
data->descr->current_size);
memset(bitmap, '\0', data->descr->current_size);
index = data->hash_base[pos];
while (index) {
printf("%d ", index);
if (bitmap[index])
exit(1);
bitmap[index] = 1;
index = data->node_base[index].next;
}
}
/* purely an optimization: intead of memset the map reset only
* the needed part: not my use to optimize test but here the
* test was so slow it was useless */
index = data->hash_base[pos];
while (index) {
bitmap[index] = 1;
index = data->node_base[index].next;
}
}
free(bitmap);
return do_abort;
}
static int check_redundant_key(odb_data_t const * data, odb_key_t max)
{
odb_node_nr_t pos;
unsigned char * bitmap = malloc(max + 1);
memset(bitmap, '\0', max + 1);
for (pos = 1 ; pos < data->descr->current_size ; ++pos) {
if (bitmap[data->node_base[pos].key]) {
printf("redundant key found %lld\n",
(unsigned long long)data->node_base[pos].key);
return 1;
}
bitmap[data->node_base[pos].key] = 1;
}
free(bitmap);
return 0;
}
int odb_check_hash(odb_t const * odb)
{
odb_node_nr_t pos;
odb_node_nr_t nr_node = 0;
odb_node_nr_t nr_node_out_of_bound = 0;
int ret = 0;
odb_key_t max = 0;
odb_data_t * data = odb->data;
for (pos = 0 ; pos < data->descr->size * BUCKET_FACTOR ; ++pos) {
odb_index_t index = data->hash_base[pos];
while (index) {
if (index >= data->descr->current_size) {
nr_node_out_of_bound++;
break;
}
++nr_node;
if (data->node_base[index].key > max)
max = data->node_base[index].key;
index = data->node_base[index].next;
}
}
if (nr_node != data->descr->current_size - 1) {
printf("hash table walk found %d node expect %d node\n",
nr_node, data->descr->current_size - 1);
ret = 1;
}
if (nr_node_out_of_bound) {
printf("out of bound node index: %d\n", nr_node_out_of_bound);
ret = 1;
}
if (ret == 0)
ret = check_circular_list(data);
if (ret == 0)
ret = check_redundant_key(data, max);
return ret;
}