db_debug.c

Go to the documentation of this file.

#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);
            free(bitmap);
            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;
}