directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
Subject [jira] Created: (DIRRMS-22) Need mechanism to find index holes in the bit vector
Date Mon, 19 Apr 2004 16:46:53 GMT

  A new issue has been created in JIRA.

View the issue:

Here is an overview of the issue:
        Key: DIRRMS-22
    Summary: Need mechanism to find index holes in the bit vector
       Type: Task

     Status: Open
   Priority: Major

    Project: Directory RMS
             Berkeley JE

   Assignee: Alex Karasulu
   Reporter: Alex Karasulu

    Created: Mon, 19 Apr 2004 9:46 AM
    Updated: Mon, 19 Apr 2004 9:46 AM

Right now it's not all that simple to rapidly find the next available bit index to occupy.
 One would think the secondary indices would help and they do but since all permissions from
all applications are involved the problem is not as simple as it seems.  At first glance it
might appear as though a join would work but we still need to find the smallest available
index and so order creeps into the picture taking the option of a join out.  

Keep in mind this operation is for write and it need not be that fast since we're optimized
for reads.  However it still needs to be efficient regardless and fairly straight forward.
 The most sensible option is to scan the appName:rowId secondary for duplicate appName records
on a specific app and build a map to use for finding wholes.  What does this map look like?

We need the map to find holes with the smallest index where we can place new BitPermissions.
 There is no simple means to do this without building the map then scanning it in the order
of ascending indices.  The map should be sorded by the bit vector index where the index is
the key.  Since we search for and fill holes we can use the index into an array as the bit
vector index without wasting space.  Hence the best structure for the map is an int[] or even
a String[].  If its an int[] then the map is an index:rowId mapping.  If it is a String[]
it is an index:name mapping.  For the int[] some none viable int value like -1 must be used
as the hole marker.  In the String[] we can just use null.  Yet another option is to just
build a BitPermission[].

There are pro's and cons to using the int[] verses the String[].  First off the String[] is
and excellent mapping which is needed for Applications anyway.  Its like killing to birds
with one stone.  However it is less efficient.  Basically the permissions

This message is automatically generated by JIRA.

If you think it was sent incorrectly contact one of the administrators:

If you want more information on JIRA, or have a bug to report see:

View raw message