/* -*- c-basic-offset: 4 indent-tabs-mode: nil -*- */

/*  Lac - Library for asynchronous communication
 *  Copyright (C) 2002  Søren Sandmann (sandmann@daimi.au.dk)
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Library General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Library General Public License for more details.
 *
 *  You should have received a copy of the GNU Library General Public
 *  License along with this library; if not, write to the 
 *  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 *  Boston, MA  02111-1307, USA.
 */

#include "lacdns-cache.h"

enum {
    MAX_NEGATIVE_CACHING = 3600,  /* max seconds to cache negative answers */
};

typedef struct CacheEntry  CacheEntry;
typedef struct CacheRecord CacheRecord;

/* CacheEntry */
typedef enum {
    CACHE_ENTRY_DATA,
    CACHE_ENTRY_NO_SUCH_NAME,
} CacheEntryKind;

struct CacheEntry {
    CacheEntryKind      kind;
    DomainName *        domain_name;
    
    union {
        struct {
            GList * cache_records;
        } data;
        struct {
            guint   time_to_die;
        } no_such_name;
    } u;
};

static CacheEntry *cache_entry_new_data         (const DomainName *name);
static CacheEntry *cache_entry_new_no_such_name (const DomainName *name,
                                                 guint             time_to_live);
static void        cache_entry_free             (CacheEntry       *entry);


/* CacheRecord */
typedef enum {
    CACHE_RECORD_DATA,
    CACHE_RECORD_NO_DATA,
} CacheRecordKind;

struct CacheRecord {
    CacheRecordKind     kind            : 8;
    QueryRRType         type            : 8;
    guint               time_to_die;
    RData *             rdata;
};

static CacheRecord *cache_record_new_no_data (RRType       type,
                                              guint        time_to_live);
static CacheRecord *cache_record_new_data    (RRType       type,
                                              guint        time_to_live,
                                              const RData *rdata);
static void         cache_record_free        (CacheRecord *record);

static GHashTable *cache = NULL;


static void
cache_init (void)
{
    if (!cache)
    {
        cache = g_hash_table_new ((GHashFunc)domain_name_hash,
                                  (GEqualFunc)domain_name_equal);
    }
}

static guint
now()
{
    static GTimer *timer = NULL;

    if (!timer)
        timer = g_timer_new ();

    return (guint)g_timer_elapsed (timer, NULL);
}

static void
cache_delete_entry (const DomainName *name)
{
    CacheEntry *entry;
    
    entry = g_hash_table_lookup (cache, name);
    if (entry)
    {
        g_hash_table_remove (cache, entry->domain_name);
        cache_entry_free (entry);
    }
}

static CacheEntry *
cache_find_entry (const DomainName *name)
{
    CacheEntry *entry = g_hash_table_lookup (cache, name);
    
    if (entry &&
        entry->kind == CACHE_ENTRY_NO_SUCH_NAME &&
        entry->u.no_such_name.time_to_die <= now())
    {
        cache_delete_entry (name);
        return NULL;
    }
    
    return entry;
}

static GList *
cache_entry_get_records_of_type (CacheEntry *entry, RRType type)
{
    GList *list;
    GList *retval = NULL;
    guint current_time = now();
    
    if (entry->kind == CACHE_ENTRY_NO_SUCH_NAME)
        return NULL;
    
    list = entry->u.data.cache_records;
    while (list != NULL)
    {
        GList *next = list->next;
        CacheRecord *record = list->data;
        
        if (record->time_to_die <= current_time)
        {
            cache_record_free (record);
            entry->u.data.cache_records =
                g_list_delete_link (entry->u.data.cache_records, list);
        }
        else
        {
            if (record->type == type)
                retval = g_list_prepend (retval, record);
        }
        list = next;
    }
    
    return retval;
}

CacheResult *
cache_lookup (const DomainName *name, RRType type)
{
    CacheResult *result;
    CacheEntry *entry;
    
    cache_init ();
    
    result = g_new (CacheResult, 1);
    result->rr_type = type;
    result->records = NULL;
    
    entry = cache_find_entry (name);
    if (!entry)
    {
        result->type = CACHE_NOTHING_KNOWN;
    }
    else if (entry->kind == CACHE_ENTRY_NO_SUCH_NAME)
    {
        result->type = CACHE_NO_SUCH_NAME;
    }
    else
    {
        GList *cache_records = cache_entry_get_records_of_type (entry, type);
        
        if (cache_records)
        {
            CacheRecord *cache_record = cache_records->data;
            
            if (cache_record->kind == CACHE_RECORD_NO_DATA)
            {
                result->type = CACHE_NO_DATA;
            }
            else
            {
                GList *list;
                
                result->type = CACHE_DATA_FOUND;
                for (list = cache_records; list != NULL; list = list->next)
                {
                    cache_record = list->data;
                    
                    result->records = g_list_prepend (
                        result->records, rdata_copy (cache_record->rdata));
                }
            }
            
            g_list_free (cache_records);
        }
        else
        {
            result->type = CACHE_NAME_EXISTS;
        }
    }
    
    return result;
}

