1 files changed, 274 insertions, 142 deletions

diff --git a/sql/sql_acl.cc b/sql/sql_acl.cc
index 052c5ada3a2..954f588b061 100644
--- a/sql/sql_acl.cc
+++ b/sql/sql_acl.cc
@@ -187,6 +187,8 @@ public:
 
   bool eq(const char *user2, const char *host2) { return !cmp(user2, host2); }
 
+  const char *get_username(){ return user.str; }
+
   bool wild_eq(const char *user2, const char *host2, const char *ip2)
   {
     if (strcmp(user.str, user2))
@@ -228,6 +230,8 @@ public:
   acl_host_and_ip host;
   const char *user,*db;
   ulong initial_access; /* access bits present in the table */
+
+  const char *get_username() { return user; }
 };
 
 #ifndef DBUG_OFF
@@ -592,7 +596,9 @@ bool ROLE_GRANT_PAIR::init(MEM_ROOT *mem, const char *username,
 /* Flag to mark that on_node was already called for this role */
 #define ROLE_OPENED             (1L << 3)
 
-static DYNAMIC_ARRAY acl_hosts, acl_users, acl_dbs, acl_proxy_users;
+static DYNAMIC_ARRAY acl_hosts, acl_users, acl_proxy_users;
+static Dynamic_array<ACL_DB> acl_dbs(0U,50U);
+typedef Dynamic_array<ACL_DB>::CMP_FUNC acl_dbs_cmp;
 static HASH acl_roles;
 /*
   An hash containing mappings user <--> role
@@ -610,7 +616,11 @@ static DYNAMIC_ARRAY acl_wild_hosts;
 static Hash_filo<acl_entry> *acl_cache;
 static uint grant_version=0; /* Version of priv tables. incremented by acl_load */
 static ulong get_access(TABLE *form,uint fieldnr, uint *next_field=0);
-static int acl_compare(ACL_ACCESS *a,ACL_ACCESS *b);
+static int acl_compare(const ACL_ACCESS *a, const ACL_ACCESS *b);
+static int acl_user_compare(const ACL_USER *a, const ACL_USER *b);
+static void rebuild_acl_users();
+static int acl_db_compare(const ACL_DB *a, const ACL_DB *b);
+static void rebuild_acl_dbs();
 static ulong get_sort(uint count,...);
 static void init_check_host(void);
 static void rebuild_check_host(void);
@@ -1973,8 +1983,7 @@ static bool acl_load(THD *thd, const Grant_tables& tables)
     DBUG_PRINT("info", ("Found user %s", user.user.str));
     push_new_user(user);
   }
-  my_qsort((uchar*) dynamic_element(&acl_users,0,ACL_USER*),acl_users.elements,
-	   sizeof(ACL_USER),(qsort_cmp) acl_compare);
+  rebuild_acl_users();
   end_read_record(&read_record_info);
   freeze_size(&acl_users);
 
@@ -2036,12 +2045,11 @@ static bool acl_load(THD *thd, const Grant_tables& tables)
 	db.access|=REFERENCES_ACL | INDEX_ACL | ALTER_ACL;
     }
 #endif
-    (void) push_dynamic(&acl_dbs,(uchar*) &db);
+    acl_dbs.push(db);
   }
-  my_qsort((uchar*) dynamic_element(&acl_dbs,0,ACL_DB*),acl_dbs.elements,
-	   sizeof(ACL_DB),(qsort_cmp) acl_compare);
   end_read_record(&read_record_info);
-  freeze_size(&acl_dbs);
+  rebuild_acl_dbs();
+  acl_dbs.freeze();
 
   const Proxies_priv_table& proxies_priv_table= tables.proxies_priv_table();
   if (proxies_priv_table.table_exists())
@@ -2120,7 +2128,7 @@ void acl_free(bool end)
   free_root(&acl_memroot,MYF(0));
   delete_dynamic(&acl_hosts);
   delete_dynamic_with_callback(&acl_users, (FREE_FUNC) free_acl_user);
