- pre3:

[davej-history.git] / fs / hfs / catalog.c

/*
 * linux/fs/hfs/catalog.c
 *
 * Copyright (C) 1995-1997  Paul H. Hargrove
 * This file may be distributed under the terms of the GNU Public License.
 *
 * This file contains the functions related to the catalog B-tree.
 *
 * "XXX" in a comment is a note to myself to consider changing something.
 *
 * Cache code shamelessly stolen from 
 *     linux/fs/inode.c Copyright (C) 1991, 1992  Linus Torvalds
 *     re-shamelessly stolen Copyright (C) 1997 Linus Torvalds
 *
 * In function preconditions the term "valid" applied to a pointer to
 * a structure means that the pointer is non-NULL and the structure it
 * points to has all fields initialized to consistent values.
 *
 * The code in this file initializes some structures by calling
 * memset(&foo, 0, sizeof(foo)).  This produces the desired behavior
 * only due to the non-ANSI assumption that the machine representation
 */

#include "hfs.h"

/*================ Variable-like macros ================*/

/* Number of hash table slots */
#define C_HASHBITS  10
#define C_HASHSIZE  (1UL << C_HASHBITS)
#define C_HASHMASK  (C_HASHSIZE - 1)

/* Number of entries to fit in a single page on an i386.
 * Actually, now it's used to increment the free entry pool. */
#define CCACHE_INC (PAGE_SIZE/sizeof(struct hfs_cat_entry))
#define CCACHE_MAX (CCACHE_INC * 8)

/*================ File-local data types ================*/

/* The catalog record for a file */
typedef struct {
        hfs_byte_t      Flags;          /* Flags such as read-only */
        hfs_byte_t      Typ;            /* file version number = 0 */
        hfs_finfo_t     UsrWds;         /* data used by the Finder */
        hfs_lword_t     FlNum;          /* The CNID */
        hfs_word_t      StBlk;          /* obsolete */
        hfs_lword_t     LgLen;          /* The logical EOF of the data fork*/
        hfs_lword_t     PyLen;          /* The physical EOF of the data fork */
        hfs_word_t      RStBlk;         /* obsolete */
        hfs_lword_t     RLgLen;         /* The logical EOF of the rsrc fork */
        hfs_lword_t     RPyLen;         /* The physical EOF of the rsrc fork */
        hfs_lword_t     CrDat;          /* The creation date */
        hfs_lword_t     MdDat;          /* The modified date */
        hfs_lword_t     BkDat;          /* The last backup date */
        hfs_fxinfo_t    FndrInfo;       /* more data for the Finder */
        hfs_word_t      ClpSize;        /* number of bytes to allocate
                                           when extending files */
        hfs_byte_t      ExtRec[12];     /* first extent record
                                           for the data fork */
        hfs_byte_t      RExtRec[12];    /* first extent record
                                           for the resource fork */
        hfs_lword_t     Resrv;          /* reserved by Apple */
} __attribute__((packed)) FIL_REC;

/* the catalog record for a directory */
typedef struct {
        hfs_word_t      Flags;          /* flags */
        hfs_word_t      Val;            /* Valence: number of files and
                                           dirs in the directory */
        hfs_lword_t     DirID;          /* The CNID */
        hfs_lword_t     CrDat;          /* The creation date */
        hfs_lword_t     MdDat;          /* The modification date */
        hfs_lword_t     BkDat;          /* The last backup date */
        hfs_dinfo_t     UsrInfo;        /* data used by the Finder */
        hfs_dxinfo_t    FndrInfo;       /* more data used by Finder */
        hfs_byte_t      Resrv[16];      /* reserved by Apple */
} __attribute__((packed)) DIR_REC;

/* the catalog record for a thread */
typedef struct {
        hfs_byte_t              Reserv[8];      /* reserved by Apple */
        hfs_lword_t             ParID;          /* CNID of parent directory */
        struct hfs_name         CName;          /* The name of this entry */
}  __attribute__((packed)) THD_REC;

/* A catalog tree record */
struct hfs_cat_rec {
        hfs_byte_t              cdrType;        /* The type of entry */
        hfs_byte_t              cdrResrv2;      /* padding */
        union {
                FIL_REC fil;
                DIR_REC dir;
                THD_REC thd;
        } u;
} __attribute__((packed));

/*================ File-local variables ================*/
 
static LIST_HEAD(entry_in_use);
static LIST_HEAD(entry_unused);
static struct list_head hash_table[C_HASHSIZE];

spinlock_t entry_lock = SPIN_LOCK_UNLOCKED;

static struct {
        int nr_entries;
        int nr_free_entries;
} entries_stat;

/*================ File-local functions ================*/

/*
 * brec_to_id
 *
 * Get the CNID from a brec
 */
static inline hfs_u32 brec_to_id(struct hfs_brec *brec)
{
        struct hfs_cat_rec *rec = brec->data;

        return hfs_get_nl((rec->cdrType==HFS_CDR_FIL) ?
                                rec->u.fil.FlNum : rec->u.dir.DirID);
}

/*
 * hashfn()
 *
 * hash an (struct mdb *) and a (struct hfs_cat_key *) to an integer.
 */
static inline unsigned int hashfn(const struct hfs_mdb *mdb,
                                  const struct hfs_cat_key *key)
{
        unsigned int hash;
        
        hash = (unsigned long) mdb | (unsigned long) key->ParID[3] | 
                hfs_strhash(key->CName.Name, key->CName.Len);
        hash = hash ^ (hash >> C_HASHBITS) ^ (hash >> C_HASHBITS*2);
        return hash & C_HASHMASK;
}

/*
 * hash()
 *
 * hash an (struct mdb *) and a (struct hfs_cat_key *)
 * to a pointer to a slot in the hash table.
 */
static inline struct list_head *hash(struct hfs_mdb *mdb,
                                     const struct hfs_cat_key *key)
{
        return hash_table + hashfn(mdb, key);
}

static inline void insert_hash(struct hfs_cat_entry *entry)
{
        struct list_head *head = hash(entry->mdb, &entry->key);
        list_add(&entry->hash, head);
}

static inline void remove_hash(struct hfs_cat_entry *entry)
{
        list_del(&entry->hash);
        INIT_LIST_HEAD(&entry->hash);
}

/*
 * wait_on_entry()
 *
 * Sleep until a locked entry is unlocked.
 */
static inline void wait_on_entry(struct hfs_cat_entry * entry)
{
        while ((entry->state & HFS_LOCK)) {
                hfs_sleep_on(&entry->wait);
        }
}

