Main Page

Source Files

Class Hierarchy

Alphabetical List

Compound List

Compound Members

File Members

Related Pages

Search for

---

libsrc/multiloaf.cxx

Go to the documentation of this file.

/**********************************************************************
 * Copyright 2002 Jeff Rush <jrush@taupro.com>
 * Original Copyright 1979-2002 Udanax.com
 *
 * This file is part of the Udanax xanalogical storage system.
 *
 * Udanax 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 of the License, or
 * (at your option) any later version.
 *
 * Udanax 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 Udanax; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 **********************************************************************/

/* Modification History:
 * $Log: multiloaf.cxx,v $
 * Revision 1.11  2004/09/11 13:59:21  jrush
 * Changed all fprintf's to stderr to use the Nana library L() macro.  Also
 * removed a 2-3 minor compiler warnings.
 *
 * Revision 1.10  2004/09/04 16:02:17  jrush
 * Added Doxygen headers before each and every function definition.
 *
 * Revision 1.9  2002/07/26 04:32:01  jrush
 * Replaced gerror() with assert()
 *
 * Revision 1.8  2002/05/28 04:22:29  jrush
 * Adjusted source files to comply with GPL licensing.
 *
 * Revision 1.7  2002/05/28 02:51:11  jrush
 * Made static any functions and global variables private to this source file
 * and commented out any unused functions.
 *
 * Revision 1.6  2002/04/13 13:09:40  jrush
 * Convert typedef of struct into just struct, for C++ style.
 *
 * Revision 1.5  2002/04/12 11:56:43  jrush
 * Reorganized include file layout, renamed xanadu.h to udanax.h and
 * typecontext/typecrumcontext to C++ class Context/CrumContext.
 *
 * Revision 1.4  2002/04/06 19:51:30  jrush
 * Renamed TRUE/FALSE constant use to the C++ standard of true/false.
 *
 * Revision 1.3  2002/04/06 15:01:17  jrush
 * Changed INT to just 'int'.
 *
 * Revision 1.2  2002/02/14 09:27:43  jrush
 * Cleaned up source:
 *
 * 1. ran thru the indent tool to achieve a standard look,
 * 2. added structured comments at top for use with DOxygen reporting
 *    as well as CVS keywords,
 * 3. fixed compiler warnings re ambiguous assign/compares,
 *    needed casts and unused/uninitialized variables,
 * 4. fixed funcs that didn't specify a return type,
 * 5. centralized prototypes in protos.h, removing incomplete ones,
 * 6. cleaned up use of bool/BOOLEAN type to suit C++ type,
 * 7. fixed initializer nesting in tumbler constants,
 * 8. renamed vars that conflict with C++ keywords (new, this),
 * 9. fixed global/extern confusion re some global vars.
 *
 */

#include <stdlib.h>
#include <memory.h>
#include <sys/types.h>
#include <netinet/in.h>
#include "udanax.h"

struct freediskconscell {
    freediskconscell  *next;
    freediskentry     *stuff;
};

#define SIZEOFFREEDISKBUCKET 50
#define NUMBEROFFREEDISKBUCKETS (NUMBYTESINLOAF/SIZEOFFREEDISKBUCKET+1)
static freediskconscell *fdorderedtable[NUMBEROFFREEDISKBUCKETS];

#define FDHASHTABLESIZE 10000
  /* a random prime */
#define FDHASHMULT 723754349

static freediskconscell *fdhashtable[FDHASHTABLESIZE];

    static void
dumpfreediskentry(
    freediskentry *ptr)
{
#ifndef DISTRIBUTION
    L("partialdiskblocknumber = %d freespaceinloaf = %d\n", ntohl(ptr->partialdiskblocknumber),
            ntohs(ptr->freespaceinloaf));
#endif
}

    static void
dumpfdhashtable()
{
#ifndef DISTRIBUTION
    int i;
    freediskconscell *ptr;

    L("dumping fdhashtable\n");
    for (i = 0; i < FDHASHTABLESIZE; i++) {
        if (fdhashtable[i]) {
            L("hashtable[%d]\n ", i);
            for (ptr = fdhashtable[i]; ptr; ptr = ptr->next)
                dumpfreediskentry(ptr->stuff);
        }
    }
    L("exiting dumping fdhashtable\n");
#endif
}

    static void
