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