/*
 * lock_entry()
 *
 * Obtain an exclusive lock on an entry.
 */
static void lock_entry(struct hfs_cat_entry * entry)
{
        wait_on_entry(entry);
        spin_lock(&entry_lock);
        entry->state |= HFS_LOCK;
        spin_unlock(&entry_lock);
}

/*
 * lock_entry()
 *
 * Relinquish an exclusive lock on an entry.
 */
static void unlock_entry(struct hfs_cat_entry * entry)
{
        spin_lock(&entry_lock);
        entry->state &= ~HFS_LOCK;
        spin_unlock(&entry_lock);
        hfs_wake_up(&entry->wait);
}

/* put entry on mdb dirty list. */
void hfs_cat_mark_dirty(struct hfs_cat_entry *entry)
{
        struct hfs_mdb *mdb = entry->mdb;

        spin_lock(&entry_lock);
        if (!(entry->state & HFS_DIRTY)) {
                entry->state |= HFS_DIRTY;

                /* Only add valid (ie hashed) entries to the dirty list. */
                if (!list_empty(&entry->hash)) {
                        list_del(&entry->list);
                        list_add(&entry->list, &mdb->entry_dirty);
                }
        }
        spin_unlock(&entry_lock);
}

/* delete an entry and remove it from the hash table. */
static void delete_entry(struct hfs_cat_entry *entry)
{
        if (!(entry->state & HFS_DELETED)) {
                entry->state |= HFS_DELETED;
                list_del(&entry->hash);
                INIT_LIST_HEAD(&entry->hash);

                if (entry->type == HFS_CDR_FIL) {
                  /* free all extents */
                  entry->u.file.data_fork.lsize = 0;
                  hfs_extent_adj(&entry->u.file.data_fork);
                  entry->u.file.rsrc_fork.lsize = 0;
                  hfs_extent_adj(&entry->u.file.rsrc_fork);
                }
        }
}


static inline void init_entry(struct hfs_cat_entry *entry)
{
        memset(entry, 0, sizeof(*entry));
        hfs_init_waitqueue(&entry->wait);
        INIT_LIST_HEAD(&entry->hash);
        INIT_LIST_HEAD(&entry->list);
}

/*
 * hfs_cat_alloc()
 *
 * Try to allocate another entry. 
 */
static inline struct hfs_cat_entry *hfs_cat_alloc(void)
{
        struct hfs_cat_entry *entry;

        if (!HFS_NEW(entry))
                return NULL;

        init_entry(entry);
        return entry;
}

/* this gets called with the spinlock held. */
static int grow_entries(void)
{
        struct hfs_cat_entry *entry;
        int i;
        
        for (i = 0; i < CCACHE_INC; i++) {
                if (!(entry = hfs_cat_alloc()))
                        break;
                list_add(&entry->list, &entry_unused);
        }

        entries_stat.nr_entries += i;
        entries_stat.nr_free_entries += i;
                
        return i;
}

/*
 * __read_entry()
 *
 * Convert a (struct hfs_cat_rec) to a (struct hfs_cat_entry).
 */
static void __read_entry(struct hfs_cat_entry *entry,
                         const struct hfs_cat_rec *cat)
{
        entry->type = cat->cdrType;

        if (cat->cdrType == HFS_CDR_DIR) {
                struct hfs_dir *dir = &entry->u.dir;

                entry->cnid = hfs_get_nl(cat->u.dir.DirID);

                dir->magic = HFS_DIR_MAGIC;
                dir->flags = hfs_get_ns(cat->u.dir.Flags);
                memcpy(&entry->info.dir.dinfo, &cat->u.dir.UsrInfo, 16);
                memcpy(&entry->info.dir.dxinfo, &cat->u.dir.FndrInfo, 16);
                entry->create_date = hfs_get_nl(cat->u.dir.CrDat);
                entry->modify_date = hfs_get_nl(cat->u.dir.MdDat);
                entry->backup_date = hfs_get_nl(cat->u.dir.BkDat);
                dir->dirs = dir->files = 0;
                hfs_init_waitqueue(&dir->read_wait);
                hfs_init_waitqueue(&dir->write_wait);
        } else if (cat->cdrType == HFS_CDR_FIL) {
                struct hfs_file *fil = &entry->u.file;

                entry->cnid = hfs_get_nl(cat->u.fil.FlNum);

                fil->magic = HFS_FILE_MAGIC;

                fil->data_fork.fork = HFS_FK_DATA;
                fil->data_fork.entry = entry;
                fil->data_fork.lsize = hfs_get_hl(cat->u.fil.LgLen);
                fil->data_fork.psize = hfs_get_hl(cat->u.fil.PyLen) >>
                                                     HFS_SECTOR_SIZE_BITS;
                hfs_extent_in(&fil->data_fork, cat->u.fil.ExtRec);

                fil->rsrc_fork.fork = HFS_FK_RSRC;
                fil->rsrc_fork.entry = entry;
                fil->rsrc_fork.lsize = hfs_get_hl(cat->u.fil.RLgLen);
                fil->rsrc_fork.psize = hfs_get_hl(cat->u.fil.RPyLen) >>
                                                     HFS_SECTOR_SIZE_BITS;
                hfs_extent_in(&fil->rsrc_fork, cat->u.fil.RExtRec);

                memcpy(&entry->info.file.finfo, &cat->u.fil.UsrWds, 16);
                memcpy(&entry->info.file.fxinfo, &cat->u.fil.FndrInfo, 16);

                entry->create_date = hfs_get_nl(cat->u.fil.CrDat);
                entry->modify_date = hfs_get_nl(cat->u.fil.MdDat);
                entry->backup_date = hfs_get_nl(cat->u.fil.BkDat);
                fil->clumpablks = (hfs_get_hs(cat->u.fil.ClpSize)
                                        / entry->mdb->alloc_blksz)
                                                >> HFS_SECTOR_SIZE_BITS;
                fil->flags = cat->u.fil.Flags;
        } else {
                hfs_warn("hfs_fs: entry is neither file nor directory!\n");
        }
}

/*
 * count_dir_entries()
 *
 * Count the number of files and directories in a given directory.
 */
static inline void count_dir_entries(struct hfs_cat_entry *entry,
                                     struct hfs_brec *brec)
{
        int error = 0;
        hfs_u32 cnid;
        hfs_u8 type;

