xref: /PHP-8.1/ext/dba/libcdb/cdb_make.c (revision 01b3fc03)
1 /*
2    +----------------------------------------------------------------------+
3    | Copyright (c) The PHP Group                                          |
4    +----------------------------------------------------------------------+
5    | This source file is subject to version 3.01 of the PHP license,      |
6    | that is bundled with this package in the file LICENSE, and is        |
7    | available through the world-wide-web at the following url:           |
8    | https://www.php.net/license/3_01.txt                                 |
9    | If you did not receive a copy of the PHP license and are unable to   |
10    | obtain it through the world-wide-web, please send a note to          |
11    | license@php.net so we can mail you a copy immediately.               |
12    +----------------------------------------------------------------------+
13    | Author: Marcus Boerger <helly@php.net>                               |
14    +----------------------------------------------------------------------+
15  */
16 
17 /* $Id: 8144ef10fb5d90aa26072e8b56f03d5238dd0d24 $ */
18 
19 /* incorporated from D.J.Bernstein's cdb-0.75 (http://cr.yp.to/cdb.html)*/
20 
21 #ifdef HAVE_CONFIG_H
22 #include "config.h"
23 #endif
24 
25 #include "php.h"
26 
27 #include <sys/types.h>
28 #ifdef HAVE_UNISTD_H
29 #include <unistd.h>
30 #endif
31 #include <stdlib.h>
32 #include <stdio.h>
33 #include <errno.h>
34 #include "cdb.h"
35 #include "cdb_make.h"
36 #include "uint32.h"
37 
38 /* {{{ cdb_make_write */
cdb_make_write(struct cdb_make * c,char * buf,uint32 sz)39 static int cdb_make_write(struct cdb_make *c, char *buf, uint32 sz) {
40 	return php_stream_write(c->fp, buf, sz) == sz ? 0 : -1;
41 }
42 
43 /* {{{ cdb_posplus */
cdb_posplus(struct cdb_make * c,uint32 len)44 static int cdb_posplus(struct cdb_make *c, uint32 len)
45 {
46 	uint32 newpos = c->pos + len;
47 	if (newpos < len) {
48 		errno = ENOMEM;
49 		return -1;
50 	}
51 	c->pos = newpos;
52 	return 0;
53 }
54 /* }}} */
55 
56 /* {{{ cdb_make_start */
cdb_make_start(struct cdb_make * c,php_stream * f)57 int cdb_make_start(struct cdb_make *c, php_stream * f)
58 {
59 	c->head = 0;
60 	c->split = 0;
61 	c->hash = 0;
62 	c->numentries = 0;
63 	c->fp = f;
64 	c->pos = sizeof(c->final);
65 	if (php_stream_seek(f, c->pos, SEEK_SET) == -1) {
66 		php_error_docref(NULL, E_NOTICE, "Fseek failed");
67 		return -1;
68 	}
69 	return php_stream_tell(c->fp);
70 }
71 /* }}} */
72 
73 /* {{{ cdb_make_addend */
cdb_make_addend(struct cdb_make * c,unsigned int keylen,unsigned int datalen,uint32 h)74 int cdb_make_addend(struct cdb_make *c, unsigned int keylen, unsigned int datalen, uint32 h)
75 {
76 	struct cdb_hplist *head;
77 
78 	head = c->head;
79 	if (!head || (head->num >= CDB_HPLIST)) {
80 		head = (struct cdb_hplist *) emalloc(sizeof(struct cdb_hplist));
81 		if (!head)
82 			return -1;
83 		head->num = 0;
84 		head->next = c->head;
85 		c->head = head;
86 	}
87 	head->hp[head->num].h = h;
88 	head->hp[head->num].p = c->pos;
89 	++head->num;
90 	++c->numentries;
91 	if (cdb_posplus(c,8) == -1)
92 		return -1;
93 	if (cdb_posplus(c, keylen) == -1)
94 		return -1;
95 	if (cdb_posplus(c, datalen) == -1)
96 		return -1;
97 	return 0;
98 }
99 /* }}} */
100 
101 /* {{{ cdb_make_addbegin */
cdb_make_addbegin(struct cdb_make * c,unsigned int keylen,unsigned int datalen)102 int cdb_make_addbegin(struct cdb_make *c, unsigned int keylen, unsigned int datalen)
103 {
104 	char buf[8];
105 
106 	if (keylen > 0xffffffff) {
107 		errno = ENOMEM;
108 		return -1;
109 	}
110 	if (datalen > 0xffffffff) {
111 		errno = ENOMEM;
112 		return -1;
113 	}
114 
115 	uint32_pack(buf, keylen);
116 	uint32_pack(buf + 4, datalen);
117 	if (cdb_make_write(c, buf, 8) != 0)
118 		return -1;
119 	return 0;
120 }
121 
122 /* {{{ cdb_make_add */
cdb_make_add(struct cdb_make * c,char * key,unsigned int keylen,char * data,unsigned int datalen)123 int cdb_make_add(struct cdb_make *c,char *key,unsigned int keylen,char *data,unsigned int datalen)
124 {
125 	if (cdb_make_addbegin(c, keylen, datalen) == -1)
126 		return -1;
127 	if (cdb_make_write(c, key, keylen) != 0)
128 		return -1;
129 	if (cdb_make_write(c, data, datalen) != 0)
130 		return -1;
131 	return cdb_make_addend(c, keylen, datalen, cdb_hash(key, keylen));
132 }
133 /* }}} */
134 
135 /* {{{ cdb_make_finish */
cdb_make_finish(struct cdb_make * c)136 int cdb_make_finish(struct cdb_make *c)
137 {
138 	char buf[8];
139 	int i;
140 	uint32 len;
141 	uint32 u;
142 	uint32 memsize;
143 	uint32 count;
144 	uint32 where;
145 	struct cdb_hplist *x;
146 	struct cdb_hp *hp;
147 
148 	for (i = 0;i < 256;++i)
149 	c->count[i] = 0;
150 
151 	for (x = c->head; x; x = x->next) {
152 		i = x->num;
153 		while (i--)
154 		++c->count[255 & x->hp[i].h];
155 	}
156 
157 	memsize = 1;
158 	for (i = 0;i < 256;++i) {
159 		u = c->count[i] * 2;
160 		if (u > memsize)
161 		memsize = u;
162 	}
163 
164 	memsize += c->numentries; /* no overflow possible up to now */
165 	u = (uint32) 0 - (uint32) 1;
166 	u /= sizeof(struct cdb_hp);
167 	if (memsize > u) {
168 		errno = ENOMEM;
169 		return -1;
170 	}
171 
172 	c->split = (struct cdb_hp *) safe_emalloc(memsize, sizeof(struct cdb_hp), 0);
173 	if (!c->split)
174 		return -1;
175 
176 	c->hash = c->split + c->numentries;
177 
178 	u = 0;
179 	for (i = 0;i < 256;++i) {
180 		u += c->count[i]; /* bounded by numentries, so no overflow */
181 		c->start[i] = u;
182 	}
183 
184 	for (x = c->head; x; x = x->next) {
185 		i = x->num;
186 		while (i--)
187 		c->split[--c->start[255 & x->hp[i].h]] = x->hp[i];
188 	}
189 
190 	for (i = 0;i < 256;++i) {
191 		count = c->count[i];
192 
193 		len = count + count; /* no overflow possible */
194 		uint32_pack(c->final + 8 * i,c->pos);
195 		uint32_pack(c->final + 8 * i + 4,len);
196 
197 		for (u = 0;u < len;++u)
198 			c->hash[u].h = c->hash[u].p = 0;
199 
200 		hp = c->split + c->start[i];
201 		for (u = 0;u < count;++u) {
202 			where = (hp->h >> 8) % len;
203 			while (c->hash[where].p)
204 				if (++where == len)
205 					where = 0;
206 			c->hash[where] = *hp++;
207 		}
208 
209 		for (u = 0;u < len;++u) {
210 			uint32_pack(buf, c->hash[u].h);
211 			uint32_pack(buf + 4, c->hash[u].p);
212 			if (cdb_make_write(c, buf, 8) != 0)
213 				return -1;
214 			if (cdb_posplus(c, 8) == -1)
215 				return -1;
216 		}
217 	}
218 
219 	if (c->split)
220 		efree(c->split);
221 
222 	for (x = c->head; x; c->head = x) {
223 		x = x->next;
224 		efree(c->head);
225 	}
226 
227 	if (php_stream_flush(c->fp) != 0)
228 		return -1;
229 	php_stream_rewind(c->fp);
230 	if (php_stream_tell(c->fp) != 0)
231 		return -1;
232 	if (cdb_make_write(c, c->final, sizeof(c->final)) != 0)
233 		return -1;
234 	return php_stream_flush(c->fp);
235 }
236 /* }}} */
237 
238 /* {{{ cdb_make_version */
cdb_make_version()239 char *cdb_make_version()
240 {
241 	return "0.75, $Id: 8144ef10fb5d90aa26072e8b56f03d5238dd0d24 $";
242 }
243