-  delete_dynamic(&acl_dbs);
+  acl_dbs.free_memory();
   delete_dynamic(&acl_wild_hosts);
   delete_dynamic(&acl_proxy_users);
   my_hash_free(&acl_check_hosts);
@@ -2158,7 +2166,8 @@ void acl_free(bool end)
 
 bool acl_reload(THD *thd)
 {
-  DYNAMIC_ARRAY old_acl_hosts, old_acl_users, old_acl_dbs, old_acl_proxy_users;
+  DYNAMIC_ARRAY old_acl_hosts, old_acl_users, old_acl_proxy_users;
+  Dynamic_array<ACL_DB> old_acl_dbs(0U,0U);
   HASH old_acl_roles, old_acl_roles_mappings;
   MEM_ROOT old_mem;
   int result;
@@ -2194,7 +2203,7 @@ bool acl_reload(THD *thd)
   old_acl_dbs= acl_dbs;
   my_init_dynamic_array(&acl_hosts, sizeof(ACL_HOST), 20, 50, MYF(0));
   my_init_dynamic_array(&acl_users, sizeof(ACL_USER), 50, 100, MYF(0));
-  my_init_dynamic_array(&acl_dbs, sizeof(ACL_DB), 50, 100, MYF(0));
+  acl_dbs.init(50, 100);
   my_init_dynamic_array(&acl_proxy_users, sizeof(ACL_PROXY_USER), 50, 100, MYF(0));
   my_hash_init2(&acl_roles,50, &my_charset_utf8_bin,
                 0, 0, 0, (my_hash_get_key) acl_role_get_key, 0,
@@ -2215,6 +2224,7 @@ bool acl_reload(THD *thd)
     acl_roles_mappings= old_acl_roles_mappings;
     acl_proxy_users= old_acl_proxy_users;
     acl_dbs= old_acl_dbs;
+    old_acl_dbs.init(0,0);
     acl_memroot= old_mem;
     init_check_host();
   }
@@ -2225,7 +2235,6 @@ bool acl_reload(THD *thd)
     delete_dynamic(&old_acl_hosts);
     delete_dynamic_with_callback(&old_acl_users, (FREE_FUNC) free_acl_user);
     delete_dynamic(&old_acl_proxy_users);
-    delete_dynamic(&old_acl_dbs);
     my_hash_free(&old_acl_roles_mappings);
   }
   mysql_mutex_unlock(&acl_cache->lock);
@@ -2317,7 +2326,7 @@ static ulong get_sort(uint count,...)
 }
 
 
-static int acl_compare(ACL_ACCESS *a,ACL_ACCESS *b)
+static int acl_compare(const ACL_ACCESS *a, const ACL_ACCESS *b)
 {
   if (a->sort > b->sort)
     return -1;
@@ -2326,6 +2335,154 @@ static int acl_compare(ACL_ACCESS *a,ACL_ACCESS *b)
   return 0;
 }
 
