[jira] Updated: (DIRRMS-22) Need mechanism to find index holes in the bit vector

[ji...@apache.org]

The following issue has been updated:

    Updater: Alex Karasulu (mailto:aok123@bellsouth.net)
       Date: Mon, 19 Apr 2004 12:23 PM
    Changes:
             description changed from 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

 to 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 writes 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.
    ---------------------------------------------------------------------
For a full history of the issue, see:

  http://issues.apache.org/jira/browse/DIRRMS-22?page=history

---------------------------------------------------------------------
View the issue:
  http://issues.apache.org/jira/browse/DIRRMS-22

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
 Components: 
             Berkeley JE

   Assignee: Alex Karasulu
   Reporter: Alex Karasulu

    Created: Mon, 19 Apr 2004 9:46 AM
    Updated: Mon, 19 Apr 2004 12:23 PM

Description:
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 writes 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.


---------------------------------------------------------------------
JIRA INFORMATION:
This message is automatically generated by JIRA.

If you think it was sent incorrectly contact one of the administrators:
   http://issues.apache.org/jira/secure/Administrators.jspa

If you want more information on JIRA, or have a bug to report see:
   http://www.atlassian.com/software/jira