xref: /PHP-8.1/ext/dba/libcdb/cdb.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: 10cc4f985215693867f001a49085c47ae65f38dd $ */
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 #include <sys/stat.h>
29 #ifndef PHP_WIN32
30 #include <sys/mman.h>
31 #endif
32 #ifdef HAVE_UNISTD_H
33 #include <unistd.h>
34 #endif
35 #include <string.h>
36 #include <errno.h>
37 #include "cdb.h"
38 
39 #ifndef EPROTO
40 # define EPROTO -15  /* cdb 0.75's default for PROTOless systems */
41 #endif
42 
43 /* {{{ cdb_match */
cdb_match(struct cdb * c,char * key,unsigned int len,uint32 pos)44 static int cdb_match(struct cdb *c, char *key, unsigned int len, uint32 pos)
45 {
46 	char buf[32];
47 	unsigned int n;
48 
49 	while (len > 0) {
50 		n = sizeof(buf);
51 		if (n > len)
52 			n = len;
53 		if (cdb_read(c, buf, n, pos) == -1)
54 			return -1;
55 		if (memcmp(buf, key, n))
56 			return 0;
57 		pos += n;
58 		key += n;
59 		len -= n;
60 	}
61 	return 1;
62 }
63 /* }}} */
64 
65 /* {{{ cdb_hash */
cdb_hash(char * buf,unsigned int len)66 uint32 cdb_hash(char *buf, unsigned int len)
67 {
68 	uint32 h;
69 	const unsigned char * b = (unsigned char *)buf;
70 
71 	h = CDB_HASHSTART;
72 	while (len--) {
73 		h = ( h + (h << 5)) ^ (*b++);
74 	}
75 	return h;
76 }
77 /* }}} */
78 
79 /* {{{ cdb_free */
cdb_free(struct cdb * c)80 void cdb_free(struct cdb *c)
81 {
82 }
83 /* }}} */
84 
85 /* {{{ cdb_findstart */
cdb_findstart(struct cdb * c)86 void cdb_findstart(struct cdb *c)
87 {
88 	c->loop = 0;
89 }
90 /* }}} */
91 
92 /* {{{ cdb_init */
cdb_init(struct cdb * c,php_stream * fp)93 void cdb_init(struct cdb *c, php_stream *fp)
94 {
95 	cdb_free(c);
96 	cdb_findstart(c);
97 	c->fp = fp;
98 }
99 /* }}} */
100 
101 /* {{{ cdb_read */
cdb_read(struct cdb * c,char * buf,unsigned int len,uint32 pos)102 int cdb_read(struct cdb *c, char *buf, unsigned int len, uint32 pos)
103 {
104 	if (php_stream_seek(c->fp, pos, SEEK_SET) == -1) {
105 		errno = EPROTO;
106 		return -1;
107 	}
108 	while (len > 0) {
109 		int r;
110 		do {
111 			r = php_stream_read(c->fp, buf, len);
112 		} while ((r == -1) && (errno == EINTR));
113 		if (r == -1)
114 			return -1;
115 		if (r == 0) {
116 			errno = EPROTO;
117 			return -1;
118 		}
119 		buf += r;
120 		len -= r;
121 	}
122 	return 0;
123 }
124 /* }}} */
125 
126 /* {{{ cdb_findnext */
cdb_findnext(struct cdb * c,char * key,unsigned int len)127 int cdb_findnext(struct cdb *c, char *key, unsigned int len)
128 {
129 	char buf[8];
130 	uint32 pos;
131 	uint32 u;
132 
133 	if (!c->loop) {
134 		u = cdb_hash(key, len);
135 		if (cdb_read(c, buf, 8, (u << 3) & 2047) == -1)
136 			return -1;
137 		uint32_unpack(buf + 4,&c->hslots);
138 		if (!c->hslots)
139 			return 0;
140 		uint32_unpack(buf, &c->hpos);
141 		c->khash = u;
142 		u >>= 8;
143 		u %= c->hslots;
144 		u <<= 3;
145 		c->kpos = c->hpos + u;
146 	}
147 
148 	while (c->loop < c->hslots) {
149 		if (cdb_read(c, buf, 8, c->kpos) == -1)
150 			return -1;
151 		uint32_unpack(buf + 4, &pos);
152 		if (!pos)
153 			return 0;
154 		c->loop += 1;
155 		c->kpos += 8;
156 		if (c->kpos == c->hpos + (c->hslots << 3))
157 			c->kpos = c->hpos;
158 		uint32_unpack(buf, &u);
159 		if (u == c->khash) {
160 			if (cdb_read(c, buf, 8, pos) == -1)
161 				return -1;
162 			uint32_unpack(buf, &u);
163 			if (u == len)
164 			switch(cdb_match(c, key, len, pos + 8)) {
165 			case -1:
166 				return -1;
167 			case 1:
168 				uint32_unpack(buf + 4, &c->dlen);
169 				c->dpos = pos + 8 + len;
170 				return 1;
171 			}
172 		}
173 	}
174 
175 	return 0;
176 }
177 /* }}} */
178 
179 /* {{{ cdb_find */
cdb_find(struct cdb * c,char * key,unsigned int len)180 int cdb_find(struct cdb *c, char *key, unsigned int len)
181 {
182 	cdb_findstart(c);
183 	return cdb_findnext(c, key, len);
184 }
185 /* }}} */
186 
187 /* {{{ cdb_version */
cdb_version()188 char *cdb_version()
189 {
190 	return "0.75, $Id: 10cc4f985215693867f001a49085c47ae65f38dd $";
191 }
192 /* }}} */
193