CacheResult *
cache_lookup_recursive (const DomainName *name, RRType type)
{
    CacheResult *result = cache_lookup (name, type);
    
    if (result->type == CACHE_NO_DATA ||
        result->type == CACHE_NAME_EXISTS)
    {
        g_assert (result->records == NULL);
        
        if (type != CNAME_TYPE)
        {
            RData *cname = cache_lookup_cname (name);
            
            if (cname)
            {
                g_assert (cname->type == CNAME_TYPE);
                cache_result_free (result);
                result = cache_lookup_recursive (cname->u.cname.name, type);
                
                rdata_free (cname);
            }
        }
    }
    
    return result;
}

RData *
cache_lookup_cname (const DomainName     *name)
{
    RData *cname = NULL;
    CacheResult *result = cache_lookup (name, CNAME_TYPE);
    
    if (result->type == CACHE_DATA_FOUND)
        cname = rdata_copy (result->records->data);
    
    cache_result_free (result);
    return cname;
}

RData *
cache_lookup_soa (const DomainName     *name)
{
    RData *soa = NULL;
    DomainName *nm = domain_name_copy (name);
    
    while (domain_name_n_labels (nm) > 0)
    {
        CacheResult *result = cache_lookup (nm, SOA_TYPE);
        
        if (result->type == CACHE_DATA_FOUND)
        {
            soa = rdata_copy (result->records->data);
            cache_result_free (result);
            break;
        }
        
        cache_result_free (result);
        domain_name_strip_prefix (nm);
    }
    
    domain_name_free (nm);
    
    return soa;
}

void
cache_result_free (CacheResult *result)
{
    if (result->type == CACHE_DATA_FOUND)
    {
        GList *list;
        for (list = result->records; list; list = list->next)
            rdata_free (list->data);
        g_list_free (result->records);
    }
    g_free (result);
}

static CacheEntry *
cache_ensure_data_entry (const DomainName *name)
{
    CacheEntry *entry;
    
    entry = cache_find_entry (name);
    
    if (entry && entry->kind == CACHE_ENTRY_NO_SUCH_NAME)
    {
        cache_delete_entry (entry->domain_name);
        entry = NULL;
    }
    
    if (!entry)
    {
        entry = cache_entry_new_data (name);
        g_hash_table_insert (cache, entry->domain_name, entry);
    }
    
    return entry;
}

static gboolean
cache_already_exists (const ResourceRecord *rr)
{
    CacheEntry *entry;
    
    entry = cache_find_entry (rr->name);
    
    if (entry && entry->kind == CACHE_ENTRY_DATA)
    {
        GList *list;
        for (list = entry->u.data.cache_records; list; list = list->next)
        {
            CacheRecord *cache_record = list->data;
            
            if (cache_record->kind == CACHE_RECORD_DATA &&
                rdata_equal (cache_record->rdata, rr->rdata))
            {
                /* found an existing exact match in the cache. Just
                 * update its time_to_die.
                 */
                
                cache_record->time_to_die =
                    rr->time_to_live + now();
                
                return TRUE;
            }
        }
    }
    
    return FALSE;
}

void
cache_insert_positive (const ResourceRecord *rr, gboolean *cname_cycle)
{
    CacheEntry *entry;
    CacheRecord *cache_record;
    
    cache_init ();
    
    g_return_if_fail (rr != NULL);
    g_return_if_fail (rr->rdata != NULL);
    
    if (cache_already_exists (rr))
        return;
    
    if (cname_cycle)
        *cname_cycle = FALSE;
    
    if (rr->rdata->type == CNAME_TYPE)
    {
        /* We must make sure we are not generating CNAME cycles
         * in the cache and that a name will never have more than
         * one CNAME record associcated with it.
         *     
         * When we want to insert a CNAME record that maps N to C,
         * first check if N already has a CNAME. If so, delete it.
         * Then follow the chain of CNAMES starting in C. If we end
         * up in N, inserting the record would generate a CNAME
         * cycle in the cache.
         */
        
        /* FIXME */
    }
    
    entry = cache_ensure_data_entry (rr->name);
    
    cache_record =
        cache_record_new_data (rr->rdata->type, rr->time_to_live, rr->rdata);
    entry->u.data.cache_records =
        g_list_prepend (entry->u.data.cache_records, cache_record);
}

void
cache_insert_no_such_name (const DomainName *name,
                           guint             time_to_live)
{
    CacheEntry *entry;
    
    cache_init ();
    
    time_to_live = MIN (MAX_NEGATIVE_CACHING, time_to_live);
    
    cache_delete_entry (name);
    
    entry = cache_entry_new_no_such_name (name, time_to_live);
    
    g_assert (entry);
    
    g_hash_table_insert (cache, entry->domain_name, entry);
}

