1 /* ISC license. */
2
3 #include <unistd.h>
4 #include <stdint.h>
5 #include <errno.h>
6 #include <skalibs/uint32.h>
7 #include <skalibs/diuint32.h>
8 #include <skalibs/buffer.h>
9 #include <skalibs/genalloc.h>
10 #include <skalibs/cdb.h>
11 #include <skalibs/cdb_make.h>
12
cdb_make_start(struct cdb_make * c,int fd)13 int cdb_make_start (struct cdb_make *c, int fd)
14 {
15 c->hplist = genalloc_zero ;
16 c->pos = 2048 ;
17 buffer_init(&c->b, &buffer_write, fd, c->buf, BUFFER_OUTSIZE) ;
18 if (lseek(fd, c->pos, SEEK_SET) < 0) return -1 ;
19 return 0 ;
20 }
21
posplus(struct cdb_make * c,uint32_t len)22 static int posplus (struct cdb_make *c, uint32_t len)
23 {
24 uint32_t newpos = c->pos + len ;
25 if (newpos < len) return (errno = ENOMEM, 0) ;
26 c->pos = newpos ;
27 return 1 ;
28 }
29
cdb_make_addend(struct cdb_make * c,unsigned int keylen,unsigned int datalen,uint32_t h)30 static inline int cdb_make_addend (struct cdb_make *c, unsigned int keylen, unsigned int datalen, uint32_t h)
31 {
32 diuint32 blah = { .left = h, .right = c->pos } ;
33 return genalloc_append(diuint32, &c->hplist, &blah) && posplus(c, 8) && posplus(c, keylen) && posplus(c, datalen) ;
34 }
35
cdb_make_addbegin(struct cdb_make * c,unsigned int keylen,unsigned int datalen)36 static inline ssize_t cdb_make_addbegin (struct cdb_make *c, unsigned int keylen, unsigned int datalen)
37 {
38 char buf[8] ;
39 uint32_pack(buf, (uint32_t)keylen) ;
40 uint32_pack(buf + 4, (uint32_t)datalen) ;
41 return buffer_put(&c->b, buf, 8) ;
42 }
43
cdb_make_add(struct cdb_make * c,char const * key,unsigned int keylen,char const * data,unsigned int datalen)44 int cdb_make_add (struct cdb_make *c, char const *key, unsigned int keylen, char const *data, unsigned int datalen)
45 {
46 if (cdb_make_addbegin(c, keylen, datalen) < 0
47 || buffer_put(&c->b, key, keylen) < 0
48 || buffer_put(&c->b, data, datalen) < 0
49 || !cdb_make_addend(c, keylen, datalen, cdb_hash(key, keylen)))
50 {
51 genalloc_free(diuint32, &c->hplist) ;
52 return -1 ;
53 }
54 return 0 ;
55 }
56
cdb_make_finish(struct cdb_make * c)57 int cdb_make_finish (struct cdb_make *c)
58 {
59 uint32_t count[256] ;
60 uint32_t start[256] ;
61 char final[2048] ;
62 unsigned int size = 1 ;
63 unsigned int n = genalloc_len(diuint32, &c->hplist) ;
64 unsigned int i = 0 ;
65 diuint32 *hp = genalloc_s(diuint32, &c->hplist) ;
66
67 for (; i < 256 ; i++) count[i] = 0 ;
68 for (i = 0 ; i < n ; i++) ++count[hp[i].left & 255] ;
69
70 {
71 uint32_t u = 0 ;
72 for (i = 0 ; i < 256 ; i++) start[i] = u += count[i] ; /* bounded by n */
73 for (i = 0 ; i < 256 ; i++)
74 {
75 u = count[i] << 1 ;
76 if (u > size) size = u ;
77 }
78 size += n ; /* no overflow possible up to now */
79 u = 0xffffffffUL ; u /= sizeof(diuint32) ;
80 if (size > u) return (errno = ENOMEM, -1) ;
81 }
82 i = n ;
83 {
84 diuint32 split[size] ;
85 while (i--) split[--start[hp[i].left & 255]] = hp[i] ;
86 genalloc_free(diuint32, &c->hplist) ;
87 hp = split + n ;
88
89 for (i = 0 ; i < 256 ; ++i)
90 {
91 char buf[8] ;
92 uint32_t k = count[i] ;
93 uint32_t len = k << 1 ; /* no overflow possible */
94 diuint32 *p = split + start[i] ;
95 unsigned int j = 0 ;
96
97 uint32_pack(final + (i << 3), c->pos) ;
98 uint32_pack(final + (i << 3) + 4, len) ;
99
100 for (; j < len ; j++) hp[j].left = hp[j].right = 0 ;
101 for (j = 0 ; j < k ; j++)
102 {
103 uint32_t where = (p->left >> 8) % len ;
104 while (hp[where].right) if (++where == len) where = 0 ;
105 hp[where] = *p++ ;
106 }
107
108 for (j = 0 ; j < len ; j++)
109 {
110 uint32_pack(buf, hp[j].left) ;
111 uint32_pack(buf + 4, hp[j].right) ;
112 if (buffer_put(&c->b, buf, 8) < 0) return -1 ;
113 if (!posplus(c, 8)) return -1 ;
114 }
115 }
116 }
117
118 if (!buffer_flush(&c->b)) return -1 ;
119 if (lseek(buffer_fd(&c->b), 0, SEEK_SET) < 0) return -1 ;
120 if (buffer_putflush(&c->b, final, 2048) < 0) return -1 ;
121 return 0 ;
122 }
123