cdbmake_finish.c (2090B)
1 /* ISC license. */ 2 3 #include <unistd.h> 4 #include <stdint.h> 5 #include <errno.h> 6 7 #include <skalibs/uint32.h> 8 #include <skalibs/diuint32.h> 9 #include <skalibs/buffer.h> 10 #include <skalibs/genalloc.h> 11 #include <skalibs/cdbmake.h> 12 #include "cdbmake-internal.h" 13 14 int cdbmake_finish (cdbmaker *c) 15 { 16 uint32_t count[256] ; 17 uint32_t start[256] ; 18 char final[2048] ; 19 unsigned int size = 1 ; 20 unsigned int n = genalloc_len(diuint32, &c->hplist) ; 21 unsigned int i = 0 ; 22 diuint32 *hp = genalloc_s(diuint32, &c->hplist) ; 23 24 for (; i < 256 ; i++) count[i] = 0 ; 25 for (i = 0 ; i < n ; i++) ++count[hp[i].left & 255] ; 26 27 { 28 uint32_t u = 0 ; 29 for (i = 0 ; i < 256 ; i++) start[i] = u += count[i] ; /* bounded by n */ 30 for (i = 0 ; i < 256 ; i++) 31 { 32 u = count[i] << 1 ; 33 if (u > size) size = u ; 34 } 35 size += n ; /* no overflow possible up to now */ 36 u = 0xffffffffUL ; u /= sizeof(diuint32) ; 37 if (size > u) return (errno = ENOMEM, 0) ; 38 } 39 i = n ; 40 { 41 diuint32 split[size] ; 42 while (i--) split[--start[hp[i].left & 255]] = hp[i] ; 43 genalloc_free(diuint32, &c->hplist) ; 44 hp = split + n ; 45 46 for (i = 0 ; i < 256 ; ++i) 47 { 48 char buf[8] ; 49 uint32_t k = count[i] ; 50 uint32_t len = k << 1 ; /* no overflow possible */ 51 diuint32 *p = split + start[i] ; 52 53 uint32_pack(final + (i << 3), c->pos) ; 54 uint32_pack(final + (i << 3) + 4, len) ; 55 56 for (uint32_t j = 0 ; j < len ; j++) hp[j].left = hp[j].right = 0 ; 57 for (uint32_t j = 0 ; j < k ; j++) 58 { 59 uint32_t where = (p->left >> 8) % len ; 60 while (hp[where].right) if (++where == len) where = 0 ; 61 hp[where] = *p++ ; 62 } 63 64 for (uint32_t j = 0 ; j < len ; j++) 65 { 66 uint32_pack(buf, hp[j].left) ; 67 uint32_pack(buf + 4, hp[j].right) ; 68 if (buffer_put(&c->b, buf, 8) < 0) return 0 ; 69 if (!cdbmake_posplus(c, 8)) return 0 ; 70 } 71 } 72 } 73 74 if (!buffer_flush(&c->b) 75 || lseek(buffer_fd(&c->b), 0, SEEK_SET) == -1 76 || buffer_putflush(&c->b, final, 2048) < 2048) return 0 ; 77 return 1 ; 78 }