r7828: Although there is still plenty to do, ldb_sqlite3 now passes the set of tests

in tests/test-sqlite3.sh (tests/test-generic.sh).

There are lots of optimizations still TBD, and some things are REALLY slow
right now (e.g. each add() operation takes 1/3 - 1/2 second) but it's ready for
interested parties to poke it and prod it and see how (un)reasonable it is.
Play away.

Still to be implemented or improved:
 - tdb specials (@MODULES, @SUBCLASSES, etc.)
 - all DNs are case-folded in their entirty right now (since doing otherwise
   would require @ATTRIBUTES to be implemented)
 - speed improvements and optimizations.  I am quite confident that the
   excessively slow add() operation can be much improved, and other areas
   can be somewhat improved.
(This used to be commit 1dd865005594671e7effe06fb088fa97fa08de0b)

1 files changed, 272 insertions, 95 deletions

diff --git a/source4/lib/ldb/ldb_sqlite3/schema b/source4/lib/ldb/ldb_sqlite3/schema
index c44351c543..08dc50de08 100644
--- a/source4/lib/ldb/ldb_sqlite3/schema
+++ b/source4/lib/ldb/ldb_sqlite3/schema
@@ -12,130 +12,160 @@
                   SELECT 'LDB' AS database_type, 
                          '1.0' AS version;
 
-                -- ------------------------------------------------------
-                -- Schema
-
                 /*
-                 * The entry table holds the information about an entry.  This
-                 * table is used to obtain the EID of the entry and to support
-                 * scope="one" and scope="base".  The parent and child table
-                 * is included in the entry table since all the other
-                 * attributes are dependent on EID.
+                 * Get the next USN value with:
+                 *   BEGIN EXCLUSIVE;
+                 *   UPDATE usn SET value = value + 1;
+                 *   SELECT value FROM usn;
+                 *   COMMIT;
                  */
-                CREATE TABLE ldb_entry
+                CREATE TABLE usn
                 (
-                  -- Unique identifier of this LDB entry
-                  eid                   INTEGER PRIMARY KEY,
-
-                  -- Unique identifier of the parent LDB entry
-                  peid                  INTEGER REFERENCES ldb_entry,
-
-                  -- Distinguished name of this entry
-                  dn                    TEXT,
-
-                  -- Time when the entry was created
-                  create_timestamp      INTEGER,
-
-                  -- Time when the entry was last modified
-                  modify_timestamp      INTEGER
+                  value           INTEGER
                 );
 
-
-                /*
-                 * The purpose of the descendant table is to support the
-                 * subtree search feature.  For each LDB entry with a unique
-                 * ID (AEID), this table contains the unique identifiers
-                 * (DEID) of the descendant entries.
-                 *
-                 * For evern entry in the directory, a row exists in this
-                 * table for each of its ancestors including itself.  The size
-                 * of the table depends on the depth of each entry.  In the
-                 * worst case, if all the entries were at the same depth, the
-                 * number of rows in the table is O(nm) where n is the number
-                 * of nodes in the directory and m is the depth of the tree.
-                 */
-                CREATE TABLE ldb_descendants
+                CREATE TABLE ldb_object
                 (
-                  -- The unique identifier of the ancestor LDB entry
-                  aeid                  INTEGER REFERENCES ldb_entry,
-
-                  -- The unique identifier of the descendant LDB entry
-                  deid                  INTEGER REFERENCES ldb_entry
-                );
-
-
-                CREATE TABLE ldb_object_classes
-                (
-                  -- Object classes are inserted into this table to track
-                  -- their class hierarchy.  'top' is the top-level class
-                  -- of which all other classes are subclasses.
-                  class_name            TEXT PRIMARY KEY,
-
-                  -- tree_key tracks the position of the class in
-                  -- the hierarchy 
-                  tree_key              TEXT UNIQUE
+                  /* tree_key is auto-generated by the insert trigger */
+                  tree_key        TEXT PRIMARY KEY,
+
+                  parent_tree_key TEXT,
+                  dn              TEXT,
+
+                  attr_name       TEXT REFERENCES ldb_attributes,
+                  attr_value      TEXT,
+
+                  /*
+                   * object_type can take on these values (to date):
+                   *   1: object is a node of a DN
+                   *   2: object is an attribute/value pair of its parent DN
+                   */
+                  object_type     INTEGER,
+
+                  /*
+                   * if object_type is 1, the node can have children.
+                   * this tracks the maximum previously assigned child
+                   * number so we can generate a new unique tree key for
+                   * a new child object.  note that this is always incremented,
+                   * so if children are deleted, this will not represent
+                   * the _number_ of children.
+                   */
+                  max_child_num   INTEGER,
+
+                  /*
+                   * Automatically maintained meta-data (a gift for metze)
+                   */
+                  object_guid     TEXT UNIQUE,
+                  timestamp       INTEGER,  -- originating_time
+                  invoke_id       TEXT,     -- GUID: originating_invocation_id
+                  usn             INTEGER,  -- hyper: originating_usn
+
+                  /* do not allow duplicate name/value pairs */
+                  UNIQUE (parent_tree_key, attr_name, attr_value, object_type)
                 );
 