+static int acl_user_compare(const ACL_USER *a, const ACL_USER *b)
+{
+  int res= strcmp(a->user.str, b->user.str);
+  if (res)
+    return res;
+
+  res= acl_compare(a, b);
+  if (res)
+    return res;
+
+  /*
+    For more deterministic results, resolve ambiguity between
+    "localhost" and "127.0.0.1"/"::1" by sorting "localhost" before
+    loopback addresses.
+    Test suite (on Windows) expects "root@localhost", even if
+    root@::1 would also match.
+  */
+  return -strcmp(a->host.hostname, b->host.hostname);
+}
+
+static int acl_db_compare(const ACL_DB *a, const ACL_DB *b)
+{
+  int res= strcmp(a->user, b->user);
+  if (res)
+    return res;
+
+  return acl_compare(a, b);
+}
+
+static void rebuild_acl_users()
+{
+   my_qsort((uchar*)dynamic_element(&acl_users, 0, ACL_USER*), acl_users.elements,
+     sizeof(ACL_USER), (qsort_cmp)acl_user_compare);
+}
+
+static void rebuild_acl_dbs()
+{
+  acl_dbs.sort(acl_db_compare);
+}
+
+
+/*
+  Return index of the first entry with given user in the array,
+  or UINT_MAX if not found.
+
+  Assumes the array is sorted by get_username
+*/
+template<typename T> uint find_first_user(T* arr, uint len, const char *user)
+{
+  uint low= 0;
+  uint high= len;
+  uint mid;
+
+  bool found= false;
+  if(!len)
+    return  UINT_MAX;
+
+#ifndef DBUG_OFF
+  for (uint i = 0; i < len - 1; i++)
+    DBUG_ASSERT(strcmp(arr[i].get_username(), arr[i + 1].get_username()) <= 0);
+#endif
+  while (low < high)
+  {
+    mid= low + (high - low) / 2;
+    int cmp= strcmp(arr[mid].get_username(),user);
+    if (cmp == 0)
+      found= true;
+
+    if (cmp >= 0 )
+      high= mid;
+    else
+      low= mid + 1;
+  }
+  return  (!found || low == len || strcmp(arr[low].get_username(), user)!=0 )?UINT_MAX:low;
+}
+
+static uint acl_find_user_by_name(const char *user)
+{
+  return find_first_user<ACL_USER>((ACL_USER *)acl_users.buffer,acl_users.elements,user);
+}
+
+static uint acl_find_db_by_username(const char *user)
+{
+  return find_first_user<ACL_DB>(acl_dbs.front(), acl_dbs.elements(), user);
+}
+
+static bool match_db(ACL_DB *acl_db, const char *db, my_bool db_is_pattern)
+{
+  return !acl_db->db || (db && !wild_compare(db, acl_db->db, db_is_pattern));
+}
+
+
+/*
+  Lookup in the acl_users or acl_dbs for the best matching entry corresponding to
+  given user, host and ip parameters (also db, in case of ACL_DB)
+
+  Historical note:
+
+  In the past, both arrays were sorted just by ACL_ENTRY::sort field and were
+  searched linearly, until the first match of (username,host) pair was found.
+
+  This function uses optimizations (binary search by username), yet preserves the
+  historical behavior, i.e the returns a match with highest ACL_ENTRY::sort.
+*/
+template <typename T> T* find_by_username_or_anon(T* arr, size_t len, const char *user,
+  const char *host, const char *ip,
+  const char *db, my_bool db_is_pattern, bool (*match_db_func)(T*,const char *,my_bool))
+{
+  size_t i;
+  T *ret = NULL;
+
+  // Check  entries matching user name.
+  size_t start = find_first_user(arr, len, user);
+  for (i= start; i < len; i++)
+  {
+    T *entry= &arr[i];
+    if (i > start && strcmp(user, entry->get_username()))
+      break;
+
+    if (compare_hostname(&entry->host, host, ip) && (!match_db_func || match_db_func(entry, db, db_is_pattern)))
+    {
+      ret= entry;
+      break;
+    }
+  }
+
+  // Look also for anonymous user (username is empty string)
+  // Due to sort by name, entries for anonymous user start at the start of array.
+  for (i= 0; i < len; i++)
+  {
+    T *entry = &arr[i];
+    if (*entry->get_username() || (ret && acl_compare(entry, ret) >= 0))
+      break;
+    if (compare_hostname(&entry->host, host, ip) && (!match_db_func || match_db_func(entry, db, db_is_pattern)))
+    {
+      ret= entry;
+      break;
+    }
+  }
+  return ret;
+}
+
+static ACL_DB *acl_db_find(const char *db, const char *user, const char *host, const char *ip, my_bool db_is_pattern)
+{
+  return find_by_username_or_anon(acl_dbs.front(), acl_dbs.elements(),
+                                  user, host, ip, db, db_is_pattern, match_db);
+}
+
 
 /*
   Gets user credentials without authentication and resource limit checks.
@@ -2347,7 +2504,6 @@ bool acl_getroot(Security_context *sctx, const char *user, const char *host,
                  const char *ip, const char *db)
 {
   int res= 1;
-  uint i;
   ACL_USER *acl_user= 0;
   DBUG_ENTER("acl_getroot");
 
@@ -2380,21 +2536,9 @@ bool acl_getroot(Security_context *sctx, const char *user, const char *host,
     if (acl_user)
     {
       res= 0;
-      for (i=0 ; i < acl_dbs.elements ; i++)
-      {
-        ACL_DB *acl_db= dynamic_element(&acl_dbs, i, ACL_DB*);
-        if (!*acl_db->user || !strcmp(user, acl_db->user))
-        {
-          if (compare_hostname(&acl_db->host, host, ip))
-          {
-            if (!acl_db->db || (db && !wild_compare(db, acl_db->db, 0)))
-            {
-              sctx->db_access= acl_db->access;
-              break;
-            }
-          }
-        }
-      }
+      if (ACL_DB *acl_db= acl_db_find(db, user, host, ip, FALSE))
+        sctx->db_access= acl_db->access;
+
       sctx->master_access= acl_user->access;
 
       strmake_buf(sctx->priv_user, user);
@@ -2409,21 +2553,9 @@ bool acl_getroot(Security_context *sctx, const char *user, const char *host,
     if (acl_role)
     {
       res= 0;
-      for (i=0 ; i < acl_dbs.elements ; i++)
-      {
-        ACL_DB *acl_db= dynamic_element(&acl_dbs, i, ACL_DB*);
-        if (!*acl_db->user || !strcmp(user, acl_db->user))
-        {
-          if (compare_hostname(&acl_db->host, "", ""))
-          {
-            if (!acl_db->db || (db && !wild_compare(db, acl_db->db, 0)))
-            {
-              sctx->db_access= acl_db->access;
-              break;
-            }
-          }
-        }
-      }
+      if (ACL_DB *acl_db= acl_db_find(db, user, "", "", FALSE))
+        sctx->db_access = acl_db->access;
+
       sctx->master_access= acl_role->access;
 
       strmake_buf(sctx->priv_role, user);
@@ -2622,10 +2754,10 @@ static bool acl_update_db(const char *user, const char *host, const char *db,
 
   bool updated= false;
 
-  for (uint i=0 ; i < acl_dbs.elements ; i++)
+  for (uint i= acl_find_db_by_username(user); i < acl_dbs.elements(); i++)
   {
-    ACL_DB *acl_db=dynamic_element(&acl_dbs,i,ACL_DB*);
-    if (!strcmp(user, acl_db->user))
+    ACL_DB *acl_db= &acl_dbs.at(i);
+    if (!strcmp(user,acl_db->user))
     {
       if ((!acl_db->host.hostname && !host[0]) ||
           (acl_db->host.hostname && !strcmp(host, acl_db->host.hostname)))
@@ -2640,11 +2772,13 @@ static bool acl_update_db(const char *user, const char *host, const char *db,
             acl_db->initial_access= acl_db->access;
           }
           else
-            delete_dynamic_element(&acl_dbs,i);
+            acl_dbs.del(i);
           updated= true;
         }
       }
     }
+    else
+     break;
   }
 
   return updated;
@@ -2675,9 +2809,8 @@ static void acl_insert_db(const char *user, const char *host, const char *db,
   acl_db.db=strdup_root(&acl_memroot,db);
   acl_db.initial_access= acl_db.access= privileges;
   acl_db.sort=get_sort(3,acl_db.host.hostname,acl_db.db,acl_db.user);
-  (void) push_dynamic(&acl_dbs,(uchar*) &acl_db);
-  my_qsort((uchar*) dynamic_element(&acl_dbs,0,ACL_DB*),acl_dbs.elements,
-	   sizeof(ACL_DB),(qsort_cmp) acl_compare);
+  acl_dbs.push(acl_db);
+  rebuild_acl_dbs();
 }
 
 
@@ -2723,26 +2856,16 @@ ulong acl_get(const char *host, const char *ip,
   /*
     Check if there are some access rights for database and user
   */