        if (!hfs_cat_open(entry, brec)) {
                while (!(error = hfs_cat_next(entry, brec, 1, &cnid, &type))) {
                        if (type == HFS_CDR_FIL) {
                                ++entry->u.dir.files;
                        } else if (type == HFS_CDR_DIR) {
                                ++entry->u.dir.dirs;
                        }
                } /* -ENOENT is normal termination */
        }
        if (error != -ENOENT) {
                entry->cnid = 0;
        }
}

/*
 * read_entry()
 *
 * Convert a (struct hfs_brec) to a (struct hfs_cat_entry).
 */
static inline void read_entry(struct hfs_cat_entry *entry,
                              struct hfs_brec *brec)
{
        int need_count;
        struct hfs_cat_rec *rec = brec->data;

        __read_entry(entry, rec);

        need_count = (rec->cdrType == HFS_CDR_DIR) && rec->u.dir.Val;

        hfs_brec_relse(brec, NULL);

        if (need_count) {
                count_dir_entries(entry, brec);
        }
}

/*
 * __write_entry()
 *
 * Convert a (struct hfs_cat_entry) to a (struct hfs_cat_rec).
 */
static void __write_entry(const struct hfs_cat_entry *entry,
                          struct hfs_cat_rec *cat)
{
        if (entry->type == HFS_CDR_DIR) {
                const struct hfs_dir *dir = &entry->u.dir;

                hfs_put_ns(dir->flags,             cat->u.dir.Flags);
                hfs_put_hs(dir->dirs + dir->files, cat->u.dir.Val);
                hfs_put_nl(entry->cnid,            cat->u.dir.DirID);
                hfs_put_nl(entry->create_date,     cat->u.dir.CrDat);
                hfs_put_nl(entry->modify_date,     cat->u.dir.MdDat);
                hfs_put_nl(entry->backup_date,     cat->u.dir.BkDat);
                memcpy(&cat->u.dir.UsrInfo, &entry->info.dir.dinfo, 16);
                memcpy(&cat->u.dir.FndrInfo, &entry->info.dir.dxinfo, 16);
        } else if (entry->type == HFS_CDR_FIL) {
                const struct hfs_file *fil = &entry->u.file;

                cat->u.fil.Flags = fil->flags;
                hfs_put_nl(entry->cnid,            cat->u.fil.FlNum);
                memcpy(&cat->u.fil.UsrWds, &entry->info.file.finfo, 16);
                hfs_put_hl(fil->data_fork.lsize, cat->u.fil.LgLen);
                hfs_put_hl(fil->data_fork.psize << HFS_SECTOR_SIZE_BITS,
                                                        cat->u.fil.PyLen);
                hfs_put_hl(fil->rsrc_fork.lsize, cat->u.fil.RLgLen);
                hfs_put_hl(fil->rsrc_fork.psize << HFS_SECTOR_SIZE_BITS,
                                                        cat->u.fil.RPyLen);
                hfs_put_nl(entry->create_date,     cat->u.fil.CrDat);
                hfs_put_nl(entry->modify_date,     cat->u.fil.MdDat);
                hfs_put_nl(entry->backup_date,     cat->u.fil.BkDat);
                memcpy(&cat->u.fil.FndrInfo, &entry->info.file.fxinfo, 16);
                hfs_put_hs((fil->clumpablks * entry->mdb->alloc_blksz)
                                << HFS_SECTOR_SIZE_BITS, cat->u.fil.ClpSize);
                hfs_extent_out(&fil->data_fork, cat->u.fil.ExtRec);
                hfs_extent_out(&fil->rsrc_fork, cat->u.fil.RExtRec);
        } else {
                hfs_warn("__write_entry: invalid entry\n");
        }
}

/*
 * write_entry()
 *
 * Write a modified entry back to the catalog B-tree. this gets called
 * with the entry locked.
 */
static void write_entry(struct hfs_cat_entry * entry)
{
        struct hfs_brec brec;
        int error;

        if (!(entry->state & HFS_DELETED)) {
                error = hfs_bfind(&brec, entry->mdb->cat_tree,
                                  HFS_BKEY(&entry->key), HFS_BFIND_WRITE);
                if (!error) {
                        if ((entry->state & HFS_KEYDIRTY)) {
                                /* key may have changed case due to a rename */
                                entry->state &= ~HFS_KEYDIRTY;
                                if (brec.key->KeyLen != entry->key.KeyLen) {
                                        hfs_warn("hfs_write_entry: key length "
                                                 "changed!\n");
                                        error = 1;
                                } else {
                                        memcpy(brec.key, &entry->key,
                                               entry->key.KeyLen);
                                }
                        } else if (entry->cnid != brec_to_id(&brec)) {
                                hfs_warn("hfs_write_entry: CNID "
                                         "changed unexpectedly!\n");
                                error = 1;
                        }
                        if (!error) {
                                __write_entry(entry, brec.data);
                        }
                        hfs_brec_relse(&brec, NULL);
                }
                if (error) {
                        hfs_warn("hfs_write_entry: unable to write "
                                 "entry %08x\n", entry->cnid);
                }
        }
}


/* this gets called with the spinlock held. */
static struct hfs_cat_entry *find_entry(struct hfs_mdb *mdb,
                                        const struct hfs_cat_key *key)
{
        struct list_head *tmp, *head = hash(mdb, key);
        struct hfs_cat_entry * entry;

        tmp = head;
        for (;;) {
                tmp = tmp->next;
                entry = NULL;
                if (tmp == head)
                        break;
                entry = list_entry(tmp, struct hfs_cat_entry, hash);
                if (entry->mdb != mdb)
                        continue;
                if (hfs_cat_compare(&entry->key, key)) {
                        continue;
                }
                entry->count++;
                break;
        }

        return entry;
}


