1                 : /*
       2                 :    +----------------------------------------------------------------------+
       3                 :    | PHP Version 6                                                        |
       4                 :    +----------------------------------------------------------------------+
       5                 :    | Copyright (c) 1997-2009 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: cdb_make.c 276986 2009-03-10 23:40:06Z helly $ */
      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                 : #ifdef HAVE_UNISTD_H
      31                 : #include <unistd.h>
      32                 : #endif
      33                 : #include <stdlib.h>
      34                 : #include <stdio.h>
      35                 : #include <errno.h>
      36                 : #include "cdb.h"
      37                 : #include "cdb_make.h"
      38                 : #include "uint32.h"
      39                 : 
      40                 : /* {{{ cdb_make_write */
      41              94 : static int cdb_make_write(struct cdb_make *c, char *buf, uint32 sz TSRMLS_DC) {
      42              94 :         return php_stream_write(c->fp, buf, sz) == sz ? 0 : -1;
      43                 : }
      44                 : 
      45                 : /* {{{ cdb_posplus */
      46                 : static int cdb_posplus(struct cdb_make *c, uint32 len)
      47              90 : {
      48              90 :         uint32 newpos = c->pos + len;
      49              90 :         if (newpos < len) {
      50               0 :                 errno = ENOMEM;
      51               0 :                 return -1;
      52                 :         }
      53              90 :         c->pos = newpos;
      54              90 :         return 0;
      55                 : }
      56                 : /* }}} */
      57                 : 
      58                 : /* {{{ cdb_make_start */
      59                 : int cdb_make_start(struct cdb_make *c, php_stream * f TSRMLS_DC)
      60               4 : {
      61               4 :         c->head = 0;
      62               4 :         c->split = 0;
      63               4 :         c->hash = 0;
      64               4 :         c->numentries = 0;
      65               4 :         c->fp = f;
      66               4 :         c->pos = sizeof(c->final);
      67               4 :         if (php_stream_seek(f, c->pos, SEEK_SET) == -1) {
      68               0 :                 php_error_docref(NULL TSRMLS_CC, E_NOTICE, "Fseek failed");
      69               0 :                 return -1;
      70                 :         }
      71               4 :         return php_stream_tell(c->fp);
      72                 : }
      73                 : /* }}} */
      74                 : 
      75                 : /* {{{ cdb_make_addend */
      76                 : int cdb_make_addend(struct cdb_make *c, unsigned int keylen, unsigned int datalen, uint32 h TSRMLS_DC)
      77              18 : {
      78                 :         struct cdb_hplist *head;
      79                 : 
      80              18 :         head = c->head;
      81              18 :         if (!head || (head->num >= CDB_HPLIST)) {
      82               4 :                 head = (struct cdb_hplist *) emalloc(sizeof(struct cdb_hplist));
      83               4 :                 if (!head)
      84               0 :                         return -1;
      85               4 :                 head->num = 0;
      86               4 :                 head->next = c->head;
      87               4 :                 c->head = head;
      88                 :         }
      89              18 :         head->hp[head->num].h = h;
      90              18 :         head->hp[head->num].p = c->pos;
      91              18 :         ++head->num;
      92              18 :         ++c->numentries;
      93              18 :         if (cdb_posplus(c,8) == -1)
      94               0 :                 return -1;
      95              18 :         if (cdb_posplus(c, keylen) == -1)
      96               0 :                 return -1;
      97              18 :         if (cdb_posplus(c, datalen) == -1)
      98               0 :                 return -1;
      99              18 :         return 0;
     100                 : }
     101                 : /* }}} */
     102                 : 
     103                 : /* {{{ cdb_make_addbegin */
     104                 : int cdb_make_addbegin(struct cdb_make *c, unsigned int keylen, unsigned int datalen TSRMLS_DC)
     105              18 : {
     106                 :         char buf[8];
     107                 : 
     108                 :         if (keylen > 0xffffffff) {
     109                 :                 errno = ENOMEM;
     110                 :                 return -1;
     111                 :         }
     112                 :         if (datalen > 0xffffffff) {
     113                 :                 errno = ENOMEM;
     114                 :                 return -1;
     115                 :         }
     116                 : 
     117              18 :         uint32_pack(buf, keylen);
     118              18 :         uint32_pack(buf + 4, datalen);
     119              18 :         if (cdb_make_write(c, buf, 8 TSRMLS_CC) != 0)
     120               0 :                 return -1;
     121              18 :         return 0;
     122                 : }
     123                 : 
     124                 : /* {{{ cdb_make_add */
     125                 : int cdb_make_add(struct cdb_make *c,char *key,unsigned int keylen,char *data,unsigned int datalen TSRMLS_DC)
     126              18 : {
     127              18 :         if (cdb_make_addbegin(c, keylen, datalen TSRMLS_CC) == -1)
     128               0 :                 return -1;
     129              18 :         if (cdb_make_write(c, key, keylen TSRMLS_CC) != 0)
     130               0 :                 return -1;
     131              18 :         if (cdb_make_write(c, data, datalen TSRMLS_CC) != 0)
     132               0 :                 return -1;
     133              18 :         return cdb_make_addend(c, keylen, datalen, cdb_hash(key, keylen) TSRMLS_CC);
     134                 : }
     135                 : /* }}} */
     136                 : 
     137                 : /* {{{ cdb_make_finish */
     138                 : int cdb_make_finish(struct cdb_make *c TSRMLS_DC)
     139               4 : {
     140                 :         char buf[8];
     141                 :         int i;
     142                 :         uint32 len;
     143                 :         uint32 u;
     144                 :         uint32 memsize;
     145                 :         uint32 count;
     146                 :         uint32 where;
     147                 :         struct cdb_hplist *x;
     148                 :         struct cdb_hp *hp;
     149                 : 
     150            1028 :         for (i = 0;i < 256;++i)
     151            1024 :         c->count[i] = 0;
     152                 : 
     153               8 :         for (x = c->head; x; x = x->next) {
     154               4 :                 i = x->num;
     155              26 :                 while (i--)
     156              18 :                 ++c->count[255 & x->hp[i].h];
     157                 :         }
     158                 : 
     159               4 :         memsize = 1;
     160            1028 :         for (i = 0;i < 256;++i) {
     161            1024 :                 u = c->count[i] * 2;
     162            1024 :                 if (u > memsize)
     163               5 :                 memsize = u;
     164                 :         }
     165                 : 
     166               4 :         memsize += c->numentries; /* no overflow possible up to now */
     167               4 :         u = (uint32) 0 - (uint32) 1;
     168               4 :         u /= sizeof(struct cdb_hp);
     169               4 :         if (memsize > u) {
     170               0 :                 errno = ENOMEM;
     171               0 :                 return -1;
     172                 :         }
     173                 : 
     174               4 :         c->split = (struct cdb_hp *) safe_emalloc(memsize, sizeof(struct cdb_hp), 0);
     175               4 :         if (!c->split)
     176               0 :                 return -1;
     177                 : 
     178               4 :         c->hash = c->split + c->numentries;
     179                 : 
     180               4 :         u = 0;
     181            1028 :         for (i = 0;i < 256;++i) {
     182            1024 :                 u += c->count[i]; /* bounded by numentries, so no overflow */
     183            1024 :                 c->start[i] = u;
     184                 :         }
     185                 : 
     186               8 :         for (x = c->head; x; x = x->next) {
     187               4 :                 i = x->num;
     188              26 :                 while (i--)
     189              18 :                 c->split[--c->start[255 & x->hp[i].h]] = x->hp[i];
     190                 :         }
     191                 : 
     192            1028 :         for (i = 0;i < 256;++i) {
     193            1024 :                 count = c->count[i];
     194                 : 
     195            1024 :                 len = count + count; /* no overflow possible */
     196            1024 :                 uint32_pack(c->final + 8 * i,c->pos);
     197            1024 :                 uint32_pack(c->final + 8 * i + 4,len);
     198                 : 
     199            1060 :                 for (u = 0;u < len;++u)
     200              36 :                         c->hash[u].h = c->hash[u].p = 0;
     201                 : 
     202            1024 :                 hp = c->split + c->start[i];
     203            1042 :                 for (u = 0;u < count;++u) {
     204              18 :                         where = (hp->h >> 8) % len;
     205              40 :                         while (c->hash[where].p)
     206               4 :                                 if (++where == len)
     207               0 :                                         where = 0;
     208              18 :                         c->hash[where] = *hp++;
     209                 :                 }
     210                 : 
     211            1060 :                 for (u = 0;u < len;++u) {
     212              36 :                         uint32_pack(buf, c->hash[u].h);
     213              36 :                         uint32_pack(buf + 4, c->hash[u].p);
     214              36 :                         if (cdb_make_write(c, buf, 8 TSRMLS_CC) != 0)
     215               0 :                                 return -1;
     216              36 :                         if (cdb_posplus(c, 8) == -1)
     217               0 :                                 return -1;
     218                 :                 }
     219                 :         }
     220                 : 
     221               4 :         if (c->split)
     222               4 :                 efree(c->split);
     223                 : 
     224               8 :         for (x = c->head; x; c->head = x) {
     225               4 :                 x = x->next;
     226               4 :                 efree(c->head);
     227                 :         }
     228                 : 
     229               4 :         if (php_stream_flush(c->fp) != 0)
     230               0 :                 return -1;
     231               4 :         php_stream_rewind(c->fp);
     232               4 :         if (php_stream_tell(c->fp) != 0)
     233               0 :                 return -1;
     234               4 :         if (cdb_make_write(c, c->final, sizeof(c->final) TSRMLS_CC) != 0)
     235               0 :                 return -1;
     236               4 :         return php_stream_flush(c->fp);
     237                 : }
     238                 : /* }}} */
     239                 : 
     240                 : /* {{{ cdb_make_version */
     241                 : char *cdb_make_version() 
     242               0 : {
     243               0 :         return "0.75, $Revision: 276986 $";
     244                 : }