//==========================================================================////      fatfs_ncache.c////      FAT file system node cache functions////==========================================================================//####ECOSGPLCOPYRIGHTBEGIN####// -------------------------------------------// This file is part of eCos, the Embedded Configurable Operating System.// Copyright (C) 2003 Savin Zlobec //// 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 // Date:                2003-06-26////####DESCRIPTIONEND####////==========================================================================#include "cyg_type.h"#include "cyg_ass.h"#include "types.h"#include "fatfs.h"#include "stdio.h"#include "malloc.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 regardless of node allocation treshold - it // should always be >= 2 or the file finding code may not// work correctly!#define DLIST_KEEP_NUM 2 //==========================================================================// Node list functions static voidnode_list_init(fatfs_node_list_t *list){    list->size = 0;    list->first = list->last = NULL;}static int node_list_get_size(fatfs_node_list_t *list){    return (list->size);}static fatfs_node_t*node_list_get_head(fatfs_node_list_t *list){    return (list->first);}static fatfs_node_t*node_list_get_tail(fatfs_node_list_t *list){    return (list->last);}static fatfs_node_t*node_list_get_next(fatfs_node_t *node){    return (node->list_next);}static fatfs_node_t*node_list_get_prev(fatfs_node_t *node){    return (node->list_prev);}static boolnode_list_is_last(fatfs_node_t *node){    return (NULL == node->list_next);}static boolnode_list_is_first(fatfs_node_t *node){    return (NULL == node->list_prev);}static voidnode_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 0static fatfs_node_t*node_list_head_get(fatfs_node_list_t *list){    return list->first;}static voidnode_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++;}#endifstatic fatfs_node_t*node_list_tail_get(fatfs_node_list_t *list){    return list->last;}static voidnode_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_XCHECKSstatic voidnode_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 voidnode_lists_check(fatfs_disk_t* disk){    node_list_check(&disk->live_nlist, 1, 99999);                            node_list_check(&disk->dead_nlist, 0, 0);                               if ((disk->live_nlist.size + disk->dead_nlist.size) >         FATFS_NODE_ALLOC_THRESHOLD)        CYG_ASSERTC(disk->dead_nlist.size <= DLIST_KEEP_NUM);}#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 voidnode_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 boolnode_hash_add(fatfs_hash_table_t *tbl, fatfs_node_t *node){    unsigned int hval;       // Calculate hash of given node filename    hval = hash_fn(node->filename, strlen(node->filename)) % tbl->size;    printf( "name='%s' hval=%d", node->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->filename, node->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];    printf( "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->parent_cluster &&            '\0' == node->filename[namelen])        {            int i = strncasecmp(node->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 boolnode_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->filename, strlen(node->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--;                        // All done            return true;        }        pnode = lnode;        lnode = lnode->hash_next;    }     // Node not in list     return false;}#ifdef USE_XCHECKSstatic void