/* be careful. this gets called with the spinlock held. */
static struct hfs_cat_entry *get_new_entry(struct hfs_mdb *mdb,
                                           const struct hfs_cat_key *key,
                                           const int read)
{
        struct hfs_cat_entry *entry;
        struct list_head *head = hash(mdb, key);
        struct list_head *tmp;

add_new_entry:
        tmp = entry_unused.next;
        if ((tmp != &entry_unused) ) {
                list_del(tmp);
                entries_stat.nr_free_entries--;
                entry = list_entry(tmp, struct hfs_cat_entry, list);
                list_add(&entry->list, &entry_in_use);
                list_add(&entry->hash, head);
                entry->mdb = mdb;
                entry->count = 1;
                memcpy(&entry->key, key, sizeof(*key));
                entry->state = HFS_LOCK;
                spin_unlock(&entry_lock);

                if (read) {
                   struct hfs_brec brec;

                   if (hfs_bfind(&brec, mdb->cat_tree,
                                 HFS_BKEY(key), HFS_BFIND_READ_EQ)) {
                        /* uh oh. we failed to read the record.
                         * the entry doesn't actually exist. */
                        goto read_fail;
                   }

                   read_entry(entry, &brec);
                   
                   /* error */
                   if (!entry->cnid) {
                        goto read_fail;
                   }

                   /* we don't have to acquire a spinlock here or
                    * below for the unlocking bits as we're the first
                    * user of this entry. */
                   entry->state &= ~HFS_LOCK;
                   hfs_wake_up(&entry->wait);
                }

                return entry;
        }


        /* try to allocate more entries. grow_entries() doesn't release
         * the spinlock. */
        if (grow_entries())
                goto add_new_entry;

        spin_unlock(&entry_lock);
        return NULL;

read_fail: 
        /* short-cut hfs_cat_put by doing everything here. */
        spin_lock(&entry_lock);
        list_del(&entry->hash);
        list_del(&entry->list);
        init_entry(entry);
        list_add(&entry->list, &entry_unused);
        entries_stat.nr_free_entries++;
        spin_unlock(&entry_lock);
        return NULL;
}

/*
 * get_entry()
 *
 * Try to return an entry for the indicated file or directory.
 * If ('read' == 0) then no attempt will be made to read it from disk
 * and a locked, but uninitialized, entry is returned.
 */
static struct hfs_cat_entry *get_entry(struct hfs_mdb *mdb,
                                       const struct hfs_cat_key *key,
                                       const int read)
{
        struct hfs_cat_entry * entry;

#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
        hfs_warn("hfs_get_entry: mdb=%p key=%s read=%d\n",
                 mdb, key->CName.Name, read);
#endif

        spin_lock(&entry_lock);
        entry = find_entry(mdb, key);
        if (!entry) {
                return get_new_entry(mdb, key, read);
        }
        spin_unlock(&entry_lock);
        wait_on_entry(entry);
        return entry;
}

/* 
 * new_cnid()
 *
 * Allocate a CNID to use for a new file or directory.
 */
static inline hfs_u32 new_cnid(struct hfs_mdb *mdb)
{
        /* If the create succeeds then the mdb will get dirtied */
        return htonl(mdb->next_id++);
}

/*
 * update_dir()
 *
 * Update counts, times and dirt on a changed directory
 */
static void update_dir(struct hfs_mdb *mdb, struct hfs_cat_entry *dir,
                       int is_dir, int count)
{
        /* update counts */
        if (is_dir) {
                mdb->dir_count += count;
                dir->u.dir.dirs += count;
                if (dir->cnid == htonl(HFS_ROOT_CNID)) {
                        mdb->root_dirs += count;
                }
        } else {
                mdb->file_count += count;
                dir->u.dir.files += count;
                if (dir->cnid == htonl(HFS_ROOT_CNID)) {
                        mdb->root_files += count;
                }
        }
        
        /* update times and dirt */
        dir->modify_date = hfs_time();
        hfs_cat_mark_dirty(dir);
}

/*
 * Add a writer to dir, excluding readers.
 *
 * XXX: this is wrong. it allows a move to occur when a directory
 *      is being written to. 
 */
static inline void start_write(struct hfs_cat_entry *dir)
{
        if (dir->u.dir.readers || waitqueue_active(&dir->u.dir.read_wait)) {
                hfs_sleep_on(&dir->u.dir.write_wait);
        }
        ++dir->u.dir.writers;
}

/*
 * Add a reader to dir, excluding writers.
 */
static inline void start_read(struct hfs_cat_entry *dir)
{
        if (dir->u.dir.writers || waitqueue_active(&dir->u.dir.write_wait)) {
                hfs_sleep_on(&dir->u.dir.read_wait);
        }
        ++dir->u.dir.readers;
}

/*
 * Remove a writer from dir, possibly admitting readers.
 */
static inline void end_write(struct hfs_cat_entry *dir)
{
        if (!(--dir->u.dir.writers)) {
                hfs_wake_up(&dir->u.dir.read_wait);
        }
}

/*
 * Remove a reader from dir, possibly admitting writers.
 */
static inline void end_read(struct hfs_cat_entry *dir)
{
        if (!(--dir->u.dir.readers)) {
                hfs_wake_up(&dir->u.dir.write_wait);
        }
}

/*
 * create_entry()
 *
 * Add a new file or directory to the catalog B-tree and
 * return a (struct hfs_cat_entry) for it in '*result'.
 */
static int create_entry(struct hfs_cat_entry *parent, struct hfs_cat_key *key,
                        const struct hfs_cat_rec *record, int is_dir,
                        hfs_u32 cnid, struct hfs_cat_entry **result)
{
        struct hfs_mdb *mdb = parent->mdb;
        struct hfs_cat_entry *entry;
        struct hfs_cat_key thd_key;
        struct hfs_cat_rec thd_rec;
        int error, has_thread;

        if (result) {
                *result = NULL;
        }

        /* keep readers from getting confused by changing dir size */
        start_write(parent);

        /* create a locked entry in the cache */
        entry = get_entry(mdb, key, 0);
        if (!entry) {
                /* The entry exists but can't be read */
                error = -EIO;
                goto done;
        }

        if (entry->cnid) {
                /* The (unlocked) entry exists in the cache */
                error = -EEXIST;
                goto bail2;
        }

        /* limit directory valence to signed 16-bit integer */
        if ((parent->u.dir.dirs + parent->u.dir.files) >= HFS_MAX_VALENCE) {
                error = -ENOSPC;
                goto bail1;
        }

        has_thread = is_dir || (record->u.fil.Flags & HFS_FIL_THD);

        if (has_thread) {
                /* init some fields for the thread record */
                memset(&thd_rec, 0, sizeof(thd_rec));
                thd_rec.cdrType = is_dir ? HFS_CDR_THD : HFS_CDR_FTH;
                memcpy(&thd_rec.u.thd.ParID, &key->ParID,
                       sizeof(hfs_u32) + sizeof(struct hfs_name));

                /* insert the thread record */
                hfs_cat_build_key(cnid, NULL, &thd_key);
                error = hfs_binsert(mdb->cat_tree, HFS_BKEY(&thd_key),
                                    &thd_rec, 2 + sizeof(THD_REC));
                if (error) {
                        goto bail1;
                }
        }

        /* insert the record */
        error = hfs_binsert(mdb->cat_tree, HFS_BKEY(key), record,
                                is_dir ?  2 + sizeof(DIR_REC) :
                                          2 + sizeof(FIL_REC));
        if (error) {
                if (has_thread && (error != -EIO)) {
                        /* at least TRY to remove the thread record */
                        (void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(&thd_key));
                }
                goto bail1;
        }

        /* update the parent directory */
        update_dir(mdb, parent, is_dir, 1);

        /* complete the cache entry and return success */
        __read_entry(entry, record);
        unlock_entry(entry);

        if (result) {
                *result = entry;
        } else {
                hfs_cat_put(entry);
        }
        goto done;

bail1:
        /* entry really didn't exist, so we don't need to really delete it.
         * we do need to remove it from the hash, though. */
        entry->state |= HFS_DELETED;
        remove_hash(entry);
        unlock_entry(entry);
bail2:
        hfs_cat_put(entry);
done:
        end_write(parent);
        return error;
}