-                /*
-                 * We keep a full listing of attribute/value pairs here
-                 */
-                CREATE TABLE ldb_attribute_values
+                CREATE TABLE ldb_attributes
                 (
-                  eid                   INTEGER REFERENCES ldb_entry,
-
-                  attr_name             TEXT, -- see ldb_attr_ATTRIBUTE_NAME
+                  attr_name             TEXT PRIMARY KEY,
+                  parent_tree_key       TEXT,
 
-                  attr_value            TEXT
-                );
+                  objectclass_p         BOOLEAN DEFAULT 0,
 
+                  case_insensitive_p    BOOLEAN DEFAULT 0,
+                  wildcard_p            BOOLEAN DEFAULT 0,
+                  hidden_p              BOOLEAN DEFAULT 0,
+                  integer_p             BOOLEAN DEFAULT 0,
 
-                /*
-                 * There is one attribute table per searchable attribute.
-                 */
-/*
-                CREATE TABLE ldb_attr_ATTRIBUTE_NAME
-                (
-                  -- The unique identifier of the LDB entry
-                  eid                   INTEGER REFERENCES ldb_entry,
-
-                  -- Normalized attribute value
-                  attr_value            TEXT
+                  /* tree_key is auto-generated by the insert trigger */
+                  tree_key              TEXT, -- null if not a object/sub class
+                                              -- level 1 if an objectclass
+                                              -- level 1-n if a subclass
+                  max_child_num         INTEGER
                 );
-*/
-
 
                 -- ------------------------------------------------------
-                -- Indexes
 
+                CREATE INDEX ldb_object_dn_idx
+                  ON ldb_object (dn);
+
+                CREATE INDEX ldb_attributes_tree_key_ids
+                  ON ldb_attributes (tree_key);
 
                 -- ------------------------------------------------------
-                -- Triggers
 
-                CREATE TRIGGER ldb_entry_insert_tr
+                /* Gifts for metze.  Automatically updated meta-data */
+                CREATE TRIGGER ldb_object_insert_tr
                   AFTER INSERT
-                  ON ldb_entry
+                  ON ldb_object
                   FOR EACH ROW
                     BEGIN
-                      UPDATE ldb_entry
-                        SET create_timestamp = strftime('%s', 'now'),
-                            modify_timestamp = strftime('%s', 'now')
-                        WHERE eid = new.eid;
+                      UPDATE ldb_object
+                        SET max_child_num = max_child_num + 1
+                        WHERE tree_key = new.parent_tree_key;
+                      UPDATE usn SET value = value + 1;
+                      UPDATE ldb_object
+                        SET tree_key =
+                              (SELECT
+                                 new.tree_key ||
+                                 base160(SELECT max_child_num
+                                           FROM ldb_object
+                                           WHERE tree_key =
+                                                 new.parent_tree_key));
+                            max_child_num = 0,
+                            object_guid = random_guid(),
+                            timestamp = strftime('%s', 'now'),
+                            usn = (SELECT value FROM usn);
+                        WHERE tree_key = new.tree_key;
                     END;
 
