1 /* cdb_make.c: basic cdb creation routines
2 *
3 * This file is a part of tinycdb package by Michael Tokarev, mjt@corpit.ru.
4 * Public domain.
5 */
6
7 #include <unistd.h>
8 #include <stdlib.h>
9 #include <string.h>
10 #include "cdb_int.h"
11
12 void
cdb_pack(unsigned num,unsigned char buf[4])13 cdb_pack(unsigned num, unsigned char buf[4])
14 {
15 buf[0] = num & 255; num >>= 8;
16 buf[1] = num & 255; num >>= 8;
17 buf[2] = num & 255;
18 buf[3] = num >> 8;
19 }
20
21 int
cdb_make_start(struct cdb_make * cdbmp,int fd)22 cdb_make_start(struct cdb_make *cdbmp, int fd)
23 {
24 memset(cdbmp, 0, sizeof(*cdbmp));
25 cdbmp->cdb_fd = fd;
26 cdbmp->cdb_dpos = 2048;
27 cdbmp->cdb_bpos = cdbmp->cdb_buf + 2048;
28 return 0;
29 }
30
31 int internal_function
_cdb_make_fullwrite(int fd,const unsigned char * buf,unsigned len)32 _cdb_make_fullwrite(int fd, const unsigned char *buf, unsigned len)
33 {
34 while(len) {
35 int l = write(fd, buf, len);
36 if (l > 0) {
37 len -= l;
38 buf += l;
39 }
40 else if (l < 0 && errno != EINTR)
41 return -1;
42 }
43 return 0;
44 }
45
46 int internal_function
_cdb_make_flush(struct cdb_make * cdbmp)47 _cdb_make_flush(struct cdb_make *cdbmp) {
48 unsigned len = cdbmp->cdb_bpos - cdbmp->cdb_buf;
49 if (len) {
50 if (_cdb_make_fullwrite(cdbmp->cdb_fd, cdbmp->cdb_buf, len) < 0)
51 return -1;
52 cdbmp->cdb_bpos = cdbmp->cdb_buf;
53 }
54 return 0;
55 }
56
57 int internal_function
_cdb_make_write(struct cdb_make * cdbmp,const unsigned char * ptr,unsigned len)58 _cdb_make_write(struct cdb_make *cdbmp, const unsigned char *ptr, unsigned len)
59 {
60 unsigned l = sizeof(cdbmp->cdb_buf) - (cdbmp->cdb_bpos - cdbmp->cdb_buf);
61 cdbmp->cdb_dpos += len;
62 if (len > l) {
63 memcpy(cdbmp->cdb_bpos, ptr, l);
64 cdbmp->cdb_bpos += l;
65 if (_cdb_make_flush(cdbmp) < 0)
66 return -1;
67 ptr += l; len -= l;
68 l = len / sizeof(cdbmp->cdb_buf);
69 if (l) {
70 l *= sizeof(cdbmp->cdb_buf);
71 if (_cdb_make_fullwrite(cdbmp->cdb_fd, ptr, l) < 0)
72 return -1;
73 ptr += l; len -= l;
74 }
75 }
76 if (len) {
77 memcpy(cdbmp->cdb_bpos, ptr, len);
78 cdbmp->cdb_bpos += len;
79 }
80 return 0;
81 }
82
83 static int
cdb_make_finish_internal(struct cdb_make * cdbmp)84 cdb_make_finish_internal(struct cdb_make *cdbmp)
85 {
86 unsigned hcnt[256]; /* hash table counts */
87 unsigned hpos[256]; /* hash table positions */
88 struct cdb_rec *htab;
89 unsigned char *p;
90 struct cdb_rl *rl;
91 unsigned hsize;
92 unsigned t, i;
93
94 if (((0xffffffff - cdbmp->cdb_dpos) >> 3) < cdbmp->cdb_rcnt)
95 return errno = ENOMEM, -1;
96
97 /* count htab sizes and reorder reclists */
98 hsize = 0;
99 for (t = 0; t < 256; ++t) {
100 struct cdb_rl *rlt = NULL;
101 i = 0;
102 rl = cdbmp->cdb_rec[t];
103 while(rl) {
104 struct cdb_rl *rln = rl->next;
105 rl->next = rlt;
106 rlt = rl;
107 i += rl->cnt;
108 rl = rln;
109 }
110 cdbmp->cdb_rec[t] = rlt;
111 if (hsize < (hcnt[t] = i << 1))
112 hsize = hcnt[t];
113 }
114
115 /* allocate memory to hold max htable */
116 htab = (struct cdb_rec*)malloc((hsize + 2) * sizeof(struct cdb_rec));
117 if (!htab)
118 return errno = ENOENT, -1;
119 p = (unsigned char *)htab;
120 htab += 2;
121
122 /* build hash tables */
123 for (t = 0; t < 256; ++t) {
124 unsigned len, hi;
125 hpos[t] = cdbmp->cdb_dpos;
126 if ((len = hcnt[t]) == 0)
127 continue;
128 for (i = 0; i < len; ++i)
129 htab[i].hval = htab[i].rpos = 0;
130 for (rl = cdbmp->cdb_rec[t]; rl; rl = rl->next)
131 for (i = 0; i < rl->cnt; ++i) {
132 hi = (rl->rec[i].hval >> 8) % len;
133 while(htab[hi].rpos)
134 if (++hi == len)
135 hi = 0;
136 htab[hi] = rl->rec[i];
137 }
138 for (i = 0; i < len; ++i) {
139 cdb_pack(htab[i].hval, p + (i << 3));
140 cdb_pack(htab[i].rpos, p + (i << 3) + 4);
141 }
142 if (_cdb_make_write(cdbmp, p, len << 3) < 0) {
143 free(p);
144 return -1;
145 }
146 }
147 free(p);
148 if (_cdb_make_flush(cdbmp) < 0)
149 return -1;
150 p = cdbmp->cdb_buf;
151 for (t = 0; t < 256; ++t) {
152 cdb_pack(hpos[t], p + (t << 3));
153 cdb_pack(hcnt[t], p + (t << 3) + 4);
154 }
155 if (lseek(cdbmp->cdb_fd, 0, 0) != 0 ||
156 _cdb_make_fullwrite(cdbmp->cdb_fd, p, 2048) != 0)
157 return -1;
158
159 return 0;
160 }
161
162 static void
cdb_make_free(struct cdb_make * cdbmp)163 cdb_make_free(struct cdb_make *cdbmp)
164 {
165 unsigned t;
166 for(t = 0; t < 256; ++t) {
167 struct cdb_rl *rl = cdbmp->cdb_rec[t];
168 while(rl) {
169 struct cdb_rl *tm = rl;
170 rl = rl->next;
171 free(tm);
172 }
173 }
174 }
175
176 int
cdb_make_finish(struct cdb_make * cdbmp)177 cdb_make_finish(struct cdb_make *cdbmp)
178 {
179 int r = cdb_make_finish_internal(cdbmp);
180 cdb_make_free(cdbmp);
181 return r;
182 }
183
184