/*================ Global functions ================*/

/* 
 * hfs_cat_put()
 *
 * Release an entry we aren't using anymore.
 *
 * nothing in hfs_cat_put goes to sleep now except on the initial entry.  
 */
void hfs_cat_put(struct hfs_cat_entry * entry)
{
        if (entry) {
                wait_on_entry(entry);

                /* just in case. this should never happen. */
                if (!entry->count) { 
                  hfs_warn("hfs_cat_put: trying to free free entry: %p\n",
                           entry);
                  return;
                }

#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
                hfs_warn("hfs_cat_put: %p(%u) type=%d state=%lu\n", 
                         entry, entry->count, entry->type, entry->state);
#endif
                spin_lock(&entry_lock);
                if (!--entry->count) {
                        if ((entry->state & HFS_DELETED))
                                goto entry_deleted;

                        if ((entry->type == HFS_CDR_FIL)) {
                                /* clear out any cached extents */
                                if (entry->u.file.data_fork.first.next) {
                                  hfs_extent_free(&entry->u.file.data_fork);
                                }
                                if (entry->u.file.rsrc_fork.first.next) {
                                  hfs_extent_free(&entry->u.file.rsrc_fork);
                                }
                        }

                        /* if we put a dirty entry, write it out. */
                        if ((entry->state & HFS_DIRTY)) {
                                entry->state ^= HFS_DIRTY | HFS_LOCK;
                                write_entry(entry);
                                entry->state &= ~HFS_LOCK;
                        }

                        list_del(&entry->hash);
entry_deleted:          /* deleted entries have already been removed
                         * from the hash list. */
                        list_del(&entry->list);
                        if (entries_stat.nr_free_entries > CCACHE_MAX) {
                                HFS_DELETE(entry);
                                entries_stat.nr_entries--;
                        } else {
                                init_entry(entry);
                                list_add(&entry->list, &entry_unused);
                                entries_stat.nr_free_entries++;
                        }
                }
                spin_unlock(&entry_lock);
        }
}

/* 
 * hfs_cat_get()
 *
 * Wrapper for get_entry() which always calls with ('read'==1).
 * Used for access to get_entry() from outside this file.
 */
struct hfs_cat_entry *hfs_cat_get(struct hfs_mdb *mdb,
                                  const struct hfs_cat_key *key)
{
        return get_entry(mdb, key, 1);
}

/* invalidate all entries for a device */
static void invalidate_list(struct list_head *head, struct hfs_mdb *mdb,
                            struct list_head *dispose)
{
        struct list_head *next;

        next = head->next;
        for (;;) {
                struct list_head *tmp = next;
                struct hfs_cat_entry * entry;
                
                next = next->next;
                if (tmp == head)
                        break;
                entry = list_entry(tmp, struct hfs_cat_entry, list);
                if (entry->mdb != mdb) {
                        continue;
                }

                if (!entry->count) {
                        list_del(&entry->hash);
                        INIT_LIST_HEAD(&entry->hash);
                        list_del(&entry->list);
                        list_add(&entry->list, dispose);
                        continue;
                }
                
                hfs_warn("hfs_fs: entry %p(%u) busy on removed device %s.\n",
                         entry, entry->count, 
                         hfs_mdb_name(entry->mdb->sys_mdb));
        }
}

/* delete entries from a list */
static void delete_list(struct list_head *head) 
{
        struct list_head *next = head->next;
        struct hfs_cat_entry *entry;
        
        for (;;) {
                struct list_head * tmp = next;

                next = next->next;
                if (tmp == head) {
                        break;
                }
                entry = list_entry(tmp, struct hfs_cat_entry, list);
                HFS_DELETE(entry);
        }
}

/* 
 * hfs_cat_invalidate()
 *
 * Called by hfs_mdb_put() to remove all the entries
 * in the cache that are associated with a given MDB.
 */
void hfs_cat_invalidate(struct hfs_mdb *mdb)
{
        LIST_HEAD(throw_away);

        spin_lock(&entry_lock);
        invalidate_list(&entry_in_use, mdb, &throw_away);
        invalidate_list(&mdb->entry_dirty, mdb, &throw_away);
        spin_unlock(&entry_lock);

        delete_list(&throw_away);
#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
        hfs_warn("hfs_cat_invalidate: free=%d total=%d\n",
                 entries_stat.nr_free_entries,
                 entries_stat.nr_entries);
#endif
}

/*
 * hfs_cat_commit()
 *
 * Called by hfs_mdb_commit() to write dirty entries to the disk buffers.
 */
void hfs_cat_commit(struct hfs_mdb *mdb)
{
        struct list_head *tmp, *head = &mdb->entry_dirty;
        struct hfs_cat_entry *entry;

        spin_lock(&entry_lock);
        while ((tmp = head->prev) != head) {
                entry = list_entry(tmp, struct hfs_cat_entry, list);
                  
                if ((entry->state & HFS_LOCK)) {
                        spin_unlock(&entry_lock);
                        wait_on_entry(entry);
                        spin_lock(&entry_lock);
                } else {
                       struct list_head *insert = &entry_in_use;

                       if (!entry->count)
                                insert = entry_in_use.prev;

                       /* add to in_use list */
                       list_del(&entry->list);
                       list_add(&entry->list, insert);

                       /* reset DIRTY, set LOCK */
                       entry->state ^= HFS_DIRTY | HFS_LOCK;
                       spin_unlock(&entry_lock);
                       write_entry(entry);
                       spin_lock(&entry_lock);
                       entry->state &= ~HFS_LOCK;
                       hfs_wake_up(&entry->wait);
                }
        }
        spin_unlock(&entry_lock);
}