-                CREATE TRIGGER ldb_entry_update_tr
+                CREATE TRIGGER ldb_object_update_tr
                   AFTER UPDATE
-                  ON ldb_entry
+                  ON ldb_object
                   FOR EACH ROW
                     BEGIN
-                      UPDATE ldb_entry
-                        SET modify_timestamp = strftime('%s', 'now')
-                        WHERE eid = old.eid;
+                      UPDATE usn SET value = value + 1;
+                      UPDATE ldb_object
+                        SET timestamp = strftime('%s', 'now'),
+                            usn = (SELECT value FROM usn);
+                        WHERE tree_key = new.tree_key;
                     END;
 
+                CREATE TRIGGER ldb_attributes_insert_tr
+                  AFTER INSERT
+                  ON ldb_attributes
+                  FOR EACH ROW
+                    BEGIN
+                      UPDATE ldb_attributes
+                        SET max_child_num = max_child_num + 1
+                        WHERE tree_key = new.parent_tree_key;
+                      UPDATE ldb_attributes
+                        SET tree_key =
+                              (SELECT
+                                 new.tree_key ||
+                                 base160(SELECT max_child_num
+                                           FROM ldb_attributes
+                                           WHERE tree_key =
+                                                 new.parent_tree_key));
+                            max_child_num = 0
+                        WHERE tree_key = new.tree_key;
+                    END;
+
+
                 -- ------------------------------------------------------
-                -- Table initialization
 
-                /* We need an implicit 'top' level object class */
+                /* Initialize usn */
+                INSERT INTO usn (value) VALUES (0);
+
+                /* Create root object */
+                INSERT INTO ldb_object
+                    (tree_key, parent_tree_key,
+                     dn,
+                     object_type, max_child_num)
+                  VALUES ('', NULL,
+                          '',
+                          1, 0);
+
+                /* We need an implicit "top" level object class */
                 INSERT INTO ldb_attributes (attr_name,
                                             parent_tree_key)
                   SELECT 'top', '';
@@ -146,13 +176,58 @@
 
                 -- ------------------------------------------------------
 
-/*** TESTS ***/
-
 /*
  * dn: o=University of Michigan,c=US
  * objectclass: organization
  * objectclass: domainRelatedObject
  */
+-- newDN
+BEGIN;
+
+INSERT OR IGNORE INTO ldb_object
+    (parent_tree_key
+     dn,
+     attr_name, attr_value, object_type, max_child_num)
+  VALUES ('',
+          'c=US',
+          'c', 'US', 1, 0);
+
+INSERT INTO ldb_object
+    (parent_tree_key,
+     dn,
+     attr_name, attr_value, object_type, max_child_num)
+  VALUES ('0001',
+          'o=University of Michigan,c=US',
+          'o', 'University of Michigan', 1, 0);
+
+-- newObjectClass
+INSERT OR IGNORE INTO ldb_attributes
+    (attr_name, parent_tree_key, objectclass_p)
+  VALUES
+    ('objectclass', '', 1);
+
+INSERT INTO ldb_object
+    (parent_tree_key,
+     dn,
+     attr_name, attr_value, object_type, max_child_num)
+  VALUES ('00010001',
+          NULL,
+          'objectclass', 'organization', 2, 0);
+
+INSERT OR IGNORE INTO ldb_attributes
+    (attr_name, parent_tree_key, objectclass_p)
+  VALUES
+    ('objectclass', '', 1);
+
+INSERT INTO ldb_object
+    (parent_tree_key,
+     dn,
+     attr_name, attr_value, object_type, max_child_num)
+  VALUES ('00010001',
+          NULL,
+          'objectclass', 'domainRelatedObject', 2, 0);
+
+COMMIT;
 
 
 /*
@@ -164,6 +239,48 @@
  * seeAlso:
  * telephonenumber: +1 313 764-1817
  */
