/* POP3 UID db Copyright (c) 2010 MAD Partners, Ltd. (rweikusat@mssgmbh.com) This file is being published in accordance with the GPLv2 terms contained in the COPYING file being part of the fetchmail 6.3.17 release, including the OpenSSL exemption. */ #include "fetchmail.h" /* includes */ #include #include #include #include /* ffs() lives here - needs #define on Solaris. */ #include "uid_db.h" #include "xmalloc.h" /* constants */ enum { MIN_RECORDS = 16 /* arbitrary */ }; /* types */ struct pat_node { struct pat_node *ptrs_[3]; /* The bit mask is stored in the nodes (as opposed to the offset, which is (re-)calculated on demand) because calculating the mask is a non-trivial operation (at least on x86). */ unsigned bit_ndx, bit_mask; struct uid_db_record *rec; }; /* The idea behind this is that the 'left' pointer of a node is accessible as ptrs(np)[-1] and the right one a ptrs(np)[1]. This implies that no separate codepaths for 'symmetric left- and right-cases' are needed. */ #define ptrs(np) ((np)->ptrs_ + 1) /* routines */ /** various helpers */ static inline unsigned bit_ofs(unsigned bit_ndx) { return bit_ndx >> 3; } static inline unsigned bit_mask(unsigned bit_ndx) { return 1 << (bit_ndx & 7); } /** PATRICIA trie insertion */ /*** walkers */ static struct pat_node *walk_down(struct uid_db *db, struct uid_db_record *rec, struct pat_node ***edgep, struct pat_node **parentp) { /* Find the pat node whose id is 'most similar' to the id stored in rec->id. Return a pointer to this node. 'parentp' and 'edgep' are output-only parameters which will point to the parent of returned node and to the edge pointer going from the parent to the returned node after the call has returned. This routine is intended for inserts only. */ struct pat_node *cur, **edge; unsigned bit_ndx, v = 0, ofs; cur = db->pat_root; ofs = -1; do { bit_ndx = cur->bit_ndx; if (bit_ofs(bit_ndx) != ofs) { ofs = bit_ofs(bit_ndx); v = ofs < rec->id_len ? rec->id[ofs] : 0; } edge = ptrs(cur) + (v & cur->bit_mask ? 1 : -1); } while ((cur = *edge) && cur->bit_ndx > bit_ndx); *parentp = (struct pat_node *) ((unsigned char *)edge - (v & bit_mask(bit_ndx) ? offsetof(struct pat_node, ptrs_) + 2 * sizeof(struct pat_node *) : offsetof(struct pat_node, ptrs_))); *edgep = edge; return cur; } static inline struct pat_node *walk_up(unsigned diff_ndx, struct pat_node **parent) { /* Walk the chain of parent pointers starting with *parent until a node is found whose parent has a bit_ndx smaller than diff_ndx. Return a pointer to this node and update *parent to point to its parent. */ struct pat_node *p, *np; np = *parent; while ((p = *ptrs(np)) && p->bit_ndx > diff_ndx) np = p; *parent = p; return np; } /*** bit fiddling */ static inline unsigned first_set_bit_in_char(unsigned v) { return ffs(v) - 1; } static int find_first_diff_bit(struct uid_db_record const *r0, struct uid_db_record const *r1) { /* Return the bit_ndx of the first differing bit in r0->id and r1->id or -1 if the strings are identical. */ struct uid_db_record const *long_id; unsigned ofs, max; unsigned char v; max = r0->id_len; if (max > r1->id_len) { max = r1->id_len; long_id = r0; } else long_id = r1; ofs = 0; do v = r0->id[ofs] ^ r1->id[ofs]; while (!v && ++ofs < max); if (!v) { if (r0->id_len == r1->id_len) return -1; v = long_id->id[ofs]; } return first_set_bit_in_char(v) + ofs * 8; } static inline unsigned bit_set(unsigned bit_ndx, struct uid_db_record const *rec) { /* Return non-zero if the bit corresponding with bit_ndx is set in rec->id */ unsigned ofs; ofs = bit_ofs(bit_ndx); if (ofs >= rec->id_len) return 0; return rec->id[ofs] & bit_mask(bit_ndx); } /*** node allocation */ static struct pat_node *get_pat_node(struct uid_db_record *rec) { /* Allocate a pat_node, set its rec pointer to rec and the next pointer of rec to NULL. Return pointer to the pat_node. */ struct pat_node *np; np = (struct pat_node *)xmalloc(sizeof(*np)); np->rec = rec; rec->next = NULL; return np; } static struct pat_node *get_standalone_node(struct uid_db_record *rec) { /* Return a pat_node suitable for being inserted on the 'left edge' of the trie, ie either linked to a node whose left pointer was zero or being inserted as root node into an empty trie. The bit_ndx of the pat_node is set to the index corresponding with the highest set bit in rec->id. NB: This is a bad choice when UIDs share a common prefix because this implies that the root node will cause a bit to be tested which is non-zero in all other nodes, adding a theoretically redundant level to the trie. This is (to the best of my knowledge) un- fortunately unavoidable if nodes with different key lengths need to be supported. */ struct pat_node *np; np = get_pat_node(rec); np->bit_ndx = first_set_bit_in_char(*rec->id); np->bit_mask = bit_mask(np->bit_ndx); retu
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
 <HEAD>
   <TITLE> [fetchmail] Patch for IMAP idling where idling is unsupported
   </TITLE>
   <LINK REL="Index" HREF="index.html" >
   <LINK REL="made" HREF="mailto:esr%40thyrsus.com">
   <META NAME="robots" CONTENT="index,nofollow">
   
   <LINK REL="Previous"  HREF="007705.html">
   <LINK REL="Next"  HREF="007706.html">
 </HEAD>
 <BODY BGCOLOR="#ffffff">
   <H1>[fetchmail] Patch for IMAP idling where idling is unsupported
   </H1>
    <B>Eric S. Raymond
    </B> 
    <A HREF="mailto:esr%40thyrsus.com"
       TITLE="[fetchmail] Patch for IMAP idling where idling is unsupported">esr@thyrsus.com
       </A><BR>
    <I>Mon, 21 Jul 2003 22:32:31 -0400</I>
    <P><UL>
        <LI> Previous message: <A HREF="007705.html">[fetchmail] Patch for IMAP idling where idling is unsupported
</A></li>
        <LI> Next message: <A HREF="007706.html">[fetchmail] [PATCH] Debian bug #156592 again + update
</A></li>
         <