/*
 * hfs_cat_free()
 *
 * Releases all the memory allocated in grow_entries().
 * Must call hfs_cat_invalidate() on all MDBs before calling this.
 * This only gets rid of the unused pool of entries. all the other
 * entry references should have either been freed by cat_invalidate
 * or moved onto the unused list.
 */
void hfs_cat_free(void)
{
        delete_list(&entry_unused);
}

/*
 * hfs_cat_compare()
 *
 * Description:
 *   This is the comparison function used for the catalog B-tree.  In
 *   comparing catalog B-tree entries, the parent id is the most
 *   significant field (compared as unsigned ints).  The name field is
 *   the least significant (compared in "Macintosh lexical order",
 *   see hfs_strcmp() in string.c)
 * Input Variable(s):
 *   struct hfs_cat_key *key1: pointer to the first key to compare
 *   struct hfs_cat_key *key2: pointer to the second key to compare
 * Output Variable(s):
 *   NONE
 * Returns:
 *   int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
 * Preconditions:
 *   key1 and key2 point to "valid" (struct hfs_cat_key)s.
 * Postconditions:
 *   This function has no side-effects
 */
int hfs_cat_compare(const struct hfs_cat_key *key1,
                    const struct hfs_cat_key *key2)
{
        unsigned int parents;
        int retval;

        parents = hfs_get_hl(key1->ParID) - hfs_get_hl(key2->ParID);
        if (parents != 0) {
                retval = (int)parents;
        } else {
                retval = hfs_strcmp(key1->CName.Name, key1->CName.Len,
                                    key2->CName.Name, key2->CName.Len);
        }
        return retval;
}

/*
 * hfs_cat_build_key()
 *
 * Given the ID of the parent and the name build a search key.
 */
void hfs_cat_build_key(hfs_u32 parent, const struct hfs_name *cname,
                       struct hfs_cat_key *key)
{
        hfs_put_nl(parent, key->ParID);

        if (cname) {
                key->KeyLen = 6 + cname->Len;
                memcpy(&key->CName, cname, sizeof(*cname));
        } else {
                key->KeyLen = 6;
                memset(&key->CName, 0, sizeof(*cname));
        }
}

/*
 * hfs_cat_open()
 *
 * Given a directory on an HFS filesystem get its thread and
 * lock the directory against insertions and deletions.
 * Return 0 on success or an error code on failure.
 */
int hfs_cat_open(struct hfs_cat_entry *dir, struct hfs_brec *brec)
{
        struct hfs_cat_key key;
        int error;

        if (dir->type != HFS_CDR_DIR) {
                return -EINVAL;
        }
        
        /* Block writers */
        start_read(dir);

        /* Find the directory */
        hfs_cat_build_key(dir->cnid, NULL, &key);
        error = hfs_bfind(brec, dir->mdb->cat_tree,
                          HFS_BKEY(&key), HFS_BFIND_READ_EQ);

        if (error) {
                end_read(dir);
        }

        return error;
}

/*
 * hfs_cat_next()
 *
 * Given a catalog brec structure, replace it with the count'th next brec
 * in the same directory.
 * Return an error code if there is a problem, 0 if OK.
 * Note that an error code of -ENOENT means there are no more entries
 * in this directory.
 * The directory is "closed" on an error.
 */
int hfs_cat_next(struct hfs_cat_entry *dir, struct hfs_brec *brec,
                 hfs_u16 count, hfs_u32 *cnid, hfs_u8 *type)
{
        int error;

        if (!dir || !brec) {
                return -EINVAL;
        }

        /* Get the count'th next catalog tree entry */
        error = hfs_bsucc(brec, count);
        if (!error) {
                struct hfs_cat_key *key = (struct hfs_cat_key *)brec->key;
                if (hfs_get_nl(key->ParID) != dir->cnid) {
                        hfs_brec_relse(brec, NULL);
                        error = -ENOENT;
                }
        }
        if (!error) {
                *type = ((struct hfs_cat_rec *)brec->data)->cdrType;
                *cnid = brec_to_id(brec);
        } else {
                end_read(dir);
        }
        return error;
}

/*
 * hfs_cat_close()
 *
 * Given a catalog brec structure, replace it with the count'th next brec
 * in the same directory.
 * Return an error code if there is a problem, 0 if OK.
 * Note that an error code of -ENOENT means there are no more entries
 * in this directory.
 */
void hfs_cat_close(struct hfs_cat_entry *dir, struct hfs_brec *brec)
{
        if (dir && brec) {
                hfs_brec_relse(brec, NULL);
                end_read(dir);
        }
}

/*
 * hfs_cat_parent()
 *
 * Given a catalog entry, return the entry for its parent.
 * Uses catalog key for the entry to get its parent's ID
 * and then uses the parent's thread record to locate the
 * parent's actual catalog entry.
 */
struct hfs_cat_entry *hfs_cat_parent(struct hfs_cat_entry *entry)
{
        struct hfs_cat_entry *retval = NULL;
        struct hfs_mdb *mdb = entry->mdb;
        struct hfs_brec brec;
        struct hfs_cat_key key;
        int error;

        lock_entry(entry);
        if (!(entry->state & HFS_DELETED)) {
                hfs_cat_build_key(hfs_get_nl(entry->key.ParID), NULL, &key);
                error = hfs_bfind(&brec, mdb->cat_tree,
                                  HFS_BKEY(&key), HFS_BFIND_READ_EQ);
                if (!error) {
                        /* convert thread record to key */
                        struct hfs_cat_rec *rec = brec.data;
                        key.KeyLen = 6 + rec->u.thd.CName.Len;
                        memcpy(&key.ParID, &rec->u.thd.ParID,
                               sizeof(hfs_u32) + sizeof(struct hfs_name));

                        hfs_brec_relse(&brec, NULL);

                        retval = hfs_cat_get(mdb, &key);
                }
        }
        unlock_entry(entry);
        return retval;
}
        
/*
 * hfs_cat_create()
 *
 * Create a new file with the indicated name in the indicated directory.
 * The file will have the indicated flags, type and creator.
 * If successful an (struct hfs_cat_entry) is returned in '*result'.
 */
