fatfs_ncache.c

嵌入式FAT文件系统

//==========================================================================
//
//      fatfs_ncache.c
//
//      FAT file system node cache functions
//
//==========================================================================
//####ECOSGPLCOPYRIGHTBEGIN####
// -------------------------------------------
// This file is part of eCos, the Embedded Configurable Operating System.
// Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004 Red Hat, Inc.
//
// eCos is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 or (at your option) any later version.
//
// eCos 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 General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License along
// with eCos; if not, write to the Free Software Foundation, Inc.,
// 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
//
// As a special exception, if other files instantiate templates or use macros
// or inline functions from this file, or you compile this file and link it
// with other works to produce a work based on this file, this file does not
// by itself cause the resulting work to be covered by the GNU General Public
// License. However the source code for this file must still be made available
// in accordance with section (3) of the GNU General Public License.
//
// This exception does not invalidate any other reasons why a work based on
// this file might be covered by the GNU General Public License.
//
// -------------------------------------------
//####ECOSGPLCOPYRIGHTEND####
//==========================================================================
//#####DESCRIPTIONBEGIN####
//
// Author(s):           Savin Zlobec <[e-mail]> 
// Date:                2003-06-26
//
//####DESCRIPTIONEND####
//
//==========================================================================

#include <pkgconf/fs_fat.h>
#include <pkgconf/infra.h>
#include <cyg/infra/cyg_type.h>
#include <cyg/infra/cyg_ass.h>
#include <cyg/infra/cyg_trac.h>
#include <cyg/infra/diag.h>
#include <sys/types.h>
#include <ctype.h>

#include "fatfs.h"

//==========================================================================
// Defines & macros 

#ifdef CYGDBG_USE_ASSERTS
# define USE_ASSERTS 1
#endif

#ifdef FATFS_NODE_CACHE_EXTRA_CHECKS
# define USE_XCHECKS 1
#endif

#ifdef FATFS_TRACE_NODE_CACHE
# define TNC 1
#else
# define TNC 0
#endif

// This defines how many nodes should always be kept in dead list - 
// it should be >= 2 or the file finding code may not work correctly!
#define DLIST_KEEP_NUM 2 

//==========================================================================
// Node list functions 

static void
node_list_init(fatfs_node_list_t *list)
{
    list->size  = 0;
    list->first = list->last = NULL;
}

static __inline__ int 
node_list_get_size(fatfs_node_list_t *list)
{
    return (list->size);
}

static __inline__ fatfs_node_t*
node_list_get_head(fatfs_node_list_t *list)
{
    return (list->first);
}

static __inline__ fatfs_node_t*
node_list_get_tail(fatfs_node_list_t *list)
{
    return (list->last);
}

static __inline__ fatfs_node_t*
node_list_get_next(fatfs_node_t *node)
{
    return (node->list_next);
}

static __inline__ fatfs_node_t*
node_list_get_prev(fatfs_node_t *node)
{
    return (node->list_prev);
}

static __inline__ bool
node_list_is_last(fatfs_node_t *node)
{
    return (NULL == node->list_next);
}

static __inline__ bool
node_list_is_first(fatfs_node_t *node)
{
    return (NULL == node->list_prev);
}

static void
node_list_head_add(fatfs_node_list_t *list, fatfs_node_t *node)
{
    node->list_prev = NULL;
    node->list_next = list->first;
    
    if (NULL == list->first)
    {
        CYG_ASSERTC(list->size == 0);
        list->last = node;
    }
    else
    {
        list->first->list_prev = node;
    }
    
    list->first = node;
    list->size++;
}

#if 0
static __inline__ fatfs_node_t*
node_list_head_get(fatfs_node_list_t *list)
{
    return list->first;
}

static void
node_list_tail_add(fatfs_node_list_t *list, fatfs_node_t *node)
{
    node->list_prev = list->last;
    node->list_next = NULL;
    
    if (NULL == list->last)
    {
        CYG_ASSERTC(list->size == 0);
        list->first = node;
    }
    else
    {
        list->last->list_next = node;
    }
    
    list->last = node;
    list->size++;
}
#endif

static __inline__ fatfs_node_t*
node_list_tail_get(fatfs_node_list_t *list)
{
    return list->last;
}

static void
node_list_remove(fatfs_node_list_t *list, fatfs_node_t *node)
{
    if (list->first == list->last)
    {
        if (list->first == node)
        {
            CYG_ASSERTC(list->size == 1);
            list->first = list->last = NULL;
        }
        else
        {
            CYG_ASSERT(false, "chain node not in list!");
        }
    }
    else if (list->first == node)
    {
        CYG_ASSERTC(node->list_prev == NULL); 
        list->first = node->list_next;
        list->first->list_prev = NULL;
    }
    else if (list->last == node)
    {
        CYG_ASSERTC(node->list_next == NULL); 
        list->last = node->list_prev;
        list->last->list_next = NULL;
    }
    else
    {
        CYG_ASSERTC(node->list_prev != NULL && node->list_next != NULL); 
        node->list_prev->list_next = node->list_next;
        node->list_next->list_prev = node->list_prev;        
    }
    list->size--;
}