dumpfdorderedtable()
{
#ifndef DISTRIBUTION
    int i;
    freediskconscell *ptr;

    L("dumping fdorderedtable\n");
    for (i = 0; i < NUMBEROFFREEDISKBUCKETS; i++) {
        if (fdorderedtable[i]) {
            L("fdorderedtable[%d] s = %d\n", i, (i + 1) * SIZEOFFREEDISKBUCKET);
            for (ptr = fdorderedtable[i]; ptr; ptr = ptr->next) {
                dumpfreediskentry(ptr->stuff);
            }
        }
    }
    L("exiting dumping fdorderedtable\n");
#endif
}

    static void
dumpincoretables()
{
#ifndef DISTRIBUTION
    dumpfdorderedtable();
    dumpfdhashtable();
#endif
}

    void
initincorealloctables()
{                                      /* since these tables are extern i.e. initialized, this routine is just a start 
                                        * at restartability */
    int i;

    for (i = 0; i < NUMBEROFFREEDISKBUCKETS; i++)
        fdorderedtable[i] = NULL;

    for (i = 0; i < FDHASHTABLESIZE; i++)
        fdhashtable[i] = NULL;
}

    void
savepartialdiskalloctabletodisk()
{
    freediskarray loaf;
    int blocknumber, i;
    int bucket;
    freediskconscell *ptr;
    typediskloafptr diskalloc(), dl;

    bucket = 0;
    ptr = fdorderedtable[bucket];
    blocknumber = PARTIALFREEDISKLOCATION;
    for (i = 0;; i++, ptr = ptr->next) {
        for (; ptr == 0;) {
            bucket++;
            if (bucket >= NUMBEROFFREEDISKBUCKETS) {
/* goto endofbuckets; */
                loaf.numberofentrysinthisblock = htonl(i);
                loaf.nextdiskblocknumber = 0;
                actuallywriteloaf((typeuberrawdiskloaf *) & loaf, blocknumber);
                return;
            }
            ptr = fdorderedtable[bucket];
        }
        loaf.freeentryarray[i] = *(ptr->stuff);
        if (i >= (int) NFREEENTRYS - 1) {
            dl = diskalloc();
            loaf.nextdiskblocknumber = htonl(dl.diskblocknumber);
            loaf.numberofentrysinthisblock = htonl(NFREEENTRYS);
            actuallywriteloaf((typeuberrawdiskloaf *) & loaf, blocknumber);
            i = 0;
            blocknumber = dl.diskblocknumber;
        }
    }
}

    static int
fdhash(
    int diskblocknumber)
{
    return abs(diskblocknumber * FDHASHMULT) % FDHASHTABLESIZE;
}

    static void
addtofreediskstructures(
    freediskentry *diskentry)
{
    freediskconscell *newcons;
    freediskentry *newde;
    int i;

/* L("entering addtofreediskstructures\n"); */
/* dumpincoretables(); */
    newde = (freediskentry *) malloc(sizeof(freediskentry));
    newcons = (freediskconscell *) malloc(sizeof(freediskconscell));
    newcons->stuff = newde;
    *newde = *diskentry;
    i = ntohs(diskentry->freespaceinloaf) / SIZEOFFREEDISKBUCKET;
/* L("orderedtable i = %d\n",i); */
    newcons->next = fdorderedtable[i];
    fdorderedtable[i] = newcons;

    newcons = (freediskconscell *) malloc(sizeof(freediskconscell));
    newcons->stuff = newde;
    i = fdhash(ntohl(diskentry->partialdiskblocknumber));
/* L("hashtable i = %d\n",i); */
    newcons->next = fdhashtable[i];
    fdhashtable[i] = newcons;

/* dumpincoretables(); */
/* L("exiting addtofreediskstructures\n"); */
}

    void
readpartialdiskalloctablefromdisk()
{
    int first = true;

    freediskarray loaf;
    int blocknumber;
    for (blocknumber = PARTIALFREEDISKLOCATION; blocknumber; blocknumber = ntohl(loaf.nextdiskblocknumber)) {
        /* L("readpartialdiskalloctablefromdisk reading block# %d\n",blocknumber); */

        actuallyreadrawloaf((typeuberrawdiskloaf *) &loaf, blocknumber);
        if (!first)
            diskfree(blocknumber);

        first = false;
        if (ntohl(loaf.numberofentrysinthisblock) > NFREEENTRYS)
            assert(0); // numberofentrysinthisblock too big!

        int i;
        for (i = 0; i < (int) ntohl(loaf.numberofentrysinthisblock); i++)
            addtofreediskstructures(&(loaf.freeentryarray[i]));
    }
}

    void