int hfs_cat_create(struct hfs_cat_entry *parent, struct hfs_cat_key *key,
                   hfs_u8 flags, hfs_u32 type, hfs_u32 creator,
                   struct hfs_cat_entry **result)
{
        struct hfs_cat_rec record;
        hfs_u32 id = new_cnid(parent->mdb);
        hfs_u32 mtime = hfs_time();

#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
        hfs_warn("hfs_cat_create: %p/%s flags=%d res=%p\n",
                 parent, key->CName.Name, flags, result);
#endif
        /* init some fields for the file record */
        memset(&record, 0, sizeof(record));
        record.cdrType = HFS_CDR_FIL;
        record.u.fil.Flags = flags | HFS_FIL_USED;
        hfs_put_nl(id,      record.u.fil.FlNum);
        hfs_put_nl(mtime,   record.u.fil.CrDat);
        hfs_put_nl(mtime,   record.u.fil.MdDat);
        hfs_put_nl(0,       record.u.fil.BkDat);
        hfs_put_nl(type,    record.u.fil.UsrWds.fdType);
        hfs_put_nl(creator, record.u.fil.UsrWds.fdCreator);

        return create_entry(parent, key, &record, 0, id, result);
}

/*
 * hfs_cat_mkdir()
 *
 * Create a new directory with the indicated name in the indicated directory.
 * If successful an (struct hfs_cat_entry) is returned in '*result'.
 */
int hfs_cat_mkdir(struct hfs_cat_entry *parent, struct hfs_cat_key *key,
                  struct hfs_cat_entry **result)
{
        struct hfs_cat_rec record;
        hfs_u32 id = new_cnid(parent->mdb);
        hfs_u32 mtime = hfs_time();

#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
        hfs_warn("hfs_cat_mkdir: %p/%s res=%p\n", parent, key->CName.Name,
                 result);
#endif

        /* init some fields for the directory record */
        memset(&record, 0, sizeof(record));
        record.cdrType = HFS_CDR_DIR;
        hfs_put_nl(id,     record.u.dir.DirID);
        hfs_put_nl(mtime, record.u.dir.CrDat);
        hfs_put_nl(mtime, record.u.dir.MdDat);
        hfs_put_nl(0,     record.u.dir.BkDat);
        hfs_put_hs(0xff,  record.u.dir.UsrInfo.frView);

        return create_entry(parent, key, &record, 1, id, result);
}

/*
 * hfs_cat_delete()
 *
 * Delete the indicated file or directory.
 * The associated thread is also removed unless ('with_thread'==0).
 */
int hfs_cat_delete(struct hfs_cat_entry *parent, struct hfs_cat_entry *entry,
                   int with_thread)
{
        struct hfs_cat_key key;
        struct hfs_mdb *mdb = parent->mdb;
        int is_dir, error = 0;

#if defined(DEBUG_CATALOG) || defined(DEBUG_ALL)
        hfs_warn("hfs_cat_delete: %p/%p type=%d state=%lu, thread=%d\n",
                 parent, entry, entry->type, entry->state, with_thread);
#endif
        if (parent->mdb != entry->mdb) {
                return -EINVAL;
        }

        if (entry->type == HFS_CDR_FIL) {
                with_thread = (entry->u.file.flags&HFS_FIL_THD) && with_thread;
                is_dir = 0;
        } else {
                is_dir = 1;
        }

        /* keep readers from getting confused by changing dir size */
        start_write(parent);

        /* don't delete a busy directory */
        if (entry->type == HFS_CDR_DIR) {
                start_read(entry);

                error = -ENOTEMPTY;
                if (entry->u.dir.files || entry->u.dir.dirs) 
                        goto hfs_delete_end;
        }

        /* try to delete the file or directory */
        lock_entry(entry);
        error = -ENOENT;
        if ((entry->state & HFS_DELETED)) {
                /* somebody beat us to it. */
                goto hfs_delete_unlock;
        }
                
        /* delete the catalog record */
        if ((error = hfs_bdelete(mdb->cat_tree, HFS_BKEY(&entry->key)))) {
                goto hfs_delete_unlock;
        }

        /* Mark the entry deleted and remove it from the cache */
        delete_entry(entry);

        /* try to delete the thread entry if it exists */
        if (with_thread) {
                hfs_cat_build_key(entry->cnid, NULL, &key);
                (void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(&key));
        }
        
        update_dir(mdb, parent, is_dir, -1);

hfs_delete_unlock:
        unlock_entry(entry);

hfs_delete_end:
        if (entry->type == HFS_CDR_DIR) {
                end_read(entry);
        }
        end_write(parent);
        return error;
}

/*
 * hfs_cat_move()
 *
 * Rename a file or directory, possibly to a new directory.
 * If the destination exists it is removed and a
 * (struct hfs_cat_entry) for it is returned in '*result'.
 */
int hfs_cat_move(struct hfs_cat_entry *old_dir, struct hfs_cat_entry *new_dir,
                 struct hfs_cat_entry *entry, struct hfs_cat_key *new_key,
                 struct hfs_cat_entry **removed)
{
        struct hfs_cat_entry *dest;
        struct hfs_mdb *mdb;
        int error = 0;
        int is_dir, has_thread;

        if (removed) {
                *removed = NULL;
        }

        /* sanity checks */
        if (!old_dir || !new_dir) {
                return -EINVAL;
        }
        mdb = old_dir->mdb;
        if (mdb != new_dir->mdb) {
                return -EXDEV;
        }

        /* precompute a few things */
        if (entry->type == HFS_CDR_DIR) {
                is_dir = 1;
                has_thread = 1;
        } else if (entry->type == HFS_CDR_FIL) {
                is_dir = 0;
                has_thread = entry->u.file.flags & HFS_FIL_THD;
        } else {
                return -EINVAL;
        }

        while (mdb->rename_lock) {
                hfs_sleep_on(&mdb->rename_wait);
        }
        spin_lock(&entry_lock);
        mdb->rename_lock = 1; /* XXX: should be atomic_inc */
        spin_unlock(&entry_lock);

        /* keep readers from getting confused by changing dir size */
        start_write(new_dir);
        if (old_dir != new_dir) {
                start_write(old_dir);
        }

