[Telepathy] [Bug 16170] New: TpIntSet should cope with larger integers

[bugzilla-daemon at freedesktop.org]

http://bugs.freedesktop.org/show_bug.cgi?id=16170

           Summary: TpIntSet should cope with larger integers
           Product: Telepathy
           Version: unspecified
          Platform: Other
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: medium
         Component: telepathy-glib
        AssignedTo: telepathy at lists.freedesktop.org
        ReportedBy: simon.mcvittie at collabora.co.uk


TpIntSet currently allocates O(h) memory where h is the highest integer in the
set. In particular, a set containing only the integer 0xFFFFFFFF will try to
allocate and zero-fill 512M of memory, then set one bit to 1.

This is fine for service-side use, where we control the allocation policy, but
it's no good for client-side use, where we want the client to be able to cope
gracefully with arbitrary handle values.

It should allocate roughly O(n) memory, where n is the number of integers in
the set, for any guint values in the set. Sjoerd suggests that a page-table
would be an appropriate data structure.

The operations that the existing API requires us to support are:

* Test a guint for presence/absence (this should be relatively fast)
* Add a guint to the set
* Remove a guint from the set
* Count the guints in the set (performance not very important)
* Iterate over the set
* Given an arbitrary guint x, find the smallest guint larger than x that is in
the set

It might be acceptable for the implementation to constrain the integers in the
set to be no larger than 0xFFFFFFFF (and g_return_if_fail if they aren't). This
is technically an ABI break, but in practice all we ever use them for in
Telepathy is storing 32-bit handles, and this constraint is already effectively
present (due to prohibitive memory requirements whenever it's not satisfied).


-- 
Configure bugmail: http://bugs.freedesktop.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.