This is psinode.c in view mode; [Download] [Up]
/*
* Name: psinode.h
* Description: Funtions of pseudo inode handling.
* Author: Christian Starkjohann <cs@hal.kph.tuwien.ac.at>
* Date: 1996-12-06
* Copyright: GNU-GPL
* Tabsize: 4
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <ctype.h>
#include "psinode.h"
#include "my_defines.h"
#define DPRINTF(arg) if(debug_mode & DEBUG_PSINODE) dprintf arg
/* ------------------------------------------------------------------------- */
psinode_table_t psitable; /* table of pseudo-inodes */
long long root_inum; /* pseudo inode numbe for root */
/* ------------------------------------------------------------------------- */
/* CRC table for a polynomial of 0xedb8832048eaaec0 */
static long long crc_tab[256] = {
0x0000000000000000ULL, 0xec63f226087b7b9dULL,
0x03b6e20c8123aabbULL, 0xefd5102a8958d126ULL,
0x076dc41902475576ULL, 0xeb0e363f0a3c2eebULL,
0x04db26158364ffcdULL, 0xe8b8d4338b1f8450ULL,
0x0edb8832048eaaecULL, 0xe2b87a140cf5d171ULL,
0x0d6d6a3e85ad0057ULL, 0xe10e98188dd67bcaULL,
0x09b64c2b06c9ff9aULL, 0xe5d5be0d0eb28407ULL,
0x0a00ae2787ea5521ULL, 0xe6635c018f912ebcULL,
0x1db71064091d55d8ULL, 0xf1d4e24201662e45ULL,
0x1e01f268883eff63ULL, 0xf262004e804584feULL,
0x1adad47d0b5a00aeULL, 0xf6b9265b03217b33ULL,
0x196c36718a79aa15ULL, 0xf50fc4578202d188ULL,
0x136c98560d93ff34ULL, 0xff0f6a7005e884a9ULL,
0x10da7a5a8cb0558fULL, 0xfcb9887c84cb2e12ULL,
0x14015c4f0fd4aa42ULL, 0xf862ae6907afd1dfULL,
0x17b7be438ef700f9ULL, 0xfbd44c65868c7b64ULL,
0x3b6e20c8123aabb0ULL, 0xd70dd2ee1a41d02dULL,
0x38d8c2c49319010bULL, 0xd4bb30e29b627a96ULL,
0x3c03e4d1107dfec6ULL, 0xd06016f71806855bULL,
0x3fb506dd915e547dULL, 0xd3d6f4fb99252fe0ULL,
0x35b5a8fa16b4015cULL, 0xd9d65adc1ecf7ac1ULL,
0x36034af69797abe7ULL, 0xda60b8d09fecd07aULL,
0x32d86ce314f3542aULL, 0xdebb9ec51c882fb7ULL,
0x316e8eef95d0fe91ULL, 0xdd0d7cc99dab850cULL,
0x26d930ac1b27fe68ULL, 0xcabac28a135c85f5ULL,
0x256fd2a09a0454d3ULL, 0xc90c2086927f2f4eULL,
0x21b4f4b51960ab1eULL, 0xcdd70693111bd083ULL,
0x220216b9984301a5ULL, 0xce61e49f90387a38ULL,
0x2802b89e1fa95484ULL, 0xc4614ab817d22f19ULL,
0x2bb45a929e8afe3fULL, 0xc7d7a8b496f185a2ULL,
0x2f6f7c871dee01f2ULL, 0xc30c8ea115957a6fULL,
0x2cd99e8b9ccdab49ULL, 0xc0ba6cad94b6d0d4ULL,
0x76dc419024755760ULL, 0x9abfb3b62c0e2cfdULL,
0x756aa39ca556fddbULL, 0x990951baad2d8646ULL,
0x71b1858926320216ULL, 0x9dd277af2e49798bULL,
0x72076785a711a8adULL, 0x9e6495a3af6ad330ULL,
0x7807c9a220fbfd8cULL, 0x94643b8428808611ULL,
0x7bb12baea1d85737ULL, 0x97d2d988a9a32caaULL,
0x7f6a0dbb22bca8faULL, 0x9309ff9d2ac7d367ULL,
0x7cdcefb7a39f0241ULL, 0x90bf1d91abe479dcULL,
0x6b6b51f42d6802b8ULL, 0x8708a3d225137925ULL,
0x68ddb3f8ac4ba803ULL, 0x84be41dea430d39eULL,
0x6c0695ed2f2f57ceULL, 0x806567cb27542c53ULL,
0x6fb077e1ae0cfd75ULL, 0x83d385c7a67786e8ULL,
0x65b0d9c629e6a854ULL, 0x89d32be0219dd3c9ULL,
0x66063bcaa8c502efULL, 0x8a65c9eca0be7972ULL,
0x62dd1ddf2ba1fd22ULL, 0x8ebeeff923da86bfULL,
0x616bffd3aa825799ULL, 0x8d080df5a2f92c04ULL,
0x4db26158364ffcd0ULL, 0xa1d1937e3e34874dULL,
0x4e048354b76c566bULL, 0xa2677172bf172df6ULL,
0x4adfa5413408a9a6ULL, 0xa6bc57673c73d23bULL,
0x4969474db52b031dULL, 0xa50ab56bbd507880ULL,
0x4369e96a32c1563cULL, 0xaf0a1b4c3aba2da1ULL,
0x40df0b66b3e2fc87ULL, 0xacbcf940bb99871aULL,
0x44042d733086034aULL, 0xa867df5538fd78d7ULL,
0x47b2cf7fb1a5a9f1ULL, 0xabd13d59b9ded26cULL,
0x5005713c3f52a908ULL, 0xbc66831a3729d295ULL,
0x53b39330be7103b3ULL, 0xbfd06116b60a782eULL,
0x5768b5253d15fc7eULL, 0xbb0b4703356e87e3ULL,
0x54de5729bc3656c5ULL, 0xb8bda50fb44d2d58ULL,
0x5edef90e3bdc03e4ULL, 0xb2bd0b2833a77879ULL,
0x5d681b02baffa95fULL, 0xb10be924b284d2c2ULL,
0x59b33d17399b5692ULL, 0xb5d0cf3131e02d0fULL,
0x5a05df1bb8b8fc29ULL, 0xb6662d3db0c387b4ULL,
0xedb8832048eaaec0ULL, 0x01db71064091d55dULL,
0xee0e612cc9c9047bULL, 0x026d930ac1b27fe6ULL,
0xead547394aadfbb6ULL, 0x06b6b51f42d6802bULL,
0xe963a535cb8e510dULL, 0x05005713c3f52a90ULL,
0xe3630b124c64042cULL, 0x0f00f934441f7fb1ULL,
0xe0d5e91ecd47ae97ULL, 0x0cb61b38c53cd50aULL,
0xe40ecf0b4e23515aULL, 0x086d3d2d46582ac7ULL,
0xe7b82d07cf00fbe1ULL, 0x0bdbdf21c77b807cULL,
0xf00f934441f7fb18ULL, 0x1c6c6162498c8085ULL,
0xf3b97148c0d451a3ULL, 0x1fda836ec8af2a3eULL,
0xf762575d43b0ae6eULL, 0x1b01a57b4bcbd5f3ULL,
0xf4d4b551c29304d5ULL, 0x18b74777cae87f48ULL,
0xfed41b76457951f4ULL, 0x12b7e9504d022a69ULL,
0xfd62f97ac45afb4fULL, 0x11010b5ccc2180d2ULL,
0xf9b9df6f473e0482ULL, 0x15da2d494f457f1fULL,
0xfa0f3d63c61dae39ULL, 0x166ccf45ce66d5a4ULL,
0xd6d6a3e85ad00570ULL, 0x3ab551ce52ab7eedULL,
0xd56041e4dbf3afcbULL, 0x3903b3c2d388d456ULL,
0xd1bb67f158975006ULL, 0x3dd895d750ec2b9bULL,
0xd20d85fdd9b4fabdULL, 0x3e6e77dbd1cf8120ULL,
0xd80d2bda5e5eaf9cULL, 0x346ed9fc5625d401ULL,
0xdbbbc9d6df7d0527ULL, 0x37d83bf0d7067ebaULL,
0xdf60efc35c19faeaULL, 0x33031de554628177ULL,
0xdcd60dcfdd3a5051ULL, 0x30b5ffe9d5412bccULL,
0xcb61b38c53cd50a8ULL, 0x270241aa5bb62b35ULL,
0xc8d75180d2eefa13ULL, 0x24b4a3a6da95818eULL,
0xcc0c7795518a05deULL, 0x206f85b359f17e43ULL,
0xcfba9599d0a9af65ULL, 0x23d967bfd8d2d4f8ULL,
0xc5ba3bbe5743fa44ULL, 0x29d9c9985f3881d9ULL,
0xc60cd9b2d66050ffULL, 0x2a6f2b94de1b2b62ULL,
0xc2d7ffa75504af32ULL, 0x2eb40d815d7fd4afULL,
0xc1611dabd4270589ULL, 0x2d02ef8ddc5c7e14ULL,
0x9b64c2b06c9ff9a0ULL, 0x7707309664e4823dULL,
0x98d220bcedbc531bULL, 0x74b1d29ae5c72886ULL,
0x9c0906a96ed8acd6ULL, 0x706af48f66a3d74bULL,
0x9fbfe4a5effb066dULL, 0x73dc1683e7807df0ULL,
0x95bf4a826811534cULL, 0x79dcb8a4606a28d1ULL,
0x9609a88ee932f9f7ULL, 0x7a6a5aa8e149826aULL,
0x92d28e9b6a56063aULL, 0x7eb17cbd622d7da7ULL,
0x91646c97eb75ac81ULL, 0x7d079eb1e30ed71cULL,
0x86d3d2d46582ac78ULL, 0x6ab020f26df9d7e5ULL,
0x856530d8e4a106c3ULL, 0x6906c2feecda7d5eULL,
0x81be16cd67c5f90eULL, 0x6ddde4eb6fbe8293ULL,
0x8208f4c1e6e653b5ULL, 0x6e6b06e7ee9d2828ULL,
0x88085ae6610c0694ULL, 0x646ba8c069777d09ULL,
0x8bbeb8eae02fac2fULL, 0x67dd4acce854d7b2ULL,
0x8f659eff634b53e2ULL, 0x63066cd96b30287fULL,
0x8cd37cf3e268f959ULL, 0x60b08ed5ea1382c4ULL,
0xa00ae2787ea55210ULL, 0x4c69105e76de298dULL,
0xa3bc0074ff86f8abULL, 0x4fdff252f7fd8336ULL,
0xa76726617ce20766ULL, 0x4b04d44774997cfbULL,
0xa4d1c46dfdc1adddULL, 0x48b2364bf5bad640ULL,
0xaed16a4a7a2bf8fcULL, 0x42b2986c72508361ULL,
0xad678846fb085247ULL, 0x41047a60f37329daULL,
0xa9bcae53786cad8aULL, 0x45df5c757017d617ULL,
0xaa0a4c5ff94f0731ULL, 0x4669be79f1347cacULL,
0xbdbdf21c77b807c8ULL, 0x51de003a7fc37c55ULL,
0xbe0b1010f69bad73ULL, 0x5268e236fee0d6eeULL,
0xbad0360575ff52beULL, 0x56b3c4237d842923ULL,
0xb966d409f4dcf805ULL, 0x5505262ffca78398ULL,
0xb3667a2e7336ad24ULL, 0x5f0588087b4dd6b9ULL,
0xb0d09822f215079fULL, 0x5cb36a04fa6e7c02ULL,
0xb40bbe377171f852ULL, 0x58684c11790a83cfULL,
0xb7bd5c3bf05252e9ULL, 0x5bdeae1df8292974ULL,
};
/* ------------------------------------------------------------------------- */
static void fatal(const char *format, ...)
{
va_list vlist;
char buffer[1024];/* should we alloc a larger chunk of virtual mem? */
va_start(vlist, format);
vsprintf(buffer, format, vlist);
eprintf("*** Fatal: %s", buffer);
va_end(vlist);
eprintf("Exiting.");
terminate(1);
}
/* ------------------------------------------------------------------------- */
static inline void refcount_dec(unsigned short *refcount)
{
if(*refcount != REFCOUNT_MAX){
if(*refcount == 0){
eprintf("refcount_dec: releasing free node\n");
}else
(*refcount)--;
}
}
static inline void refcount_inc(unsigned short *refcount)
{
if(*refcount != REFCOUNT_MAX){
(*refcount)++;
if(*refcount == REFCOUNT_MAX){
DPRINTF(("reference count has reached maximum\n"));
}
}
}
/* ------------------------------------------------------------------------- */
static int psitable_find(psinode_table_t *table, long long ino)
{
int i = ino & (table->table_size - 1);
int l = table->max_search;
while(l-- > 0){
if(table->table[i]!=NULL && table->table[i]->ino == ino){
DPRINTF(("psitable_find(): inode %d found\n", (int)ino));
list_move_to_end(&table->lru, table->table[i]);
return i;
}
i = (i + 1) & (table->table_size - 1);
}
DPRINTF(("psitable_find(): inode %d not found\n", (int)ino));
return -1;
}
/* ------------------------------------------------------------------------- */
static void psitable_delete(psinode_table_t *table, long long ino)
{
int i = psitable_find(table, ino);
if(i >= 0){
DPRINTF(("psitable_delete(): deleting inode %d\n", (int)ino));
if(table->table[i]->refcount != 0){
eprintf("psitable_delete: deleting entry with refcount %d\n",
(int)table->table[i]->refcount);
}
if(table->table[i]->parent != NULL)
refcount_dec(&table->table[i]->parent->refcount);
list_remove_element(&table->lru, table->table[i]);
free(table->table[i]);
table->table[i] = NULL;
table->load--;
}
}
/* ------------------------------------------------------------------------- */
static void psitable_gc(psinode_table_t *table)
{
psinode_t *p, *next;
int to_delete = table->delete_on_gc;
DPRINTF(("running garbage collection in psitable\n"));
for(p=table->lru.head;to_delete>0 && p!=NULL;p=next){
next = p->next;
if(p->refcount == 0){ /* remove only unreferenced nodes */
psitable_delete(table, p->ino);
to_delete --;
}
}
}
/* ------------------------------------------------------------------------- */
static int psitable_insert(psinode_table_t *table, psinode_t *entry)
{
int i = entry->ino & (table->table_size - 1);
int l = table->max_search;
DPRINTF(("psitable_insert(): inserting inode %d: ->%s<-\n",
(int)entry->ino, entry->name));
while(l-- > 0){
if(table->table[i]== NULL)
break;
i = (i + 1) & (table->table_size - 1);
}
if(table->table[i] != NULL){
fatal("hashtable full!\n");
}
table->table[i] = entry;
if(entry->parent != NULL)
refcount_inc(&entry->parent->refcount);
list_append(&table->lru, entry);
if(++table->load > table->fill_limit){
psitable_gc(table);
}
return i;
}
/* ------------------------------------------------------------------------- */
static inline void hash_add_char(long long *buffer, unsigned char c)
{
c = tolower(c);
*buffer = (*buffer >> 8) ^ crc_tab[(*buffer ^ c) & 0xff];
}
static void hash_add_string(long long *buffer, char *string)
{
char *p = string;
hash_add_char(buffer, 0); /* separate path components with 0-byte */
while(*p != 0){
hash_add_char(buffer, *p++);
}
}
/* ------------------------------------------------------------------------- */
/* ------------------------------------------------------------------------- */
int psi_index(long long ino)
{
return psitable_find(&psitable, ino);
}
/* ------------------------------------------------------------------------- */
int psi_lookup(int parent_i, char *name, long long *ino)
{
int i;
long long hash;
psinode_t *p;
if(strcmp(name, ".") == 0){
*ino = psitable.table[parent_i]->ino;
return parent_i;
}else if(strcmp(name, "..") == 0){
if(psitable.table[parent_i]->parent == NULL){ /* we are root */
*ino = psitable.table[parent_i]->ino;
return parent_i;
}else{
i = psitable_find(&psitable,psitable.table[parent_i]->parent->ino);
if(i < 0){
fatal("could not find parent of inode %d\n", (int)ino);
}
*ino = psitable.table[i]->ino;
return i;
}
}
hash = psitable.table[parent_i]->ino;
hash_add_string(&hash, name);
i = psitable_find(&psitable, hash);
if(i < 0){
p = calloc(1, sizeof(psinode_t) + strlen(name));
p->ino = hash;
strcpy(p->name, name);
p->parent = psitable.table[parent_i];
i = psitable_insert(&psitable, p);
}
*ino = psitable.table[i]->ino;
return i;
}
/* ------------------------------------------------------------------------- */
long long psi_inum(long long parent_ino, char *name)
{
long long hash = parent_ino;
int parent_i;
if(strcmp(name, ".") == 0){
return parent_ino;
}else if(strcmp(name, "..") == 0){
if((parent_i = psi_index(parent_ino)) < 0)
fatal("parent inode not found in psi_inum()\n");
psi_lookup(parent_i, name, &hash);
}else
hash_add_string(&hash, name);
return hash;
}
/* ------------------------------------------------------------------------- */
void psi_delete(long long ino)
{
psitable_delete(&psitable, ino);
}
/* ------------------------------------------------------------------------- */
int psi_define_root(char *name, long long *ino)
{
int i;
long long hash;
psinode_t *p;
hash = HASH_MAGIC_H;
hash <<= 32;
hash |= HASH_MAGIC_L;
hash_add_string(&hash, name);
p = calloc(1, sizeof(psinode_t) + strlen(name));
p->ino = hash;
root_inum = hash;
strcpy(p->name, name);
p->parent = NULL;
i = psitable_insert(&psitable, p);
*ino = psitable.table[i]->ino;
return i;
}
/* ------------------------------------------------------------------------- */
char *psi_to_path(int index, char pathsep, char *ending)
{
static char name[PATHBUF_SIZE + 1];
int l, name_i;
psinode_t *p;
if(index < 0)
return NULL;
name_i = sizeof(name) - 1;
name[name_i] = 0;
if(ending != NULL){
l = strlen(ending);
name_i -= l;
if(name_i <= 0){
fatal("name buffer overflow from ending for inode %ud\n",
(unsigned)psitable.table[index]->ino);
}
memcpy(&name[name_i], ending, l);
name[--name_i] = pathsep;
}
for(p=psitable.table[index];p!=NULL;p=p->parent){
list_move_to_end(&psitable.lru, p);
l = strlen(p->name);
name_i -= l;
if(name_i <= 0){
fatal("name buffer overflow for inode %ud\n",
(unsigned)psitable.table[index]->ino);
}
memcpy(&name[name_i], p->name, l);
if(p->parent != NULL)
name[--name_i] = pathsep;
}
return &name[name_i];
}
/* ------------------------------------------------------------------------- */
void psi_init(int table_size, int low_mark, int high_mark)
{
if((table_size & (table_size - 1)) != 0){
fatal("psi_init(): table_size != power of 2\n");
}
list_init(&psitable.lru);
psitable.table_size = table_size;
psitable.load = 0;
psitable.fill_limit = high_mark;
psitable.delete_on_gc = high_mark - low_mark;
psitable.max_search = 150;
psitable.table = calloc(table_size, sizeof(psinode_t *));
}
/* ------------------------------------------------------------------------- */
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.