        /* Don't move a directory inside itself */
        if (is_dir) {
                struct hfs_cat_key thd_key;
                struct hfs_brec brec;

                hfs_u32 id = new_dir->cnid;
                while (id != htonl(HFS_ROOT_CNID)) {
                        if (id == entry->cnid) {
                                error = -EINVAL;
                        } else {
                                hfs_cat_build_key(id, NULL, &thd_key);
                                error = hfs_bfind(&brec, mdb->cat_tree,
                                                  HFS_BKEY(&thd_key),
                                                  HFS_BFIND_READ_EQ);
                        }
                        if (error) {
                                goto done;
                        } else {
                                struct hfs_cat_rec *rec = brec.data;
                                id = hfs_get_nl(rec->u.thd.ParID);
                                hfs_brec_relse(&brec, NULL);
                        }
                }
        }

restart:
        /* see if the destination exists, getting it if it does */
        dest = hfs_cat_get(mdb, new_key);
        if (!dest) {
                /* destination doesn't exist, so create it */
                struct hfs_cat_rec new_record;

                /* create a locked entry in the cache */
                dest = get_entry(mdb, new_key, 0);
                if (!dest) {
                        error = -EIO;
                        goto done;
                }
                if (dest->cnid) {
                        /* The (unlocked) entry exists in the cache */
                        goto have_distinct;
                }

                /* limit directory valence to signed 16-bit integer */
                if ((new_dir->u.dir.dirs + new_dir->u.dir.files) >=
                                                        HFS_MAX_VALENCE) {
                        error = -ENOSPC;
                        goto bail3;
                }

                /* build the new record. make sure to zero out the
                   record. */
                memset(&new_record, 0, sizeof(new_record));
                new_record.cdrType = entry->type;
                __write_entry(entry, &new_record);

                /* insert the new record */
                error = hfs_binsert(mdb->cat_tree, HFS_BKEY(new_key),
                                    &new_record, is_dir ? 2 + sizeof(DIR_REC) :
                                    2 + sizeof(FIL_REC));
                if (error == -EEXIST) {
                        delete_entry(dest);
                        unlock_entry(dest);
                        hfs_cat_put(dest);
                        goto restart;
                } else if (error) {
                        goto bail3;
                }

                /* update the destination directory */
                update_dir(mdb, new_dir, is_dir, 1);
        } else if (entry != dest) {
have_distinct:
                /* The destination exists and is not same as source */
                lock_entry(dest);
                if ((dest->state & HFS_DELETED)) {
                        unlock_entry(dest);
                        hfs_cat_put(dest);
                        goto restart;
                }
                if (dest->type != entry->type) {
                        /* can't move a file on top
                           of a dir nor vice versa. */
                        error = is_dir ? -ENOTDIR : -EISDIR;
                } else if (is_dir && (dest->u.dir.dirs || dest->u.dir.files)) {
                        /* directory to replace is not empty */
                        error = -ENOTEMPTY;
                }

                if (error) {
                        goto bail2;
                }
        } else {
                /* The destination exists but is same as source */
                --entry->count;
                dest = NULL;
        }

        /* lock the entry */
        lock_entry(entry);
        if ((entry->state & HFS_DELETED)) {
                error = -ENOENT;
                goto bail1;
        }

        if (dest) {
                /* remove the old entry */
                error = hfs_bdelete(mdb->cat_tree, HFS_BKEY(&entry->key));

                if (error) {
                        /* We couldn't remove the entry for the
                           original file, so nothing has changed. */
                        goto bail1;
                }
                update_dir(mdb, old_dir, is_dir, -1);
        }

        /* update the thread of the dir/file we're moving */
        if (has_thread) {
                struct hfs_cat_key thd_key;
                struct hfs_brec brec;

                hfs_cat_build_key(entry->cnid, NULL, &thd_key);
                error = hfs_bfind(&brec, mdb->cat_tree,
                                  HFS_BKEY(&thd_key), HFS_BFIND_WRITE);
                if (error == -ENOENT) {
                        if (is_dir) {
                                /* directory w/o a thread! */
                                error = -EIO;
                        } else {
                                /* We were lied to! */
                                entry->u.file.flags &= ~HFS_FIL_THD;
                                hfs_cat_mark_dirty(entry);
                        }
                }
                if (!error) {
                        struct hfs_cat_rec *rec = brec.data;
                        memcpy(&rec->u.thd.ParID, &new_key->ParID,
                               sizeof(hfs_u32) + sizeof(struct hfs_name));
                        hfs_brec_relse(&brec, NULL);
                } else if (error == -ENOENT) {
                        error = 0;
                } else if (!dest) {
                        /* Nothing was changed */
                        unlock_entry(entry);
                        goto done;
                } else {
                        /* Something went seriously wrong.
                           The dir/file has been deleted. */
                        /* XXX try some recovery? */
                        delete_entry(entry);
                        goto bail1;
                }
        }

        /* TRY to remove the thread for the pre-existing entry */
        if (dest && dest->cnid &&
            (is_dir || (dest->u.file.flags & HFS_FIL_THD))) {
                struct hfs_cat_key thd_key;

                hfs_cat_build_key(dest->cnid, NULL, &thd_key);
                (void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(&thd_key));
        }

        /* update directories */
        new_dir->modify_date = hfs_time();
        hfs_cat_mark_dirty(new_dir);

        /* update key */
        remove_hash(entry);
        memcpy(&entry->key, new_key, sizeof(*new_key));
        /* KEYDIRTY as case might differ */
        entry->state |= HFS_KEYDIRTY;
        insert_hash(entry);
        hfs_cat_mark_dirty(entry);
        unlock_entry(entry);

        /* delete any pre-existing or place-holder entry */
        if (dest) {
                delete_entry(dest);
                unlock_entry(dest);
                if (removed && dest->cnid) {
                        *removed = dest;
                } else {
                        hfs_cat_put(dest);
                }
        }
        goto done;

bail1:
        unlock_entry(entry);
bail2:
        if (dest) {
                if (!dest->cnid) {
                        /* TRY to remove the new entry */
                        (void)hfs_bdelete(mdb->cat_tree, HFS_BKEY(new_key));
                        update_dir(mdb, new_dir, is_dir, -1);
bail3:
                        delete_entry(dest);
                }
                unlock_entry(dest);
                hfs_cat_put(dest);
        }
done:
        if (new_dir != old_dir) {
                end_write(old_dir);
        }
        end_write(new_dir);
        spin_lock(&entry_lock);
        mdb->rename_lock = 0; /* XXX: should use atomic_dec */
        hfs_wake_up(&mdb->rename_wait);
        spin_unlock(&entry_lock);

        return error;
}

/*
 * Initialize the hash tables
 */
void hfs_cat_init(void)
{
        int i;
        struct list_head *head = hash_table;

        i = C_HASHSIZE;
        do {
                INIT_LIST_HEAD(head);
                head++;
                i--;
        } while (i);
}