Permit and Deny lists in PurpleAccount

[Mark Doliner]

(I'm responding to a really old email.)

On Tue, Jul 9, 2013 at 6:29 PM, Ankit Vani <a at nevitus.org> wrote:
> Currently, in account.h, there's a TODO:
>
>   /*
>    * TODO: Supplementing the next two linked lists with hash tables
>    * should help performance a lot when these lists are long.  This
>    * matters quite a bit for protocols like MSN, where all your
>    * buddies are added to your permit list.  Currently we have to
>    * iterate through the entire list if we want to check if someone
>    * is permitted or denied.  We should do this for 3.0.0.
>    * Or maybe use a GTree.
>    */
>   GSList *permit;             /**< Permit list.                           */
>   GSList *deny;               /**< Deny list.                             */
>
> I had started with hash tables to supplement the linked lists, and soon found
> the linked lists to no longer be of any use. I am therefore considering
> replacing them with hash tables, and making the appropriate changes to whoever
> uses these.
>
> I would like to know if there are any disadvantages to doing so. Such as, would
> any protocol depend on the order of values in these lists? Or anything else?

I think the advantage of a linked list is that iterating through it is
generally faster than iterating through a hash table. I don't know how
often we iterate through these lists--probably less often than we look
things up in them. I doubt any protocols care about the order of these
lists.

It looks like you decided to leave these as GSLists, and that's cool.
I think we should avoid changing this in the gobjectification branch
if we don't need to. We can change it after gobjectification is merged
into main. I think I'm the one who wrote this TODO. I still think we'd
benefit from faster lookups for MSN. I think using both a GSList and a
GHashTable is probably a bad idea because it's complicated.

Options are:
1. GHashTable instead of GSList (if we decide that iterating through
GHashTables is fast enough, or we don't iterate through the permit and
deny lists often enough for it to mater)
2. GTree (a decent compromise for fast iteration, fastish look-ups,
and moderate memory usage).