camel/camel-partition-table.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
   2 /*
   3  * Copyright (C) 2001-2003 Ximian Inc.
   4  *
   5  * Authors: Michael Zucchi <notzed@ximian.com>
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of version 2 of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this program; if not, write to the
  18  * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  19  * Boston, MA 02110-1301, USA.
  20  */
  21
  22
  23 #ifdef HAVE_CONFIG_H
  24 #include <config.h>
  25 #endif
  26
  27 #include <errno.h>
  28 #include <fcntl.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <sys/stat.h>
  32 #include <sys/types.h>
  33 #include <unistd.h>
  34
  35 #include <libedataserver/e-msgport.h>
  36
  37 #include "camel-block-file.h"
  38 #include "camel-partition-table.h"
  39
  40 /* Do we synchronously write table updates - makes the
  41    tables consistent after program crash without sync */
  42 /*#define SYNC_UPDATES*/
  43
  44 #define d(x) /*(printf("%s(%d):%s: ",  __FILE__, __LINE__, __PRETTY_FUNCTION__),(x))*/
  45 /* key index debug */
  46 #define k(x) /*(printf("%s(%d):%s: ",  __FILE__, __LINE__, __PRETTY_FUNCTION__),(x))*/
  47
  48
  49 struct _CamelPartitionTablePrivate {
  50         pthread_mutex_t lock;   /* for locking partition */
  51 };
  52
  53 #define CAMEL_PARTITION_TABLE_LOCK(kf, lock) (pthread_mutex_lock(&(kf)->priv->lock))
  54 #define CAMEL_PARTITION_TABLE_UNLOCK(kf, lock) (pthread_mutex_unlock(&(kf)->priv->lock))
  55
  56
  57 static void
  58 camel_partition_table_class_init(CamelPartitionTableClass *klass)
  59 {
  60 }
  61
  62 static void
  63 camel_partition_table_init(CamelPartitionTable *cpi)
  64 {
  65         struct _CamelPartitionTablePrivate *p;
  66
  67         e_dlist_init(&cpi->partition);
  68
  69         p = cpi->priv = g_malloc0(sizeof(*cpi->priv));
  70         pthread_mutex_init(&p->lock, NULL);
  71 }
  72
  73 static void
  74 camel_partition_table_finalise(CamelPartitionTable *cpi)
  75 {
  76         CamelBlock *bl;
  77         struct _CamelPartitionTablePrivate *p;
  78
  79         p = cpi->priv;
  80
  81         if (cpi->blocks) {
  82                 while ((bl = (CamelBlock *)e_dlist_remhead(&cpi->partition))) {
  83                         camel_block_file_sync_block(cpi->blocks, bl);
  84                         camel_block_file_unref_block(cpi->blocks, bl);
  85                 }
  86                 camel_block_file_sync(cpi->blocks);
  87
  88                 camel_object_unref((CamelObject *)cpi->blocks);
  89         }
  90
  91         pthread_mutex_destroy(&p->lock);
  92
  93         g_free(p);
  94
  95 }
  96
  97 CamelType
  98 camel_partition_table_get_type(void)
  99 {
 100         static CamelType type = CAMEL_INVALID_TYPE;
 101
 102         if (type == CAMEL_INVALID_TYPE) {
 103                 type = camel_type_register(camel_object_get_type(), "CamelPartitionTable",
 104                                            sizeof (CamelPartitionTable),
 105                                            sizeof (CamelPartitionTableClass),
 106                                            (CamelObjectClassInitFunc) camel_partition_table_class_init,
 107                                            NULL,
 108                                            (CamelObjectInitFunc) camel_partition_table_init,
 109                                            (CamelObjectFinalizeFunc) camel_partition_table_finalise);
 110         }
 111
 112         return type;
 113 }
 114
 115 /* ********************************************************************** */
 116
 117 /*
 118   Have 2 hashes:
 119   Name -> nameid
 120   Word -> wordid
 121
 122 nameid is pointer to name file, includes a bit to say if name is deleted
 123 wordid is a pointer to word file, includes pointer to start of word entries
 124
 125 delete a name -> set it as deleted, do nothing else though
 126
 127 lookup word, if nameid is deleted, mark it in wordlist as unused and mark for write (?)
 128 */
 129
 130 /* ********************************************************************** */
 131
 132 /* This simple hash seems to work quite well */
 133 static camel_hash_t hash_key(const char *key)
 134 {
 135         camel_hash_t hash = 0xABADF00D;
 136
 137         while (*key) {
 138                 hash = hash * (*key) ^ (*key);
 139                 key++;
 140         }
 141
 142         return hash;
 143 }
 144
 145 /* Call with lock held */
 146 static CamelBlock *find_partition(CamelPartitionTable *cpi, camel_hash_t id, int *indexp)
 147 {
 148         int index, jump;
 149         CamelBlock *bl;
 150         CamelPartitionMapBlock *ptb;
 151         CamelPartitionMap *part;
 152
 153         /* first, find the block this key might be in, then binary search the block */
 154         bl = (CamelBlock *)cpi->partition.head;
 155         while (bl->next) {
 156                 ptb = (CamelPartitionMapBlock *)&bl->data;
 157                 part = ptb->partition;
 158                 if (ptb->used > 0 && id <= part[ptb->used-1].hashid) {
 159                         index = ptb->used/2;
 160                         jump = ptb->used/4;
 161
 162                         if (jump == 0)
 163                                 jump = 1;
 164
 165                         while (1) {
 166                                 if (id <= part[index].hashid) {
 167                                         if (index == 0 || id > part[index-1].hashid)
 168                                                 break;
 169                                         index -= jump;
 170                                 } else {
 171                                         if (index >= ptb->used-1)
 172                                                 break;
 173                                         index += jump;
 174                                 }
 175                                 jump = jump/2;
 176                                 if (jump == 0)
 177                                         jump = 1;
 178                         }
 179                         *indexp = index;
 180
 181                         return bl;
 182                 }
 183                 bl = bl->next;
 184         }
 185
 186         g_warning("could not find a partition that could fit !  partition table corrupt!");
 187
 188         /* This should never be reached */
 189
 190         return NULL;
 191 }
 192
 193 CamelPartitionTable *camel_partition_table_new(struct _CamelBlockFile *bs, camel_block_t root)
 194 {
 195         CamelPartitionTable *cpi;
 196         CamelPartitionMapBlock *ptb;
 197         CamelPartitionKeyBlock *kb;
 198         CamelBlock *block, *pblock;
 199
 200         cpi = (CamelPartitionTable *)camel_object_new(camel_partition_table_get_type());
 201         cpi->rootid = root;
 202         cpi->blocks = bs;
 203         camel_object_ref((CamelObject *)bs);
 204
 205         /* read the partition table into memory */
 206         do {
 207                 block = camel_block_file_get_block(bs, root);
 208                 if (block == NULL)
 209                         goto fail;
 210
 211                 ptb = (CamelPartitionMapBlock *)&block->data;
 212
 213                 d(printf("Adding partition block, used = %d, hashid = %08x\n", ptb->used, ptb->partition[0].hashid));
 214
 215                 /* if we have no data, prime initial block */
 216                 if (ptb->used == 0 && e_dlist_empty(&cpi->partition) && ptb->next == 0) {
 217                         pblock = camel_block_file_new_block(bs);
 218                         if (pblock == NULL) {
 219                                 camel_block_file_unref_block(bs, block);
 220                                 goto fail;
 221                         }
 222                         kb = (CamelPartitionKeyBlock *)&pblock->data;
 223                         kb->used = 0;
 224                         ptb->used = 1;
 225                         ptb->partition[0].hashid = 0xffffffff;
 226                         ptb->partition[0].blockid = pblock->id;
 227                         camel_block_file_touch_block(bs, pblock);
 228                         camel_block_file_unref_block(bs, pblock);
 229                         camel_block_file_touch_block(bs, block);
 230 #ifdef SYNC_UPDATES
 231                         camel_block_file_sync_block(bs, block);
 232 #endif
 233                 }
 234
 235                 root = ptb->next;
 236                 camel_block_file_detach_block(bs, block);
 237                 e_dlist_addtail(&cpi->partition, (EDListNode *)block);
 238         } while (root);
 239
 240         return cpi;
 241
 242 fail:
 243         camel_object_unref((CamelObject *)cpi);
 244         return NULL;
 245 }
 246
 247 /* sync our blocks, the caller must still sync the blockfile itself */
 248 int
 249 camel_partition_table_sync(CamelPartitionTable *cpi)
 250 {
 251         CamelBlock *bl, *bn;
 252         int ret = 0;
 253
 254         CAMEL_PARTITION_TABLE_LOCK(cpi, lock);
 255
 256         if (cpi->blocks) {
 257                 bl = (CamelBlock *)cpi->partition.head;
 258                 bn = bl->next;
 259                 while (bn) {
 260                         ret = camel_block_file_sync_block(cpi->blocks, bl);
 261                         if (ret == -1)
 262                                 goto fail;
 263                         bl = bn;
 264                         bn = bn->next;
 265                 }
 266         }
 267 fail:
 268         CAMEL_PARTITION_TABLE_UNLOCK(cpi, lock);
 269
 270         return ret;
 271 }
 272
 273 camel_key_t camel_partition_table_lookup(CamelPartitionTable *cpi, const char *key)
 274 {
 275         CamelPartitionKeyBlock *pkb;
 276         CamelPartitionMapBlock *ptb;
 277         CamelBlock *block, *ptblock;
 278         camel_hash_t hashid;
 279         camel_key_t keyid = 0;
 280         int index, i;
 281
 282         hashid = hash_key(key);
 283
 284         CAMEL_PARTITION_TABLE_LOCK(cpi, lock);
 285
 286         ptblock = find_partition(cpi, hashid, &index);
 287         if (ptblock == NULL) {
 288                 CAMEL_PARTITION_TABLE_UNLOCK(cpi, lock);
 289                 return 0;
 290         }
 291         ptb = (CamelPartitionMapBlock *)&ptblock->data;
 292         block = camel_block_file_get_block(cpi->blocks, ptb->partition[index].blockid);
 293         if (block == NULL) {
 294                 CAMEL_PARTITION_TABLE_UNLOCK(cpi, lock);
 295                 return 0;
 296         }
 297
 298         pkb = (CamelPartitionKeyBlock *)&block->data;
 299
 300         /* What to do about duplicate hash's? */
 301         for (i=0;i<pkb->used;i++) {
 302                 if (pkb->keys[i].hashid == hashid) {
 303                         /* !! need to: lookup and compare string value */
 304                         /* get_key() if key == key ... */
 305                         keyid = pkb->keys[i].keyid;
 306                         break;
 307                 }
 308         }
 309
 310         CAMEL_PARTITION_TABLE_UNLOCK(cpi, lock);
 311
 312         camel_block_file_unref_block(cpi->blocks, block);
 313
 314         return keyid;
 315 }
 316
 317 void camel_partition_table_remove(CamelPartitionTable *cpi, const char *key)
 318 {
 319         CamelPartitionKeyBlock *pkb;
 320         CamelPartitionMapBlock *ptb;
 321         CamelBlock *block, *ptblock;
 322         camel_hash_t hashid;
 323         int index, i;
 324
 325         hashid = hash_key(key);
 326
 327         CAMEL_PARTITION_TABLE_LOCK(cpi, lock);
 328
 329         ptblock = find_partition(cpi, hashid, &index);
 330         if (ptblock == NULL) {
 331                 CAMEL_PARTITION_TABLE_UNLOCK(cpi, lock);
 332                 return;
 333         }
 334         ptb = (CamelPartitionMapBlock *)&ptblock->data;
 335         block = camel_block_file_get_block(cpi->blocks, ptb->partition[index].blockid);
 336         if (block == NULL) {
 337                 CAMEL_PARTITION_TABLE_UNLOCK(cpi, lock);
 338                 return;
 339         }
 340         pkb = (CamelPartitionKeyBlock *)&block->data;
 341
 342         /* What to do about duplicate hash's? */
 343         for (i=0;i<pkb->used;i++) {
 344                 if (pkb->keys[i].hashid == hashid) {
 345                         /* !! need to: lookup and compare string value */
 346                         /* get_key() if key == key ... */
 347
 348                         /* remove this key */
 349                         pkb->used--;
 350                         for (;i<pkb->used;i++) {
 351                                 pkb->keys[i].keyid = pkb->keys[i+1].keyid;
 352                                 pkb->keys[i].hashid = pkb->keys[i+1].hashid;
 353                         }
 354                         camel_block_file_touch_block(cpi->blocks, block);
 355                         break;
 356                 }
 357         }
 358
 359         CAMEL_PARTITION_TABLE_UNLOCK(cpi, lock);
 360
 361         camel_block_file_unref_block(cpi->blocks, block);
 362 }
 363
 364 static int
 365 keys_cmp(const void *ap, const void *bp)
 366 {
 367         const CamelPartitionKey *a = ap;
 368         const CamelPartitionKey *b = bp;
 369
 370         if (a->hashid < b->hashid)
 371                 return -1;
 372         else if (a->hashid > b->hashid)
 373                 return 1;
 374
 375         return 0;
 376 }
 377
 378 int
 379 camel_partition_table_add(CamelPartitionTable *cpi, const char *key, camel_key_t keyid)
 380 {
 381         camel_hash_t hashid, partid;
 382         int index, newindex = 0; /* initialisation of this and pkb/nkb is just to silence compiler */
 383         CamelPartitionMapBlock *ptb, *ptn;
 384         CamelPartitionKeyBlock *kb, *newkb, *nkb = NULL, *pkb = NULL;
 385         CamelBlock *block, *ptblock, *ptnblock;
 386         int i, half, len;
 387         struct _CamelPartitionKey keys[CAMEL_BLOCK_SIZE/4];
 388         int ret = -1;
 389
 390 #define KEY_SIZE (sizeof(kb->keys)/sizeof(kb->keys[0]))
 391
 392         hashid = hash_key(key);
 393
 394         CAMEL_PARTITION_TABLE_LOCK(cpi, lock);
 395         ptblock = find_partition(cpi, hashid, &index);
 396         if (ptblock == NULL) {
 397                 CAMEL_PARTITION_TABLE_UNLOCK(cpi, lock);
 398                 return -1;
 399         }
 400         ptb = (CamelPartitionMapBlock *)&ptblock->data;
 401         block = camel_block_file_get_block(cpi->blocks, ptb->partition[index].blockid);
 402         if (block == NULL) {
 403                 CAMEL_PARTITION_TABLE_UNLOCK(cpi, lock);
 404                 return -1;
 405         }
 406         kb = (CamelPartitionKeyBlock *)&block->data;
 407
 408         /* TODO: Keep the key array in sorted order, cheaper lookups and split operation */
 409
 410         if (kb->used < sizeof(kb->keys)/sizeof(kb->keys[0])) {
 411                 /* Have room, just put it in */
 412                 kb->keys[kb->used].hashid = hashid;
 413                 kb->keys[kb->used].keyid = keyid;
 414                 kb->used++;
 415         } else {
 416                 CamelBlock *newblock = NULL, *nblock = NULL, *pblock = NULL;
 417
 418                 /* Need to split?  See if previous or next has room, then split across that instead */
 419
 420                 /* TODO: Should look at next/previous partition table block as well ... */
 421
 422                 if (index > 0) {
 423                         pblock = camel_block_file_get_block(cpi->blocks, ptb->partition[index-1].blockid);
 424                         if (pblock == NULL)
 425                                 goto fail;
 426                         pkb = (CamelPartitionKeyBlock *)&pblock->data;
 427                 }
 428                 if (index < (ptb->used-1)) {
 429                         nblock = camel_block_file_get_block(cpi->blocks, ptb->partition[index+1].blockid);
 430                         if (nblock == NULL) {
 431                                 if (pblock)
 432                                         camel_block_file_unref_block(cpi->blocks, pblock);
 433                                 goto fail;
 434                         }
 435                         nkb = (CamelPartitionKeyBlock *)&nblock->data;
 436                 }
 437
 438                 if (pblock && pkb->used < KEY_SIZE) {
 439                         if (nblock && nkb->used < KEY_SIZE) {
 440                                 if (pkb->used < nkb->used) {
 441                                         newindex = index+1;
 442                                         newblock = nblock;
 443                                 } else {
 444                                         newindex = index-1;
 445                                         newblock = pblock;
 446                                 }
 447                         } else {
 448                                 newindex = index-1;
 449                                 newblock = pblock;
 450                         }
 451                 } else {
 452                         if (nblock && nkb->used < KEY_SIZE) {
 453                                 newindex = index+1;
 454                                 newblock = nblock;
 455                         }
 456                 }
 457
 458                 /* We had no room, need to split across another block */
 459                 if (newblock == NULL) {
 460                         /* See if we have room in the partition table for this block or need to split that too */
 461                         if (ptb->used >= sizeof(ptb->partition)/sizeof(ptb->partition[0])) {
 462                                 /* TODO: Could check next block to see if it'll fit there first */
 463                                 ptnblock = camel_block_file_new_block(cpi->blocks);
 464                                 if (ptnblock == NULL) {
 465                                         if (nblock)
 466                                                 camel_block_file_unref_block(cpi->blocks, nblock);
 467                                         if (pblock)
 468                                                 camel_block_file_unref_block(cpi->blocks, pblock);
 469                                         goto fail;
 470                                 }
 471                                 camel_block_file_detach_block(cpi->blocks, ptnblock);
 472
 473                                 /* split block and link on-disk, always sorted */
 474                                 ptn = (CamelPartitionMapBlock *)&ptnblock->data;
 475                                 ptn->next = ptb->next;
 476                                 ptb->next = ptnblock->id;
 477                                 len = ptb->used / 2;
 478                                 ptn->used = ptb->used - len;
 479                                 ptb->used = len;
 480                                 memcpy(ptn->partition, &ptb->partition[len], ptn->used * sizeof(ptb->partition[0]));
 481
 482                                 /* link in-memory */
 483                                 ptnblock->next = ptblock->next;
 484                                 ptblock->next->prev = ptnblock;
 485                                 ptblock->next = ptnblock;
 486                                 ptnblock->prev = ptblock;
 487
 488                                 /* write in right order to ensure structure */
 489                                 camel_block_file_touch_block(cpi->blocks, ptnblock);
 490 #ifdef SYNC_UPDATES
 491                                 camel_block_file_sync_block(cpi->blocks, ptnblock);
 492 #endif
 493                                 if (index > len) {
 494                                         camel_block_file_touch_block(cpi->blocks, ptblock);
 495 #ifdef SYNC_UPDATES
 496                                         camel_block_file_sync_block(cpi->blocks, ptblock);
 497 #endif
 498                                         index -= len;
 499                                         ptb = ptn;
 500                                         ptblock = ptnblock;
 501                                 }
 502                         }
 503
 504                         /* try get newblock before modifying existing */
 505                         newblock = camel_block_file_new_block(cpi->blocks);
 506                         if (newblock == NULL) {
 507                                 if (nblock)
 508                                         camel_block_file_unref_block(cpi->blocks, nblock);
 509                                 if (pblock)
 510                                         camel_block_file_unref_block(cpi->blocks, pblock);
 511                                 goto fail;
 512                         }
 513
 514                         for (i=ptb->used-1;i>index;i--) {
 515                                 ptb->partition[i+1].hashid = ptb->partition[i].hashid;
 516                                 ptb->partition[i+1].blockid = ptb->partition[i].blockid;
 517                         }
 518                         ptb->used++;
 519
 520                         newkb = (CamelPartitionKeyBlock *)&newblock->data;
 521                         newkb->used = 0;
 522                         newindex = index+1;
 523
 524                         ptb->partition[newindex].hashid = ptb->partition[index].hashid;
 525                         ptb->partition[newindex].blockid = newblock->id;
 526
 527                         if (nblock)
 528                                 camel_block_file_unref_block(cpi->blocks, nblock);
 529                         if (pblock)
 530                                 camel_block_file_unref_block(cpi->blocks, pblock);
 531                 } else {
 532                         newkb = (CamelPartitionKeyBlock *)&newblock->data;
 533
 534                         if (newblock == pblock) {
 535                                 if (nblock)
 536                                         camel_block_file_unref_block(cpi->blocks, nblock);
 537                         } else {
 538                                 if (pblock)
 539                                         camel_block_file_unref_block(cpi->blocks, pblock);
 540                         }
 541                 }
 542
 543                 /* sort keys to find midpoint */
 544                 len = kb->used;
 545                 memcpy(keys, kb->keys, sizeof(kb->keys[0])*len);
 546                 memcpy(keys+len, newkb->keys, sizeof(newkb->keys[0])*newkb->used);
 547                 len += newkb->used;
 548                 keys[len].hashid = hashid;
 549                 keys[len].keyid = keyid;
 550                 len++;
 551                 qsort(keys, len, sizeof(keys[0]), keys_cmp);
 552
 553                 /* Split keys, fix partition table */
 554                 half = len/2;
 555                 partid = keys[half-1].hashid;
 556
 557                 if (index < newindex) {
 558                         memcpy(kb->keys, keys, sizeof(keys[0])*half);
 559                         kb->used = half;
 560                         memcpy(newkb->keys, keys+half, sizeof(keys[0])*(len-half));
 561                         newkb->used = len-half;
 562                         ptb->partition[index].hashid = partid;
 563                 } else {
 564                         memcpy(newkb->keys, keys, sizeof(keys[0])*half);
 565                         newkb->used = half;
 566                         memcpy(kb->keys, keys+half, sizeof(keys[0])*(len-half));
 567                         kb->used = len-half;
 568                         ptb->partition[newindex].hashid = partid;
 569                 }
 570
 571                 camel_block_file_touch_block(cpi->blocks, ptblock);
 572 #ifdef SYNC_UPDATES
 573                 camel_block_file_sync_block(cpi->blocks, ptblock);
 574 #endif
 575                 camel_block_file_touch_block(cpi->blocks, newblock);
 576                 camel_block_file_unref_block(cpi->blocks, newblock);
 577         }
 578
 579         camel_block_file_touch_block(cpi->blocks, block);
 580         camel_block_file_unref_block(cpi->blocks, block);
 581
 582         ret = 0;
 583 fail:
 584         CAMEL_PARTITION_TABLE_UNLOCK(cpi, lock);
 585
 586         return ret;
 587 }
 588
 589 /* ********************************************************************** */
 590
 591
 592 struct _CamelKeyTablePrivate {
 593         pthread_mutex_t lock;   /* for locking key */
 594 };
 595
 596 #define CAMEL_KEY_TABLE_LOCK(kf, lock) (pthread_mutex_lock(&(kf)->priv->lock))
 597 #define CAMEL_KEY_TABLE_UNLOCK(kf, lock) (pthread_mutex_unlock(&(kf)->priv->lock))
 598
 599
 600 static void
 601 camel_key_table_class_init(CamelKeyTableClass *klass)
 602 {
 603 }
 604
 605 static void
 606 camel_key_table_init(CamelKeyTable *ki)
 607 {
 608         struct _CamelKeyTablePrivate *p;
 609
 610         p = ki->priv = g_malloc0(sizeof(*ki->priv));
 611         pthread_mutex_init(&p->lock, NULL);
 612 }
 613
 614 static void
 615 camel_key_table_finalise(CamelKeyTable *ki)
 616 {
 617         struct _CamelKeyTablePrivate *p;
 618
 619         p = ki->priv;
 620
 621         if (ki->blocks) {
 622                 if (ki->root_block) {
 623                         camel_block_file_sync_block(ki->blocks, ki->root_block);
 624                         camel_block_file_unref_block(ki->blocks, ki->root_block);
 625                 }
 626                 camel_block_file_sync(ki->blocks);
 627                 camel_object_unref((CamelObject *)ki->blocks);
 628         }
 629
 630         pthread_mutex_destroy(&p->lock);
 631
 632         g_free(p);
 633
 634 }
 635
 636 CamelType
 637 camel_key_table_get_type(void)
 638 {
 639         static CamelType type = CAMEL_INVALID_TYPE;
 640
 641         if (type == CAMEL_INVALID_TYPE) {
 642                 type = camel_type_register(camel_object_get_type(), "CamelKeyTable",
 643                                            sizeof (CamelKeyTable),
 644                                            sizeof (CamelKeyTableClass),
 645                                            (CamelObjectClassInitFunc) camel_key_table_class_init,
 646                                            NULL,
 647                                            (CamelObjectInitFunc) camel_key_table_init,
 648                                            (CamelObjectFinalizeFunc) camel_key_table_finalise);
 649         }
 650
 651         return type;
 652 }
 653
 654
 655 CamelKeyTable *
 656 camel_key_table_new(CamelBlockFile *bs, camel_block_t root)
 657 {
 658         CamelKeyTable *ki;
 659
 660         ki = (CamelKeyTable *)camel_object_new(camel_key_table_get_type());
 661
 662         ki->blocks = bs;
 663         camel_object_ref((CamelObject *)bs);
 664         ki->rootid = root;
 665
 666         ki->root_block = camel_block_file_get_block(bs, ki->rootid);
 667         if (ki->root_block == NULL) {
 668                 camel_object_unref((CamelObject *)ki);
 669                 ki = NULL;
 670         } else {
 671                 camel_block_file_detach_block(bs, ki->root_block);
 672                 ki->root = (CamelKeyRootBlock *)&ki->root_block->data;
 673
 674                 k(printf("Opening key index\n"));
 675                 k(printf(" first %u\n last %u\n free %u\n", ki->root->first, ki->root->last, ki->root->free));
 676         }
 677
 678         return ki;
 679 }
 680
 681 int
 682 camel_key_table_sync(CamelKeyTable *ki)
 683 {
 684 #ifdef SYNC_UPDATES
 685         return 0;
 686 #else
 687         return camel_block_file_sync_block(ki->blocks, ki->root_block);
 688 #endif
 689 }
 690
 691 camel_key_t
 692 camel_key_table_add(CamelKeyTable *ki, const char *key, camel_block_t data, unsigned int flags)
 693 {
 694         CamelBlock *last, *next;
 695         CamelKeyBlock *kblast, *kbnext;
 696         int len, left;
 697         unsigned int offset;
 698         camel_key_t keyid = 0;
 699
 700         /* Maximum key size = 128 chars */
 701         len = strlen(key);
 702         if (len > CAMEL_KEY_TABLE_MAX_KEY)
 703                 len = 128;
 704
 705         CAMEL_KEY_TABLE_LOCK(ki, lock);
 706
 707         if (ki->root->last == 0) {
 708                 last = camel_block_file_new_block(ki->blocks);
 709                 if (last == NULL)
 710                         goto fail;
 711                 ki->root->last = ki->root->first = last->id;
 712                 camel_block_file_touch_block(ki->blocks, ki->root_block);
 713                 k(printf("adding first block, first = %u\n", ki->root->first));
 714         } else {
 715                 last = camel_block_file_get_block(ki->blocks, ki->root->last);
 716                 if (last == NULL)
 717                         goto fail;
 718         }
 719
 720         kblast = (CamelKeyBlock *)&last->data;
 721
 722         if (kblast->used >= 127)
 723                 goto fail;
 724
 725         if (kblast->used > 0) {
 726                 /*left = &kblast->u.keydata[kblast->u.keys[kblast->used-1].offset] - (char *)(&kblast->u.keys[kblast->used+1]);*/
 727                 left = kblast->u.keys[kblast->used-1].offset - sizeof(kblast->u.keys[0])*(kblast->used+1);
 728                 d(printf("key '%s' used = %d (%d), filled = %d, left = %d  len = %d?\n",
 729                          key, kblast->used, kblast->used * sizeof(kblast->u.keys[0]),
 730                          sizeof(kblast->u.keydata) - kblast->u.keys[kblast->used-1].offset,
 731                          left, len));
 732                 if (left < len) {
 733                         next = camel_block_file_new_block(ki->blocks);
 734                         if (next == NULL) {
 735                                 camel_block_file_unref_block(ki->blocks, last);
 736                                 goto fail;
 737                         }
 738                         kbnext = (CamelKeyBlock *)&next->data;
 739                         kblast->next = next->id;
 740                         ki->root->last = next->id;
 741                         d(printf("adding new block, first = %u, last = %u\n", ki->root->first, ki->root->last));
 742                         camel_block_file_touch_block(ki->blocks, ki->root_block);
 743                         camel_block_file_touch_block(ki->blocks, last);
 744                         camel_block_file_unref_block(ki->blocks, last);
 745                         kblast = kbnext;
 746                         last = next;
 747                 }
 748         }
 749
 750         if (kblast->used > 0)
 751                 offset = kblast->u.keys[kblast->used-1].offset - len;
 752         else
 753                 offset = sizeof(kblast->u.keydata)-len;
 754
 755         kblast->u.keys[kblast->used].flags = flags;
 756         kblast->u.keys[kblast->used].data = data;
 757         kblast->u.keys[kblast->used].offset = offset;
 758         memcpy(kblast->u.keydata + offset, key, len);
 759
 760         keyid = (last->id & (~(CAMEL_BLOCK_SIZE-1))) | kblast->used;
 761
 762         kblast->used++;
 763
 764         g_assert(kblast->used < 127);
 765
 766         camel_block_file_touch_block(ki->blocks, last);
 767         camel_block_file_unref_block(ki->blocks, last);
 768
 769 #ifdef SYNC_UPDATES
 770         camel_block_file_sync_block(ki->blocks, ki->root_block);
 771 #endif
 772 fail:
 773         CAMEL_KEY_TABLE_UNLOCK(ki, lock);
 774
 775         return keyid;
 776 }
 777
 778 void
 779 camel_key_table_set_data(CamelKeyTable *ki, camel_key_t keyid, camel_block_t data)
 780 {
 781         CamelBlock *bl;
 782         camel_block_t blockid;
 783         int index;
 784         CamelKeyBlock *kb;
 785
 786         if (keyid == 0)
 787                 return;
 788
 789         blockid =  keyid & (~(CAMEL_BLOCK_SIZE-1));
 790         index = keyid & (CAMEL_BLOCK_SIZE-1);
 791
 792         bl = camel_block_file_get_block(ki->blocks, blockid);
 793         if (bl == NULL)
 794                 return;
 795         kb = (CamelKeyBlock *)&bl->data;
 796
 797         CAMEL_KEY_TABLE_LOCK(ki, lock);
 798
 799         if (kb->u.keys[index].data != data) {
 800                 kb->u.keys[index].data = data;
 801                 camel_block_file_touch_block(ki->blocks, bl);
 802         }
 803
 804         CAMEL_KEY_TABLE_UNLOCK(ki, lock);
 805
 806         camel_block_file_unref_block(ki->blocks, bl);
 807 }
 808
 809 void
 810 camel_key_table_set_flags(CamelKeyTable *ki, camel_key_t keyid, unsigned int flags, unsigned int set)
 811 {
 812         CamelBlock *bl;
 813         camel_block_t blockid;
 814         int index;
 815         CamelKeyBlock *kb;
 816         unsigned int old;
 817
 818         if (keyid == 0)
 819                 return;
 820
 821         blockid =  keyid & (~(CAMEL_BLOCK_SIZE-1));
 822         index = keyid & (CAMEL_BLOCK_SIZE-1);
 823
 824         bl = camel_block_file_get_block(ki->blocks, blockid);
 825         if (bl == NULL)
 826                 return;
 827         kb = (CamelKeyBlock *)&bl->data;
 828
 829         g_assert(kb->used < 127);
 830         g_assert(index < kb->used);
 831
 832         CAMEL_KEY_TABLE_LOCK(ki, lock);
 833
 834         old = kb->u.keys[index].flags;
 835         if ((old & set) != (flags & set)) {
 836                 kb->u.keys[index].flags = (old & (~set)) | (flags & set);
 837                 camel_block_file_touch_block(ki->blocks, bl);
 838         }
 839
 840         CAMEL_KEY_TABLE_UNLOCK(ki, lock);
 841
 842         camel_block_file_unref_block(ki->blocks, bl);
 843 }
 844
 845 camel_block_t
 846 camel_key_table_lookup(CamelKeyTable *ki, camel_key_t keyid, char **keyp, unsigned int *flags)
 847 {
 848         CamelBlock *bl;
 849         camel_block_t blockid;
 850         int index, len, off;
 851         char *key;
 852         CamelKeyBlock *kb;
 853
 854         if (keyp)
 855                 *keyp = 0;
 856         if (flags)
 857                 *flags = 0;
 858         if (keyid == 0)
 859                 return 0;
 860
 861         blockid =  keyid & (~(CAMEL_BLOCK_SIZE-1));
 862         index = keyid & (CAMEL_BLOCK_SIZE-1);
 863
 864         bl = camel_block_file_get_block(ki->blocks, blockid);
 865         if (bl == NULL)
 866                 return 0;
 867
 868         kb = (CamelKeyBlock *)&bl->data;
 869
 870 #if 1
 871         g_assert(kb->used < 127); /* this should be more accurate */
 872         g_assert(index < kb->used);
 873 #else
 874         if (kb->used >=127 || index >= kb->used) {
 875                 g_warning("Block %x: Invalid index or content: index %d used %d\n", blockid, index, kb->used);
 876                 return 0;
 877         }
 878 #endif
 879
 880         CAMEL_KEY_TABLE_LOCK(ki, lock);
 881
 882         blockid = kb->u.keys[index].data;
 883         if (flags)
 884                 *flags = kb->u.keys[index].flags;
 885
 886         if (keyp) {
 887                 off = kb->u.keys[index].offset;
 888                 if (index == 0)
 889                         len = sizeof(kb->u.keydata) - off;
 890                 else
 891                         len = kb->u.keys[index-1].offset - off;
 892                 *keyp = key = g_malloc(len+1);
 893                 memcpy(key, kb->u.keydata + off, len);
 894                 key[len] = 0;
 895         }
 896
 897         CAMEL_KEY_TABLE_UNLOCK(ki, lock);
 898
 899         camel_block_file_unref_block(ki->blocks, bl);
 900
 901         return blockid;
 902 }
 903
 904 /* iterate through all keys */
 905 camel_key_t
 906 camel_key_table_next(CamelKeyTable *ki, camel_key_t next, char **keyp, unsigned int *flagsp, camel_block_t *datap)
 907 {
 908         CamelBlock *bl;
 909         CamelKeyBlock *kb;
 910         camel_block_t blockid;
 911         int index;
 912
 913         if (keyp)
 914                 *keyp = 0;
 915         if (flagsp)
 916                 *flagsp = 0;
 917         if (datap)
 918                 *datap = 0;
 919
 920         CAMEL_KEY_TABLE_LOCK(ki, lock);
 921
 922         if (next == 0) {
 923                 next = ki->root->first;
 924                 if (next == 0) {
 925                         CAMEL_KEY_TABLE_UNLOCK(ki, lock);
 926                         return 0;
 927                 }
 928         } else
 929                 next++;
 930
 931         do {
 932                 blockid =  next & (~(CAMEL_BLOCK_SIZE-1));
 933                 index = next & (CAMEL_BLOCK_SIZE-1);
 934
 935                 bl = camel_block_file_get_block(ki->blocks, blockid);
 936                 if (bl == NULL) {
 937                         CAMEL_KEY_TABLE_UNLOCK(ki, lock);
 938                         return 0;
 939                 }
 940
 941                 kb = (CamelKeyBlock *)&bl->data;
 942
 943                 /* see if we need to goto the next block */
 944                 if (index >= kb->used) {
 945                         /* FIXME: check for loops */
 946                         next = kb->next;
 947                         camel_block_file_unref_block(ki->blocks, bl);
 948                         bl = NULL;
 949                 }
 950         } while (bl == NULL);
 951
 952         /* invalid block data */
 953         if ((kb->u.keys[index].offset >= sizeof(kb->u.keydata)
 954              /*|| kb->u.keys[index].offset < kb->u.keydata - (char *)&kb->u.keys[kb->used])*/
 955              || kb->u.keys[index].offset < sizeof(kb->u.keys[0]) * kb->used
 956             || (index > 0 &&
 957                 (kb->u.keys[index-1].offset >= sizeof(kb->u.keydata)
 958                  /*|| kb->u.keys[index-1].offset < kb->u.keydata - (char *)&kb->u.keys[kb->used]))) {*/
 959                  || kb->u.keys[index-1].offset < sizeof(kb->u.keys[0]) * kb->used)))) {
 960                 g_warning("Block %u invalid scanning keys", bl->id);
 961                 camel_block_file_unref_block(ki->blocks, bl);
 962                 CAMEL_KEY_TABLE_UNLOCK(ki, lock);
 963                 return 0;
 964         }
 965
 966         if (datap)
 967                 *datap = kb->u.keys[index].data;
 968
 969         if (flagsp)
 970                 *flagsp = kb->u.keys[index].flags;
 971
 972         if (keyp) {
 973                 int len, off = kb->u.keys[index].offset;
 974                 char *key;
 975
 976                 if (index == 0)
 977                         len = sizeof(kb->u.keydata) - off;
 978                 else
 979                         len = kb->u.keys[index-1].offset - off;
 980                 *keyp = key = g_malloc(len+1);
 981                 memcpy(key, kb->u.keydata + off, len);
 982                 key[len] = 0;
 983         }
 984
 985         CAMEL_KEY_TABLE_UNLOCK(ki, lock);
 986
 987         camel_block_file_unref_block(ki->blocks, bl);
 988
 989         return next;
 990 }
 991
 992 /* ********************************************************************** */