[GitHub] [geode] dschneider-pivotal commented on a change in pull request #7389: GEODE-9950: Add LRANGE command

[GitBox <gi...@apache.org>]

dschneider-pivotal commented on a change in pull request #7389:
URL: https://github.com/apache/geode/pull/7389#discussion_r815076771



##########
File path: geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
##########
@@ -60,6 +112,11 @@ public RedisList() {
     }
   }
 
+  /** Changes negative index to corresponding positive index */
+  private int transformNegIndexToPosIndex(int index) {

Review comment:
       abbreviations are frowned upon these days (like Neg and Pos). Could this method just be named "normalizeIndex" or "getArrayIndex" and the parameter could be named "listIndex"? 

##########
File path: geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
##########
@@ -42,16 +45,65 @@ public RedisList() {
     this.elementList = new SizeableByteArrayList();
   }
 
+  /**
+   * @param start start index of desired elments
+   * @param stop stop index of desired elments
+   * @return list of elements in the range (inclusive).
+   */
+  public List<byte[]> lrange(int start, int stop) {
+    start = transformNegIndexToPosIndex(start);
+    stop = transformNegIndexToPosIndex(stop);
+
+    // Out of range negative index changes to 0
+    start = Math.max(0, start);
+
+    int elementSize = elementList.size();
+    if (start > stop || elementSize <= start) {
+      return Collections.emptyList();
+    }
+
+    // Out of range positive stop index changes to last index available
+    stop = elementSize <= stop ? elementSize - 1 : stop;
+
+    List<byte[]> result = new LinkedList<>();
+    int curIndex;
+
+    // Finds the shortest distance to access nodes in range
+    if (start <= elementSize - stop - 1) {
+      // Starts at head to access nodes at start index then iterates forwards
+      curIndex = 0;
+      ListIterator<byte[]> iterator = elementList.listIterator(curIndex);
+
+      while (iterator.hasNext() && curIndex <= stop) {
+        byte[] element = iterator.next();
+        if (start <= curIndex) {
+          result.add(element);
+        }
+        curIndex = iterator.nextIndex();

Review comment:
       Could this just be "curIndex++"? Also could the block of code just use a normal iterator instead of a listIterator?

##########
File path: geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
##########
@@ -60,6 +112,11 @@ public RedisList() {
     }
   }
 
+  /** Changes negative index to corresponding positive index */
+  private int transformNegIndexToPosIndex(int index) {

Review comment:
       Something I find confusing about this method is even though it says it will convert it to a positive index, it could still be negative (if size() is smaller than -index.
   It seems like you should have a normalizeStartIndex that also does the Math.max(0, start) check;
   and another normalizeStopIndex that does the elementSize <= stop ? elementSize - 1 : stop check.

##########
File path: geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
##########
@@ -42,16 +45,65 @@ public RedisList() {
     this.elementList = new SizeableByteArrayList();
   }
 
+  /**
+   * @param start start index of desired elments
+   * @param stop stop index of desired elments
+   * @return list of elements in the range (inclusive).
+   */
+  public List<byte[]> lrange(int start, int stop) {
+    start = transformNegIndexToPosIndex(start);
+    stop = transformNegIndexToPosIndex(stop);
+
+    // Out of range negative index changes to 0
+    start = Math.max(0, start);
+
+    int elementSize = elementList.size();
+    if (start > stop || elementSize <= start) {
+      return Collections.emptyList();
+    }
+
+    // Out of range positive stop index changes to last index available
+    stop = elementSize <= stop ? elementSize - 1 : stop;
+
+    List<byte[]> result = new LinkedList<>();
+    int curIndex;
+
+    // Finds the shortest distance to access nodes in range
+    if (start <= elementSize - stop - 1) {
+      // Starts at head to access nodes at start index then iterates forwards
+      curIndex = 0;
+      ListIterator<byte[]> iterator = elementList.listIterator(curIndex);
+
+      while (iterator.hasNext() && curIndex <= stop) {
+        byte[] element = iterator.next();
+        if (start <= curIndex) {
+          result.add(element);
+        }
+        curIndex = iterator.nextIndex();
+      }
+    } else {
+      // Starts at tail to access nodes at stop index then iterates backwards
+      curIndex = elementSize - 1;
+      ListIterator<byte[]> iterator = elementList.listIterator(elementSize);
+
+      while (iterator.hasPrevious() && start <= curIndex) {
+        byte[] element = iterator.previous();
+        if (curIndex <= stop) {
+          result.add(0, element); // LinkedList is used to add to head
+        }
+        curIndex = iterator.previousIndex();

Review comment:
       could this just be "curIndex--"?

##########
File path: geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
##########
@@ -42,16 +45,65 @@ public RedisList() {
     this.elementList = new SizeableByteArrayList();
   }
 
+  /**
+   * @param start start index of desired elments
+   * @param stop stop index of desired elments
+   * @return list of elements in the range (inclusive).
+   */
+  public List<byte[]> lrange(int start, int stop) {
+    start = transformNegIndexToPosIndex(start);
+    stop = transformNegIndexToPosIndex(stop);
+
+    // Out of range negative index changes to 0
+    start = Math.max(0, start);
+
+    int elementSize = elementList.size();
+    if (start > stop || elementSize <= start) {
+      return Collections.emptyList();
+    }
+
+    // Out of range positive stop index changes to last index available
+    stop = elementSize <= stop ? elementSize - 1 : stop;
+
+    List<byte[]> result = new LinkedList<>();
+    int curIndex;
+
+    // Finds the shortest distance to access nodes in range
+    if (start <= elementSize - stop - 1) {
+      // Starts at head to access nodes at start index then iterates forwards
+      curIndex = 0;
+      ListIterator<byte[]> iterator = elementList.listIterator(curIndex);
+
+      while (iterator.hasNext() && curIndex <= stop) {
+        byte[] element = iterator.next();
+        if (start <= curIndex) {
+          result.add(element);
+        }
+        curIndex = iterator.nextIndex();
+      }
+    } else {
+      // Starts at tail to access nodes at stop index then iterates backwards
+      curIndex = elementSize - 1;
+      ListIterator<byte[]> iterator = elementList.listIterator(elementSize);
+
+      while (iterator.hasPrevious() && start <= curIndex) {
+        byte[] element = iterator.previous();
+        if (curIndex <= stop) {
+          result.add(0, element); // LinkedList is used to add to head
+        }
+        curIndex = iterator.previousIndex();
+      }
+    }
+    return result;
+  }
+
   /**
    * @param index index of desired element. Positive index starts at the head. Negative index starts
    *        at the tail.
    * @return element at index. Null if index is out of range.
    */
   public byte[] lindex(int index) {
-    if (index < 0) {
-      // Changes negative index to corresponding positive index to utilize get(int index)
-      index = elementList.size() + index;
-    }
+    index = transformNegIndexToPosIndex(index);
 
     if (index < 0 || elementList.size() <= index) {

Review comment:
       if transformNegIndexToPosIndex checked to see if it was going to return something < 0 and instead returns Integer.MAX then this if statement could drop the "index < 0" check.
   Maybe not Integer.MAX just so we could support lists of size 2G. Are redis native lists also limited to <= 2G elements?
   But we could just have this method make sure the index it returns would be a valid list index [0...size-1]. If not then it could either throw an exception or return an exceptional value (for example we could define a constant int INVALID_INDEX = -1). Then the callers can just ask if the result is invalid and then return null/emptyList. Once lrange knows start and stop are both valid it just needs the additional check that start is not greator that stop.

##########
File path: geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
##########
@@ -42,16 +45,65 @@ public RedisList() {
     this.elementList = new SizeableByteArrayList();
   }
 
+  /**
+   * @param start start index of desired elments
+   * @param stop stop index of desired elments
+   * @return list of elements in the range (inclusive).
+   */
+  public List<byte[]> lrange(int start, int stop) {
+    start = transformNegIndexToPosIndex(start);
+    stop = transformNegIndexToPosIndex(stop);
+
+    // Out of range negative index changes to 0
+    start = Math.max(0, start);
+
+    int elementSize = elementList.size();
+    if (start > stop || elementSize <= start) {

Review comment:
       is it really correct to check if start > stop before you do the next "stop" check of it being out of range? I think if you normalized stop first then all you need to check here is start > stop since you know stop is < elementSize.

##########
File path: geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
##########
@@ -42,16 +45,65 @@ public RedisList() {
     this.elementList = new SizeableByteArrayList();
   }
 
+  /**
+   * @param start start index of desired elments
+   * @param stop stop index of desired elments
+   * @return list of elements in the range (inclusive).
+   */
+  public List<byte[]> lrange(int start, int stop) {
+    start = transformNegIndexToPosIndex(start);
+    stop = transformNegIndexToPosIndex(stop);
+
+    // Out of range negative index changes to 0
+    start = Math.max(0, start);
+
+    int elementSize = elementList.size();
+    if (start > stop || elementSize <= start) {
+      return Collections.emptyList();
+    }
+
+    // Out of range positive stop index changes to last index available
+    stop = elementSize <= stop ? elementSize - 1 : stop;
+
+    List<byte[]> result = new LinkedList<>();

Review comment:
       given that you have figured out start and stop at this point it seems like you know exactly how many elements you will return. So I'd expect an array here instead of LinkedList.
   I know you have a case that you iterator the elements in reverse order but couldn't you then just add them to the array in that case at the last array index and work your way down to the 0 element?

##########
File path: geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
##########
@@ -42,16 +45,65 @@ public RedisList() {
     this.elementList = new SizeableByteArrayList();
   }
 
+  /**
+   * @param start start index of desired elments
+   * @param stop stop index of desired elments
+   * @return list of elements in the range (inclusive).
+   */
+  public List<byte[]> lrange(int start, int stop) {
+    start = transformNegIndexToPosIndex(start);
+    stop = transformNegIndexToPosIndex(stop);
+
+    // Out of range negative index changes to 0
+    start = Math.max(0, start);
+
+    int elementSize = elementList.size();
+    if (start > stop || elementSize <= start) {
+      return Collections.emptyList();
+    }
+
+    // Out of range positive stop index changes to last index available
+    stop = elementSize <= stop ? elementSize - 1 : stop;
+
+    List<byte[]> result = new LinkedList<>();
+    int curIndex;
+
+    // Finds the shortest distance to access nodes in range
+    if (start <= elementSize - stop - 1) {
+      // Starts at head to access nodes at start index then iterates forwards
+      curIndex = 0;
+      ListIterator<byte[]> iterator = elementList.listIterator(curIndex);
+
+      while (iterator.hasNext() && curIndex <= stop) {
+        byte[] element = iterator.next();

Review comment:
       It looks like "element" is only used inside the "if" so should this call be moved inside the if?

##########
File path: geode-for-redis/src/main/java/org/apache/geode/redis/internal/data/RedisList.java
##########
@@ -42,16 +45,65 @@ public RedisList() {
     this.elementList = new SizeableByteArrayList();
   }
 
+  /**
+   * @param start start index of desired elments
+   * @param stop stop index of desired elments
+   * @return list of elements in the range (inclusive).
+   */
+  public List<byte[]> lrange(int start, int stop) {
+    start = transformNegIndexToPosIndex(start);
+    stop = transformNegIndexToPosIndex(stop);
+
+    // Out of range negative index changes to 0
+    start = Math.max(0, start);
+
+    int elementSize = elementList.size();
+    if (start > stop || elementSize <= start) {
+      return Collections.emptyList();
+    }
+
+    // Out of range positive stop index changes to last index available
+    stop = elementSize <= stop ? elementSize - 1 : stop;
+
+    List<byte[]> result = new LinkedList<>();
+    int curIndex;
+
+    // Finds the shortest distance to access nodes in range
+    if (start <= elementSize - stop - 1) {
+      // Starts at head to access nodes at start index then iterates forwards
+      curIndex = 0;
+      ListIterator<byte[]> iterator = elementList.listIterator(curIndex);
+
+      while (iterator.hasNext() && curIndex <= stop) {
+        byte[] element = iterator.next();
+        if (start <= curIndex) {
+          result.add(element);
+        }
+        curIndex = iterator.nextIndex();
+      }
+    } else {
+      // Starts at tail to access nodes at stop index then iterates backwards
+      curIndex = elementSize - 1;
+      ListIterator<byte[]> iterator = elementList.listIterator(elementSize);
+
+      while (iterator.hasPrevious() && start <= curIndex) {
+        byte[] element = iterator.previous();

Review comment:
       It looks like "element" is only used inside the "if" so should this call be moved inside the if?




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: notifications-unsubscribe@geode.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org