void
cache_insert_no_data (const DomainName *name,
                      RRType      type,
                      guint32     time_to_live)
{
    CacheEntry *entry;
    CacheRecord *new_record;
    
    cache_init ();
    
    time_to_live = MIN (MAX_NEGATIVE_CACHING, time_to_live);
    
    cache_delete_by_type (name, type);
    entry = cache_ensure_data_entry (name);
    
    new_record = cache_record_new_no_data (type, time_to_live);
    entry->u.data.cache_records =
        g_list_prepend (entry->u.data.cache_records, new_record);
}

/* Deletes all records that matches type
 */
void
cache_delete_by_type (const DomainName      *name,
                      RRType                 type)
{
    CacheEntry *entry;
    
    cache_init ();
    
    entry = cache_find_entry (name);
    if (entry && entry->kind == CACHE_ENTRY_DATA)
    {
        GList *list;
        
        list = entry->u.data.cache_records;
        while (list != NULL)
        {
            GList *next = list->next;
            CacheRecord *old_record = list->data;
            
            if (old_record->type == type)
            {
                cache_record_free (old_record);
                entry->u.data.cache_records =
                    g_list_delete_link (entry->u.data.cache_records, list);
            }
            
            list = next;
        }
        
        if (entry->u.data.cache_records == NULL)
        {
            g_hash_table_remove (cache, entry->domain_name);
            cache_entry_free (entry);
        }
    }
}

/* Deletes all records that rdata.
 */
void
cache_delete_rdata (const DomainName      *name,
                    const RData           *rdata)
{
    CacheEntry *entry;
    
    cache_init ();
    
    entry = cache_find_entry (name);
    if (entry && entry->kind == CACHE_ENTRY_DATA)
    {
        GList *list;
        
        list = entry->u.data.cache_records;
        while (list != NULL)
        {
            GList *next = list->next;
            CacheRecord *old_record = list->data;
            
            if (rdata_equal (rdata, old_record->rdata))
            {
                cache_record_free (old_record);
                entry->u.data.cache_records =
                    g_list_delete_link (entry->u.data.cache_records, list);
            }
            
            list = next;
        }
        
        if (entry->u.data.cache_records == NULL)
        {
            g_hash_table_remove (cache, entry->domain_name);
            cache_entry_free (entry);
        }
    }
}

/*
 * CacheRecord implementation
 */
static CacheRecord *
cache_record_new_no_data (RRType type, guint time_to_live)
{
    CacheRecord *record;
    
    record = g_new (CacheRecord, 1);
    
    record->type = type;
    record->kind = CACHE_RECORD_NO_DATA;
    record->time_to_die = now() + time_to_live;
    record->rdata = NULL;
    
    return record;
}

static CacheRecord *
cache_record_new_data (RRType type, guint time_to_live, const RData *rdata)
{
    CacheRecord *record;
    
    g_return_val_if_fail (rdata != NULL, NULL);
    
    record = g_new (CacheRecord, 1);
    
    record->type = type;
    record->kind = CACHE_RECORD_DATA;
    record->time_to_die = now() + time_to_live;
    record->rdata = rdata_copy (rdata);
    
    return record;
}

static void
cache_record_free (CacheRecord *record)
{
    g_return_if_fail (record != NULL);
    
    if (record->kind == CACHE_RECORD_DATA)
        rdata_free (record->rdata);
    
    g_free (record);
}

/*
 * CacheEntry implementation
 */
static CacheEntry *
cache_entry_new_data (const DomainName *name)
{
    CacheEntry *entry;
    
    g_return_val_if_fail (name != NULL, NULL);
    
    entry = g_new (CacheEntry, 1);
    entry->domain_name = domain_name_copy (name);
    entry->kind = CACHE_ENTRY_DATA;
    entry->u.data.cache_records = NULL;
    
    return entry;
}

static CacheEntry *
cache_entry_new_no_such_name (const DomainName *name, guint time_to_live)
{
    CacheEntry *entry;
    
    g_return_val_if_fail (name != NULL, NULL);
    
    entry = g_new (CacheEntry, 1);
    entry->kind = CACHE_ENTRY_NO_SUCH_NAME;
    entry->domain_name = domain_name_copy (name);
    entry->u.no_such_name.time_to_die = now() + time_to_live;
    
    return entry;
}

static void
cache_entry_free (CacheEntry *entry)
{
    GList *list;
    
    g_return_if_fail (entry != NULL);
    g_return_if_fail (entry->domain_name != NULL);
    
    domain_name_free (entry->domain_name);
    switch (entry->kind)
    {
    case CACHE_ENTRY_DATA:
        for (list = entry->u.data.cache_records; list != NULL; list = list->next)
        {
            CacheRecord *record = list->data;
            
            cache_record_free (record);
        }
        break;
        
    case CACHE_ENTRY_NO_SUCH_NAME:
        break;
    }
    
    g_free (entry);
}