addallocatedloaftopartialallocedtables(
    typediskloafptr dp,
    int             size)
{
    freediskentry stuff;

/* L("addallocatedloaftopartialallocedtables entering\n"); */
    stuff.partialdiskblocknumber = htonl(dp.diskblocknumber);
    stuff.freespaceinloaf = htons(sizeof(typeuberrawdiskloaf) - size - SIZEOFUBERDISKHEADER);
    addtofreediskstructures(&stuff);
/* L("addallocatedloaftopartialallocedtables exiting\n"); */
}

#define BESTFIT
#ifdef BESTFIT

    static freediskentry *
findfreeenoughloafinbucket(
    int size)
{
    int i;
    freediskconscell *ptr;

    for (i = size / SIZEOFFREEDISKBUCKET + 1; i < (int) NUMBEROFFREEDISKBUCKETS; i++) {
        for (ptr = fdorderedtable[i]; ptr; ptr->next) {
            if ((int) ntohs(ptr->stuff->freespaceinloaf) >= size)
                return ptr->stuff;
        }
    }
    return NULL;
}
#else                                  /* worst fit */

    static freediskentry *
findfreeenoughloafinbucket(
    int size)
{
    int i;
    freediskconscell *ptr;

    for (i = NUMBEROFFREEDISKBUCKETS - 1; i >= size / SIZEOFFREEDISKBUCKET; i--) {
        for (ptr = fdorderedtable[i]; ptr; ptr = ptr->next) {
            if (ntohs(ptr->stuff->freespaceinloaf) >= size)
                return ptr->stuff;
        }
    }
    return NULL;
}
#endif

    static void
changefreediskstructures(
    freediskentry *diskentry,
    int            newsize)
{
    int temp;
    freediskconscell *ptr, *newptr = NULL, *oldptr;

/* first change hash table */
/* L("entering changefreediskstructures-----------------\n"); */
/* dumpfdhashtable(); */
    temp = fdhash(ntohl(diskentry->partialdiskblocknumber));
    oldptr = 0;
    for (ptr = fdhashtable[temp]; ptr; ptr = ptr->next) {
        if (ptr->stuff->partialdiskblocknumber == diskentry->partialdiskblocknumber) {
            newptr = ptr;
            break;
        }
        oldptr = ptr;
    }

    if (oldptr == newptr)
        assert(0); // in hashfromdiskblock not found

    if (oldptr == 0) {
        fdhashtable[temp] = newptr->next;
    } else {
        oldptr->next = newptr->next;
    }
/* next change ordered table */
/* dumpfdhashtable(); */
/* L(" I changefreediskstructures---------------\n"); */
/* dumpfdorderedtable(); */
    temp = ntohs(diskentry->freespaceinloaf) / SIZEOFFREEDISKBUCKET;
    oldptr = 0;
    for (ptr = fdorderedtable[temp]; ptr; ptr = ptr->next) {
        if (ptr->stuff->partialdiskblocknumber == diskentry->partialdiskblocknumber) {
            newptr = ptr;
            break;
        }
        oldptr = ptr;
    }
    if (oldptr == 0) {
        fdorderedtable[temp] = newptr->next;
    } else {
        oldptr->next = newptr->next;
    }
/* last change size in entry */
    newptr->stuff->freespaceinloaf = htons(newsize);
    addtofreediskstructures(newptr->stuff);     /* just call standard routine */
/* then delete stuff left lying around do this more efficiently later */
    free((char *)newptr->stuff);
    free((char *)newptr);
/* dumpfdorderedtable(); */
/* L(" X changefreediskstructures++++++++++++++++++++\n"); */
}

    static int
findandallocateinsidediskblocknumber(
    int               diskblocknumber,
    int               size,
    typeuberdiskloaf *loafp)
{
    char *lp;
    int number;
    int i;
    int temp;
    short loaftemp;

/* L("entering findandallocateinsidediskblocknumber\n"); */
    lp = /* (char * *)&loafp->fakepartialuberloaf; */ (char *)loafp + 6;
/* zzz 1999** */
    number = ntohs(loafp->numberofunterloafs);
    for (i = 0; i < number; i++) {
        temp = intof((humber) lp);
        lp += temp;
    }
/* L("2temp = %d lp = %x loafp = %x i = %d n = %d size = %d \n",temp,lp,loafp,i,0,size);
 * L("lp - loafp = %d ",lp-(char*)loafp); */
    loaftemp = ntohs(loafp->numberofunterloafs) + 1;
    loafp->numberofunterloafs = htons(loaftemp);
    temp = sizeof(typeuberrawdiskloaf) - (lp - (char *)loafp) - size;
#ifndef DISTRIBUTION
    if (temp < 0) {
        dumphexstuff(lp);
        dumphexstuff((char *) loafp);
        L("2temp = %d lp = %x loafp = %x i = %d  size = %d \n", temp, (int) lp, (int) loafp, i, size);
        L("lp - loafp = %d ", lp - (char *)loafp);
        L("expression = %d diskblocknumber = %d number = %d\n", temp, diskblocknumber, number);
        dumpincoretables();
        assert(0); // expression negative in findandallocateinsidediskblocknumber
        L("expression negative in findandallocateinsidediskblocknumber");
        return i;
    }
#endif
    movmem(lp, lp + size, sizeof(typeuberrawdiskloaf) - (lp - (char *)loafp) - size);
/* L(" B findandallocateinsidediskblocknumber\n"); */
/* dumphexstuff(loafp); */
    return i;
}

    typediskloafptr
