saihemanth-cloudera commented on code in PR #4601:
URL: https://github.com/apache/hive/pull/4601#discussion_r1303113256
##########
ql/src/java/org/apache/hadoop/hive/ql/security/authorization/plugin/HivePrivilegeObjectUtils.java:
##########
@@ -59,7 +57,127 @@ public static List<HivePrivilegeObject>
getHivePrivDcObjects(List<String> dcList
objs.add(new HivePrivilegeObject(HivePrivilegeObjectType.DATACONNECTOR,
null, dcname));
}
return objs;
+ }
+
+ /**
+ * A helper enabling efficient lookup of a table in a list by database name,
table name.
+ * <p>When filtering a source list of tables by checking their presence in
another permission list
+ * using the database name, table name, we need to avoid performing a
cartesian product. This
+ * product stems from checking each table from the source (n tables) by
comparing it to each
+ * table in the permission list (m permissions), thus an n * m
complexity.</p>
+ * <p>This class reduces the complexity of the lookup in the permission by
sorting them and
+ * using a binary search; the sort cost is m*log(m) and each lookup is
log(m), the overall
+ * complexity of a check for all tables is in the order of m*log(m) +
n*log(m) = (m + n)*log(n),
+ * close to m * log(n).</p>
+ *
+ */
+ public abstract static class TableLookup<T> {
+ /** The container. */
+ private final T[] index;
+
+ /**
+ * @param table the table
+ * @return the database name of the table
+ */
+ protected abstract String getDbName(T table);
+
+ /**
+ * @param table the table
+ * @return the table name of the table
+ */
+ protected abstract String getTableName(T table);
+
+ /**
+ * Compares a table to another by names.
+ * @param table the table
+ * @param arg the argument table
+ * @return < 0, 0, > 0
+ */
+ private int compareNames(final T table, final T arg) {
+ int cmp = getDbName(table).compareTo(getDbName(arg));
+ if (cmp == 0) {
+ cmp = getTableName(table).compareTo(getTableName(arg));
+ }
+ return cmp;
+ }
+
+ /**
+ * Compares a table to names.
+ * @param table the table
+ * @param dbName the argument database name
+ * @param dbName the argument table name
+ * @return < 0, 0, > 0
+ */
+ private int compareNames(final T table, final String dbName, final String
tableName) {
+ int cmp = getDbName(table).compareTo(dbName);
+ if (cmp == 0) {
+ cmp = getTableName(table).compareTo(tableName);
+ }
+ return cmp;
+ }
+
+ /**
+ * Creates a ByName
+ * @param tables the tables to consider as a clique
+ */
+ protected TableLookup(List<T> tables) {
+ if (tables != null) {
+ index = tables.toArray((T[]) new Object[0]);
+ // sort them by names
+ Arrays.sort(index, this::compareNames);
+ } else {
+ index = (T[]) new Object[0];
+ }
+ }
+ /**
+ * Lookup using dichotomy using order described by database name, table
name.
+ * @param dbName the database name
+ * @param tableName the table name
+ * @return the table if found in the index, null otherwise
+ */
+ public final T lookup(final String dbName, final String tableName) {
+ int low = 0;
+ int high = index.length - 1;
+ while (low <= high) {
+ int mid = (low + high) >>> 1;
+ T item = index[mid];
+ int cmp = compareNames(item, dbName, tableName);
+ if (cmp < 0) {
+ low = mid + 1;
+ } else if (cmp > 0) {
+ high = mid - 1;
+ } else {
+ return item; // key found
+ }
+ }
+ return null; // key not found.
+ }
+
+ /**
+ * Checks whether a given table is present in this set.
+ * @param tt the table to check
+ * @return true if the set contains an item having the same database and
table name
+ */
+ public final boolean contains(T tt) {
+ return lookup(getDbName(tt), getTableName(tt)) != null;
+ }
}
+ /**
+ * Specialized lookup for HivePrivilegeObject.
+ */
+ public static class PrivilegeLookup extends TableLookup<HivePrivilegeObject>
{
Review Comment:
nit: 'PrivilegeLookup', should this be 'PrivilegeTableLookup'?
--
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: gitbox-unsubscr...@hive.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: gitbox-unsubscr...@hive.apache.org
For additional commands, e-mail: gitbox-h...@hive.apache.org