#ifdef USE_XCHECKS
static void
node_list_check(fatfs_node_list_t *list, int min_ref, int max_ref)
{
    int i;
    fatfs_node_t *node, *pnode;

    CYG_ASSERT((list->last == NULL && list->first == NULL) ||
               (list->last != NULL && list->first != NULL), 
               "list->first and list->last broken!");

    if (list->first == NULL)
    {
        CYG_ASSERTC(list->size == 0);
        return;
    }
    
    CYG_ASSERTC(list->first->list_prev == NULL);
    CYG_ASSERTC(list->last->list_next == NULL);

    CYG_ASSERTC(list->first->refcnt >= min_ref && 
                list->first->refcnt <= max_ref);
    CYG_ASSERTC(list->last->refcnt >= min_ref && 
                list->last->refcnt <= max_ref);
    
    i = 1;
    node = list->first; 
    pnode = NULL;
    while (node->list_next != NULL)
    {
        i++;
        CYG_ASSERTC(node->list_prev == pnode);
        CYG_ASSERTC(node->refcnt >= min_ref && node->refcnt <= max_ref);
        pnode = node;
        node = node->list_next;
    }
    CYG_ASSERTC(node->list_prev == pnode);
    CYG_ASSERTC(list->size == i);
    CYG_ASSERTC(node == list->last);
}

static void
node_lists_check(fatfs_disk_t* disk)
{
    node_list_check(&disk->live_nlist, 1, 99999);                        
    node_list_check(&disk->dead_nlist, 0, 0);                           
}
#endif // USE_XCHECKS

//==========================================================================
// Node hash functions 

static unsigned int 
hash_fn(const char *str, unsigned int strlen)
{
    unsigned int i = 0, val = 0;

    while (i++ < strlen)
        val = (val ^ (int)toupper(*str++)) << 1;
    return(val);
}

static void
node_hash_init(fatfs_hash_table_t *tbl)
{
    int i;

    // Set size and clear all slots
    tbl->size = FATFS_HASH_TABLE_SIZE;
    for (i = 0; i < tbl->size; i++)
        tbl->nodes[i] = NULL;
    tbl->n = 0;
}

static bool
node_hash_add(fatfs_hash_table_t *tbl, fatfs_node_t *node)
{
    unsigned int hval;
   
    // Calculate hash of given node filename
    hval = hash_fn(node->dentry.filename, 
                   strlen(node->dentry.filename)) % tbl->size;

    CYG_TRACE2(TNC, "name='%s' hval=%d", node->dentry.filename, hval);

    if (tbl->nodes[hval] == NULL)
    {
        // First node in this slot
        node->hash_next  = NULL;
        tbl->nodes[hval] = node;
        tbl->n++; 
        return true;
    }
    else
    { 
        // More nodes in this slot
        fatfs_node_t *lnode, *pnode;
       
        pnode = NULL;
        lnode = tbl->nodes[hval];

        // Insert node into list so that it is sorted by filename        
        while (lnode != NULL)
        {
            if (lnode == node)
                return false;
            
            if (strcasecmp(lnode->dentry.filename, node->dentry.filename) > 0)
            {
                if (pnode != NULL)
                    pnode->hash_next = node; // Insert in the middle
                else
                    tbl->nodes[hval] = node; // Insert at the beginning
                node->hash_next = lnode;
                tbl->n++; 
                return true;
            }    
            
            pnode = lnode;    
            lnode = lnode->hash_next;
        }
        // Insert at the end
        pnode->hash_next = node;
        node->hash_next  = NULL;
        tbl->n++; 
        return true;
    }
}

static fatfs_node_t*
node_hash_find(fatfs_hash_table_t *tbl, 
               const char         *name,
               unsigned int        namelen,
               unsigned int        parent_cluster)
{   
    unsigned int  hval; 
    fatfs_node_t *node;

    // Calculate hash of name and get the first node in slot
    hval = hash_fn(name, namelen) % tbl->size;
    node = tbl->nodes[hval];

    CYG_TRACE2(TNC, "name='%s' hval=%d\n", name, hval);
 
    // Find the node in list wich matches the 
    // given name and parent_cluster
    while (node != NULL)
    {
        // First compare the parent cluster number and 
        // check filename length since it is faster than 
        // comparing filenames
        if (parent_cluster == node->dentry.parent_cluster &&
            '\0' == node->dentry.filename[namelen])
        {
            int i = strncasecmp(node->dentry.filename, name, namelen);

            if (i == 0)
                return node;
            else if (i > 0)
                return NULL; // Stop searching - we have a 
                             // sorted list so there can't be
                             // any matching filename further on
                             // if i > 0 - look at node_hash_add
        }
        node = node->hash_next;
    }
    
    // No such node found
    return NULL; 
}

static bool
node_hash_remove_keyless(fatfs_hash_table_t *tbl, fatfs_node_t *node)
{
    int i;
    fatfs_node_t *lnode, *pnode;

    // Look in all slots, since we have no key
    for (i = 0; i < tbl->size; i++)
    {
        // Look in list and remove it if there
        lnode = tbl->nodes[i];
        pnode = NULL;
        while (lnode != NULL)
        {
            if (lnode == node)
            {
                if (pnode == NULL)
                    tbl->nodes[i]    = lnode->hash_next;
                else
                    pnode->hash_next = lnode->hash_next;
                node->hash_next = NULL;
                tbl->n--;
            
                // All done
                return true;
            }
            pnode = lnode;
            lnode = lnode->hash_next;
        }    
    }
    return false;
}

static bool 
node_hash_remove(fatfs_hash_table_t *tbl, fatfs_node_t *node)
{
    unsigned int hval;
    fatfs_node_t *lnode, *pnode;
   
    // Calculate hash of name and get the first node in slot
    hval = hash_fn(node->dentry.filename, 
                   strlen(node->dentry.filename)) % tbl->size;
    lnode = tbl->nodes[hval];

    // Now find the node in list and remove it
    pnode = NULL;
    while (lnode != NULL)
    {
        if (lnode == node)
        {
            if (pnode == NULL)
                tbl->nodes[hval] = lnode->hash_next;
            else
                pnode->hash_next = lnode->hash_next;
            node->hash_next = NULL;
            tbl->n--;