+-- addAttrValuePair
+BEGIN;
+
+INSERT INTO ldb_object
+    (parent_tree_key, dn,
+     attr_name, attr_value, object_type, max_child_num)
+  VALUES ('00010001', NULL,
+          'l', 'Ann Arbor, Michigan', 2, 0);
+
+INSERT INTO ldb_object
+    (parent_tree_key, dn,
+     attr_name, attr_value, object_type, max_child_num)
+  VALUES ('00010001', NULL,
+          'st', 'Michigan', 2, 0);
+
+INSERT INTO ldb_object
+    (parent_tree_key, dn,
+     attr_name, attr_value, object_type, max_child_num)
+  VALUES ('00010001', NULL,
+          'o', 'University of Michigan', 2, 0);
+
+INSERT INTO ldb_object
+    (parent_tree_key, dn,
+     attr_name, attr_value, object_type, max_child_num)
+  VALUES ('00010001', NULL,
+          'o', 'UMICH', 2, 0);
+
+INSERT INTO ldb_object
+    (parent_tree_key, dn,
+     attr_name, attr_value, object_type, max_child_num)
+  VALUES ('00010001', NULL,
+          'seeAlso', '', 2, 0);
+
+INSERT INTO ldb_object
+    (parent_tree_key, dn,
+     attr_name, attr_value, object_type, max_child_num)
+  VALUES ('00010001', NULL,
+          'telephonenumber', '+1 313 764-1817', 2, 0);
+
+COMMIT;
+
+-- ----------------------------------------------------------------------
 
 /*
  * dn: @ATTRIBUTES
@@ -172,6 +289,44 @@
  * ou: CASE_INSENSITIVE
  * dn: CASE_INSENSITIVE
  */
+-- newAttribute
+
+BEGIN;
+
+INSERT OR IGNORE INTO ldb_attributes
+    (attr_name, parent_tree_key, objectclass_p)
+  VALUES
+    ('uid', '', 0);
+
+UPDATE ldb_attributes
+  SET case_insensitive_p = 1,
+      wildcard_p = 1,
+      hidden_p = 0,
+      integer_p = 0
+  WHERE attr_name = 'uid'
+
+UPDATE ldb_attributes
+  SET case_insensitive_p = 1,
+      wildcard_p = 0,
+      hidden_p = 0,
+      integer_p = 0
+  WHERE attr_name = 'cn'
+
+UPDATE ldb_attributes
+  SET case_insensitive_p = 1,
+      wildcard_p = 0,
+      hidden_p = 0,
+      integer_p = 0
+  WHERE attr_name = 'ou'
+
+UPDATE ldb_attributes
+  SET case_insensitive_p = 1,
+      wildcard_p = 0,
+      hidden_p = 0,
+      integer_p = 0
+  WHERE attr_name = 'dn'
+
+-- ----------------------------------------------------------------------
 
 /*
  * dn: @SUBCLASSES
@@ -184,3 +339,25 @@
  * organizationalPerson: OpenLDAPperson
  * user: computer
  */
+-- insertSubclass
+
+/* NOT YET UPDATED!!! *
+
+
+INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key)
+  SELECT 'domain', /* next_tree_key('top') */ '00010001';
+INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key)
+  SELECT 'person', /* next_tree_key('top') */ '00010002';
+INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key)
+  SELECT 'domainDNS', /* next_tree_key('domain') */ '000100010001';
+INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key)
+  SELECT 'organizationalPerson', /* next_tree_key('person') */ '000100020001';
+INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key)
+  SELECT 'fooPerson', /* next_tree_key('person') */ '000100020002';
+INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key)
+  SELECT 'user', /* next_tree_key('organizationalPerson') */ '0001000200010001';
+INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key)
+  SELECT 'OpenLDAPperson', /* next_tree_key('organizationPerson') */ '0001000200010002';
+INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key)
+  SELECT 'computer', /* next_tree_key('user') */ '0001000200010001';
+