partialdiskalloc(
    int  size,
    int *newloafp)
{
    freediskentry diskentry, *freeentry;
    typediskloafptr dlp;
    typeuberdiskloaf loaf;

#ifndef DISTRIBUTION
    if (size != 1010 && size > 990) {
        L("partialdiskalloc size = %d\n", size);
    }
#endif
    freeentry = findfreeenoughloafinbucket(size);
/* L("partialdiskalloc freeentry = %x\n",freeentry); */
    if (!freeentry) {
        dlp = diskalloc();
        dlp.insidediskblocknumber = 0 /* 1 */ ;
        diskentry.partialdiskblocknumber = htonl(dlp.diskblocknumber);
        diskentry.freespaceinloaf = htons(NUMBYTESINLOAF - size - SIZEOFUBERDISKHEADER);
        addtofreediskstructures(&diskentry);
/* L("partialdiskblock returning true with diskblocknumber = %d\n",dlp.diskblocknumber); */
        *newloafp = true;
        return dlp;
    } else {
        if (size >= ntohs(freeentry->freespaceinloaf)) {
            dumpincoretables();
#ifndef DISTRIBUTION
            L("size = %d number = %d\n ", size, ntohl(freeentry->partialdiskblocknumber));
            assert(0); // partialdiskalloc  found loaf too small
#else
            assert(0);
#endif
        }
        dlp.diskblocknumber = ntohl(freeentry->partialdiskblocknumber);
        actuallyreadrawloaf((typeuberrawdiskloaf *) & loaf, ntohl(freeentry->partialdiskblocknumber));
        dlp.insidediskblocknumber = findandallocateinsidediskblocknumber(dlp.diskblocknumber, size, &loaf);

        if (dlp.insidediskblocknumber > 100)
            assert(0); // partialdiskalloc insidediskblocknumber >100

        changefreediskstructures(freeentry, (int) (ntohs(freeentry->freespaceinloaf) - size));
        *newloafp = false;
/* L("leaving partialdiskalloc o\n"); */
        return dlp;
    }
}

    int
numberofliveunterloafs(
    typeuberdiskloaf *loafp)
{
    char *lp;
    unsigned int number, n;
    int i;
    int ret;
    unsigned int temp;

    ret = 0;
    lp = /* (char *)&loafp->fakepartialuberloaf; */ (char *)loafp + 6;
    number = ntohs(loafp->numberofunterloafs);
    for (i = 0; i < (int) number; i++) {
        n = lengthof((humber) /* loafp */ lp);  /* ECH 8-29-88 */
        temp = intof((humber) lp);
        if (n >= temp) {
            lp += n;
        } else {
            lp += temp;
        }
        if (n != temp) {
            ret++;
        }
    }
    return ret;
}

    char *
findinsideloaf(
    typeuberdiskloaf *loafp,
    int               ninsideloaf)
{
    char *lp;
    unsigned int number, n;
    int i;
    unsigned int temp;

/* L("findinsideloaf ninsideloaf = %x \n",ninsideloaf); */
/* L("findinsideloaf loafp = %x \n",loafp); */
/* L("findinsideloaf lp = %x \n",lp); */
    lp = /* (char *)&loafp->fakepartialuberloaf; */ (char *)loafp + 6;

    number = ntohs(loafp->numberofunterloafs);
/* L("findinsideloaf number = %x \n",number); */
    for (i = 0; i < (int) number; i++) {
        n = lengthof((humber) loafp);
/* L("findinsideloaf n = %x \n",n); */
        if (i == ninsideloaf) {
/* L("findinsideloaf returning lp = %x \n",lp); */
            return lp;
        }
        temp = intof((humber) lp);
        if (n >= temp) {
            lp += n;
        } else {
            lp += temp;
        }
    }
/* L("findinsideloaf returningNULL substitute\n"); */
    return lp;
}

---