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.
15 #include <strings.h> // ffs() lives here
22 MIN_RECORDS = 16 /* arbitrary */
27 struct pat_node *ptrs_[3];
30 The bit mask is stored in the nodes (as opposed to the
31 offset, which is (re-)calculated on demand) because
32 calculating the mask is a non-trivial operation (at
35 unsigned bit_ndx, bit_mask;
37 struct uid_db_record *rec;
41 The idea behind this is that the 'left' pointer of
42 a node is accessible as ptrs(np)[-1] and the right
43 one a ptrs(np)[1]. This implies that no separate codepaths
44 for 'symmetric left- and right-cases' are needed.
46 #define ptrs(np) ((np)->ptrs_ + 1)
49 /** various helpers */
50 static inline unsigned bit_ofs(unsigned bit_ndx)
55 static inline unsigned bit_mask(unsigned bit_ndx)
57 return 1 << (bit_ndx & 7);
60 /** PATRICIA trie insertion */
62 static struct pat_node *walk_down(struct uid_db *db, struct uid_db_record *rec,
63 struct pat_node ***edgep, struct pat_node **parentp)
66 Find the pat node whose id is 'most similar' to the id
67 stored in rec->id. Return a pointer to this node.
68 'parentp' and 'edgep' are output-only parameters which
69 will point to the parent of returned node and to the edge
70 pointer going from the parent to the returned node after
71 the call has returned.
73 This routine is intended for inserts only.
75 struct pat_node *cur, **edge;
76 unsigned bit_ndx, v = 0, ofs;
81 bit_ndx = cur->bit_ndx;
83 if (bit_ofs(bit_ndx) != ofs) {
84 ofs = bit_ofs(bit_ndx);
85 v = ofs < rec->id_len ? rec->id[ofs] : 0;
88 edge = ptrs(cur) + (v & cur->bit_mask ? 1 : -1);
89 } while ((cur = *edge) && cur->bit_ndx > bit_ndx);
93 ((unsigned char *)edge - (v & bit_mask(bit_ndx) ?
94 offsetof(struct pat_node, ptrs_[2])
95 : offsetof(struct pat_node, ptrs_[0])));
100 static inline struct pat_node *walk_up(unsigned diff_ndx, struct pat_node **parent)
103 Walk the chain of parent pointers starting with *parent until a node
104 is found whose parent has a bit_ndx smaller than diff_ndx. Return
105 a pointer to this node and update *parent to point to its parent.
107 struct pat_node *p, *np;
111 while ((p = *ptrs(np)) && p->bit_ndx > diff_ndx)
119 static inline unsigned first_set_bit_in_char(unsigned v)
124 static int find_first_diff_bit(struct uid_db_record const *r0,
125 struct uid_db_record const *r1)
128 Return the bit_ndx of the first differing bit in
129 r0->id and r1->id or -1 if the strings are identical.
131 struct uid_db_record const *long_id;
136 if (max > r1->id_len) {
144 v = r0->id[ofs] ^ r1->id[ofs];
145 while (!v && ++ofs < max);
148 if (r0->id_len == r1->id_len) return -1;
149 v = long_id->id[ofs];
152 return first_set_bit_in_char(v) + ofs * 8;
155 static inline unsigned bit_set(unsigned bit_ndx, struct uid_db_record const *rec)
158 Return non-zero if the bit corresponding with bit_ndx is set
163 ofs = bit_ofs(bit_ndx);
164 if (ofs >= rec->id_len) return 0;
165 return rec->id[ofs] & bit_mask(bit_ndx);
168 /*** node allocation */
169 static struct pat_node *get_pat_node(struct uid_db_record *rec)
172 Allocate a pat_node, set its rec pointer to rec and the
173 next pointer of rec to NULL. Return pointer to the pat_node.
177 np = (struct pat_node *)xmalloc(sizeof(*np));
183 static struct pat_node *get_standalone_node(struct uid_db_record *rec)
186 Return a pat_node suitable for being inserted on the 'left edge'
187 of the trie, ie either linked to a node whose left pointer was zero
188 or being inserted as root node into an empty trie. The bit_ndx of
189 the pat_node is set to the index corresponding with the highest
192 NB: This is a bad choice when UIDs share a common prefix because
193 this implies that the root node will cause a bit to be tested which
194 is non-zero in all other nodes, adding a theoretically redundant
195 level to the trie. This is (to the best of my knowledge) un-
196 fortunately unavoidable if nodes with different key lengths need
201 np = get_pat_node(rec);
202 np->bit_ndx = first_set_bit_in_char(*rec->id);
203 np->bit_mask = bit_mask(np->bit_ndx);
207 /*** various helpers */
209 static inline int record_id_equal(struct uid_db_record const *r0,
210 struct uid_db_record const *r1)
213 r0->id_len == r1->id_len
214 && memcmp(r0->id, r1->id, r0->id_len) == 0;
218 static struct uid_db_record *append_to_list(struct uid_db_record **recp,
219 struct uid_db_record *rec)
222 Append the uid_db_record pointed to by rec to the uid_db_record
223 list accessible as *recp and return rec.
225 while (*recp) recp = &(*recp)->next;
232 /*** insert routine */
233 static struct uid_db_record *pat_insert(struct uid_db *db,
234 struct uid_db_record *rec)
237 Insert the record pointed to by rec in the (potentially empty)
238 PATRICIA trie pointed to by db->pat_root and return rec.
240 struct pat_node *np, *closest, *parent, **edge;
244 np = get_standalone_node(rec);
245 ptrs(np)[-1] = *ptrs(np) = NULL;
252 closest = walk_down(db, rec, &edge, &parent);
255 bit_ndx = find_first_diff_bit(closest->rec, rec);
257 return append_to_list(&closest->rec->next, rec);
259 np = get_pat_node(rec);
260 np->bit_ndx = bit_ndx;
261 np->bit_mask = bit_mask(bit_ndx);
263 np = get_standalone_node(rec);
265 if (parent->bit_ndx > np->bit_ndx) {
266 closest = walk_up(np->bit_ndx, &parent);
268 if (!parent) edge = &db->pat_root;
269 else edge = ptrs(parent)[-1] == closest ?
270 ptrs(parent) - 1 : ptrs(parent) + 1;
277 me = bit_set(np->bit_ndx, rec) ? 1 : -1;
279 ptrs(np)[-me] = closest;
284 /** general db insertion */
285 static struct uid_db_record *get_uid_db_record(char const *id, unsigned status)
288 Allocate a uid_db_record structure and set its id pointer to a
289 dynamically allocated copy of id. The status member of the
290 new record is set to status and its message number to zero (invalid).
291 A pointer to it is then returned.
293 struct uid_db_record *rec;
296 rec = (struct uid_db_record *)xmalloc(sizeof(*rec));
299 rec->id = (char *)memcpy(xmalloc(id_len + 1), id, id_len + 1);
300 rec->id_len = id_len;
301 rec->status = status;
307 static void insert_into_records(struct uid_db *db,
308 struct uid_db_record *rec)
311 Insert rec into the records array of the uid_db pointed
312 to by db. The array is grown as necessary and the
313 corresponding state variables of the db are updated
314 accordingly. The pos member of rec is set to its position
319 next = db->records_next;
321 if (next == db->records_max) {
322 want = db->records_max *= 2;
323 db->records = (struct uid_db_record **)xrealloc(db->records, want * sizeof(rec));
327 db->records[next] = rec;
328 db->records_next = next + 1;
331 struct uid_db_record *uid_db_insert(struct uid_db *db,
332 char const *id, unsigned status)
335 Create an uid_db_record whose id is id and whose status is
336 status and insert it into the uid_db pointed to by db.
337 Return a pointer to the newly created record.
339 struct uid_db_record *rec;
341 rec = get_uid_db_record(id, status);
342 insert_into_records(db, rec);
343 return pat_insert(db, rec);
346 /** message number index */
347 void set_uid_db_num(struct uid_db *db, struct uid_db_record *rec,
351 Set the message number of the record pointed to by rec to num
352 and insert it into the num_ndx of the uid_db pointed to by db
353 at position corresponding with num. The num_ndx lookup array
354 is grown as needed. Message numbers are expected to 'generally'
355 be recorded in ascending order and hence, no provisions are
356 made to deal with the potentially quadratic complexity of
357 inserting a sequence of numbers into an array such that it
358 needs to be grown continuously.
360 struct num_ndx *num_ndx;
363 num_ndx = &db->num_ndx;
365 if (num_ndx->end_value > num) {
366 have = num_ndx->pos_0_value - num_ndx->end_value + 1;
367 want = num_ndx->pos_0_value - num + 1;
368 num_ndx->end_value = num;
370 num_ndx->records = (struct uid_db_record **)xrealloc(num_ndx->records, want * sizeof(rec));
371 do num_ndx->records[--want] = NULL; while (want > have);
374 num_ndx->records[uid_db_num_ofs(num_ndx, num)] = rec;
377 void reset_uid_db_nums(struct uid_db *db)
380 Reset the message numbers of all uid_db_records stored
381 in the uid_db pointed to by db. The corresponding num_ndx
382 lookup array is afterwards freed and the num_ndx end_value
383 adjusted in order to indicate an 'empty' message number
386 struct uid_db_record **rec;
387 struct num_ndx *num_ndx;
390 num_ndx = &db->num_ndx;
392 if (num_ndx->end_value < num_ndx->pos_0_value) {
393 ndx = num_ndx->pos_0_value - num_ndx->end_value;
395 rec = num_ndx->records + --ndx;
396 if (*rec) (*rec)->num = 0;
399 num_ndx->end_value = num_ndx->pos_0_value + 1;
401 free(num_ndx->records);
402 num_ndx->records = NULL;
406 /** search routines */
407 struct uid_db_record *find_uid_by_id(struct uid_db *db, char const *id)
410 Search for an uid_db_record whose id is id in the uid_db pointed
411 to by db and return a pointer to it or NULL if no such record was
415 struct uid_db_record *rec;
416 unsigned v = 0, bit_ndx, ofs;
424 bit_ndx = np->bit_ndx;
426 if (bit_ofs(bit_ndx) != ofs) {
427 ofs = bit_ofs(bit_ndx);
428 v = ofs < len ? id[ofs] : 0;
431 np = ptrs(np)[v & np->bit_mask ? 1 : -1];
432 } while (np && np->bit_ndx > bit_ndx);
434 if (!np) return NULL;
437 return rec->id_len == len && memcmp(id, rec->id, len) == 0 ?
444 struct uid_db_record *last_uid_in_db(struct uid_db *db, char const *id)
447 Return a pointer to the 'last' (insert order) uid_db_record
448 contained in the uid_db pointed to by db whose id is id or
449 NULL if no such record exists.
451 struct uid_db_record *rec;
453 rec = find_uid_by_id(db, id);
454 if (!rec) return NULL;
456 while (rec->next) rec = rec->next;
461 static void free_uid_list(struct uid_db_record *rec)
464 Free the list of uid_db_records starting with
465 the record pointed to by rec.
467 if (rec->next) free_uid_list(rec->next);
473 static void free_pat_trie(struct pat_node *np)
476 Free the PATRCIA-trie pointed to by np and all
477 uid_db_records contained in it.
479 The algorithm implemented below is:
481 1. Load the left pointer of the node pointed to by
484 2. If the result is not NULL,
485 2a) Set the left pointer to NULL.
486 2b) Goto 1 if next points to a child of np.
488 3. Load the right pointer of the node pointed to by
491 4. If the result is not NULL,
492 4a) Set the right pointer to NULL.
493 4b) Goto 1 id next points to a child of np.
495 5. Load next with the parent pointer of np.
497 6. Free np->rec and np.
499 7. Set np to next and goto 1 if it is not null.
501 struct pat_node *next;
507 if (next->bit_ndx > np->bit_ndx) continue;
513 if (next->bit_ndx > np->bit_ndx) continue;
518 free_uid_list(np->rec);
520 } while ((np = next));
523 void free_uid_db(struct uid_db *db)
526 Free all dynamically allocated memory of the uid_db
527 pointed to by db. The structure is not reinitialized.
529 if (db->pat_root) free_pat_trie(db->pat_root);
532 xfree(db->num_ndx.records);
535 /** various public interfaces */
536 void init_uid_db(struct uid_db *db)
539 Initialize the uid_db structure pointed to by db 'properly'
540 such that it represents an empty database. An array of
541 size MIN_RECORDS is allocated and assigned to db->records.
543 struct num_ndx *num_ndx;
547 db->records = (struct uid_db_record **)xmalloc(MIN_RECORDS * sizeof(*db->records));
548 db->records_max = MIN_RECORDS;
549 db->records_next = 0;
551 num_ndx = &db->num_ndx;
552 num_ndx->pos_0_value = num_ndx->end_value = -1;
553 num_ndx->records = NULL;
556 void swap_uid_db_data(struct uid_db *db_0, struct uid_db *db_1)
565 int traverse_uid_db(struct uid_db *db,
566 uid_db_traversal_routine *r, void *arg)
569 Traverses the struct uid_db records array in insert order,
570 invoking the subroutine pointed to by r with a pointer to
571 each record and the arg pointer as arguments. If the return
572 value of that is non-zero, traverse_uid_db immediately returns
573 with this value. Otherwise, zero is returned after the last
576 The uid_db_traversal_routine must not modify the uid_db during
579 struct uid_db_record **recs;
585 max = db->records_next;
587 while (ndx < max && (rc = r(recs[ndx], arg)) == 0)