-  for (i=0 ; i < acl_dbs.elements ; i++)
+  if (ACL_DB *acl_db= acl_db_find(db,user, host, ip, db_is_pattern))
   {
-    ACL_DB *acl_db=dynamic_element(&acl_dbs,i,ACL_DB*);
-    if (!*acl_db->user || !strcmp(user, acl_db->user))
-    {
-      if (compare_hostname(&acl_db->host,host,ip))
-      {
-        if (!acl_db->db || !wild_compare(db,acl_db->db,db_is_pattern))
-        {
-          db_access=acl_db->access;
-          if (acl_db->host.hostname)
-            goto exit;                          // Fully specified. Take it
-          /* the host table is not used for roles */
-          if ((!host || !host[0]) && !acl_db->host.hostname && find_acl_role(user))
-            goto exit;
-          break; /* purecov: tested */
-	}
-      }
-    }
+    db_access= acl_db->access;
+    if (acl_db->host.hostname)
+      goto exit; // Fully specified. Take it
+    /* the host table is not used for roles */
+    if ((!host || !host[0]) && !acl_db->host.hostname && find_acl_role(user))
+      goto exit;
   }
+
   if (!db_access)
     goto exit;					// Can't be better
 
@@ -3397,20 +3520,9 @@ bool is_acl_user(const char *host, const char *user)
 */
 static ACL_USER *find_user_or_anon(const char *host, const char *user, const char *ip)
 {
-  ACL_USER *result= NULL;
-  mysql_mutex_assert_owner(&acl_cache->lock);
-  for (uint i=0; i < acl_users.elements; i++)
-  {
-    ACL_USER *acl_user_tmp= dynamic_element(&acl_users, i, ACL_USER*);
-    if ((!acl_user_tmp->user.length ||
-         !strcmp(user, acl_user_tmp->user.str)) &&
-         compare_hostname(&acl_user_tmp->host, host, ip))
-    {
-      result= acl_user_tmp;
-      break;
-    }
-  }
-  return result;
+  return find_by_username_or_anon<ACL_USER>
+    (reinterpret_cast<ACL_USER*>(acl_users.buffer), acl_users.elements,
+     user, host, ip, NULL, FALSE, NULL);
 }
 
 
