4 Copyright (c) 2010 MAD Partners, Ltd. (rweikusat@mssgmbh.com)
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.
21 MIN_RECORDS = 16 /* arbitrary */
26 struct pat_node *ptrs_[3];
29 The bit mask is stored in the nodes (as opposed to the
30 offset, which is (re-)calculated on demand) because
31 calculating the mask is a non-trivial operation (at
34 unsigned bit_ndx, bit_mask;
36 struct uid_db_record *rec;
40 The idea behind this is that the 'left' pointer of
41 a node is accessible as ptrs(np)[-1] and the right
42 one a ptrs(np)[1]. This implies that no separate codepaths
43 for 'symmetric left- and right-cases' are needed.
45 #define ptrs(np) ((np)->ptrs_ + 1)
48 /** various helpers */
49 static inline unsigned bit_ofs(unsigned bit_ndx)
54 static inline unsigned bit_mask(unsigned bit_ndx)
56 return 1 << (bit_ndx & 7);
59 /** PATRICIA trie insertion */
61 static struct pat_node *walk_down(struct uid_db *db, struct uid_db_record *rec,
62 struct pat_node ***edgep, struct pat_node **parentp)
65 Find the pat node whose id is 'most similar' to the id
66 stored in rec->id. Return a pointer to this node.
67 'parentp' and 'edgep' are output-only parameters which
68 will point to the parent of returned node and to the edge
69 pointer going from the parent to the returned node after
70 the call has returned.
72 This routine is intended for inserts only.
74 struct pat_node *cur, **edge;
75 unsigned bit_ndx, v = 0, ofs;
80 bit_ndx = cur->bit_ndx;
82 if (bit_ofs(bit_ndx) != ofs) {
83 ofs = bit_ofs(bit_ndx);
84 v = ofs < rec->id_len ? rec->id[ofs] : 0;
87 edge = ptrs(cur) + (v & cur->bit_mask ? 1 : -1);
88 } while ((cur = *edge) && cur->bit_ndx > bit_ndx);
92 ((unsigned char *)edge - (v & bit_mask(bit_ndx) ?
93 offsetof(struct pat_node, ptrs_[2])
94 : offsetof(struct pat_node, ptrs_[0])));
99 static inline struct pat_node *walk_up(unsigned diff_ndx, struct pat_node **parent)
102 Walk the chain of parent pointers starting with *parent until a node
103 is found whose parent has a bit_ndx smaller than diff_ndx. Return
104 a pointer to this node and update *parent to point to its parent.
106 struct pat_node *p, *np;
110 while ((p = *ptrs(np)) && p->bit_ndx > diff_ndx)
118 static inline unsigned first_set_bit_in_char(unsigned v)
123 static int find_first_diff_bit(struct uid_db_record const *r0,
124 struct uid_db_record const *r1)
127 Return the bit_ndx of the first differing bit in
128 r0->id and r1->id or -1 if the strings are identical.
130 struct uid_db_record const *long_id;
135 if (max > r1->id_len) {
143 v = r0->id[ofs] ^ r1->id[ofs];
144 while (!v && ++ofs < max);
147 if (r0->id_len == r1->id_len) return -1;
148 v = long_id->id[ofs];
151 return first_set_bit_in_char(v) + ofs * 8;
154 static inline unsigned bit_set(unsigned bit_ndx, struct uid_db_record const *rec)
157 Return non-zero if the bit corresponding with bit_ndx is set
162 ofs = bit_ofs(bit_ndx);
163 if (ofs >= rec->id_len) return 0;
164 return rec->id[ofs] & bit_mask(bit_ndx);
167 /*** node allocation */
168 static struct pat_node *get_pat_node(struct uid_db_record *rec)
171 Allocate a pat_node, set its rec pointer to rec and the
172 next pointer of rec to NULL. Return pointer to the pat_node.
176 np = (struct pat_node *)xmalloc(sizeof(*np));
182 static struct pat_node *get_standalone_node(struct uid_db_record *rec)
185 Return a pat_node suitable for being inserted on the 'left edge'
186 of the trie, ie either linked to a node whose left pointer was zero
187 or being inserted as root node into an empty trie. The bit_ndx of
188 the pat_node is set to the index corresponding with the highest
191 NB: This is a bad choice when UIDs share a common prefix because
192 this implies that the root node will cause a bit to be tested which
193 is non-zero in all other nodes, adding a theoretically redundant
194 level to the trie. This is (to the best of my knowledge) un-
195 fortunately unavoidable if nodes with different key lengths need
200 np = get_pat_node(rec);
201 np->bit_ndx = first_set_bit_in_char(*rec->id);
202 np->bit_mask = bit_mask(np->bit_ndx);
206 /*** various helpers */
207 static inline int record_id_equal(struct uid_db_record const *r0,
208 struct uid_db_record const *r1)
211 r0->id_len == r1->id_len
212 && memcmp(r0->id, r1->id, r0->id_len) == 0;
215 static struct uid_db_record *append_to_list(struct uid_db_record **recp,
216 struct uid_db_record *rec)
219 Append the uid_db_record pointed to by rec to the uid_db_record
220 list accessible as *recp and return rec.
222 while (*recp) recp = &(*recp)->next;
229 /*** insert routine */
230 static struct uid_db_record *pat_insert(struct uid_db *db,
231 struct uid_db_record *rec)
234 Insert the record pointed to by rec in the (potentially empty)
235 PATRICIA trie pointed to by db->pat_root and return rec.
237 struct pat_node *np, *closest, *parent, **edge;
241 np = get_standalone_node(rec);
242 ptrs(np)[-1] = *ptrs(np) = NULL;
249 closest = walk_down(db, rec, &edge, &parent);
252 bit_ndx = find_first_diff_bit(closest->rec, rec);
254 return append_to_list(&closest->rec->next, rec);
256 np = get_pat_node(rec);
257 np->bit_ndx = bit_ndx;
258 np->bit_mask = bit_mask(bit_ndx);
260 np = get_standalone_node(rec);
262 if (parent->bit_ndx > np->bit_ndx) {
263 closest = walk_up(np->bit_ndx, &parent);
265 if (!parent) edge = &db->pat_root;
266 else edge = ptrs(parent)[-1] == closest ?
267 ptrs(parent) - 1 : ptrs(parent) + 1;
274 me = bit_set(np->bit_ndx, rec) ? 1 : -1;
276 ptrs(np)[-me] = closest;
281 /** general db insertion */
282 static struct uid_db_record *get_uid_db_record(char const *id, unsigned status)
285 Allocate a uid_db_record structure and set its id pointer to a
286 dynamically allocated copy of id. The status member of the
287 new record is set to status and its message number to zero (invalid).
288 A pointer to it is then returned.
290 struct uid_db_record *rec;
293 rec = (struct uid_db_record *)xmalloc(sizeof(*rec));
296 rec->id = (char *)memcpy(xmalloc(id_len + 1), id, id_len + 1);
297 rec->id_len = id_len;
298 rec->status = status;
304 static void insert_into_records(struct uid_db *db,
305 struct uid_db_record *rec)
308 Insert rec into the records array of the uid_db pointed
309 to by db. The array is grown as necessary and the
310 corresponding state variables of the db are updated
311 accordingly. The pos member of rec is set to its position
316 next = db->records_next;
318 if (next == db->records_max) {
319 want = db->records_max *= 2;
320 db->records = (struct uid_db_record **)xrealloc(db->records, want * sizeof(rec));
324 db->records[next] = rec;
325 db->records_next = next + 1;
328 struct uid_db_record *uid_db_insert(struct uid_db *db,
329 char const *id, unsigned status)
332 Create an uid_db_record whose id is id and whose status is
333 status and insert it into the uid_db pointed to by db.
334 Return a pointer to the newly created record.
336 struct uid_db_record *rec;
338 rec = get_uid_db_record(id, status);
339 insert_into_records(db, rec);
340 return pat_insert(db, rec);
343 /** message number index */
344 void set_uid_db_num(struct uid_db *db, struct uid_db_record *rec,
348 Set the message number of the record pointed to by rec to num
349 and insert it into the num_ndx of the uid_db pointed to by db
350 at position corresponding with num. The num_ndx lookup array
351 is grown as needed. Message numbers are expected to 'generally'
352 be recorded in ascending order and hence, no provisions are
353 made to deal with the potentially quadratic complexity of
354 inserting a sequence of numbers into an array such that it
355 needs to be grown continuously.
357 struct num_ndx *num_ndx;
360 num_ndx = &db->num_ndx;
362 if (num_ndx->end_value > num) {
363 have = num_ndx->pos_0_value - num_ndx->end_value + 1;
364 want = num_ndx->pos_0_value - num + 1;
365 num_ndx->end_value = num;
367 num_ndx->records = (struct uid_db_record **)xrealloc(num_ndx->records, want * sizeof(rec));
368 do num_ndx->records[--want] = NULL; while (want > have);
371 num_ndx->records[uid_db_num_ofs(num_ndx, num)] = rec;
374 void reset_uid_db_nums(struct uid_db *db)
377 Reset the message numbers of all uid_db_records stored
378 in the uid_db pointed to by db. The corresponding num_ndx
379 lookup array is afterwards freed and the num_ndx end_value
380 adjusted in order to indicate an 'empty' message number
383 struct uid_db_record **rec;
384 struct num_ndx *num_ndx;
387 num_ndx = &db->num_ndx;
389 if (num_ndx->end_value < num_ndx->pos_0_value) {
390 ndx = num_ndx->pos_0_value - num_ndx->end_value;
392 rec = num_ndx->records + --ndx;
393 if (*rec) (*rec)->num = 0;
396 num_ndx->end_value = num_ndx->pos_0_value + 1;
398 free(num_ndx->records);
399 num_ndx->records = NULL;
403 /** search routines */
404 struct uid_db_record *find_uid_by_id(struct uid_db *db, char const *id)
407 Search for an uid_db_record whose id is id in the uid_db pointed
408 to by db and return a pointer to it or NULL if no such record was
412 struct uid_db_record *rec;
413 unsigned v = 0, bit_ndx, ofs;
421 bit_ndx = np->bit_ndx;
423 if (bit_ofs(bit_ndx) != ofs) {
424 ofs = bit_ofs(bit_ndx);
425 v = ofs < len ? id[ofs] : 0;
428 np = ptrs(np)[v & np->bit_mask ? 1 : -1];
429 } while (np && np->bit_ndx > bit_ndx);
431 if (!np) return NULL;
434 return rec->id_len == len && memcmp(id, rec->id, len) == 0 ?
441 struct uid_db_record *last_uid_in_db(struct uid_db *db, char const *id)
444 Return a pointer to the 'last' (insert order) uid_db_record
445 contained in the uid_db pointed to by db whose id is id or
446 NULL if no such record exists.
448 struct uid_db_record *rec;
450 rec = find_uid_by_id(db, id);
451 if (!rec) return NULL;
453 while (rec->next) rec = rec->next;
458 static void free_uid_list(struct uid_db_record *rec)
461 Free the list of uid_db_records starting with
462 the record pointed to by rec.
464 if (rec->next) free_uid_list(rec->next);
470 static void free_pat_trie(struct pat_node *np)
473 Free the PATRCIA-trie pointed to by np and all
474 uid_db_records contained in it.
476 The algorithm implemented below is:
478 1. Load the left pointer of the node pointed to by
481 2. If the result is not NULL,
482 2a) Set the left pointer to NULL.
483 2b) Goto 1 if next points to a child of np.
485 3. Load the right pointer of the node pointed to by
488 4. If the result is not NULL,
489 4a) Set the right pointer to NULL.
490 4b) Goto 1 id next points to a child of np.
492 5. Load next with the parent pointer of np.
494 6. Free np->rec and np.
496 7. Set np to next and goto 1 if it is not null.
498 struct pat_node *next;
504 if (next->bit_ndx > np->bit_ndx) continue;
510 if (next->bit_ndx > np->bit_ndx) continue;
515 free_uid_list(np->rec);
517 } while ((np = next));
520 void free_uid_db(struct uid_db *db)
523 Free all dynamically allocated memory of the uid_db
524 pointed to by db. The structure is not reinitialized.
526 if (db->pat_root) free_pat_trie(db->pat_root);
529 xfree(db->num_ndx.records);
532 /** various public interfaces */
533 void init_uid_db(struct uid_db *db)
536 Initialize the uid_db structure pointed to by db 'properly'
537 such that it represents an empty database. An array of
538 size MIN_RECORDS is allocated and assigned to db->records.
540 struct num_ndx *num_ndx;
544 db->records = (struct uid_db_record **)xmalloc(MIN_RECORDS * sizeof(*db->records));
545 db->records_max = MIN_RECORDS;
546 db->records_next = 0;
548 num_ndx = &db->num_ndx;
549 num_ndx->pos_0_value = num_ndx->end_value = -1;
550 num_ndx->records = NULL;
553 void swap_uid_db_data(struct uid_db *db_0, struct uid_db *db_1)
562 int traverse_uid_db(struct uid_db *db,
563 uid_db_traversal_routine *r, void *arg)
566 Traverses the struct uid_db records array in insert order,
567 invoking the subroutine pointed to by r with a pointer to
568 each record and the arg pointer as arguments. If the return
569 value of that is non-zero, traverse_uid_db immediately returns
570 with this value. Otherwise, zero is returned after the last
573 The uid_db_traversal_routine must not modify the uid_db during
576 struct uid_db_record **recs;
582 max = db->records_next;
584 while (ndx < max && (rc = r(recs[ndx], arg)) == 0)