hash_st.c

Go to the documentation of this file.

/*
 * kernel_libs/data_structures/hash_st.c
 *
 * Copyright (c) 2003-2004 Lukasz Dembinski <dembol@nasa.com.pl>
 * All Rights Reserved
 * 
 * Date:        2004/01
 * Author:      Lukasz Dembinski
 * Info:        hash_st.c core file, hashing with open addressing
 * Contact:     mailto: <dembol@nasa.com.pl>
 * 
 */

#include <agnix/agnix.h>
#include <agnix/init.h>
#include <agnix/memory.h>
#include <agnix/list.h>
#include <agnix/errno.h>
#include <agnix/spinlock.h>
#include <agnix/console.h>

#define HASH_ENTRIES            ((PAGE_SIZE - sizeof(struct hash_table_s)) >> 3)
#define MAX_HASH_TABLES         16
#define MAX_HASH_ORDER          16

#define PSEUDO_KEY_FREE         0
#define PSEUDO_KEY_DELETED      1
#define PSEUDO_KEY_BUSY         2

#define find_hash_table(hashd) (&hash_tables[hashd])

#define HASH_DEBUG              0
#define MOD_NAME                "HASH: "

struct hash_entry_s {
    u32 hash_key;
    u32 hash_addr;
    int hash_status;
};

struct hash_table_s {
    char *hash_name;
    int max_entries;
    int cur_entries;
    int page_order;
    int hashd;

    u32 (*hash_fn)(u32 key);
    struct hash_entry_s *hash_entry;
    spinlock_t hash_lock;
};

struct hash_table_s hash_tables[MAX_HASH_TABLES];

u32 hash_fn_default(u32 key)
{
    return key;
}

u32 hash_math_pseudo(struct hash_table_s *hash_table_ptr, u32 hash_key)
{
    if (hash_table_ptr->hash_fn)
        return hash_table_ptr->hash_fn(hash_key);
    else
        return hash_key;
}

void hash_count_entries(int hashd) 
{
    struct hash_table_s *hash_table_ptr;    

    hash_table_ptr = find_hash_table(hashd);
    printk("hash_ptr %x\n", hash_table_ptr);
    printk("hash_max_entries %x\n", hash_table_ptr->max_entries);
    printk("hash_cur_entries %x\n", hash_table_ptr->cur_entries);
}

int hash_entry_add(int hashd, u32 hash_key, u32 hash_addr)
{
    struct hash_table_s *hash_table_ptr;
    struct hash_entry_s *hash_entry;
    u32 pseudo_key = 0;
    int loops;
    u32 flags;

    spin_lock_irqsave(&hash_table_ptr->hash_lock, flags);

    hash_table_ptr = find_hash_table(hashd);

    if (!hash_table_ptr->max_entries)
        return -1;

    hash_entry = hash_table_ptr->hash_entry;
    pseudo_key = hash_math_pseudo(hash_table_ptr, hash_key) % hash_table_ptr->max_entries;

    loops = 0;
    do {
        if (hash_entry[pseudo_key].hash_status == PSEUDO_KEY_BUSY) {
            pseudo_key = (pseudo_key + 1) % hash_table_ptr->max_entries;
        } else {
            hash_entry[pseudo_key].hash_key    = hash_key;
            hash_entry[pseudo_key].hash_addr   = hash_addr;
            hash_entry[pseudo_key].hash_status = PSEUDO_KEY_BUSY;
            hash_table_ptr->cur_entries++;
            spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
            return 0;
        }
        
        loops++;
        
    } while(loops < hash_table_ptr->max_entries);
        
    spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
    
    return -1;   
}

int hash_entry_del(int hashd, u32 hash_key)
{
    struct hash_table_s *hash_table_ptr;
    struct hash_entry_s *hash_entry;
    u32 pseudo_key = 0;
    int loops;
    u32 flags;

    spin_lock_irqsave(&hash_table_ptr->hash_lock, flags);

    hash_table_ptr = find_hash_table(hashd);
    if (!hash_table_ptr->max_entries)
        return -1;

    hash_entry = hash_table_ptr->hash_entry;
    pseudo_key = hash_math_pseudo(hash_table_ptr, hash_key) % hash_table_ptr->max_entries;

    loops = 0;
    do {
        
        if (hash_entry[pseudo_key].hash_status == PSEUDO_KEY_FREE) {
            break;
        }
    
        if ((hash_entry[pseudo_key].hash_status != PSEUDO_KEY_BUSY) || 
            ((u32)hash_entry[pseudo_key].hash_key != (u32)hash_key)) {
            pseudo_key = (pseudo_key + 1) % hash_table_ptr->max_entries;
        }
        else {   
            hash_entry[pseudo_key].hash_status = PSEUDO_KEY_DELETED;    
            spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
            return 0;
        }
        
        loops++;
        
    } while(loops < hash_table_ptr->max_entries);
    
    spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
    return -1;   
}