@@ -3420,11 +3532,15 @@ static ACL_USER *find_user_or_anon(const char *host, const char *user, const cha
 static ACL_USER *find_user_exact(const char *host, const char *user)
 {
   mysql_mutex_assert_owner(&acl_cache->lock);
+  uint start= acl_find_user_by_name(user);
 
-  for (uint i=0 ; i < acl_users.elements ; i++)
+  for (uint i= start; i < acl_users.elements; i++)
   {
-    ACL_USER *acl_user=dynamic_element(&acl_users, i, ACL_USER*);
-    if (acl_user->eq(user, host))
+    ACL_USER *acl_user= dynamic_element(&acl_users, i, ACL_USER*);
+    if (i > start && strcmp(acl_user->user.str, user))
+      return 0;
+
+    if (!my_strcasecmp(system_charset_info, acl_user->host.hostname, host))
       return acl_user;
   }
   return 0;
@@ -3437,10 +3553,14 @@ static ACL_USER * find_user_wild(const char *host, const char *user, const char
 {
   mysql_mutex_assert_owner(&acl_cache->lock);
 
-  for (uint i=0 ; i < acl_users.elements ; i++)
+  uint start = acl_find_user_by_name(user);
+
+  for (uint i= start; i < acl_users.elements; i++)
   {
     ACL_USER *acl_user=dynamic_element(&acl_users,i,ACL_USER*);
-    if (acl_user->wild_eq(user, host, ip))
+    if (i > start && strcmp(acl_user->user.str, user))
+      break;
+    if (compare_hostname(&acl_user->host, host, ip ? ip : host))
       return acl_user;
   }
   return 0;
@@ -3970,8 +4090,7 @@ end:
       else
       {
         push_new_user(new_acl_user);
-        my_qsort(dynamic_element(&acl_users, 0, ACL_USER*), acl_users.elements,
-                 sizeof(ACL_USER),(qsort_cmp) acl_compare);
+        rebuild_acl_users();
 
         /* Rebuild 'acl_check_hosts' since 'acl_users' has been modified */
         rebuild_check_host();
@@ -5554,15 +5673,15 @@ static bool merge_role_global_privileges(ACL_ROLE *grantee)
   return old != grantee->access;
 }
 
-static int db_name_sort(ACL_DB * const *db1, ACL_DB * const *db2)
+static int db_name_sort(const int *db1, const int *db2)
 {
-  return strcmp((*db1)->db, (*db2)->db);
+  return strcmp(acl_dbs.at(*db1).db, acl_dbs.at(*db2).db);
 }
 
 /**
   update ACL_DB for given database and a given role with merged privileges
 
-  @param merged ACL_DB of the role in question (or NULL if it wasn't found)
+  @param merged ACL_DB of the role in question (or -1 if it wasn't found)
   @param first  first ACL_DB in an array for the database in question
   @param access new privileges for the given role on the gived database
   @param role   the name of the given role
@@ -5572,15 +5691,15 @@ static int db_name_sort(ACL_DB * const *db1, ACL_DB * const *db2)
           2 - ACL_DB was added
           4 - ACL_DB was deleted
 */
-static int update_role_db(ACL_DB *merged, ACL_DB **first, ulong access,
+static int update_role_db(int merged, int first, ulong access,
                           const char *role)
 {
-  if (!first)
+  if (first < 0)
     return 0;
 
   DBUG_EXECUTE_IF("role_merge_stats", role_db_merges++;);
 
-  if (merged == NULL)
+  if (merged < 0)
   {
     /*
       there's no ACL_DB for this role (all db grants come from granted roles)
@@ -5595,11 +5714,11 @@ static int update_role_db(ACL_DB *merged, ACL_DB **first, ulong access,
     acl_db.user= role;
     acl_db.host.hostname= const_cast<char*>("");
     acl_db.host.ip= acl_db.host.ip_mask= 0;
-    acl_db.db= first[0]->db;
+    acl_db.db= acl_dbs.at(first).db;
     acl_db.access= access;
     acl_db.initial_access= 0;
     acl_db.sort=get_sort(3, "", acl_db.db, role);
-    push_dynamic(&acl_dbs,(uchar*) &acl_db);
+    acl_dbs.push(acl_db);
     return 2;
   }
   else if (access == 0)
@@ -5615,13 +5734,13 @@ static int update_role_db(ACL_DB *merged, ACL_DB **first, ulong access,
       2. it's O(N) operation, and we may need many of them
       so we only mark elements deleted and will delete later.
     */
-    merged->sort= 0; // lower than any valid ACL_DB sort value, will be sorted last
+    acl_dbs.at(merged).sort= 0; // lower than any valid ACL_DB sort value, will be sorted last
     return 4;
   }
-  else if (merged->access != access)
+  else if (acl_dbs.at(merged).access != access)
   {
     /* this is easy */
-    merged->access= access;
+    acl_dbs.at(merged).access= access;
     return 1;
   }
   return 0;
@@ -5636,7 +5755,7 @@ static int update_role_db(ACL_DB *merged, ACL_DB **first, ulong access,
 static bool merge_role_db_privileges(ACL_ROLE *grantee, const char *dbname,
                                      role_hash_t *rhash)
 {
-  Dynamic_array<ACL_DB *> dbs; 
+  Dynamic_array<int> dbs;
 
   /*
     Supposedly acl_dbs can be huge, but only a handful of db grants
@@ -5644,9 +5763,9 @@ static bool merge_role_db_privileges(ACL_ROLE *grantee, const char *dbname,
 
     Collect these applicable db grants.
   */
-  for (uint i=0 ; i < acl_dbs.elements ; i++)
+  for (uint i=0 ; i < acl_dbs.elements() ; i++)
   {
-    ACL_DB *db= dynamic_element(&acl_dbs,i,ACL_DB*);
+    ACL_DB *db= &acl_dbs.at(i);
     if (db->host.hostname[0])
       continue;
     if (dbname && strcmp(db->db, dbname))
@@ -5654,7 +5773,7 @@ static bool merge_role_db_privileges(ACL_ROLE *grantee, const char *dbname,
     ACL_ROLE *r= rhash->find(db->user, strlen(db->user));
     if (!r)
       continue;
-    dbs.append(db);
+    dbs.append(i);
   }
   dbs.sort(db_name_sort);
 
@@ -5663,42 +5782,47 @@ static bool merge_role_db_privileges(ACL_ROLE *grantee, const char *dbname,
     (that should be merged) are sorted together. The grantee's ACL_DB element
     is not necessarily the first and may be not present at all.
   */
-  ACL_DB **first= NULL, *merged= NULL;
+  int first= -1, merged= -1;
   ulong access= 0, update_flags= 0;
-  for (ACL_DB **cur= dbs.front(); cur <= dbs.back(); cur++)
+  for (int *p= dbs.front(); p <= dbs.back(); p++)
   {
-    if (!first || (!dbname && strcmp(cur[0]->db, cur[-1]->db)))
+    if (first<0 || (!dbname && strcmp(acl_dbs.at(*p).db, acl_dbs.at(*p-1).db)))
     { // new db name series
       update_flags|= update_role_db(merged, first, access, grantee->user.str);
-      merged= NULL;
+      merged= -1;
       access= 0;
-      first= cur;
+      first= *p;
     }
-    if (strcmp(cur[0]->user, grantee->user.str) == 0)
-      access|= (merged= cur[0])->initial_access;
+    if (strcmp(acl_dbs.at(*p).user, grantee->user.str) == 0)
+      access|= acl_dbs.at(merged= *p).initial_access;
     else
-      access|= cur[0]->access;
+      access|= acl_dbs.at(*p).access;
   }
   update_flags|= update_role_db(merged, first, access, grantee->user.str);
 
-  /*
-    to make this code a bit simpler, we sort on deletes, to move
-    deleted elements to the end of the array. strictly speaking it's
-    unnecessary, it'd be faster to remove them in one O(N) array scan.
-    
-    on the other hand, qsort on almost sorted array is pretty fast anyway...
-  */
-  if (update_flags & (2|4))
-  { // inserted or deleted, need to sort
-    my_qsort((uchar*) dynamic_element(&acl_dbs,0,ACL_DB*),acl_dbs.elements,
-             sizeof(ACL_DB),(qsort_cmp) acl_compare);
-  }
   if (update_flags & 4)
-  { // deleted, trim the end
-    while (acl_dbs.elements &&
-           dynamic_element(&acl_dbs, acl_dbs.elements-1, ACL_DB*)->sort == 0)
-      acl_dbs.elements--;
+  {
+    // Remove elements marked for deletion.
+    uint count= 0;
+    for(uint i= 0; i < acl_dbs.elements(); i++)
+    {
+      ACL_DB *acl_db= &acl_dbs.at(i);
+      if (acl_db->sort)
+      {
+        if (i > count)
+          acl_dbs.set(count, *acl_db);
+        count++;
+      }
+    }
+    acl_dbs.elements(count);
   }
+
+
+  if (update_flags & 2)
+  { // inserted, need to sort
+    rebuild_acl_dbs();
+  }
+
   return update_flags;
 }
 
@@ -8645,16 +8769,14 @@ static bool show_database_privileges(THD *thd, const char *username,
                                      const char *hostname,
                                      char *buff, size_t buffsize)
 {
-  ACL_DB *acl_db;
   ulong want_access;
-  uint counter;
   Protocol *protocol= thd->protocol;
 
-  for (counter=0 ; counter < acl_dbs.elements ; counter++)
+  for (uint i=0 ; i < acl_dbs.elements() ; i++)
   {
     const char *user, *host;
 
-    acl_db=dynamic_element(&acl_dbs,counter,ACL_DB*);
+    ACL_DB *acl_db= &acl_dbs.at(i);
     user= acl_db->user;
     host=acl_db->host.hostname;
 
@@ -9409,7 +9531,7 @@ static int handle_grant_struct(enum enum_acl_lists struct_no, bool drop,
     elements= acl_users.elements;
     break;
   case DB_ACL:
-    elements= acl_dbs.elements;
+    elements= acl_dbs.elements();
     break;
   case COLUMN_PRIVILEGES_HASH:
     grant_name_hash= &column_priv_hash;
@@ -9461,7 +9583,7 @@ static int handle_grant_struct(enum enum_acl_lists struct_no, bool drop,
     break;
 
     case DB_ACL:
-      acl_db= dynamic_element(&acl_dbs, idx, ACL_DB*);
+      acl_db= &acl_dbs.at(idx);
       user= acl_db->user;
       host= acl_db->host.hostname;
       break;
@@ -9545,7 +9667,7 @@ static int handle_grant_struct(enum enum_acl_lists struct_no, bool drop,
         break;
 
       case DB_ACL:
-        delete_dynamic_element(&acl_dbs, idx);
+        acl_dbs.del(idx);
         break;
 
       case COLUMN_PRIVILEGES_HASH:
@@ -10245,6 +10367,8 @@ bool mysql_rename_user(THD *thd, List <LEX_USER> &list)
     some_users_renamed= TRUE;
   }
 
+  rebuild_acl_users();
+
   /* Rebuild 'acl_check_hosts' since 'acl_users' has been modified */
   rebuild_check_host();
 
@@ -10438,11 +10562,11 @@ bool mysql_revoke_all(THD *thd,  List <LEX_USER> &list)
      */
     do
     {
-      for (counter= 0, revoked= 0 ; counter < acl_dbs.elements ; )
+      for (counter= 0, revoked= 0 ; counter < acl_dbs.elements() ; )
       {
-	const char *user,*host;
+        const char *user, *host;
 
-	acl_db=dynamic_element(&acl_dbs,counter,ACL_DB*);
+        acl_db= &acl_dbs.at(counter);
 
         user= acl_db->user;
         host= safe_str(acl_db->host.hostname);
@@ -11045,6 +11169,14 @@ static int show_column_grants(THD *thd, SHOW_VAR *var, char *buff,
   return 0;
 }
 
+static int show_database_grants(THD *thd, SHOW_VAR *var, char *buff,
+                                enum enum_var_type scope)
+{
+  var->type= SHOW_UINT;
+  var->value= buff;
+  *(uint *)buff= acl_dbs.elements();
+  return 0;
+}
 
 #else
 bool check_grant(THD *, ulong, TABLE_LIST *, bool, uint, bool)
@@ -11056,7 +11188,7 @@ bool check_grant(THD *, ulong, TABLE_LIST *, bool, uint, bool)
 SHOW_VAR acl_statistics[] = {
 #ifndef NO_EMBEDDED_ACCESS_CHECKS
   {"column_grants",    (char*)show_column_grants,          SHOW_SIMPLE_FUNC},
-  {"database_grants",  (char*)&acl_dbs.elements,           SHOW_UINT},
+  {"database_grants",  (char*)show_database_grants,        SHOW_SIMPLE_FUNC},
   {"function_grants",  (char*)&func_priv_hash.records,     SHOW_ULONG},
   {"procedure_grants", (char*)&proc_priv_hash.records,     SHOW_ULONG},
   {"package_spec_grants", (char*)&package_spec_priv_hash.records, SHOW_ULONG},
@@ -11329,11 +11461,11 @@ int fill_schema_schema_privileges(THD *thd, TABLE_LIST *tables, COND *cond)
     DBUG_RETURN(0);
   mysql_mutex_lock(&acl_cache->lock);
 
-  for (counter=0 ; counter < acl_dbs.elements ; counter++)
+  for (counter=0 ; counter < acl_dbs.elements() ; counter++)
   {
     const char *user, *host, *is_grantable="YES";
 
-    acl_db=dynamic_element(&acl_dbs,counter,ACL_DB*);
+    acl_db=&acl_dbs.at(counter);
     user= acl_db->user;
     host= safe_str(acl_db->host.hostname);