ext/dba/libcdb/cdb

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
cdb_make_write
cdb_posplus
cdb_make_start
cdb_make_addend
cdb_make_addbegin
cdb_make_add
cdb_make_finish
cdb_make_version
   1 /*
   2    +----------------------------------------------------------------------+
   3    | PHP Version 7                                                        |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 1997-2016 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: b1e33abb9b35b5403eb6a19e70a1b6271c371b04 $ */
  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 static int cdb_make_write(struct cdb_make *c, char *buf, uint32 sz) {
  42         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 {
  48         uint32 newpos = c->pos + len;
  49         if (newpos < len) {
  50                 errno = ENOMEM;
  51                 return -1;
  52         }
  53         c->pos = newpos;
  54         return 0;
  55 }
  56 /* }}} */
  57 
  58 /* {{{ cdb_make_start */
  59 int cdb_make_start(struct cdb_make *c, php_stream * f)
  60 {
  61         c->head = 0;
  62         c->split = 0;
  63         c->hash = 0;
  64         c->numentries = 0;
  65         c->fp = f;
  66         c->pos = sizeof(c->final);
  67         if (php_stream_seek(f, c->pos, SEEK_SET) == -1) {
  68                 php_error_docref(NULL, E_NOTICE, "Fseek failed");
  69                 return -1;
  70         }
  71         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)
  77 {
  78         struct cdb_hplist *head;
  79 
  80         head = c->head;
  81         if (!head || (head->num >= CDB_HPLIST)) {
  82                 head = (struct cdb_hplist *) emalloc(sizeof(struct cdb_hplist));
  83                 if (!head)
  84                         return -1;
  85                 head->num = 0;
  86                 head->next = c->head;
  87                 c->head = head;
  88         }
  89         head->hp[head->num].h = h;
  90         head->hp[head->num].p = c->pos;
  91         ++head->num;
  92         ++c->numentries;
  93         if (cdb_posplus(c,8) == -1)
  94                 return -1;
  95         if (cdb_posplus(c, keylen) == -1)
  96                 return -1;
  97         if (cdb_posplus(c, datalen) == -1)
  98                 return -1;
  99         return 0;
 100 }
 101 /* }}} */
 102 
 103 /* {{{ cdb_make_addbegin */
 104 int cdb_make_addbegin(struct cdb_make *c, unsigned int keylen, unsigned int datalen)
 105 {
 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         uint32_pack(buf, keylen);
 118         uint32_pack(buf + 4, datalen);
 119         if (cdb_make_write(c, buf, 8) != 0)
 120                 return -1;
 121         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)
 126 {
 127         if (cdb_make_addbegin(c, keylen, datalen) == -1)
 128                 return -1;
 129         if (cdb_make_write(c, key, keylen) != 0)
 130                 return -1;
 131         if (cdb_make_write(c, data, datalen) != 0)
 132                 return -1;
 133         return cdb_make_addend(c, keylen, datalen, cdb_hash(key, keylen));
 134 }
 135 /* }}} */
 136 
 137 /* {{{ cdb_make_finish */
 138 int cdb_make_finish(struct cdb_make *c)
 139 {
 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         for (i = 0;i < 256;++i)
 151         c->count[i] = 0;
 152 
 153         for (x = c->head; x; x = x->next) {
 154                 i = x->num;
 155                 while (i--)
 156                 ++c->count[255 & x->hp[i].h];
 157         }
 158 
 159         memsize = 1;
 160         for (i = 0;i < 256;++i) {
 161                 u = c->count[i] * 2;
 162                 if (u > memsize)
 163                 memsize = u;
 164         }
 165 
 166         memsize += c->numentries; /* no overflow possible up to now */
 167         u = (uint32) 0 - (uint32) 1;
 168         u /= sizeof(struct cdb_hp);
 169         if (memsize > u) {
 170                 errno = ENOMEM;
 171                 return -1;
 172         }
 173 
 174         c->split = (struct cdb_hp *) safe_emalloc(memsize, sizeof(struct cdb_hp), 0);
 175         if (!c->split)
 176                 return -1;
 177 
 178         c->hash = c->split + c->numentries;
 179 
 180         u = 0;
 181         for (i = 0;i < 256;++i) {
 182                 u += c->count[i]; /* bounded by numentries, so no overflow */
 183                 c->start[i] = u;
 184         }
 185 
 186         for (x = c->head; x; x = x->next) {
 187                 i = x->num;
 188                 while (i--)
 189                 c->split[--c->start[255 & x->hp[i].h]] = x->hp[i];
 190         }
 191 
 192         for (i = 0;i < 256;++i) {
 193                 count = c->count[i];
 194 
 195                 len = count + count; /* no overflow possible */
 196                 uint32_pack(c->final + 8 * i,c->pos);
 197                 uint32_pack(c->final + 8 * i + 4,len);
 198 
 199                 for (u = 0;u < len;++u)
 200                         c->hash[u].h = c->hash[u].p = 0;
 201 
 202                 hp = c->split + c->start[i];
 203                 for (u = 0;u < count;++u) {
 204                         where = (hp->h >> 8) % len;
 205                         while (c->hash[where].p)
 206                                 if (++where == len)
 207                                         where = 0;
 208                         c->hash[where] = *hp++;
 209                 }
 210 
 211                 for (u = 0;u < len;++u) {
 212                         uint32_pack(buf, c->hash[u].h);
 213                         uint32_pack(buf + 4, c->hash[u].p);
 214                         if (cdb_make_write(c, buf, 8) != 0)
 215                                 return -1;
 216                         if (cdb_posplus(c, 8) == -1)
 217                                 return -1;
 218                 }
 219         }
 220 
 221         if (c->split)
 222                 efree(c->split);
 223 
 224         for (x = c->head; x; c->head = x) {
 225                 x = x->next;
 226                 efree(c->head);
 227         }
 228 
 229         if (php_stream_flush(c->fp) != 0)
 230                 return -1;
 231         php_stream_rewind(c->fp);
 232         if (php_stream_tell(c->fp) != 0)
 233                 return -1;
 234         if (cdb_make_write(c, c->final, sizeof(c->final)) != 0)
 235                 return -1;
 236         return php_stream_flush(c->fp);
 237 }
 238 /* }}} */
 239 
 240 /* {{{ cdb_make_version */
 241 char *cdb_make_version()
 242 {
 243         return "0.75, $Id: b1e33abb9b35b5403eb6a19e70a1b6271c371b04 $";
 244 }
/* [<][>][^][v][top][bottom][index][help] */
root/ext/dba/libcdb/cdb_make.c

DEFINITIONS
