Return to turbo_load.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / contrib / isode-beta / quipu

Annotation of 43BSDReno/contrib/isode-beta/quipu/turbo_load.c, revision 1.1

1.1     ! root        1: /* turbo_load.c - Quickly check for duplicate RDN's (from Tim Howes) */
        !             2: 
        !             3: #ifndef        lint
        !             4: static char *rcsid = "$Header: /f/osi/quipu/RCS/turbo_load.c,v 7.1 90/07/09 14:46:48 mrose Exp $";
        !             5: #endif
        !             6: 
        !             7: /* 
        !             8:  * $Header: /f/osi/quipu/RCS/turbo_load.c,v 7.1 90/07/09 14:46:48 mrose Exp $
        !             9:  *
        !            10:  *
        !            11:  * $Log:       turbo_load.c,v $
        !            12:  * Revision 7.1  90/07/09  14:46:48  mrose
        !            13:  * sync
        !            14:  * 
        !            15:  * Revision 7.0  89/11/23  22:20:57  mrose
        !            16:  * Release 6.0
        !            17:  * 
        !            18:  */
        !            19: 
        !            20: /*
        !            21:  *                               NOTICE
        !            22:  *
        !            23:  *    Acquisition, use, and distribution of this module and related
        !            24:  *    materials are subject to the restrictions of a license agreement.
        !            25:  *    Consult the Preface in the User's Manual for the full terms of
        !            26:  *    this agreement.
        !            27:  *
        !            28:  */
        !            29: 
        !            30: #include "quipu/config.h"
        !            31: #include "quipu/util.h"
        !            32: #include "quipu/entry.h"
        !            33: #include "quipu/malloc.h"
        !            34: #include <sys/stat.h>
        !            35: #ifdef TURBO_DISK
        !            36: #include "../../gdbm-1.3/gdbmdefs.h"
        !            37: #endif
        !            38: 
        !            39: extern LLog * log_dsap;
        !            40: 
        !            41: extern int turbo_size;
        !            42: extern int turbo_name_size;
        !            43: 
        !            44: struct node {
        !            45:        char *name;
        !            46:        struct node *left;
        !            47:        struct node *right;
        !            48:        int bf;
        !            49: };
        !            50: 
        !            51: static struct node *node_heap;
        !            52: static struct node *node_next;
        !            53: 
        !            54: static char *name_heap;
        !            55: static char *name_next;
        !            56: 
        !            57: static struct node *root;
        !            58: static long count;
        !            59: static long comparisons;
        !            60: static long entries;
        !            61: 
        !            62: turbo_start(file)
        !            63: #ifdef TURBO_DISK
        !            64: gdbm_file_info *file;
        !            65: #else
        !            66: FILE           *file;
        !            67: #endif
        !            68: {
        !            69:        struct stat buf;
        !            70:        int save_heap;
        !            71: 
        !            72: #ifdef TURBO_DISK
        !            73:        if ( fstat(file->desc, &buf) != 0 ) {
        !            74: #else
        !            75:        if ( fstat(fileno(file), &buf) != 0 ) {
        !            76: #endif
        !            77:                LLOG (log_dsap, LLOG_EXCEPTIONS,("turbo: could not get filesize"));
        !            78:                return FALSE;
        !            79:        }
        !            80: 
        !            81:        /* 
        !            82:         * This is a heuristic based on some edb file sizes at
        !            83:         * UM.  If you find this isn't enough, try using
        !            84:         * a smaller turbo_size (in quiputailor).  This should
        !            85:         * eventually be fixed to malloc more if the heuristic
        !            86:         * turns out not to be enough.
        !            87:        */
        !            88:        entries = (buf.st_size) / turbo_size;
        !            89:        if ( entries < 100 ) entries = 100;
        !            90: 
        !            91:        save_heap = mem_heap;
        !            92:        GENERAL_HEAP;
        !            93:        node_heap = (struct node *) calloc( (unsigned)entries, sizeof(struct node) );
        !            94:        node_next = node_heap;
        !            95:        name_heap = (char *) calloc( (unsigned)entries, (unsigned)turbo_name_size );
        !            96:        name_next = name_heap;
        !            97:        mem_heap = save_heap;
        !            98:        root = 0;
        !            99:        count = 0;
        !           100:        comparisons = 0;
        !           101: 
        !           102:        mem_heap = save_heap;
        !           103:        return TRUE;
        !           104: }
        !           105: 
        !           106: #define LH     -1
        !           107: #define EH     0
        !           108: #define RH     1
        !           109: #define ROTATERIGHT(x) { struct node *tmp;\
        !           110:        if ( *x == NULL || (*x)->left == NULL ) {\
        !           111:                (void) printf("RR error\n"); exit(1); \
        !           112:        }\
        !           113:        tmp = (*x)->left;\
        !           114:        (*x)->left = tmp->right;\
        !           115:        tmp->right = *x;\
        !           116:        *x = tmp;\
        !           117: }
        !           118: #define ROTATELEFT(x)  { struct node *tmp;\
        !           119:        if ( *x == NULL || (*x)->right == NULL ) {\
        !           120:                (void) printf("RL error\n"); exit(1); \
        !           121:        }\
        !           122:        tmp = (*x)->right;\
        !           123:        (*x)->right = tmp->left;\
        !           124:        tmp->left = *x;\
        !           125:        *x = tmp;\
        !           126: }
        !           127: 
        !           128: 
        !           129: static avl_insert(iroot, name, taller)
        !           130: struct node **iroot;
        !           131: char *name;
        !           132: int *taller;
        !           133: {
        !           134:        int rc, cmp, tallersub;
        !           135:        struct node *l, *r;
        !           136: 
        !           137:        comparisons++;
        !           138:        if ( *iroot == 0 ) {
        !           139:                *iroot = node_next++;
        !           140:                (*iroot)->left = 0;
        !           141:                (*iroot)->right = 0;
        !           142:                (*iroot)->bf = 0;
        !           143:                (*iroot)->name = name_next;
        !           144:                while ( *(name_next++) = *(name++) );
        !           145:                *taller = 1;
        !           146:                return (OK);
        !           147:        }
        !           148: 
        !           149:        cmp = strcmp(name, (*iroot)->name);
        !           150:        /* equal - duplicate name */
        !           151:        if ( cmp == 0 ) {
        !           152:                 *taller = 0;
        !           153:                return (NOTOK);
        !           154:        }
        !           155:        /* go right */
        !           156:        else if ( cmp > 0 ) {
        !           157:                rc = avl_insert(&((*iroot)->right), name, &tallersub);
        !           158:                if (tallersub)
        !           159:                        switch ((*iroot)->bf) {
        !           160:                        case LH : /* left high - balance is restored */
        !           161:                                (*iroot)->bf = EH;
        !           162:                                *taller = 0;
        !           163:                                break;
        !           164:                        case EH : /* equal height - now right heavy */
        !           165:                                (*iroot)->bf = RH;
        !           166:                                *taller = 1;
        !           167:                                break;
        !           168:                        case RH : /* right heavy to start - right balance */
        !           169:                                r = (*iroot)->right;
        !           170:                                switch (r->bf) {
        !           171:                                case LH : /* double rotation left */
        !           172:                                        l = r->left;
        !           173:                                        switch (l->bf) {
        !           174:                                        case LH : (*iroot)->bf = EH;
        !           175:                                                  r->bf = RH;
        !           176:                                                  break;
        !           177:                                        case EH : (*iroot)->bf = EH;
        !           178:                                                  r->bf = EH;
        !           179:                                                  break;
        !           180:                                        case RH : (*iroot)->bf = LH;
        !           181:                                                  r->bf = EH;
        !           182:                                                  break;
        !           183:                                        }
        !           184:                                        l->bf = EH;
        !           185:                                        ROTATERIGHT((&r))
        !           186:                                        (*iroot)->right = r;
        !           187:                                        ROTATELEFT(iroot)
        !           188:                                        *taller = 0;
        !           189:                                        break;
        !           190:                                case EH : /* This should never happen */
        !           191:                                        break;
        !           192:                                case RH : /* single rotation left */
        !           193:                                        (*iroot)->bf = EH;
        !           194:                                        r->bf = EH;
        !           195:                                        ROTATELEFT(iroot)
        !           196:                                        *taller = 0;
        !           197:                                        break;
        !           198:                                }
        !           199:                                break;
        !           200:                        }
        !           201:                else
        !           202:                        *taller = 0;
        !           203:        }
        !           204:        /* go left */
        !           205:        else {
        !           206:                rc = avl_insert(&((*iroot)->left), name, &tallersub);
        !           207:                if (tallersub)
        !           208:                        switch ((*iroot)->bf) {
        !           209:                        case LH : /* left high to start - left balance */
        !           210:                                l = (*iroot)->left;
        !           211:                                switch (l->bf) {
        !           212:                                case LH : /* single rotation right */
        !           213:                                        (*iroot)->bf = EH;
        !           214:                                        l->bf = EH;
        !           215:                                        ROTATERIGHT(iroot)
        !           216:                                        *taller = 0;
        !           217:                                        break;
        !           218:                                case EH : /* this should never happen */
        !           219:                                        break;
        !           220:                                case RH : /* double rotation right */
        !           221:                                        r = l->right;
        !           222:                                        switch (r->bf) {
        !           223:                                        case LH : (*iroot)->bf = RH;
        !           224:                                                  l->bf = EH;
        !           225:                                                  break;
        !           226:                                        case EH : (*iroot)->bf = EH;
        !           227:                                                  l->bf = EH;
        !           228:                                                  break;
        !           229:                                        case RH : (*iroot)->bf = EH;
        !           230:                                                  l->bf = LH;
        !           231:                                                  break;
        !           232:                                        }
        !           233:                                        r->bf = EH;
        !           234:                                        ROTATELEFT((&l))
        !           235:                                        (*iroot)->left = l;
        !           236:                                        ROTATERIGHT(iroot)
        !           237:                                        *taller = 0;
        !           238:                                        break;
        !           239:                                }
        !           240:                                break;
        !           241:                        case EH : /* equal height - now left heavy */
        !           242:                                (*iroot)->bf = LH;
        !           243:                                *taller = 1;
        !           244:                                break;
        !           245:                        case RH : /* right high - balance is restored */
        !           246:                                (*iroot)->bf = EH;
        !           247:                                *taller = 0;
        !           248:                                break;
        !           249:                        }
        !           250:                else
        !           251:                        *taller = 0;
        !           252:        }
        !           253:        return(rc);
        !           254: }
        !           255: 
        !           256: turbo_insert(name)
        !           257: RDN name;
        !           258: {
        !           259:        int taller;
        !           260: 
        !           261:        if ( ++count >= entries ) {
        !           262:                if (count == entries)
        !           263:                        LLOG (log_dsap,LLOG_EXCEPTIONS,("turbo botch - decrease turbo_size (currently %d - %d entries read)",turbo_size,entries));
        !           264:                /* should realloc */
        !           265:                return OK;
        !           266:        }
        !           267: 
        !           268:        if (strlen ((char *) name->rdn_av.av_struct) >= turbo_name_size) {
        !           269:                LLOG (log_dsap,LLOG_EXCEPTIONS,("turbo botch - increase turbo_name_size (%d required for '%s', currently %d)",
        !           270:                        strlen ((char *) name->rdn_av.av_struct),
        !           271:                        (char *)name->rdn_av.av_struct, turbo_name_size));
        !           272:                /* should realloc */
        !           273:                return OK;
        !           274:        }
        !           275: 
        !           276:        return (avl_insert(&root, (char *) name->rdn_av.av_struct, &taller));
        !           277: }
        !           278: 
        !           279: turbo_end()
        !           280: {
        !           281:        int save_heap;
        !           282: 
        !           283:        DLOG (log_dsap,LLOG_DEBUG,("turbo %d entries unused",entries - count));
        !           284: 
        !           285:        save_heap = mem_heap;
        !           286:        GENERAL_HEAP;
        !           287: 
        !           288:        free(name_heap);
        !           289:        free((char *)node_heap);
        !           290: 
        !           291:        mem_heap = save_heap;
        !           292: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.