[BACK]Return to cdbw.c CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / lib / libc / cdb

Annotation of src/lib/libc/cdb/cdbw.c, Revision 1.6

1.6     ! alnsn       1: /*     $NetBSD: cdbw.c,v 1.5 2012/07/21 22:49:37 joerg Exp $   */
1.1       joerg       2: /*-
1.6     ! alnsn       3:  * Copyright (c) 2009, 2010, 2015 The NetBSD Foundation, Inc.
1.1       joerg       4:  * All rights reserved.
                      5:  *
                      6:  * This code is derived from software contributed to The NetBSD Foundation
1.6     ! alnsn       7:  * by Joerg Sonnenberger and Alexander Nasonov.
1.1       joerg       8:  *
                      9:  * Redistribution and use in source and binary forms, with or without
                     10:  * modification, are permitted provided that the following conditions
                     11:  * are met:
                     12:  *
                     13:  * 1. Redistributions of source code must retain the above copyright
                     14:  *    notice, this list of conditions and the following disclaimer.
                     15:  * 2. Redistributions in binary form must reproduce the above copyright
                     16:  *    notice, this list of conditions and the following disclaimer in
                     17:  *    the documentation and/or other materials provided with the
                     18:  *    distribution.
                     19:  *
                     20:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
                     21:  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
                     22:  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
                     23:  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
                     24:  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
                     25:  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
                     26:  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
                     27:  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
                     28:  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
                     29:  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
                     30:  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     31:  * SUCH DAMAGE.
                     32:  */
                     33:
                     34: #if HAVE_NBTOOL_CONFIG_H
                     35: #include "nbtool_config.h"
                     36: #endif
                     37:
                     38: #include <sys/cdefs.h>
1.6     ! alnsn      39: __RCSID("$NetBSD: cdbw.c,v 1.5 2012/07/21 22:49:37 joerg Exp $");
1.1       joerg      40:
                     41: #include "namespace.h"
                     42:
1.4       joerg      43: #if !HAVE_NBTOOL_CONFIG_H || HAVE_SYS_ENDIAN_H
1.1       joerg      44: #include <sys/endian.h>
1.4       joerg      45: #endif
1.1       joerg      46: #include <sys/queue.h>
                     47: #include <cdbw.h>
                     48: #include <stdlib.h>
                     49: #include <string.h>
                     50: #include <unistd.h>
                     51:
                     52: #ifdef __weak_alias
                     53: __weak_alias(cdbw_close,_cdbw_close)
                     54: __weak_alias(cdbw_open,_cdbw_open)
                     55: __weak_alias(cdbw_output,_cdbw_output)
                     56: __weak_alias(cdbw_put,_cdbw_put)
                     57: __weak_alias(cdbw_put_data,_cdbw_put_data)
                     58: __weak_alias(cdbw_put_key,_cdbw_put_key)
                     59: #endif
                     60:
                     61: struct key_hash {
                     62:        SLIST_ENTRY(key_hash) link;
                     63:        uint32_t hashes[3];
                     64:        uint32_t idx;
                     65:        void *key;
                     66:        size_t keylen;
                     67: };
                     68:
                     69: SLIST_HEAD(key_hash_head, key_hash);
                     70:
                     71: struct cdbw {
                     72:        size_t data_counter;
                     73:        size_t data_allocated;
                     74:        size_t data_size;
                     75:        size_t *data_len;
                     76:        void **data_ptr;
                     77:
                     78:        size_t hash_size;
                     79:        struct key_hash_head *hash;
                     80:        size_t key_counter;
                     81: };
                     82:
                     83:  /* Max. data counter that allows the index size to be 32bit. */
                     84: static const uint32_t max_data_counter = 0xccccccccU;
                     85:
                     86: struct cdbw *
                     87: cdbw_open(void)
                     88: {
                     89:        struct cdbw *cdbw;
                     90:        size_t i;
                     91:
                     92:        cdbw = calloc(sizeof(*cdbw), 1);
                     93:        if (cdbw == NULL)
                     94:                return NULL;
                     95:
                     96:        cdbw->hash_size = 1024;
                     97:        cdbw->hash = calloc(cdbw->hash_size, sizeof(*cdbw->hash));
                     98:        if (cdbw->hash == NULL) {
                     99:                free(cdbw);
                    100:                return NULL;
                    101:        }
                    102:
                    103:        for (i = 0; i < cdbw->hash_size; ++i)
                    104:                SLIST_INIT(cdbw->hash + i);
                    105:
                    106:        return cdbw;
                    107: }
                    108:
                    109: int
                    110: cdbw_put(struct cdbw *cdbw, const void *key, size_t keylen,
                    111:     const void *data, size_t datalen)
                    112: {
                    113:        uint32_t idx;
                    114:        int rv;
                    115:
                    116:        rv = cdbw_put_data(cdbw, data, datalen, &idx);
                    117:        if (rv)
                    118:                return rv;
                    119:        rv = cdbw_put_key(cdbw, key, keylen, idx);
                    120:        if (rv) {
                    121:                --cdbw->data_counter;
                    122:                free(cdbw->data_ptr[cdbw->data_counter]);
                    123:                cdbw->data_size -= datalen;
                    124:                return rv;
                    125:        }
                    126:        return 0;
                    127: }
                    128:
                    129: int
                    130: cdbw_put_data(struct cdbw *cdbw, const void *data, size_t datalen,
                    131:     uint32_t *idx)
                    132: {
                    133:
                    134:        if (cdbw->data_counter == max_data_counter)
                    135:                return -1;
                    136:
                    137:        if (cdbw->data_size + datalen < cdbw->data_size ||
                    138:            cdbw->data_size + datalen > 0xffffffffU)
                    139:                return -1; /* Overflow */
                    140:
                    141:        if (cdbw->data_allocated == cdbw->data_counter) {
                    142:                void **new_data_ptr;
                    143:                size_t *new_data_len;
                    144:                size_t new_allocated;
                    145:
                    146:                if (cdbw->data_allocated == 0)
                    147:                        new_allocated = 256;
                    148:                else
                    149:                        new_allocated = cdbw->data_allocated * 2;
                    150:
                    151:                new_data_ptr = realloc(cdbw->data_ptr,
                    152:                    sizeof(*cdbw->data_ptr) * new_allocated);
                    153:                if (new_data_ptr == NULL)
                    154:                        return -1;
                    155:                cdbw->data_ptr = new_data_ptr;
                    156:
                    157:                new_data_len = realloc(cdbw->data_len,
                    158:                    sizeof(*cdbw->data_len) * new_allocated);
                    159:                if (new_data_len == NULL)
                    160:                        return -1;
                    161:                cdbw->data_len = new_data_len;
                    162:
                    163:                cdbw->data_allocated = new_allocated;
                    164:        }
                    165:
                    166:        cdbw->data_ptr[cdbw->data_counter] = malloc(datalen);
                    167:        if (cdbw->data_ptr[cdbw->data_counter] == NULL)
                    168:                return -1;
                    169:        memcpy(cdbw->data_ptr[cdbw->data_counter], data, datalen);
                    170:        cdbw->data_len[cdbw->data_counter] = datalen;
                    171:        cdbw->data_size += datalen;
1.3       joerg     172:        *idx = cdbw->data_counter++;
1.1       joerg     173:        return 0;
                    174: }
                    175:
                    176: int
                    177: cdbw_put_key(struct cdbw *cdbw, const void *key, size_t keylen, uint32_t idx)
                    178: {
                    179:        uint32_t hashes[3];
                    180:        struct key_hash_head *head, *head2, *new_head;
                    181:        struct key_hash *key_hash;
                    182:        size_t new_hash_size, i;
                    183:
                    184:        if (idx >= cdbw->data_counter ||
                    185:            cdbw->key_counter == max_data_counter)
                    186:                return -1;
                    187:
                    188:        mi_vector_hash(key, keylen, 0, hashes);
                    189:
                    190:        head = cdbw->hash + (hashes[0] & (cdbw->hash_size - 1));
                    191:        SLIST_FOREACH(key_hash, head, link) {
                    192:                if (key_hash->keylen != keylen)
                    193:                        continue;
                    194:                if (key_hash->hashes[0] != hashes[0])
                    195:                        continue;
                    196:                if (key_hash->hashes[1] != hashes[1])
                    197:                        continue;
                    198:                if (key_hash->hashes[2] != hashes[2])
                    199:                        continue;
                    200:                if (memcmp(key, key_hash->key, keylen))
                    201:                        continue;
                    202:                return -1;
                    203:        }
                    204:        key_hash = malloc(sizeof(*key_hash));
                    205:        if (key_hash == NULL)
                    206:                return -1;
                    207:        key_hash->key = malloc(keylen);
                    208:        if (key_hash->key == NULL) {
                    209:                free(key_hash);
                    210:                return -1;
                    211:        }
                    212:        memcpy(key_hash->key, key, keylen);
                    213:        key_hash->hashes[0] = hashes[0];
                    214:        key_hash->hashes[1] = hashes[1];
                    215:        key_hash->hashes[2] = hashes[2];
                    216:        key_hash->keylen = keylen;
                    217:        key_hash->idx = idx;
                    218:        SLIST_INSERT_HEAD(head, key_hash, link);
                    219:        ++cdbw->key_counter;
                    220:
                    221:        if (cdbw->key_counter <= cdbw->hash_size)
                    222:                return 0;
                    223:
                    224:        /* Try to resize the hash table, but ignore errors. */
                    225:        new_hash_size = cdbw->hash_size * 2;
                    226:        new_head = calloc(sizeof(*new_head), new_hash_size);
                    227:        if (new_head == NULL)
                    228:                return 0;
                    229:
                    230:        head = &cdbw->hash[hashes[0] & (cdbw->hash_size - 1)];
                    231:        for (i = 0; i < new_hash_size; ++i)
                    232:                SLIST_INIT(new_head + i);
                    233:
                    234:        for (i = 0; i < cdbw->hash_size; ++i) {
                    235:                head = cdbw->hash + i;
                    236:
                    237:                while ((key_hash = SLIST_FIRST(head)) != NULL) {
                    238:                        SLIST_REMOVE_HEAD(head, link);
                    239:                        head2 = new_head +
                    240:                            (key_hash->hashes[0] & (new_hash_size - 1));
                    241:                        SLIST_INSERT_HEAD(head2, key_hash, link);
                    242:                }
                    243:        }
                    244:        free(cdbw->hash);
                    245:        cdbw->hash_size = new_hash_size;
                    246:        cdbw->hash = new_head;
                    247:
                    248:        return 0;
                    249: }
                    250:
                    251: void
                    252: cdbw_close(struct cdbw *cdbw)
                    253: {
                    254:        struct key_hash_head *head;
                    255:        struct key_hash *key_hash;
                    256:        size_t i;
                    257:
                    258:        for (i = 0; i < cdbw->hash_size; ++i) {
                    259:                head = cdbw->hash + i;
                    260:                while ((key_hash = SLIST_FIRST(head)) != NULL) {
                    261:                        SLIST_REMOVE_HEAD(head, link);
                    262:                        free(key_hash->key);
                    263:                        free(key_hash);
                    264:                }
                    265:        }
                    266:
                    267:        for (i = 0; i < cdbw->data_counter; ++i)
                    268:                free(cdbw->data_ptr[i]);
                    269:        free(cdbw->data_ptr);
                    270:        free(cdbw->data_len);
                    271:        free(cdbw->hash);
                    272:        free(cdbw);
                    273: }
                    274:
1.4       joerg     275: uint32_t
                    276: cdbw_stable_seeder(void)
                    277: {
                    278:        return 0;
                    279: }
                    280:
1.6     ! alnsn     281: /*
        !           282:  * The algorithm below is based on paper
        !           283:  * Cache-Oblivious Peeling of Random Hypergraphs by Djamal Belazzougui,
        !           284:  * Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano
        !           285:  * Vigna.
        !           286:  * http://zola.di.unipi.it/rossano/wp-content/papercite-data/pdf/dcc14.pdf
        !           287:  */
1.1       joerg     288:
1.6     ! alnsn     289: /*
        !           290:  * Data type for a valid oriented edge (v0, v1, v2), v1 < v2.
        !           291:  * The first vertex v0 is implicit and is determined by an index
        !           292:  * of the corresponding element in the state->oedges array.
        !           293:  * If the degree of v0 is greater than 1, other members don't
        !           294:  * make sense because they're a result of XORing multiple values.
        !           295:  */
        !           296: struct oedge {
        !           297:        uint32_t degree;   /* Degree of v0. */
        !           298:        uint32_t verts[2]; /* v1 and v2 */
        !           299:        uint32_t edge;
1.1       joerg     300: };
                    301:
                    302: struct edge {
                    303:        uint32_t idx;
                    304:
                    305:        uint32_t left, middle, right;
                    306: };
                    307:
                    308: struct state {
                    309:        uint32_t data_entries;
                    310:        uint32_t entries;
                    311:        uint32_t keys;
                    312:        uint32_t seed;
                    313:
                    314:        uint32_t *g;
                    315:        char *visited;
                    316:
1.6     ! alnsn     317:        struct oedge *oedges;
1.1       joerg     318:        struct edge *edges;
                    319:        uint32_t output_index;
                    320:        uint32_t *output_order;
                    321: };
                    322:
1.6     ! alnsn     323: /*
        !           324:  * Add (delta == 1) or remove (delta == -1) the edge e from vertex v0.
        !           325:  */
        !           326: static inline void
        !           327: add_remove_edge(struct oedge *o, int delta, uint32_t e,
        !           328:     uint32_t v0, uint32_t v1, uint32_t v2)
1.1       joerg     329: {
                    330:
1.6     ! alnsn     331:        o[v0].verts[v1 < v2 ? 0 : 1] ^= v1;
        !           332:        o[v0].verts[v1 < v2 ? 1 : 0] ^= v2;
        !           333:        o[v0].degree += delta;
        !           334:        o[v0].edge ^= e;
        !           335: }
        !           336:
        !           337: static inline void
        !           338: add_edge(struct oedge *o, uint32_t e,
        !           339:     uint32_t v0, uint32_t v1, uint32_t v2)
        !           340: {
1.1       joerg     341:
1.6     ! alnsn     342:        add_remove_edge(o, 1, e, v0, v1, v2);
        !           343: }
1.1       joerg     344:
1.6     ! alnsn     345: static inline void
        !           346: remove_vertex(struct state *state, uint32_t v0)
        !           347: {
        !           348:        uint32_t e, v1, v2;
        !           349:        struct oedge *o = state->oedges;
1.1       joerg     350:
1.6     ! alnsn     351:        if (o[v0].degree == 1) {
        !           352:                e = o[v0].edge;
        !           353:                v1 = o[v0].verts[0];
        !           354:                v2 = o[v0].verts[1];
        !           355:                o[v0].degree = 0;
        !           356:                add_remove_edge(o, -1, e, v1, v0, v2);
        !           357:                add_remove_edge(o, -1, e, v2, v0, v1);
        !           358:                state->output_order[--state->output_index] = e;
        !           359:        }
1.1       joerg     360: }
                    361:
                    362: static int
                    363: build_graph(struct cdbw *cdbw, struct state *state)
                    364: {
                    365:        struct key_hash_head *head;
                    366:        struct key_hash *key_hash;
                    367:        struct edge *e;
1.3       joerg     368:        uint32_t hashes[3];
                    369:        size_t i;
1.1       joerg     370:
1.6     ! alnsn     371:        memset(state->oedges, 0, sizeof(struct oedge) * state->entries);
        !           372:
1.1       joerg     373:        e = state->edges;
                    374:        for (i = 0; i < cdbw->hash_size; ++i) {
                    375:                head = &cdbw->hash[i];
                    376:                SLIST_FOREACH(key_hash, head, link) {
                    377:                        e->idx = key_hash->idx;
                    378:                        mi_vector_hash(key_hash->key, key_hash->keylen,
                    379:                            state->seed, hashes);
                    380:                        e->left = hashes[0] % state->entries;
                    381:                        e->middle = hashes[1] % state->entries;
                    382:                        e->right = hashes[2] % state->entries;
                    383:
1.5       joerg     384:                        if (e->left == e->middle)
                    385:                                return -1;
1.6     ! alnsn     386:                        add_edge(state->oedges, e - state->edges,
        !           387:                            e->right, e->left, e->middle);
1.5       joerg     388:                        if (e->left == e->right)
                    389:                                return -1;
1.6     ! alnsn     390:                        add_edge(state->oedges, e - state->edges,
        !           391:                            e->middle, e->left, e->right);
1.5       joerg     392:                        if (e->middle == e->right)
                    393:                                return -1;
1.6     ! alnsn     394:                        add_edge(state->oedges, e - state->edges,
        !           395:                            e->left, e->middle, e->right);
1.5       joerg     396:
1.1       joerg     397:                        ++e;
                    398:                }
                    399:        }
                    400:
                    401:        state->output_index = state->keys;
                    402:        for (i = 0; i < state->entries; ++i)
1.6     ! alnsn     403:                remove_vertex(state, i);
1.1       joerg     404:
                    405:        i = state->keys;
                    406:        while (i > 0 && i > state->output_index) {
                    407:                --i;
                    408:                e = state->edges + state->output_order[i];
1.6     ! alnsn     409:                remove_vertex(state, e->left);
        !           410:                remove_vertex(state, e->middle);
        !           411:                remove_vertex(state, e->right);
1.1       joerg     412:        }
                    413:
                    414:        return state->output_index == 0 ? 0 : -1;
                    415: }
                    416:
                    417: static void
                    418: assign_nodes(struct state *state)
                    419: {
                    420:        struct edge *e;
                    421:        size_t i;
                    422:
                    423:        for (i = 0; i < state->keys; ++i) {
                    424:                e = state->edges + state->output_order[i];
                    425:
                    426:                if (!state->visited[e->left]) {
                    427:                        state->g[e->left] =
                    428:                            (2 * state->data_entries + e->idx
                    429:                            - state->g[e->middle] - state->g[e->right])
                    430:                            % state->data_entries;
                    431:                } else if (!state->visited[e->middle]) {
                    432:                        state->g[e->middle] =
                    433:                            (2 * state->data_entries + e->idx
                    434:                            - state->g[e->left] - state->g[e->right])
                    435:                            % state->data_entries;
                    436:                } else {
                    437:                        state->g[e->right] =
                    438:                            (2 * state->data_entries + e->idx
                    439:                            - state->g[e->left] - state->g[e->middle])
                    440:                            % state->data_entries;
                    441:                }
                    442:                state->visited[e->left] = 1;
                    443:                state->visited[e->middle] = 1;
                    444:                state->visited[e->right] = 1;
                    445:        }
                    446: }
                    447:
                    448: static size_t
                    449: compute_size(uint32_t size)
                    450: {
                    451:        if (size < 0x100)
                    452:                return 1;
                    453:        else if (size < 0x10000)
                    454:                return 2;
                    455:        else
                    456:                return 4;
                    457: }
                    458:
                    459: #define COND_FLUSH_BUFFER(n) do {                              \
                    460:        if (__predict_false(cur_pos + (n) >= sizeof(buf))) {    \
                    461:                ret = write(fd, buf, cur_pos);                  \
                    462:                if (ret == -1 || (size_t)ret != cur_pos)        \
                    463:                        return -1;                              \
                    464:                cur_pos = 0;                                    \
                    465:        }                                                       \
                    466: } while (/* CONSTCOND */ 0)
                    467:
                    468: static int
                    469: print_hash(struct cdbw *cdbw, struct state *state, int fd, const char *descr)
                    470: {
                    471:        uint32_t data_size;
                    472:        uint8_t buf[90000];
                    473:        size_t i, size, size2, cur_pos;
                    474:        ssize_t ret;
                    475:
                    476:        memcpy(buf, "NBCDB\n\0", 7);
                    477:        buf[7] = 1;
                    478:        strncpy((char *)buf + 8, descr, 16);
1.3       joerg     479:        le32enc(buf + 24, cdbw->data_size);
                    480:        le32enc(buf + 28, cdbw->data_counter);
1.1       joerg     481:        le32enc(buf + 32, state->entries);
                    482:        le32enc(buf + 36, state->seed);
                    483:        cur_pos = 40;
                    484:
                    485:        size = compute_size(state->entries);
                    486:        for (i = 0; i < state->entries; ++i) {
                    487:                COND_FLUSH_BUFFER(4);
                    488:                le32enc(buf + cur_pos, state->g[i]);
                    489:                cur_pos += size;
                    490:        }
1.3       joerg     491:        size2 = compute_size(cdbw->data_size);
1.1       joerg     492:        size = size * state->entries % size2;
                    493:        if (size != 0) {
                    494:                size = size2 - size;
                    495:                COND_FLUSH_BUFFER(4);
                    496:                le32enc(buf + cur_pos, 0);
                    497:                cur_pos += size;
                    498:        }
                    499:        for (data_size = 0, i = 0; i < cdbw->data_counter; ++i) {
                    500:                COND_FLUSH_BUFFER(4);
                    501:                le32enc(buf + cur_pos, data_size);
                    502:                cur_pos += size2;
1.3       joerg     503:                data_size += cdbw->data_len[i];
1.1       joerg     504:        }
                    505:        COND_FLUSH_BUFFER(4);
                    506:        le32enc(buf + cur_pos, data_size);
                    507:        cur_pos += size2;
                    508:
                    509:        for (i = 0; i < cdbw->data_counter; ++i) {
                    510:                COND_FLUSH_BUFFER(cdbw->data_len[i]);
                    511:                if (cdbw->data_len[i] < sizeof(buf)) {
                    512:                        memcpy(buf + cur_pos, cdbw->data_ptr[i],
                    513:                            cdbw->data_len[i]);
                    514:                        cur_pos += cdbw->data_len[i];
                    515:                } else {
                    516:                        ret = write(fd, cdbw->data_ptr[i], cdbw->data_len[i]);
                    517:                        if (ret == -1 || (size_t)ret != cdbw->data_len[i])
                    518:                                return -1;
                    519:                }
                    520:        }
                    521:        if (cur_pos != 0) {
                    522:                ret = write(fd, buf, cur_pos);
                    523:                if (ret == -1 || (size_t)ret != cur_pos)
                    524:                        return -1;
                    525:        }
                    526:        return 0;
                    527: }
                    528:
                    529: int
                    530: cdbw_output(struct cdbw *cdbw, int fd, const char descr[16],
                    531:     uint32_t (*seedgen)(void))
                    532: {
                    533:        struct state state;
                    534:        int rv;
                    535:
                    536:        if (cdbw->data_counter == 0 || cdbw->key_counter == 0) {
                    537:                state.entries = 0;
                    538:                state.seed = 0;
                    539:                print_hash(cdbw, &state, fd, descr);
                    540:                return 0;
                    541:        }
                    542:
1.4       joerg     543: #if HAVE_NBTOOL_CONFIG_H
                    544:        if (seedgen == NULL)
                    545:                seedgen = cdbw_stable_seeder;
                    546: #else
1.1       joerg     547:        if (seedgen == NULL)
                    548:                seedgen = arc4random;
1.4       joerg     549: #endif
1.1       joerg     550:
                    551:        rv = 0;
                    552:
1.3       joerg     553:        state.keys = cdbw->key_counter;
                    554:        state.data_entries = cdbw->data_counter;
1.1       joerg     555:        state.entries = state.keys + (state.keys + 3) / 4;
                    556:        if (state.entries < 10)
                    557:                state.entries = 10;
                    558:
                    559: #define        NALLOC(var, n)  var = calloc(sizeof(*var), n)
                    560:        NALLOC(state.g, state.entries);
                    561:        NALLOC(state.visited, state.entries);
1.6     ! alnsn     562:        NALLOC(state.oedges, state.entries);
        !           563:        NALLOC(state.edges, state.keys);
1.1       joerg     564:        NALLOC(state.output_order, state.keys);
                    565: #undef NALLOC
                    566:
1.6     ! alnsn     567:        if (state.g == NULL || state.visited == NULL || state.oedges == NULL ||
1.1       joerg     568:            state.edges == NULL || state.output_order == NULL) {
                    569:                rv = -1;
                    570:                goto release;
                    571:        }
                    572:
1.4       joerg     573:        state.seed = 0;
1.1       joerg     574:        do {
1.4       joerg     575:                if (seedgen == cdbw_stable_seeder)
                    576:                        ++state.seed;
                    577:                else
                    578:                        state.seed = (*seedgen)();
1.1       joerg     579:        } while (build_graph(cdbw, &state));
                    580:
                    581:        assign_nodes(&state);
                    582:        rv = print_hash(cdbw, &state, fd, descr);
                    583:
                    584: release:
                    585:        free(state.g);
                    586:        free(state.visited);
1.6     ! alnsn     587:        free(state.oedges);
1.1       joerg     588:        free(state.edges);
                    589:        free(state.output_order);
                    590:
                    591:        return rv;
                    592: }

CVSweb <webmaster@jp.NetBSD.org>