u32 hash_entry_find(int hashd, u32 hash_key)
{
    struct hash_table_s *hash_table_ptr;
    struct hash_entry_s *hash_entry;
    u32 pseudo_key = 0;
    int loops;
    u32 flags;
    
    spin_lock_irqsave(&hash_table_ptr->hash_lock, flags);
    
    hash_table_ptr = find_hash_table(hashd);
    if (!hash_table_ptr->max_entries)
        return 0;

    hash_entry = hash_table_ptr->hash_entry;
    pseudo_key = hash_math_pseudo(hash_table_ptr, hash_key) % hash_table_ptr->max_entries;

    loops = 0;    
    do {
        if (hash_entry[pseudo_key].hash_status == PSEUDO_KEY_FREE)
            break;
            
        if ((hash_entry[pseudo_key].hash_status != PSEUDO_KEY_BUSY) || 
            ((u32)hash_entry[pseudo_key].hash_key != (u32)hash_key)) {
            pseudo_key = (pseudo_key + 1) % hash_table_ptr->max_entries;
        }
        else {   

            spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
            return hash_entry[pseudo_key].hash_addr;
        }
        
        loops++;
        
    } while(loops < hash_table_ptr->max_entries);
    
    spin_unlock_irqrestore(&hash_table_ptr->hash_lock, flags);
    
    return 0;
}

static int get_empty_hash_table(void)
{
    u32 flags;
    int i;
    
    for (i = 0; i < MAX_HASH_TABLES; i++) {
        spin_lock_irqsave(&hash_tables[i].hash_lock, flags);
        if (!hash_tables[i].cur_entries &&
            !hash_tables[i].max_entries) {
                spin_unlock_irqrestore(&hash_tables[i].hash_lock, flags);
                return i;
        }
            
        spin_unlock_irqrestore(&hash_tables[i].hash_lock, flags);
    }
    
    return -1;
}

static void put_empty_hash_table(int hashd)
{
    u32 flags;

    spin_lock_irqsave(&hash_tables[hashd].hash_lock, flags);
    memset(&hash_tables[hashd], 0, sizeof(struct hash_table_s));
    spin_unlock_irqrestore(&hash_tables[hashd].hash_lock, flags);
}

int register_hash_table(char *name, u32 rows, u32 (*hash_fn)(u32 key))
{
    struct hash_table_s *hash_table;
    struct hash_entry_s *hash_entry;
    int page_order = 0;  
    int hashd;  
    int i;

    hashd = get_empty_hash_table();
    if (hashd == -1)
        return -EAGAIN;

    for (i = 0; i < MAX_HASH_ORDER; i++) {
        if (rows < (((1 << i) * PAGE_SIZE) / sizeof(struct hash_entry_s))) {
            page_order = i;
            break;
        }
    }

    if (i == MAX_HASH_ORDER)
        return -EINVAL;

    hash_table = &hash_tables[hashd];
    hash_entry = (struct hash_entry_s *)get_free_pages(page_order);
    
    if (!hash_table) {
        put_empty_hash_table(hashd);
        return -ENOMEM;
    }

    if (hash_fn)
        hash_table->hash_fn = hash_fn;
    else
        hash_table->hash_fn = hash_fn_default;

    hash_table->hash_name   = name;
    hash_table->max_entries = ((1 << page_order) * PAGE_SIZE) / sizeof(struct hash_entry_s);
    hash_table->cur_entries = 0;
    hash_table->page_order  = page_order;
    hash_table->hashd       = hashd;        
    hash_table->hash_entry  = hash_entry;
    
    for (i = 0; i < hash_table->max_entries; i++)
        hash_table->hash_entry[i].hash_status = PSEUDO_KEY_FREE;
    
#if HASH_DEBUG
    printk(MOD_NAME "registering %s hashing table (%d rows/%d pages)\n", name, hash_table->max_entries, page_order);
#endif

    spin_lock_init(&hash_table->hash_lock);
    
    return hashd;
}

int unregister_hash_table(int hashd)
{
    struct hash_table_s *hash_table_ptr;    

    hash_table_ptr = find_hash_table(hashd);

    if (hash_table_ptr) {
        put_free_pages((u32)hash_table_ptr->hash_entry, (u8)(hash_table_ptr->page_order));
        put_free_pages((u32)hash_table_ptr, 0);
    }

    return 0;
}

int hash_static_init(void)
{
    int i;

    for (i = 0; i < MAX_HASH_TABLES; i++) {
        memset((void *)&hash_tables[i], 0, sizeof(struct hash_table_s));
    }

    return 0;
}