Back to index

php5  5.3.10
cdb_make.c
Go to the documentation of this file.
00001 /*
00002    +----------------------------------------------------------------------+
00003    | PHP Version 5                                                        |
00004    +----------------------------------------------------------------------+
00005    | Copyright (c) 1997-2010 The PHP Group                                |
00006    +----------------------------------------------------------------------+
00007    | This source file is subject to version 3.01 of the PHP license,      |
00008    | that is bundled with this package in the file LICENSE, and is        |
00009    | available through the world-wide-web at the following url:           |
00010    | http://www.php.net/license/3_01.txt                                  |
00011    | If you did not receive a copy of the PHP license and are unable to   |
00012    | obtain it through the world-wide-web, please send a note to          |
00013    | license@php.net so we can mail you a copy immediately.               |
00014    +----------------------------------------------------------------------+
00015    | Author: Marcus Boerger <helly@php.net>                               |
00016    +----------------------------------------------------------------------+
00017  */
00018 
00019 /* $Id: cdb_make.c 293036 2010-01-03 09:23:27Z sebastian $ */
00020 
00021 /* incorporated from D.J.Bernstein's cdb-0.75 (http://cr.yp.to/cdb.html)*/
00022 
00023 #ifdef HAVE_CONFIG_H
00024 #include "config.h"
00025 #endif
00026 
00027 #include "php.h"
00028 
00029 #include <sys/types.h>
00030 #ifdef HAVE_UNISTD_H
00031 #include <unistd.h>
00032 #endif
00033 #include <stdlib.h>
00034 #include <stdio.h>
00035 #include <errno.h>
00036 #include "cdb.h"
00037 #include "cdb_make.h"
00038 #include "uint32.h"
00039 
00040 /* {{{ cdb_make_write */
00041 static int cdb_make_write(struct cdb_make *c, char *buf, uint32 sz TSRMLS_DC) {
00042        return php_stream_write(c->fp, buf, sz) == sz ? 0 : -1;
00043 }
00044 
00045 /* {{{ cdb_posplus */
00046 static int cdb_posplus(struct cdb_make *c, uint32 len)
00047 {
00048        uint32 newpos = c->pos + len;
00049        if (newpos < len) {
00050               errno = ENOMEM;
00051               return -1;
00052        }
00053        c->pos = newpos;
00054        return 0;
00055 }
00056 /* }}} */
00057 
00058 /* {{{ cdb_make_start */
00059 int cdb_make_start(struct cdb_make *c, php_stream * f TSRMLS_DC)
00060 {
00061        c->head = 0;
00062        c->split = 0;
00063        c->hash = 0;
00064        c->numentries = 0;
00065        c->fp = f;
00066        c->pos = sizeof(c->final);
00067        if (php_stream_seek(f, c->pos, SEEK_SET) == -1) {
00068               php_error_docref(NULL TSRMLS_CC, E_NOTICE, "Fseek failed");
00069               return -1;
00070        }
00071        return php_stream_tell(c->fp);
00072 }
00073 /* }}} */
00074 
00075 /* {{{ cdb_make_addend */
00076 int cdb_make_addend(struct cdb_make *c, unsigned int keylen, unsigned int datalen, uint32 h TSRMLS_DC)
00077 {
00078        struct cdb_hplist *head;
00079 
00080        head = c->head;
00081        if (!head || (head->num >= CDB_HPLIST)) {
00082               head = (struct cdb_hplist *) emalloc(sizeof(struct cdb_hplist));
00083               if (!head)
00084                      return -1;
00085               head->num = 0;
00086               head->next = c->head;
00087               c->head = head;
00088        }
00089        head->hp[head->num].h = h;
00090        head->hp[head->num].p = c->pos;
00091        ++head->num;
00092        ++c->numentries;
00093        if (cdb_posplus(c,8) == -1)
00094               return -1;
00095        if (cdb_posplus(c, keylen) == -1)
00096               return -1;
00097        if (cdb_posplus(c, datalen) == -1)
00098               return -1;
00099        return 0;
00100 }
00101 /* }}} */
00102 
00103 /* {{{ cdb_make_addbegin */
00104 int cdb_make_addbegin(struct cdb_make *c, unsigned int keylen, unsigned int datalen TSRMLS_DC)
00105 {
00106        char buf[8];
00107 
00108        if (keylen > 0xffffffff) {
00109               errno = ENOMEM;
00110               return -1;
00111        }
00112        if (datalen > 0xffffffff) {
00113               errno = ENOMEM;
00114               return -1;
00115        }
00116 
00117        uint32_pack(buf, keylen);
00118        uint32_pack(buf + 4, datalen);
00119        if (cdb_make_write(c, buf, 8 TSRMLS_CC) != 0)
00120               return -1;
00121        return 0;
00122 }
00123 
00124 /* {{{ cdb_make_add */
00125 int cdb_make_add(struct cdb_make *c,char *key,unsigned int keylen,char *data,unsigned int datalen TSRMLS_DC)
00126 {
00127        if (cdb_make_addbegin(c, keylen, datalen TSRMLS_CC) == -1)
00128               return -1;
00129        if (cdb_make_write(c, key, keylen TSRMLS_CC) != 0)
00130               return -1;
00131        if (cdb_make_write(c, data, datalen TSRMLS_CC) != 0)
00132               return -1;
00133        return cdb_make_addend(c, keylen, datalen, cdb_hash(key, keylen) TSRMLS_CC);
00134 }
00135 /* }}} */
00136 
00137 /* {{{ cdb_make_finish */
00138 int cdb_make_finish(struct cdb_make *c TSRMLS_DC)
00139 {
00140        char buf[8];
00141        int i;
00142        uint32 len;
00143        uint32 u;
00144        uint32 memsize;
00145        uint32 count;
00146        uint32 where;
00147        struct cdb_hplist *x;
00148        struct cdb_hp *hp;
00149 
00150        for (i = 0;i < 256;++i)
00151        c->count[i] = 0;
00152 
00153        for (x = c->head; x; x = x->next) {
00154               i = x->num;
00155               while (i--)
00156               ++c->count[255 & x->hp[i].h];
00157        }
00158 
00159        memsize = 1;
00160        for (i = 0;i < 256;++i) {
00161               u = c->count[i] * 2;
00162               if (u > memsize)
00163               memsize = u;
00164        }
00165 
00166        memsize += c->numentries; /* no overflow possible up to now */
00167        u = (uint32) 0 - (uint32) 1;
00168        u /= sizeof(struct cdb_hp);
00169        if (memsize > u) {
00170               errno = ENOMEM;
00171               return -1;
00172        }
00173 
00174        c->split = (struct cdb_hp *) safe_emalloc(memsize, sizeof(struct cdb_hp), 0);
00175        if (!c->split)
00176               return -1;
00177 
00178        c->hash = c->split + c->numentries;
00179 
00180        u = 0;
00181        for (i = 0;i < 256;++i) {
00182               u += c->count[i]; /* bounded by numentries, so no overflow */
00183               c->start[i] = u;
00184        }
00185 
00186        for (x = c->head; x; x = x->next) {
00187               i = x->num;
00188               while (i--)
00189               c->split[--c->start[255 & x->hp[i].h]] = x->hp[i];
00190        }
00191 
00192        for (i = 0;i < 256;++i) {
00193               count = c->count[i];
00194 
00195               len = count + count; /* no overflow possible */
00196               uint32_pack(c->final + 8 * i,c->pos);
00197               uint32_pack(c->final + 8 * i + 4,len);
00198 
00199               for (u = 0;u < len;++u)
00200                      c->hash[u].h = c->hash[u].p = 0;
00201 
00202               hp = c->split + c->start[i];
00203               for (u = 0;u < count;++u) {
00204                      where = (hp->h >> 8) % len;
00205                      while (c->hash[where].p)
00206                             if (++where == len)
00207                                    where = 0;
00208                      c->hash[where] = *hp++;
00209               }
00210 
00211               for (u = 0;u < len;++u) {
00212                      uint32_pack(buf, c->hash[u].h);
00213                      uint32_pack(buf + 4, c->hash[u].p);
00214                      if (cdb_make_write(c, buf, 8 TSRMLS_CC) != 0)
00215                             return -1;
00216                      if (cdb_posplus(c, 8) == -1)
00217                             return -1;
00218               }
00219        }
00220 
00221        if (c->split)
00222               efree(c->split);
00223 
00224        for (x = c->head; x; c->head = x) {
00225               x = x->next;
00226               efree(c->head);
00227        }
00228 
00229        if (php_stream_flush(c->fp) != 0)
00230               return -1;
00231        php_stream_rewind(c->fp);
00232        if (php_stream_tell(c->fp) != 0)
00233               return -1;
00234        if (cdb_make_write(c, c->final, sizeof(c->final) TSRMLS_CC) != 0)
00235               return -1;
00236        return php_stream_flush(c->fp);
00237 }
00238 /* }}} */
00239 
00240 /* {{{ cdb_make_version */
00241 char *cdb_make_version() 
00242 {
00243        return "0.75, $Revision: 293036 $";
00244 }