Pileus Git - ~andy/fetchmail/blob - uid_db.c

   1 /*
   2   POP3 UID db
   3
   4         Copyright (c) 2010 MAD Partners, Ltd. (rweikusat@mssgmbh.com)
   5
   6         This file is being published in accordance with the GPLv2 terms
   7         contained in the COPYING file being part of the fetchmail
   8         6.3.17 release, including the OpenSSL exemption.
   9 */
  10
  11 #include "fetchmail.h"
  12
  13 /*  includes */
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include <strings.h>  /* ffs() lives here - needs #define on Solaris. */
  18
  19 #include "uid_db.h"
  20
  21 #include "xmalloc.h"
  22
  23 /*  constants */
  24 enum {
  25     MIN_RECORDS =       16      /* arbitrary */
  26 };
  27
  28 /*  types */
  29 struct pat_node {
  30     struct pat_node *ptrs_[3];
  31
  32     /*
  33       The bit mask is stored in the nodes (as opposed to the
  34       offset, which is (re-)calculated on demand) because
  35       calculating the mask is a non-trivial operation (at
  36       least on x86).
  37      */
  38     unsigned bit_ndx, bit_mask;
  39
  40     struct uid_db_record *rec;
  41 };
  42
  43 /*
  44   The idea behind this is that the 'left' pointer of
  45   a node is accessible as ptrs(np)[-1] and the right
  46   one a ptrs(np)[1]. This implies that no separate codepaths
  47   for 'symmetric left- and right-cases' are needed.
  48 */
  49 #define ptrs(np) ((np)->ptrs_ + 1)
  50
  51 /*  routines */
  52 /**  various helpers */
  53 static inline unsigned bit_ofs(unsigned bit_ndx)
  54 {
  55     return bit_ndx >> 3;
  56 }
  57
  58 static inline unsigned bit_mask(unsigned bit_ndx)
  59 {
  60     return 1 << (bit_ndx & 7);
  61 }
  62
  63 /**  PATRICIA trie insertion */
  64 /***  walkers */
  65 static struct pat_node *walk_down(struct uid_db *db, struct uid_db_record *rec,
  66                                   struct pat_node ***edgep, struct pat_node **parentp)
  67 {
  68     /*
  69       Find the pat node whose id is 'most similar' to the id
  70       stored in rec->id. Return a pointer to this node.
  71       'parentp' and 'edgep' are output-only parameters which
  72       will point to the parent of returned node and to the edge
  73       pointer going from the parent to the returned node after
  74       the call has returned.
  75
  76       This routine is intended for inserts only.
  77      */
  78     struct pat_node *cur, **edge;
  79     unsigned bit_ndx, v = 0, ofs;
  80
  81     cur = db->pat_root;
  82     ofs = -1;
  83     do {
  84         bit_ndx = cur->bit_ndx;
  85
  86         if (bit_ofs(bit_ndx) != ofs) {
  87             ofs = bit_ofs(bit_ndx);
  88             v = ofs < rec->id_len ? rec->id[ofs] : 0;
  89         }
  90
  91         edge = ptrs(cur) + (v & cur->bit_mask ? 1 : -1);
  92     } while ((cur = *edge) && cur->bit_ndx > bit_ndx);
  93
  94     *parentp =
  95         (struct pat_node *)
  96         ((unsigned char *)edge - (v & bit_mask(bit_ndx) ?
  97                                   offsetof(struct pat_node, ptrs_) + 2 * sizeof(struct pat_node *)
  98                                   : offsetof(struct pat_node, ptrs_)));
  99     *edgep = edge;
 100     return cur;
 101 }
 102
 103 static inline struct pat_node *walk_up(unsigned diff_ndx, struct pat_node **parent)
 104 {
 105     /*
 106       Walk the chain of parent pointers starting with *parent until a node
 107       is found whose parent has a bit_ndx smaller than diff_ndx. Return
 108       a pointer to this node and update *parent to point to its parent.
 109     */
 110     struct pat_node *p, *np;
 111
 112     np = *parent;
 113
 114     while ((p = *ptrs(np)) && p->bit_ndx > diff_ndx)
 115         np = p;
 116
 117     *parent = p;
 118     return np;
 119 }
 120
 121 /***  bit fiddling */
 122 static inline unsigned first_set_bit_in_char(unsigned v)
 123 {
 124     return ffs(v) - 1;
 125 }
 126
 127 static int find_first_diff_bit(struct uid_db_record const *r0,
 128                                struct uid_db_record const *r1)
 129 {
 130     /*
 131       Return the bit_ndx of the first differing bit in
 132       r0->id and r1->id or -1 if the strings are identical.
 133     */
 134     struct uid_db_record const *long_id;
 135     unsigned ofs, max;
 136     unsigned char v;
 137
 138     max = r0->id_len;
 139     if (max > r1->id_len) {
 140         max = r1->id_len;
 141         long_id = r0;
 142     } else
 143         long_id = r1;
 144
 145     ofs = 0;
 146     do
 147         v = r0->id[ofs] ^ r1->id[ofs];
 148     while (!v && ++ofs < max);
 149
 150     if (!v) {
 151         if (r0->id_len == r1->id_len) return -1;
 152         v = long_id->id[ofs];
 153     }
 154
 155     return first_set_bit_in_char(v) + ofs * 8;
 156 }
 157
 158 static inline unsigned bit_set(unsigned bit_ndx, struct uid_db_record const *rec)
 159 {
 160     /*
 161       Return non-zero if the bit corresponding with bit_ndx is set
 162       in rec->id
 163     */
 164     unsigned ofs;
 165
 166     ofs = bit_ofs(bit_ndx);
 167     if (ofs >= rec->id_len) return 0;
 168     return rec->id[ofs] & bit_mask(bit_ndx);
 169 }
 170
 171 /***  node allocation */
 172 static struct pat_node *get_pat_node(struct uid_db_record *rec)
 173 {
 174     /*
 175       Allocate a pat_node, set its rec pointer to rec and the
 176       next pointer of rec to NULL. Return pointer to the pat_node.
 177     */
 178     struct pat_node *np;
 179
 180     np = (struct pat_node *)xmalloc(sizeof(*np));
 181     np->rec = rec;
 182     rec->next = NULL;
 183     return np;
 184 }
 185
 186 static struct pat_node *get_standalone_node(struct uid_db_record *rec)
 187 {
 188     /*
 189       Return a pat_node suitable for being inserted on the 'left edge'
 190       of the trie, ie either linked to a node whose left pointer was zero
 191       or being inserted as root node into an empty trie. The bit_ndx of
 192       the pat_node is set to the index corresponding with the highest
 193       set bit in rec->id.
 194
 195       NB: This is a bad choice when UIDs share a common prefix because
 196       this implies that the root node will cause a bit to be tested which
 197       is non-zero in all other nodes, adding a theoretically redundant
 198       level to the trie. This is (to the best of my knowledge) un-
 199       fortunately unavoidable if nodes with different key lengths need
 200       to be supported.
 201     */
 202     struct pat_node *np;
 203
 204     np = get_pat_node(rec);
 205     np->bit_ndx = first_set_bit_in_char(*rec->id);
 206     np->bit_mask = bit_mask(np->bit_ndx);
 207     return np;
 208 }
 209
 210 /***  various helpers */
 211 #if 0
 212 static inline int record_id_equal(struct uid_db_record const *r0,
 213                                   struct uid_db_record const *r1)
 214 {
 215     return
 216         r0->id_len == r1->id_len
 217         && memcmp(r0->id, r1->id, r0->id_len) == 0;
 218 }
 219 #endif
 220
 221 static struct uid_db_record *append_to_list(struct uid_db_record **recp,
 222                                             struct uid_db_record *rec)
 223 {
 224     /*
 225       Append the uid_db_record pointed to by rec to the uid_db_record
 226       list accessible as *recp and return rec.
 227     */
 228     while (*recp) recp = &(*recp)->next;
 229     *recp = rec;
 230
 231     rec->next = NULL;
 232     return rec;
 233 }
 234
 235 /***  insert routine */
 236 static struct uid_db_record *pat_insert(struct uid_db *db,
 237                                         struct uid_db_record *rec)
 238 {
 239     /*
 240       Insert the record pointed to by rec in the (potentially empty)
 241       PATRICIA trie pointed to by db->pat_root and return rec.
 242     */
 243     struct pat_node *np, *closest, *parent, **edge;
 244     int me, bit_ndx;
 245
 246     if (!db->pat_root) {
 247         np = get_standalone_node(rec);
 248         ptrs(np)[-1] = *ptrs(np) = NULL;
 249         ptrs(np)[1] = np;
 250
 251         db->pat_root = np;
 252         return rec;
 253     }
 254
 255     closest = walk_down(db, rec, &edge, &parent);
 256
 257     if (closest) {
 258         bit_ndx = find_first_diff_bit(closest->rec, rec);
 259         if (bit_ndx < 0)
 260             return append_to_list(&closest->rec->next, rec);
 261
 262         np = get_pat_node(rec);
 263         np->bit_ndx = bit_ndx;
 264         np->bit_mask = bit_mask(bit_ndx);
 265     } else
 266         np = get_standalone_node(rec);
 267
 268     if (parent->bit_ndx > np->bit_ndx) {
 269         closest = walk_up(np->bit_ndx, &parent);
 270
 271         if (!parent) edge = &db->pat_root;
 272         else edge = ptrs(parent)[-1] == closest ?
 273                  ptrs(parent) - 1 : ptrs(parent) + 1;
 274         *ptrs(closest) = np;
 275     }
 276
 277     *edge = np;
 278     *ptrs(np) = parent;
 279
 280     me = bit_set(np->bit_ndx, rec) ? 1 : -1;
 281     ptrs(np)[me] = np;
 282     ptrs(np)[-me] = closest;
 283
 284     return rec;
 285 }
 286
 287 /**  general db insertion */
 288 static struct uid_db_record *get_uid_db_record(char const *id, unsigned status)
 289 {
 290     /*
 291       Allocate a uid_db_record structure and set its id pointer to a
 292       dynamically allocated copy of id. The status member of the
 293       new record is set to status and its message number to zero (invalid).
 294       A pointer to it is then returned.
 295      */
 296     struct uid_db_record *rec;
 297     size_t id_len;
 298
 299     rec = (struct uid_db_record *)xmalloc(sizeof(*rec));
 300
 301     id_len = strlen(id);
 302     rec->id = (char *)memcpy(xmalloc(id_len + 1), id, id_len + 1);
 303     rec->id_len = id_len;
 304     rec->status = status;
 305     rec->num = 0;
 306
 307     return rec;
 308 }
 309
 310 static void insert_into_records(struct uid_db *db,
 311                                 struct uid_db_record *rec)
 312 {
 313     /*
 314       Insert rec into the records array of the uid_db pointed
 315       to by db. The array is grown as necessary and the
 316       corresponding state variables of the db are updated
 317       accordingly. The pos member of rec is set to its position
 318       in the array.
 319     */
 320     unsigned next, want;
 321
 322     next = db->records_next;
 323
 324     if (next == db->records_max) {
 325         want = db->records_max *= 2;
 326         db->records = (struct uid_db_record **)xrealloc(db->records, want * sizeof(rec));
 327     }
 328
 329     rec->pos = next;
 330     db->records[next] = rec;
 331     db->records_next = next + 1;
 332 }
 333
 334 struct uid_db_record *uid_db_insert(struct uid_db *db,
 335                                     char const *id, unsigned status)
 336 {
 337     /*
 338       Create an uid_db_record whose id is id and whose status is
 339       status and insert it into the uid_db pointed to by db.
 340       Return a pointer to the newly created record.
 341     */
 342     struct uid_db_record *rec;
 343
 344     rec = get_uid_db_record(id, status);
 345     insert_into_records(db, rec);
 346     return pat_insert(db, rec);
 347 }
 348
 349 /**  message number index */
 350 void set_uid_db_num(struct uid_db *db, struct uid_db_record *rec,
 351                     unsigned num)
 352 {
 353     /*
 354       Set the message number of the record pointed to by rec to num
 355       and insert it into the num_ndx of the uid_db pointed to by db
 356       at position corresponding with num. The num_ndx lookup array
 357       is grown as needed. Message numbers are expected to 'generally'
 358       be recorded in ascending order and hence, no provisions are
 359       made to deal with the potentially quadratic complexity of
 360       inserting a sequence of numbers into an array such that it
 361       needs to be grown continuously.
 362     */
 363     struct num_ndx *num_ndx;
 364     unsigned have, want;
 365
 366     num_ndx = &db->num_ndx;
 367
 368     if (num_ndx->end_value > num) {
 369         have = num_ndx->pos_0_value - num_ndx->end_value + 1;
 370         want = num_ndx->pos_0_value - num + 1;
 371         num_ndx->end_value = num;
 372
 373         num_ndx->records = (struct uid_db_record **)xrealloc(num_ndx->records, want * sizeof(rec));
 374         do num_ndx->records[--want] = NULL; while (want > have);
 375     }
 376
 377     num_ndx->records[uid_db_num_ofs(num_ndx, num)] = rec;
 378 }
 379
 380 void reset_uid_db_nums(struct uid_db *db)
 381 {
 382     /*
 383       Reset the message numbers of all uid_db_records stored
 384       in the uid_db pointed to by db. The corresponding num_ndx
 385       lookup array is afterwards freed and the num_ndx end_value
 386       adjusted in order to indicate an 'empty' message number
 387       index.
 388     */
 389     struct uid_db_record **rec;
 390     struct num_ndx *num_ndx;
 391     unsigned ndx;
 392
 393     num_ndx = &db->num_ndx;
 394
 395     if (num_ndx->end_value < num_ndx->pos_0_value) {
 396         ndx = num_ndx->pos_0_value - num_ndx->end_value;
 397         while (ndx) {
 398             rec = num_ndx->records + --ndx;
 399             if (*rec) (*rec)->num = 0;
 400         }
 401
 402         num_ndx->end_value = num_ndx->pos_0_value + 1;
 403
 404         free(num_ndx->records);
 405         num_ndx->records = NULL;
 406     }
 407 }
 408
 409 /**  search routines */
 410 struct uid_db_record *find_uid_by_id(struct uid_db *db, char const *id)
 411 {
 412     /*
 413       Search for an uid_db_record whose id is id in the uid_db pointed
 414       to by db and return a pointer to it or NULL if no such record was
 415       found.
 416     */
 417     struct pat_node *np;
 418     struct uid_db_record *rec;
 419     unsigned v = 0, bit_ndx, ofs;
 420     size_t len;
 421
 422     np = db->pat_root;
 423     if (np) {
 424         len = strlen(id);
 425         ofs = -1;
 426         do {
 427             bit_ndx = np->bit_ndx;
 428
 429             if (bit_ofs(bit_ndx) != ofs) {
 430                 ofs = bit_ofs(bit_ndx);
 431                 v = ofs < len ? id[ofs] : 0;
 432             }
 433
 434             np = ptrs(np)[v & np->bit_mask ? 1 : -1];
 435         } while (np && np->bit_ndx > bit_ndx);
 436
 437         if (!np) return NULL;
 438
 439         rec = np->rec;
 440         return rec->id_len == len && memcmp(id, rec->id, len) == 0 ?
 441             rec : NULL;
 442     }
 443
 444     return NULL;
 445 }
 446
 447 struct uid_db_record *last_uid_in_db(struct uid_db *db, char const *id)
 448 {
 449     /*
 450       Return a pointer to the 'last' (insert order) uid_db_record
 451       contained in the uid_db pointed to by db whose id is id or
 452       NULL if no such record exists.
 453     */
 454     struct uid_db_record *rec;
 455
 456     rec = find_uid_by_id(db, id);
 457     if (!rec) return NULL;
 458
 459     while (rec->next) rec = rec->next;
 460     return rec;
 461 }
 462
 463 /**  destruction */
 464 static void free_uid_list(struct uid_db_record *rec)
 465 {
 466     if (!rec) return;
 467
 468     /*
 469       Free the list of uid_db_records starting with
 470       the record pointed to by rec.
 471     */
 472     if (rec->next) free_uid_list(rec->next);
 473
 474     xfree(rec->id);
 475     xfree(rec);
 476 }
 477
 478 static void free_pat_trie(struct pat_node *np)
 479 {
 480     /*
 481       Free the PATRCIA-trie pointed to by np and all
 482       uid_db_records contained in it.
 483
 484       The algorithm implemented below is:
 485
 486         1. Load the left pointer of the node pointed to by
 487            np into next.
 488
 489         2. If the result is not NULL,
 490                 2a) Set the left pointer to NULL.
 491                 2b) Goto 1 if next points to a child of np.
 492
 493         3. Load the right pointer of the node pointed to by
 494            np into next.
 495
 496         4. If the result is not NULL,
 497                 4a) Set the right pointer to NULL.
 498                 4b) Goto 1 id next points to a child of np.
 499
 500         5. Load next with the parent pointer of np.
 501
 502         6. Free np->rec and np.
 503
 504         7. Set np to next and goto 1 if it is not null.
 505     */
 506     struct pat_node *next;
 507
 508     do {
 509         next = ptrs(np)[-1];
 510         if (next) {
 511             ptrs(np)[-1] = NULL;
 512             if (next->bit_ndx > np->bit_ndx) continue;
 513         }
 514
 515         next = ptrs(np)[1];
 516         if (next) {
 517             ptrs(np)[1] = NULL;
 518             if (next->bit_ndx > np->bit_ndx) continue;
 519         }
 520
 521         next = *ptrs(np);
 522
 523         free_uid_list(np->rec);
 524         free(np);
 525     } while ((np = next));
 526 }
 527
 528 void free_uid_db(struct uid_db *db)
 529 {
 530     /*
 531       Free all dynamically allocated memory of the uid_db
 532       pointed to by db. The structure is not reinitialized.
 533     */
 534     if (db->pat_root) free_pat_trie(db->pat_root);
 535
 536     xfree(db->records);
 537     xfree(db->num_ndx.records);
 538 }
 539
 540 /**  various public interfaces */
 541 void init_uid_db(struct uid_db *db)
 542 {
 543     /*
 544       Initialize the uid_db structure pointed to by db 'properly'
 545       such that it represents an empty database. An array of
 546       size MIN_RECORDS is allocated and assigned to db->records.
 547     */
 548     struct num_ndx *num_ndx;
 549
 550     db->pat_root = NULL;
 551
 552     db->records = (struct uid_db_record **)xmalloc(MIN_RECORDS * sizeof(*db->records));
 553     db->records_max = MIN_RECORDS;
 554     db->records_next = 0;
 555
 556     num_ndx = &db->num_ndx;
 557     num_ndx->pos_0_value = num_ndx->end_value = -1;
 558     num_ndx->records = NULL;
 559 }
 560
 561 void swap_uid_db_data(struct uid_db *db_0, struct uid_db *db_1)
 562 {
 563     struct uid_db tmp;
 564
 565     tmp = *db_0;
 566     *db_0 = *db_1;
 567     *db_1 = tmp;
 568 }
 569
 570 int traverse_uid_db(struct uid_db *db,
 571                      uid_db_traversal_routine *r, void *arg)
 572 {
 573     /*
 574       Traverses the struct uid_db records array in insert order,
 575       invoking the subroutine pointed to by r with a pointer to
 576       each record and the arg pointer as arguments. If the return
 577       value of that is non-zero, traverse_uid_db immediately returns
 578       with this value. Otherwise, zero is returned after the last
 579       record was visited.
 580
 581       The uid_db_traversal_routine must not modify the uid_db during
 582       traversal.
 583     */
 584     struct uid_db_record **recs;
 585     unsigned ndx, max;
 586     int rc;
 587
 588     rc = 0;
 589     ndx = 0;
 590     max = db->records_next;
 591     recs = db->records;
 592     while (ndx < max && (rc = r(recs[ndx], arg)) == 0)
 593         ++ndx;
 594
 595     return rc;
 596 }