db.c

   1 /*
   2  * Copyright 2004-2005 Timo Hirvonen
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  17  * 02111-1307, USA.
  18  */
  19
  20 #include "db.h"
  21 #include "xmalloc.h"
  22 #include "xstrjoin.h"
  23 #include "file.h"
  24
  25 #include <inttypes.h>
  26 #include <sys/types.h>
  27 #include <sys/stat.h>
  28 #include <fcntl.h>
  29 #include <errno.h>
  30 #include <unistd.h>
  31 #include <netinet/in.h>
  32
  33 struct db_entry {
  34         uint32_t data_pos;
  35         uint32_t data_size;
  36         char *key;
  37 };
  38
  39 struct db {
  40         /* always sorted by key */
  41         struct db_entry *entries;
  42         unsigned int nr_entries;
  43         unsigned int nr_allocated;
  44
  45         /* insert queue, not sorted */
  46         struct db_entry *iq_entries;
  47         void **iq_datas;
  48         unsigned int iq_size;
  49         unsigned int iq_fill;
  50
  51         char *idx_fn;
  52         char *dat_fn;
  53
  54         int dat_fd;
  55
  56         unsigned int index_dirty : 1;
  57 };
  58
  59 static int db_entry_cmp(const void *a, const void *b)
  60 {
  61         const struct db_entry *ae = a;
  62         const struct db_entry *be = b;
  63
  64         return strcmp(ae->key, be->key);
  65 }
  66
  67 static void array_remove(void *array, size_t nmemb, size_t size, int idx)
  68 {
  69         char *a = array;
  70         char *s, *d;
  71         size_t c;
  72
  73         d = a + idx * size;
  74         s = d + size;
  75         c = size * (nmemb - idx - 1);
  76         if (c > 0)
  77                 memmove(d, s, c);
  78 }
  79
  80 /* index {{{ */
  81
  82 static uint32_t nbuf2l(const char *buffer)
  83 {
  84         const unsigned char *buf = (const unsigned char *)buffer;
  85         uint32_t tmp;
  86
  87         tmp  = buf[0] << 24;
  88         tmp |= buf[1] << 16;
  89         tmp |= buf[2] << 8;
  90         tmp |= buf[3];
  91         return tmp;
  92 }
  93
  94 static int index_load(struct db *db)
  95 {
  96         int fd, size, pos, rc, i;
  97         char *buf;
  98
  99         fd = open(db->idx_fn, O_RDONLY);
 100         if (fd == -1) {
 101                 if (errno == ENOENT)
 102                         return 0;
 103                 return -1;
 104         }
 105         size = lseek(fd, 0, SEEK_END);
 106         if (size == -1)
 107                 return -1;
 108         if (lseek(fd, 0, SEEK_SET) == -1)
 109                 return -1;
 110         if (size < 4)
 111                 return -2;
 112         buf = xnew(char, size);
 113         rc = read_all(fd, buf, size);
 114         if (rc == -1) {
 115                 free(buf);
 116                 return -1;
 117         }
 118         if (rc != size) {
 119                 free(buf);
 120                 return -2;
 121         }
 122         /* format: nr_rows, nr_rows * (pos, size, key_size, key) */
 123         pos = 0;
 124         db->nr_entries = nbuf2l((char *)(buf + pos)); pos += 4;
 125         db->entries = xnew(struct db_entry, db->nr_entries);
 126         db->nr_allocated = db->nr_entries;
 127         for (i = 0; i < db->nr_entries; i++) {
 128                 struct db_entry *e = &db->entries[i];
 129                 uint32_t key_size;
 130
 131                 if (size - pos < 3 * 4)
 132                         goto corrupt;
 133                 e->data_pos = nbuf2l(buf + pos); pos += 4;
 134                 e->data_size = nbuf2l(buf + pos); pos += 4;
 135                 key_size = nbuf2l(buf + pos); pos += 4;
 136                 if (size - pos < key_size)
 137                         goto corrupt;
 138                 e->key = xmalloc(key_size);
 139                 memcpy(e->key, buf + pos, key_size);
 140                 pos += key_size;
 141         }
 142         free(buf);
 143         return 0;
 144 corrupt:
 145         free(buf);
 146         free(db->entries);
 147         db->entries = NULL;
 148         db->nr_entries = 0;
 149         db->nr_allocated = 0;
 150         return -2;
 151 }
 152
 153 static int index_save(struct db *db)
 154 {
 155         uint32_t data;
 156         int fd, i;
 157
 158         fd = creat(db->idx_fn, 0666);
 159         if (fd == -1)
 160                 return -1;
 161         data = htonl(db->nr_entries);
 162         if (write_all(fd, &data, 4) != 4)
 163                 goto err;
 164         for (i = 0; i < db->nr_entries; i++) {
 165                 uint32_t key_size = strlen(db->entries[i].key) + 1;
 166
 167                 data = htonl(db->entries[i].data_pos);
 168                 if (write_all(fd, &data, 4) != 4)
 169                         goto err;
 170                 data = htonl(db->entries[i].data_size);
 171                 if (write_all(fd, &data, 4) != 4)
 172                         goto err;
 173                 data = htonl(key_size);
 174                 if (write_all(fd, &data, 4) != 4)
 175                         goto err;
 176                 if (write_all(fd, db->entries[i].key, key_size) != key_size)
 177                         goto err;
 178         }
 179         close(fd);
 180         db->index_dirty = 0;
 181         return 0;
 182 err:
 183         close(fd);
 184         return -1;
 185 }
 186
 187 static void index_free(struct db *db)
 188 {
 189         int i;
 190
 191         for (i = 0; i < db->nr_entries; i++)
 192                 free(db->entries[i].key);
 193         free(db->entries);
 194         db->entries = NULL;
 195         db->nr_entries = 0;
 196         db->nr_allocated = 0;
 197 }
 198
 199 static struct db_entry *index_search(struct db *db, const char *key)
 200 {
 201         struct db_entry k;
 202
 203         k.key = (char *)key;
 204         return bsearch(&k, db->entries, db->nr_entries, sizeof(struct db_entry), db_entry_cmp);
 205 }
 206
 207 static int index_remove(struct db *db, const char *key)
 208 {
 209         struct db_entry *e;
 210
 211         e = index_search(db, key);
 212         if (e == NULL)
 213                 return 0;
 214
 215         free(e->key);
 216
 217         array_remove(db->entries, db->nr_entries, sizeof(struct db_entry), e - db->entries);
 218         db->nr_entries--;
 219         db->index_dirty = 1;
 220         return 1;
 221 }
 222
 223 /* }}} */
 224
 225 /* iq {{{ */
 226
 227 static int iq_flush(struct db *db)
 228 {
 229         int pos, rc, i;
 230
 231         /* write data */
 232         pos = lseek(db->dat_fd, 0, SEEK_END);
 233         if (pos == -1)
 234                 return -1;
 235         for (i = 0; i < db->iq_fill; i++) {
 236                 rc = write_all(db->dat_fd, db->iq_datas[i], db->iq_entries[i].data_size);
 237                 if (rc == -1)
 238                         return -1;
 239         }
 240
 241         /* free datas */
 242         for (i = 0; i < db->iq_fill; i++)
 243                 free(db->iq_datas[i]);
 244
 245         /* update index */
 246         if (db->iq_fill + db->nr_entries > db->nr_allocated) {
 247                 db->nr_allocated = db->iq_fill + db->nr_entries;
 248                 db->entries = xrenew(struct db_entry, db->entries, db->nr_allocated);
 249         }
 250         for (i = 0; i < db->iq_fill; i++) {
 251                 struct db_entry *s = &db->iq_entries[i];
 252                 struct db_entry *d = &db->entries[db->nr_entries];
 253
 254                 d->data_pos = pos;
 255                 d->data_size = s->data_size;
 256                 d->key = s->key;
 257                 db->nr_entries++;
 258                 pos += d->data_size;
 259         }
 260         db->iq_fill = 0;
 261         qsort(db->entries, db->nr_entries, sizeof(struct db_entry), db_entry_cmp);
 262         db->index_dirty = 1;
 263         return 0;
 264 }
 265
 266 static int iq_search(struct db *db, const void *key)
 267 {
 268         int i;
 269
 270         for (i = 0; i < db->iq_fill; i++) {
 271                 if (strcmp(db->iq_entries[i].key, key) == 0)
 272                         return i;
 273         }
 274         return -1;
 275 }
 276
 277 static int iq_remove(struct db *db, const char *key)
 278 {
 279         int i;
 280
 281         i = iq_search(db, key);
 282         if (i == -1)
 283                 return 0;
 284
 285         free(db->iq_entries[i].key);
 286         free(db->iq_datas[i]);
 287
 288         array_remove(db->iq_entries, db->iq_fill, sizeof(struct db_entry), i);
 289         array_remove(db->iq_datas, db->iq_fill, sizeof(void *), i);
 290         db->iq_fill--;
 291         return 1;
 292 }
 293
 294 /* }}} */
 295
 296 struct db *db_new(const char *filename_base)
 297 {
 298         struct db *db;
 299
 300         db = xnew(struct db, 1);
 301         db->index_dirty = 0;
 302         db->idx_fn = xstrjoin(filename_base, ".idx");
 303         db->dat_fn = xstrjoin(filename_base, ".dat");
 304         db->entries = NULL;
 305         db->nr_entries = 0;
 306         db->nr_allocated = 0;
 307         db->dat_fd = -1;
 308
 309         db->iq_size = 128;
 310         db->iq_fill = 0;
 311         db->iq_entries = xnew(struct db_entry, db->iq_size);
 312         db->iq_datas = xnew(void *, db->iq_size);
 313         return db;
 314 }
 315
 316 int db_load(struct db *db)
 317 {
 318         int rc;
 319
 320         rc = index_load(db);
 321         if (rc)
 322                 return rc;
 323
 324         db->dat_fd = open(db->dat_fn, O_RDWR | O_CREAT, 0666);
 325         if (db->dat_fd == -1) {
 326                 index_free(db);
 327                 return -1;
 328         }
 329         return 0;
 330 }
 331
 332 int db_close(struct db *db)
 333 {
 334         int rc = 0;
 335
 336         if (db->iq_fill > 0)
 337                 iq_flush(db);
 338         close(db->dat_fd);
 339         if (db->index_dirty)
 340                 rc = index_save(db);
 341
 342         index_free(db);
 343         free(db->iq_entries);
 344         free(db->iq_datas);
 345         free(db->idx_fn);
 346         free(db->dat_fn);
 347         free(db);
 348         return rc;
 349 }
 350
 351 int db_insert(struct db *db, char *key, void *data, unsigned int data_size)
 352 {
 353         int i;
 354
 355         if (db->iq_fill == db->iq_size) {
 356                 int rc = iq_flush(db);
 357                 if (rc)
 358                         return rc;
 359         }
 360         i = db->iq_fill;
 361         db->iq_entries[i].data_pos = 0;
 362         db->iq_entries[i].data_size = data_size;
 363         db->iq_entries[i].key = key;
 364         db->iq_datas[i] = data;
 365         db->iq_fill++;
 366         return 0;
 367 }
 368
 369 int db_remove(struct db *db, const char *key)
 370 {
 371         if (index_remove(db, key))
 372                 return 1;
 373         if (iq_remove(db, key))
 374                 return 1;
 375         return 0;
 376 }
 377
 378 int db_query(struct db *db, const char *key, void **datap, unsigned int *data_sizep)
 379 {
 380         struct db_entry *e;
 381         void *buf;
 382         int rc;
 383
 384         *datap = NULL;
 385         *data_sizep = 0;
 386
 387         e = index_search(db, key);
 388         if (e == NULL) {
 389                 int i;
 390
 391                 i = iq_search(db, key);
 392                 if (i == -1)
 393                         return 0;
 394                 *data_sizep = db->iq_entries[i].data_size;
 395                 *datap = xmalloc(*data_sizep);
 396                 memcpy(*datap, db->iq_datas[i], *data_sizep);
 397                 return 1;
 398         }
 399
 400         if (lseek(db->dat_fd, e->data_pos, SEEK_SET) == -1) {
 401                 return -1;
 402         }
 403
 404         buf = xmalloc(e->data_size);
 405         rc = read_all(db->dat_fd, buf, e->data_size);
 406         if (rc == -1) {
 407                 free(buf);
 408                 return -1;
 409         }
 410         if (rc != e->data_size) {
 411                 free(buf);
 412                 return -2;
 413         }
 414
 415         *data_sizep = e->data_size;
 416         *datap = buf;
 417         return 1;
 418 }