xref: /PHP-7.2/ext/dba/libcdb/cdb.c (revision 7a7ec01a)
1 /*
2    +----------------------------------------------------------------------+
3    | PHP Version 7                                                        |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1997-2018 The PHP Group                                |
6    +----------------------------------------------------------------------+
7    | This source file is subject to version 3.01 of the PHP license,      |
8    | that is bundled with this package in the file LICENSE, and is        |
9    | available through the world-wide-web at the following url:           |
10    | http://www.php.net/license/3_01.txt                                  |
11    | If you did not receive a copy of the PHP license and are unable to   |
12    | obtain it through the world-wide-web, please send a note to          |
13    | license@php.net so we can mail you a copy immediately.               |
14    +----------------------------------------------------------------------+
15    | Author: Marcus Boerger <helly@php.net>                               |
16    +----------------------------------------------------------------------+
17  */
18 
19 /* $Id: d8d6f46f29c667868a8d3630cd0d08003d0236bd $ */
20 
21 /* incorporated from D.J.Bernstein's cdb-0.75 (http://cr.yp.to/cdb.html)*/
22 
23 #ifdef HAVE_CONFIG_H
24 #include "config.h"
25 #endif
26 
27 #include "php.h"
28 
29 #include <sys/types.h>
30 #include <sys/stat.h>
31 #ifndef PHP_WIN32
32 #include <sys/mman.h>
33 #endif
34 #ifdef HAVE_UNISTD_H
35 #include <unistd.h>
36 #endif
37 #include <string.h>
38 #include <errno.h>
39 #include "cdb.h"
40 
41 #ifndef EPROTO
42 # define EPROTO -15  /* cdb 0.75's default for PROTOless systems */
43 #endif
44 
45 /* {{{ cdb_match */
cdb_match(struct cdb * c,char * key,unsigned int len,uint32 pos)46 static int cdb_match(struct cdb *c, char *key, unsigned int len, uint32 pos)
47 {
48 	char buf[32];
49 	unsigned int n;
50 
51 	while (len > 0) {
52 		n = sizeof(buf);
53 		if (n > len)
54 			n = len;
55 		if (cdb_read(c, buf, n, pos) == -1)
56 			return -1;
57 		if (memcmp(buf, key, n))
58 			return 0;
59 		pos += n;
60 		key += n;
61 		len -= n;
62 	}
63 	return 1;
64 }
65 /* }}} */
66 
67 /* {{{ cdb_hash */
cdb_hash(char * buf,unsigned int len)68 uint32 cdb_hash(char *buf, unsigned int len)
69 {
70 	uint32 h;
71 	const unsigned char * b = (unsigned char *)buf;
72 
73 	h = CDB_HASHSTART;
74 	while (len--) {
75 		h = ( h + (h << 5)) ^ (*b++);
76 	}
77 	return h;
78 }
79 /* }}} */
80 
81 /* {{{ cdb_free */
cdb_free(struct cdb * c)82 void cdb_free(struct cdb *c)
83 {
84 }
85 /* }}} */
86 
87 /* {{{ cdb_findstart */
cdb_findstart(struct cdb * c)88 void cdb_findstart(struct cdb *c)
89 {
90 	c->loop = 0;
91 }
92 /* }}} */
93 
94 /* {{{ cdb_init */
cdb_init(struct cdb * c,php_stream * fp)95 void cdb_init(struct cdb *c, php_stream *fp)
96 {
97 	cdb_free(c);
98 	cdb_findstart(c);
99 	c->fp = fp;
100 }
101 /* }}} */
102 
103 /* {{{ cdb_read */
cdb_read(struct cdb * c,char * buf,unsigned int len,uint32 pos)104 int cdb_read(struct cdb *c, char *buf, unsigned int len, uint32 pos)
105 {
106 	if (php_stream_seek(c->fp, pos, SEEK_SET) == -1) {
107 		errno = EPROTO;
108 		return -1;
109 	}
110 	while (len > 0) {
111 		int r;
112 		do {
113 			r = php_stream_read(c->fp, buf, len);
114 		} while ((r == -1) && (errno == EINTR));
115 		if (r == -1)
116 			return -1;
117 		if (r == 0) {
118 			errno = EPROTO;
119 			return -1;
120 		}
121 		buf += r;
122 		len -= r;
123 	}
124 	return 0;
125 }
126 /* }}} */
127 
128 /* {{{ cdb_findnext */
cdb_findnext(struct cdb * c,char * key,unsigned int len)129 int cdb_findnext(struct cdb *c, char *key, unsigned int len)
130 {
131 	char buf[8];
132 	uint32 pos;
133 	uint32 u;
134 
135 	if (!c->loop) {
136 		u = cdb_hash(key, len);
137 		if (cdb_read(c, buf, 8, (u << 3) & 2047) == -1)
138 			return -1;
139 		uint32_unpack(buf + 4,&c->hslots);
140 		if (!c->hslots)
141 			return 0;
142 		uint32_unpack(buf, &c->hpos);
143 		c->khash = u;
144 		u >>= 8;
145 		u %= c->hslots;
146 		u <<= 3;
147 		c->kpos = c->hpos + u;
148 	}
149 
150 	while (c->loop < c->hslots) {
151 		if (cdb_read(c, buf, 8, c->kpos) == -1)
152 			return -1;
153 		uint32_unpack(buf + 4, &pos);
154 		if (!pos)
155 			return 0;
156 		c->loop += 1;
157 		c->kpos += 8;
158 		if (c->kpos == c->hpos + (c->hslots << 3))
159 			c->kpos = c->hpos;
160 		uint32_unpack(buf, &u);
161 		if (u == c->khash) {
162 			if (cdb_read(c, buf, 8, pos) == -1)
163 				return -1;
164 			uint32_unpack(buf, &u);
165 			if (u == len)
166 			switch(cdb_match(c, key, len, pos + 8)) {
167 			case -1:
168 				return -1;
169 			case 1:
170 				uint32_unpack(buf + 4, &c->dlen);
171 				c->dpos = pos + 8 + len;
172 				return 1;
173 			}
174 		}
175 	}
176 
177 	return 0;
178 }
179 /* }}} */
180 
181 /* {{{ cdb_find */
cdb_find(struct cdb * c,char * key,unsigned int len)182 int cdb_find(struct cdb *c, char *key, unsigned int len)
183 {
184 	cdb_findstart(c);
185 	return cdb_findnext(c, key, len);
186 }
187 /* }}} */
188 
189 /* {{{ cdb_version */
cdb_version()190 char *cdb_version()
191 {
192 	return "0.75, $Id: d8d6f46f29c667868a8d3630cd0d08003d0236bd $";
193 }
194 /* }}} */
195