diff options
Diffstat (limited to 'storage')
54 files changed, 2318 insertions, 1386 deletions
diff --git a/storage/connect/ha_connect.cc b/storage/connect/ha_connect.cc index e79682d331b..d07b657389d 100644 --- a/storage/connect/ha_connect.cc +++ b/storage/connect/ha_connect.cc @@ -170,9 +170,9 @@ #define JSONMAX 10 // JSON Default max grp size extern "C" { - char version[]= "Version 1.06.0008 October 06, 2018"; + char version[]= "Version 1.06.0009 January 27, 2019"; #if defined(__WIN__) - char compver[]= "Version 1.06.0008 " __DATE__ " " __TIME__; + char compver[]= "Version 1.06.0009 " __DATE__ " " __TIME__; char slash= '\\'; #else // !__WIN__ char slash= '/'; @@ -204,6 +204,26 @@ pthread_mutex_t parmut; pthread_mutex_t usrmut; pthread_mutex_t tblmut; +#if defined(DEVELOPMENT) +char *GetUserVariable(PGLOBAL g, const uchar *varname); + +char *GetUserVariable(PGLOBAL g, const uchar *varname) +{ + char buf[1024]; + bool b; + THD *thd = current_thd; + CHARSET_INFO *cs = system_charset_info; + String *str = NULL, tmp(buf, sizeof(buf), cs); + HASH uvars = thd->user_vars; + user_var_entry *uvar = (user_var_entry*)my_hash_search(&uvars, varname, 0); + + if (uvar) + str = uvar->val_str(&b, &tmp, NOT_FIXED_DEC); + + return str ? PlugDup(g, str->ptr()) : NULL; +}; // end of GetUserVariable +#endif // DEVELOPMENT + /***********************************************************************/ /* Utility functions. */ /***********************************************************************/ @@ -1793,7 +1813,9 @@ PCSZ ha_connect::GetDBName(PCSZ name) const char *ha_connect::GetTableName(void) { - return tshp ? tshp->table_name.str : table_share->table_name.str; + const char *path= tshp ? tshp->path.str : table_share->path.str; + const char *name= strrchr(path, '/'); + return name ? name+1 : path; } // end of GetTableName char *ha_connect::GetPartName(void) @@ -1912,9 +1934,11 @@ int ha_connect::OpenTable(PGLOBAL g, bool del) break; } // endswitch xmode - if (xmod != MODE_INSERT || tdbp->GetAmType() == TYPE_AM_MYSQL - || tdbp->GetAmType() == TYPE_AM_ODBC - || tdbp->GetAmType() == TYPE_AM_JDBC) { + // g->More is 1 when executing commands from triggers + if (!g->More && (xmod != MODE_INSERT + || tdbp->GetAmType() == TYPE_AM_MYSQL + || tdbp->GetAmType() == TYPE_AM_ODBC + || tdbp->GetAmType() == TYPE_AM_JDBC)) { // Get the list of used fields (columns) char *p; unsigned int k1, k2, n1, n2; @@ -4629,7 +4653,9 @@ MODE ha_connect::CheckMode(PGLOBAL g, THD *thd, break; case SQLCOM_CREATE_VIEW: case SQLCOM_DROP_VIEW: - newmode= MODE_ANY; + case SQLCOM_CREATE_TRIGGER: + case SQLCOM_DROP_TRIGGER: + newmode= MODE_ANY; break; case SQLCOM_ALTER_TABLE: *chk= true; @@ -4672,6 +4698,9 @@ int ha_connect::start_stmt(THD *thd, thr_lock_type lock_type) PGLOBAL g= GetPlug(thd, xp); DBUG_ENTER("ha_connect::start_stmt"); + if (table->triggers) + g->More= 1; // We don't know which columns are used by the trigger + if (check_privileges(thd, GetTableOptionStruct(), table->s->db.str, true)) DBUG_RETURN(HA_ERR_INTERNAL_ERROR); @@ -7310,7 +7339,7 @@ maria_declare_plugin(connect) 0x0106, /* version number (1.06) */ NULL, /* status variables */ connect_system_variables, /* system variables */ - "1.06.0008", /* string version */ + "1.06.0009", /* string version */ MariaDB_PLUGIN_MATURITY_STABLE /* maturity */ } maria_declare_plugin_end; diff --git a/storage/connect/jsonudf.cpp b/storage/connect/jsonudf.cpp index 07a67e37379..d521322edb6 100644 --- a/storage/connect/jsonudf.cpp +++ b/storage/connect/jsonudf.cpp @@ -1667,7 +1667,7 @@ static PCSZ MakeKey(PGLOBAL g, UDF_ARGS *args, int i) int j = 0, n = args->attribute_lengths[i]; my_bool b; // true if attribute is zero terminated PSZ p; - const char *s = args->attributes[i]; + PCSZ s = args->attributes[i]; if (s && *s && (n || *s == '\'')) { if ((b = (!n || !s[n]))) @@ -5806,6 +5806,52 @@ char *envar(UDF_INIT *initid, UDF_ARGS *args, char *result, return str; } // end of envar +#if defined(DEVELOPMENT) +extern char *GetUserVariable(PGLOBAL g, const uchar *varname); + +/*********************************************************************************/ +/* Utility function returning a user variable value. */ +/*********************************************************************************/ +my_bool uvar_init(UDF_INIT *initid, UDF_ARGS *args, char *message) +{ + unsigned long reslen, memlen; + + if (args->arg_count != 1) { + strcpy(message, "Unique argument must be a user variable name"); + return true; + } else + CalcLen(args, false, reslen, memlen, true); + + initid->maybe_null = true; + return JsonInit(initid, args, message, true, reslen, memlen, 2048); +} // end of uvar_init + +char *uvar(UDF_INIT *initid, UDF_ARGS *args, char *result, + unsigned long *res_length, char *is_null, char *) +{ + char *str, varname[256]; + PGLOBAL g = (PGLOBAL)initid->ptr; + int n = MY_MIN(args->lengths[0], sizeof(varname) - 1); + + PlugSubSet(g->Sarea, g->Sarea_Size); + memcpy(varname, args->args[0], n); + varname[n] = 0; + + if (!(str = GetUserVariable(g, (const uchar*)&varname))) { + *res_length = 0; + *is_null = 1; + } else + *res_length = strlen(str); + + return str; +} // end of uvar + +void uvar_deinit(UDF_INIT* initid) +{ + JsonFreeMem((PGLOBAL)initid->ptr); +} // end of uvar_deinit +#endif // DEVELOPMENT + /*********************************************************************************/ /* Returns the distinct number of B occurences in A. */ /*********************************************************************************/ diff --git a/storage/connect/jsonudf.h b/storage/connect/jsonudf.h index 23e8c0e1aed..ee56869a111 100644 --- a/storage/connect/jsonudf.h +++ b/storage/connect/jsonudf.h @@ -238,6 +238,11 @@ extern "C" { DllExport my_bool envar_init(UDF_INIT*, UDF_ARGS*, char*); DllExport char *envar(UDF_EXEC_ARGS); +#if defined(DEVELOPMENT) + DllExport my_bool uvar_init(UDF_INIT*, UDF_ARGS*, char*); + DllExport char *uvar(UDF_EXEC_ARGS); +#endif // DEVELOPMENT + DllExport my_bool countin_init(UDF_INIT*, UDF_ARGS*, char*); DllExport long long countin(UDF_EXEC_ARGS); } // extern "C" diff --git a/storage/connect/mysql-test/connect/r/jdbc_postgresql.result b/storage/connect/mysql-test/connect/r/jdbc_postgresql.result index 07cc3c465ea..bec1dc8725b 100644 --- a/storage/connect/mysql-test/connect/r/jdbc_postgresql.result +++ b/storage/connect/mysql-test/connect/r/jdbc_postgresql.result @@ -1,4 +1,4 @@ -SET GLOBAL connect_class_path='C:/MariaDB-10.2/MariaDB/storage/connect/mysql-test/connect/std_data/JavaWrappers.jar;C:/Jconnectors/postgresql-42.2.1.jar'; +SET GLOBAL connect_class_path='C:/MariaDB-10.0/MariaDB/storage/connect/mysql-test/connect/std_data/JavaWrappers.jar;C:/Jconnectors/postgresql-42.2.1.jar'; CREATE TABLE t2 ( command varchar(128) not null, number int(5) not null flag=1, diff --git a/storage/connect/mysql-test/connect/r/part_table.result b/storage/connect/mysql-test/connect/r/part_table.result index f3a556ae784..ee17a1d32b9 100644 --- a/storage/connect/mysql-test/connect/r/part_table.result +++ b/storage/connect/mysql-test/connect/r/part_table.result @@ -23,7 +23,7 @@ id msg CREATE TABLE xt3 ( id INT KEY NOT NULL, msg VARCHAR(32)) -ENGINE=CONNECT TABLE_TYPE=CSV AVG_ROW_LENGTH=10; +ENGINE=CONNECT TABLE_TYPE=CSV AVG_ROW_LENGTH=6; Warnings: Warning 1105 No file name. Table will use xt3.csv INSERT INTO xt3 VALUES(60,'sixty'),(81,'eighty one'),(72,'seventy two'); @@ -92,7 +92,7 @@ id msg EXPLAIN PARTITIONS SELECT * FROM t1 WHERE id = 81; id select_type table partitions type possible_keys key key_len ref rows Extra -1 SIMPLE t1 3 ALL NULL NULL NULL NULL 4 Using where +1 SIMPLE t1 3 ALL NULL NULL NULL NULL 6 Using where DELETE FROM t1; Warnings: Note 1105 xt1: 4 affected rows diff --git a/storage/connect/mysql-test/connect/t/part_table.test b/storage/connect/mysql-test/connect/t/part_table.test index 5edd5766bd6..0fb2a11f0f9 100644 --- a/storage/connect/mysql-test/connect/t/part_table.test +++ b/storage/connect/mysql-test/connect/t/part_table.test @@ -22,7 +22,7 @@ SELECT * FROM xt2; CREATE TABLE xt3 ( id INT KEY NOT NULL, msg VARCHAR(32)) -ENGINE=CONNECT TABLE_TYPE=CSV AVG_ROW_LENGTH=10; +ENGINE=CONNECT TABLE_TYPE=CSV AVG_ROW_LENGTH=6; INSERT INTO xt3 VALUES(60,'sixty'),(81,'eighty one'),(72,'seventy two'); SELECT * FROM xt3; diff --git a/storage/connect/tabext.cpp b/storage/connect/tabext.cpp index f2d5eb0e69d..e9c7b2490d8 100644 --- a/storage/connect/tabext.cpp +++ b/storage/connect/tabext.cpp @@ -1,7 +1,7 @@ /************* Tabext C++ Functions Source Code File (.CPP) ************/ -/* Name: TABEXT.CPP Version 1.0 */ +/* Name: TABEXT.CPP Version 1.1 */ /* */ -/* (C) Copyright to the author Olivier BERTRAND 2017 */ +/* (C) Copyright to the author Olivier BERTRAND 2017 - 2019 */ /* */ /* This file contains the TBX, TDB and OPJOIN classes functions. */ /***********************************************************************/ @@ -446,6 +446,43 @@ bool TDBEXT::MakeSQL(PGLOBAL g, bool cnt) } // end of MakeSQL /***********************************************************************/ +/* Remove the NAME_CONST functions that are added by procedures. */ +/***********************************************************************/ +void TDBEXT::RemoveConst(PGLOBAL g, char *stmt) +{ + char *p, *p2; + char val[1025], nval[1025]; + int n, nc; + + while ((p = strstr(stmt, "NAME_CONST"))) + if ((n = sscanf(p, "%*[^,],%1024[^)])%n", val, &nc))) { + if (trace(33)) + htrc("p=%s\nn=%d val=%s nc=%d\n", p, n, val, nc); + + *p = 0; + + if ((p2 = strstr(val, "'"))) { + if ((n = sscanf(p2, "%*['\\]%1024[^'\\]", nval))) { + if (trace(33)) + htrc("p2=%s\nn=%d nval=%s\n", p2, n, nval); + + strcat(strcat(strcat(strcat(stmt, "'"), nval), "'"), p + nc); + } else + break; + + } else + strcat(strcat(strcat(strcat(stmt, "("), val), ")"), p + nc); + + if (trace(33)) + htrc("stmt=%s\n", stmt); + + } else + break; + + return; +} // end of RemoveConst + +/***********************************************************************/ /* MakeCommand: make the Update or Delete statement to send to the */ /* MySQL server. Limited to remote values and filtering. */ /***********************************************************************/ @@ -524,6 +561,8 @@ bool TDBEXT::MakeCommand(PGLOBAL g) stmt[i++] = (Qrystr[k] == '`') ? q : Qrystr[k]; } while (Qrystr[k++]); + RemoveConst(g, stmt); + if (body) strcat(stmt, body); diff --git a/storage/connect/tabext.h b/storage/connect/tabext.h index 6b67c2ab5ed..5fef1b9ece0 100644 --- a/storage/connect/tabext.h +++ b/storage/connect/tabext.h @@ -1,7 +1,7 @@ /*************** Tabext H Declares Source Code File (.H) ***************/ -/* Name: TABEXT.H Version 1.0 */ +/* Name: TABEXT.H Version 1.1 */ /* */ -/* (C) Copyright to the author Olivier BERTRAND 2017 */ +/* (C) Copyright to the author Olivier BERTRAND 2017 - 2019 */ /* */ /* This is the EXTDEF, TABEXT and EXTCOL classes definitions. */ /***********************************************************************/ @@ -130,6 +130,7 @@ protected: virtual bool MakeSQL(PGLOBAL g, bool cnt); //virtual bool MakeInsert(PGLOBAL g); virtual bool MakeCommand(PGLOBAL g); + void RemoveConst(PGLOBAL g, char *stmt); int Decode(PCSZ utf, char *buf, size_t n); // Members diff --git a/storage/connect/tabjdbc.cpp b/storage/connect/tabjdbc.cpp index adb3fc4fb51..789daff6fcd 100644 --- a/storage/connect/tabjdbc.cpp +++ b/storage/connect/tabjdbc.cpp @@ -1,11 +1,11 @@ /************* TabJDBC C++ Program Source Code File (.CPP) *************/ /* PROGRAM NAME: TABJDBC */ /* ------------- */ -/* Version 1.2 */ +/* Version 1.3 */ /* */ /* COPYRIGHT: */ /* ---------- */ -/* (C) Copyright to the author Olivier BERTRAND 2016-2017 */ +/* (C) Copyright to the author Olivier BERTRAND 2016-2019 */ /* */ /* WHAT THIS PROGRAM DOES: */ /* ----------------------- */ @@ -72,7 +72,6 @@ #include "tabext.h" #include "tabjdbc.h" #include "tabmul.h" -//#include "reldef.h" #include "tabcol.h" #include "valblk.h" #include "ha_connect.h" @@ -89,6 +88,9 @@ extern int num_read, num_there, num_eq[2]; // Statistics /* External function. */ /***********************************************************************/ bool ExactInfo(void); +#if defined(DEVELOPMENT) +extern char *GetUserVariable(PGLOBAL g, const uchar *varname); +#endif // DEVELOPMENT /* -------------------------- Class JDBCDEF -------------------------- */ @@ -147,10 +149,6 @@ int JDBCDEF::ParseURL(PGLOBAL g, char *url, bool b) return RC_FX; Tabname = p; -// } else if (b) { -// // Otherwise, straight server name, -// Tabname = GetStringCatInfo(g, "Name", NULL); -// Tabname = GetStringCatInfo(g, "Tabname", Tabname); } // endif if (trace(1)) @@ -165,6 +163,11 @@ int JDBCDEF::ParseURL(PGLOBAL g, char *url, bool b) return RC_FX; } // endif server +#if defined(DEVELOPMENT) + if (*server->host == '@') { + Url = GetUserVariable(g, (const uchar*)&server->host[1]); + } else +#endif // 0 if (strncmp(server->host, "jdbc:", 5)) { // Now make the required URL Url = (PSZ)PlugSubAlloc(g, NULL, 0); @@ -185,12 +188,15 @@ int JDBCDEF::ParseURL(PGLOBAL g, char *url, bool b) } else // host is a URL Url = PlugDup(g, server->host); - if (server->username) + if (!Username && server->username) Username = PlugDup(g, server->username); - if (server->password) + if (!Password && server->password) Password = PlugDup(g, server->password); + Driver = PlugDup(g, GetListOption(g, "Driver", server->owner, NULL)); + Wrapname = PlugDup(g, GetListOption(g, "Wrapper", server->owner, NULL)); + Memory = atoi(GetListOption(g, "Memory", server->owner, "0")); return RC_NF; } // endif @@ -208,7 +214,6 @@ bool JDBCDEF::DefineAM(PGLOBAL g, LPCSTR am, int poff) if (EXTDEF::DefineAM(g, am, poff)) return true; - Driver = GetStringCatInfo(g, "Driver", NULL); Desc = Url = GetStringCatInfo(g, "Connect", NULL); if (!Url && !Catfunc) { @@ -228,7 +233,10 @@ bool JDBCDEF::DefineAM(PGLOBAL g, LPCSTR am, int poff) return true; } // endif rc - Wrapname = GetStringCatInfo(g, "Wrapper", NULL); + // Default values may have been set in ParseURL + Memory = GetIntCatInfo("Memory", Memory); + Driver = GetStringCatInfo(g, "Driver", Driver); + Wrapname = GetStringCatInfo(g, "Wrapper", Wrapname); return false; } // end of DefineAM @@ -558,33 +566,42 @@ bool TDBJDBC::OpenDB(PGLOBAL g) this, Tdb_No, Use, Mode); if (Use == USE_OPEN) { - /*******************************************************************/ - /* Table already open, just replace it at its beginning. */ - /*******************************************************************/ - if (Memory == 1) { - if ((Qrp = Jcp->AllocateResult(g, this))) - Memory = 2; // Must be filled - else - Memory = 0; // Allocation failed, don't use it - - } else if (Memory == 2) - Memory = 3; // Ok to use memory result - - if (Memory < 3) { - // Method will depend on cursor type - if ((Rbuf = Query ? Jcp->Rewind(Query->GetStr()) : 0) < 0) - if (Mode != MODE_READX) { - Jcp->Close(); - return true; - } else - Rbuf = 0; + if (Mode == MODE_READ || Mode == MODE_READX) { + /*****************************************************************/ + /* Table already open, just replace it at its beginning. */ + /*****************************************************************/ + if (Memory == 1) { + if ((Qrp = Jcp->AllocateResult(g, this))) + Memory = 2; // Must be filled + else + Memory = 0; // Allocation failed, don't use it - } else - Rbuf = Qrp->Nblin; + } else if (Memory == 2) + Memory = 3; // Ok to use memory result + + if (Memory < 3) { + // Method will depend on cursor type + if ((Rbuf = Query ? Jcp->Rewind(Query->GetStr()) : 0) < 0) + if (Mode != MODE_READX) { + Jcp->Close(); + return true; + } else + Rbuf = 0; + + } else + Rbuf = Qrp->Nblin; + + CurNum = 0; + Fpos = 0; + Curpos = 1; + } else if (Mode == MODE_UPDATE || Mode == MODE_DELETE) { + // new update coming from a trigger or procedure + Query = NULL; + SetCondFil(NULL); + Qrystr = To_Def->GetStringCatInfo(g, "Query_String", "?"); + } else { //if (Mode == MODE_INSERT) + } // endif Mode - CurNum = 0; - Fpos = 0; - Curpos = 1; return false; } // endif use diff --git a/storage/connect/tabjson.cpp b/storage/connect/tabjson.cpp index d20e793ff88..afab52aa282 100644 --- a/storage/connect/tabjson.cpp +++ b/storage/connect/tabjson.cpp @@ -1,6 +1,6 @@ /************* tabjson C++ Program Source Code File (.CPP) *************/ -/* PROGRAM NAME: tabjson Version 1.5 */ -/* (C) Copyright to the author Olivier BERTRAND 2014 - 2017 */ +/* PROGRAM NAME: tabjson Version 1.7 */ +/* (C) Copyright to the author Olivier BERTRAND 2014 - 2019 */ /* This program are the JSON class DB execution routines. */ /***********************************************************************/ @@ -110,8 +110,8 @@ PQRYRES JSONColumns(PGLOBAL g, PCSZ db, PCSZ dsn, PTOS topt, bool info) buftyp, fldtyp, length, false, false); crp = qrp->Colresp->Next->Next->Next->Next->Next->Next; - crp->Name = "Nullable"; - crp->Next->Name = "Jpath"; + crp->Name = PlugDup(g, "Nullable"); + crp->Next->Name = PlugDup(g, "Jpath"); if (info || !qrp) return qrp; @@ -173,6 +173,7 @@ JSONDISC::JSONDISC(PGLOBAL g, uint *lg) int JSONDISC::GetColumns(PGLOBAL g, PCSZ db, PCSZ dsn, PTOS topt) { + char filename[_MAX_PATH]; bool mgo = (GetTypeID(topt->type) == TAB_MONGO); PCSZ level = GetStringTableOption(g, topt, "Level", NULL); @@ -209,6 +210,12 @@ int JSONDISC::GetColumns(PGLOBAL g, PCSZ db, PCSZ dsn, PTOS topt) return 0; } // endif Fn + if (tdp->Fn) { + // We used the file name relative to recorded datapath + PlugSetPath(filename, tdp->Fn, tdp->GetPath()); + tdp->Fn = PlugDup(g, filename); + } // endif Fn + if (trace(1)) htrc("File %s objname=%s pretty=%d lvl=%d\n", tdp->Fn, tdp->Objname, tdp->Pretty, lvl); @@ -342,7 +349,7 @@ int JSONDISC::GetColumns(PGLOBAL g, PCSZ db, PCSZ dsn, PTOS topt) strncpy(colname, jpp->GetKey(), 64); fmt[bf] = 0; - if (Find(g, jpp->GetVal(), MY_MIN(lvl, 0))) + if (Find(g, jpp->GetVal(), colname, MY_MIN(lvl, 0))) goto err; } // endfor jpp @@ -385,7 +392,7 @@ err: return 0; } // end of GetColumns -bool JSONDISC::Find(PGLOBAL g, PJVAL jvp, int j) +bool JSONDISC::Find(PGLOBAL g, PJVAL jvp, PCSZ key, int j) { char *p, *pc = colname + strlen(colname); int ars; @@ -413,12 +420,14 @@ bool JSONDISC::Find(PGLOBAL g, PJVAL jvp, int j) job = (PJOB)jsp; for (PJPR jrp = job->GetFirst(); jrp; jrp = jrp->GetNext()) { - if (*jrp->GetKey() != '$') { - strncat(strncat(fmt, sep, 128), jrp->GetKey(), 128); - strncat(strncat(colname, "_", 64), jrp->GetKey(), 64); + PCSZ k = jrp->GetKey(); + + if (*k != '$') { + strncat(strncat(fmt, sep, 128), k, 128); + strncat(strncat(colname, "_", 64), k, 64); } // endif Key - if (Find(g, jrp->GetVal(), j + 1)) + if (Find(g, jrp->GetVal(), k, j + 1)) return true; *p = *pc = 0; @@ -428,13 +437,13 @@ bool JSONDISC::Find(PGLOBAL g, PJVAL jvp, int j) case TYPE_JAR: jar = (PJAR)jsp; - if (all || (tdp->Xcol && !stricmp(tdp->Xcol, colname))) + if (all || (tdp->Xcol && !stricmp(tdp->Xcol, key))) ars = jar->GetSize(false); else ars = MY_MIN(jar->GetSize(false), 1); for (int k = 0; k < ars; k++) { - if (!tdp->Xcol || stricmp(tdp->Xcol, colname)) { + if (!tdp->Xcol || stricmp(tdp->Xcol, key)) { sprintf(buf, "%d", k); if (tdp->Uri) @@ -448,7 +457,7 @@ bool JSONDISC::Find(PGLOBAL g, PJVAL jvp, int j) } else strncat(fmt, (tdp->Uri ? sep : "[*]"), 128); - if (Find(g, jar->GetValue(k), j)) + if (Find(g, jar->GetValue(k), "", j)) return true; *p = *pc = 0; @@ -522,7 +531,9 @@ void JSONDISC::AddColumn(PGLOBAL g) n++; } // endif jcp - pjcp = jcp; + if (jcp) + pjcp = jcp; + } // end of AddColumn @@ -549,7 +560,7 @@ JSONDEF::JSONDEF(void) /***********************************************************************/ /* DefineAM: define specific AM block values. */ /***********************************************************************/ -bool JSONDEF::DefineAM(PGLOBAL g, LPCSTR, int poff) +bool JSONDEF::DefineAM(PGLOBAL g, LPCSTR am, int poff) { Schema = GetStringCatInfo(g, "DBname", Schema); Jmode = (JMODE)GetIntCatInfo("Jmode", MODE_OBJECT); @@ -561,7 +572,8 @@ bool JSONDEF::DefineAM(PGLOBAL g, LPCSTR, int poff) Sep = *GetStringCatInfo(g, "Separator", "."); Accept = GetBoolCatInfo("Accept", false); - if (Uri = GetStringCatInfo(g, "Connect", NULL)) { + // Don't use url as uri when called from REST OEM module + if (stricmp(am, "REST") && (Uri = GetStringCatInfo(g, "Connect", NULL))) { #if defined(JAVA_SUPPORT) || defined(CMGO_SUPPORT) Collname = GetStringCatInfo(g, "Name", (Catfunc & (FNC_TABLE | FNC_COL)) ? NULL : Name); @@ -2340,7 +2352,7 @@ void TDBJSON::CloseDB(PGLOBAL g) TDBJCL::TDBJCL(PJDEF tdp) : TDBCAT(tdp) { Topt = tdp->GetTopt(); - Db = tdp->Schema; + Db = tdp->Schema; Dsn = tdp->Uri; } // end of TDBJCL constructor diff --git a/storage/connect/tabjson.h b/storage/connect/tabjson.h index fcbfe4ed1ec..8721a2a5ab7 100644 --- a/storage/connect/tabjson.h +++ b/storage/connect/tabjson.h @@ -52,7 +52,7 @@ public: // Functions int GetColumns(PGLOBAL g, PCSZ db, PCSZ dsn, PTOS topt); - bool Find(PGLOBAL g, PJVAL jvp, int j); + bool Find(PGLOBAL g, PJVAL jvp, PCSZ key, int j); void AddColumn(PGLOBAL g); // Members diff --git a/storage/connect/tabxml.cpp b/storage/connect/tabxml.cpp index 573339bce35..19490d350e8 100644 --- a/storage/connect/tabxml.cpp +++ b/storage/connect/tabxml.cpp @@ -163,8 +163,11 @@ PQRYRES XMLColumns(PGLOBAL g, char *db, char *tab, PTOS topt, bool info) return NULL; tdp->Tabname = tab; + tdp->Tabname = (char*)GetStringTableOption(g, topt, "Tabname", tab); + tdp->Rowname = (char*)GetStringTableOption(g, topt, "Rownode", NULL); tdp->Zipped = GetBooleanTableOption(g, topt, "Zipped", false); tdp->Entry = GetStringTableOption(g, topt, "Entry", NULL); + tdp->Skip = GetBooleanTableOption(g, topt, "Skipnull", false); if (!(op = GetStringTableOption(g, topt, "Xmlsup", NULL))) #if defined(__WIN__) @@ -280,7 +283,9 @@ PQRYRES XMLColumns(PGLOBAL g, char *db, char *tab, PTOS topt, bool info) if (!vp->atp) node = vp->nl->GetItem(g, vp->k++, tdp->Usedom ? node : NULL); - strncat(fmt, colname, XLEN(fmt)); + if (!j) + strncat(fmt, colname, XLEN(fmt)); + strncat(fmt, "/", XLEN(fmt)); strncat(xcol->Name, "_", XLEN(xcol->Name)); j++; @@ -302,6 +307,7 @@ PQRYRES XMLColumns(PGLOBAL g, char *db, char *tab, PTOS topt, bool info) case RC_INFO: PushWarning(g, txmp); case RC_OK: + xcol->Cbn = !strlen(buf); break; default: goto err; @@ -327,9 +333,9 @@ PQRYRES XMLColumns(PGLOBAL g, char *db, char *tab, PTOS topt, bool info) xcp->Len = MY_MAX(xcp->Len, xcol->Len); xcp->Scale = MY_MAX(xcp->Scale, xcol->Scale); - xcp->Cbn |= xcol->Cbn; + xcp->Cbn |= (xcol->Cbn || !xcol->Len); xcp->Found = true; - } else { + } else if(xcol->Len || !tdp->Skip) { // New column xcp = new(g) XMCOL(g, xcol, fmt, i); length[0] = MY_MAX(length[0], strlen(xcol->Name)); @@ -344,7 +350,8 @@ PQRYRES XMLColumns(PGLOBAL g, char *db, char *tab, PTOS topt, bool info) n++; } // endif xcp - pxcp = xcp; + if (xcp) + pxcp = xcp; if (vp->atp) vp->atp = vp->atp->GetNext(g); @@ -445,6 +452,7 @@ XMLDEF::XMLDEF(void) Usedom = false; Zipped = false; Mulentries = false; + Skip = false; } // end of XMLDEF constructor /***********************************************************************/ @@ -814,127 +822,141 @@ bool TDBXML::Initialize(PGLOBAL g) } // endif Bufdone #if !defined(UNIX) - if (!Root) try { + if (!Root) try { #else - if (!Root) { + if (!Root) { #endif - char tabpath[64], filename[_MAX_PATH]; - - // We used the file name relative to recorded datapath - PlugSetPath(filename, Xfile, GetPath()); - - // Load or re-use the table file - rc = LoadTableFile(g, filename); - - if (rc == RC_OK) { - // Get root node - if (!(Root = Docp->GetRoot(g))) { - // This should never happen as load should have failed - strcpy(g->Message, MSG(EMPTY_DOC)); - goto error; - } // endif Root - - // If tabname is not an Xpath, - // construct one that will find it anywhere - if (!strchr(Tabname, '/')) - strcat(strcpy(tabpath, "//"), Tabname); - else - strcpy(tabpath, Tabname); - - // Evaluate table xpath - if ((TabNode = Root->SelectSingleNode(g, tabpath))) { - if (TabNode->GetType() != XML_ELEMENT_NODE) { - sprintf(g->Message, MSG(BAD_NODE_TYPE), TabNode->GetType()); - goto error; - } // endif Type - - } else if (Mode == MODE_INSERT && XmlDB) { - // We are adding a new table to a multi-table file - - // If XmlDB is not an Xpath, - // construct one that will find it anywhere - if (!strchr(XmlDB, '/')) - strcat(strcpy(tabpath, "//"), XmlDB); - else - strcpy(tabpath, XmlDB); - - if (!(DBnode = Root->SelectSingleNode(g, tabpath))) { - // DB node does not exist yet; we cannot create it - // because we don't know where it should be placed - sprintf(g->Message, MSG(MISSING_NODE), XmlDB, Xfile); - goto error; - } // endif DBnode - - if (!(TabNode = DBnode->AddChildNode(g, Tabname))) { - sprintf(g->Message, MSG(FAIL_ADD_NODE), Tabname); - goto error; - } // endif TabNode - - DBnode->AddText(g, "\n"); - } else - TabNode = Root; // Try this ? - - } else if (rc == RC_NF || rc == RC_EF) { - // The XML file does not exist or is void - if (Mode == MODE_INSERT) { - // New Document - char buf[64]; - - // Create the XML node - if (Docp->NewDoc(g, "1.0")) { - strcpy(g->Message, MSG(NEW_DOC_FAILED)); - goto error; - } // endif NewDoc - - // Now we can link the Xblock - To_Xb = Docp->LinkXblock(g, Mode, rc, filename); - - // Add a CONNECT comment node - strcpy(buf, " Created by the MariaDB CONNECT Storage Engine"); - Docp->AddComment(g, buf); - - if (XmlDB) { - // This is a multi-table file - DBnode = Root = Docp->NewRoot(g, XmlDB); - DBnode->AddText(g, "\n"); - TabNode = DBnode->AddChildNode(g, Tabname); - DBnode->AddText(g, "\n"); - } else - TabNode = Root = Docp->NewRoot(g, Tabname); - - if (TabNode == NULL || Root == NULL) { - strcpy(g->Message, MSG(XML_INIT_ERROR)); - goto error; - } else if (SetTabNode(g)) - goto error; - - } else { - sprintf(g->Message, MSG(FILE_UNFOUND), Xfile); - - if (Mode == MODE_READ) { - PushWarning(g, this); - Void = true; - } // endif Mode - - goto error; - } // endif Mode - - } else if (rc == RC_INFO) { - // Loading failed - sprintf(g->Message, MSG(LOADING_FAILED), Xfile); - goto error; - } else // (rc == RC_FX) - goto error; - - // Get row node list - if (Rowname) - Nlist = TabNode->SelectNodes(g, Rowname); - else - Nlist = TabNode->GetChildElements(g); - - Docp->SetNofree(true); // For libxml2 + char tabpath[64], filename[_MAX_PATH]; + + // We used the file name relative to recorded datapath + PlugSetPath(filename, Xfile, GetPath()); + + // Load or re-use the table file + rc = LoadTableFile(g, filename); + + if (rc == RC_OK) { + // Get root node + if (!(Root = Docp->GetRoot(g))) { + // This should never happen as load should have failed + strcpy(g->Message, MSG(EMPTY_DOC)); + goto error; + } // endif Root + + // If tabname is not an Xpath, + // construct one that will find it anywhere + if (!strchr(Tabname, '/')) + strcat(strcpy(tabpath, "//"), Tabname); + else + strcpy(tabpath, Tabname); + + // Evaluate table xpath + if ((TabNode = Root->SelectSingleNode(g, tabpath))) { + if (TabNode->GetType() != XML_ELEMENT_NODE) { + sprintf(g->Message, MSG(BAD_NODE_TYPE), TabNode->GetType()); + goto error; + } // endif Type + + } else if (Mode == MODE_INSERT && XmlDB) { + // We are adding a new table to a multi-table file + + // If XmlDB is not an Xpath, + // construct one that will find it anywhere + if (!strchr(XmlDB, '/')) + strcat(strcpy(tabpath, "//"), XmlDB); + else + strcpy(tabpath, XmlDB); + + if (!(DBnode = Root->SelectSingleNode(g, tabpath))) { + // DB node does not exist yet; we cannot create it + // because we don't know where it should be placed + sprintf(g->Message, MSG(MISSING_NODE), XmlDB, Xfile); + goto error; + } // endif DBnode + + if (!(TabNode = DBnode->AddChildNode(g, Tabname))) { + sprintf(g->Message, MSG(FAIL_ADD_NODE), Tabname); + goto error; + } // endif TabNode + + DBnode->AddText(g, "\n"); + } else { + TabNode = Root; // Try this ? + Tabname = TabNode->GetName(g); + } // endif's + + } else if (rc == RC_NF || rc == RC_EF) { + // The XML file does not exist or is void + if (Mode == MODE_INSERT) { + // New Document + char buf[64]; + + // Create the XML node + if (Docp->NewDoc(g, "1.0")) { + strcpy(g->Message, MSG(NEW_DOC_FAILED)); + goto error; + } // endif NewDoc + + // Now we can link the Xblock + To_Xb = Docp->LinkXblock(g, Mode, rc, filename); + + // Add a CONNECT comment node + strcpy(buf, " Created by the MariaDB CONNECT Storage Engine"); + Docp->AddComment(g, buf); + + if (XmlDB) { + // This is a multi-table file + DBnode = Root = Docp->NewRoot(g, XmlDB); + DBnode->AddText(g, "\n"); + TabNode = DBnode->AddChildNode(g, Tabname); + DBnode->AddText(g, "\n"); + } else + TabNode = Root = Docp->NewRoot(g, Tabname); + + if (TabNode == NULL || Root == NULL) { + strcpy(g->Message, MSG(XML_INIT_ERROR)); + goto error; + } else if (SetTabNode(g)) + goto error; + + } else { + sprintf(g->Message, MSG(FILE_UNFOUND), Xfile); + + if (Mode == MODE_READ) { + PushWarning(g, this); + Void = true; + } // endif Mode + + goto error; + } // endif Mode + + } else if (rc == RC_INFO) { + // Loading failed + sprintf(g->Message, MSG(LOADING_FAILED), Xfile); + goto error; + } else // (rc == RC_FX) + goto error; + + if (!Rowname) { + for (PXNODE n = TabNode->GetChild(g); n; n = n->GetNext(g)) + if (n->GetType() == XML_ELEMENT_NODE) { + Rowname = n->GetName(g); + break; + } // endif Type + + if (!Rowname) + Rowname = TabNode->GetName(g); + } // endif Rowname + + // Get row node list + if (strcmp(Rowname, Tabname)) + Nlist = TabNode->SelectNodes(g, Rowname); + else + Nrow = 1; + + + Docp->SetNofree(true); // For libxml2 #if defined(__WIN__) - } catch(_com_error e) { + } catch (_com_error e) { // We come here if a DOM command threw an error char buf[128]; @@ -1221,10 +1243,14 @@ int TDBXML::ReadDB(PGLOBAL g) htrc("TDBXML ReadDB: Irow=%d RowNode=%p\n", Irow, RowNode); // Get the new row node - if ((RowNode = Nlist->GetItem(g, Irow, RowNode)) == NULL) { - sprintf(g->Message, MSG(MISSING_ROWNODE), Irow); - return RC_FX; - } // endif RowNode + if (Nlist) { + if ((RowNode = Nlist->GetItem(g, Irow, RowNode)) == NULL) { + sprintf(g->Message, MSG(MISSING_ROWNODE), Irow); + return RC_FX; + } // endif RowNode + + } else + RowNode = TabNode; if (Colname && Coltype == 2) Clist = RowNode->SelectNodes(g, Colname, Clist); @@ -1279,6 +1305,7 @@ int TDBXML::WriteDB(PGLOBAL g) /***********************************************************************/ int TDBXML::DeleteDB(PGLOBAL g, int irc) { + // TODO: Handle null Nlist if (irc == RC_FX) { // Delete all rows for (Irow = 0; Irow < Nrow; Irow++) diff --git a/storage/connect/tabxml.h b/storage/connect/tabxml.h index 102767e965a..fb3913f08ea 100644 --- a/storage/connect/tabxml.h +++ b/storage/connect/tabxml.h @@ -52,6 +52,7 @@ class DllExport XMLDEF : public TABDEF { /* Logical table description */ bool Usedom; /* True: DOM, False: libxml2 */ bool Zipped; /* True: Zipped XML file(s) */ bool Mulentries; /* True: multiple entries in zip file*/ + bool Skip; /* Skip null columns */ }; // end of XMLDEF #if defined(INCLUDE_TDBXML) diff --git a/storage/innobase/buf/buf0buf.cc b/storage/innobase/buf/buf0buf.cc index 1f67b3a292f..c4ab160111f 100644 --- a/storage/innobase/buf/buf0buf.cc +++ b/storage/innobase/buf/buf0buf.cc @@ -2,7 +2,7 @@ Copyright (c) 1995, 2018, Oracle and/or its affiliates. All Rights Reserved. Copyright (c) 2008, Google Inc. -Copyright (c) 2013, 2018, MariaDB Corporation. +Copyright (c) 2013, 2019, MariaDB Corporation. Portions of this file contain modifications contributed and copyrighted by Google, Inc. Those modifications are gratefully acknowledged and are described @@ -1011,7 +1011,10 @@ buf_page_is_corrupted( /* Check whether the checksum fields have correct values */ - if (srv_checksum_algorithm == SRV_CHECKSUM_ALGORITHM_NONE) { + const srv_checksum_algorithm_t curr_algo = + static_cast<srv_checksum_algorithm_t>(srv_checksum_algorithm); + + if (curr_algo == SRV_CHECKSUM_ALGORITHM_NONE) { return(false); } @@ -1050,9 +1053,6 @@ buf_page_is_corrupted( return(false); } - const srv_checksum_algorithm_t curr_algo = - static_cast<srv_checksum_algorithm_t>(srv_checksum_algorithm); - switch (curr_algo) { case SRV_CHECKSUM_ALGORITHM_STRICT_CRC32: return !buf_page_is_checksum_valid_crc32( @@ -1097,9 +1097,7 @@ buf_page_is_corrupted( != mach_read_from_4(read_buf + FIL_PAGE_LSN) && checksum_field2 != BUF_NO_CHECKSUM_MAGIC) { - if (srv_checksum_algorithm - == SRV_CHECKSUM_ALGORITHM_CRC32) { - + if (curr_algo == SRV_CHECKSUM_ALGORITHM_CRC32) { DBUG_EXECUTE_IF( "page_intermittent_checksum_mismatch", { static int page_counter; @@ -1108,7 +1106,6 @@ buf_page_is_corrupted( } }); - crc32 = buf_page_check_crc32(read_buf, checksum_field2); crc32_inited = true; @@ -1119,7 +1116,7 @@ buf_page_is_corrupted( return true; } } else { - ut_ad(srv_checksum_algorithm + ut_ad(curr_algo == SRV_CHECKSUM_ALGORITHM_INNODB); if (checksum_field2 @@ -1137,9 +1134,7 @@ buf_page_is_corrupted( if (checksum_field1 == 0 || checksum_field1 == BUF_NO_CHECKSUM_MAGIC) { - } else if (srv_checksum_algorithm - == SRV_CHECKSUM_ALGORITHM_CRC32) { - + } else if (curr_algo == SRV_CHECKSUM_ALGORITHM_CRC32) { if (!crc32_inited) { crc32 = buf_page_check_crc32( read_buf, checksum_field2); @@ -1152,8 +1147,7 @@ buf_page_is_corrupted( return true; } } else { - ut_ad(srv_checksum_algorithm - == SRV_CHECKSUM_ALGORITHM_INNODB); + ut_ad(curr_algo == SRV_CHECKSUM_ALGORITHM_INNODB); if (checksum_field1 != buf_calc_page_new_checksum(read_buf)) { diff --git a/storage/innobase/handler/ha_innodb.cc b/storage/innobase/handler/ha_innodb.cc index 509be41e48f..2377778f0e7 100644 --- a/storage/innobase/handler/ha_innodb.cc +++ b/storage/innobase/handler/ha_innodb.cc @@ -8201,7 +8201,8 @@ report_error: && wsrep_thd_exec_mode(m_user_thd) == LOCAL_STATE && !wsrep_consistency_check(m_user_thd) && !wsrep_thd_ignore_table(m_user_thd)) { - if (wsrep_append_keys(m_user_thd, false, record, NULL)) { + if (wsrep_append_keys(m_user_thd, WSREP_KEY_EXCLUSIVE, record, + NULL)) { DBUG_PRINT("wsrep", ("row key failed")); error_result = HA_ERR_INTERNAL_ERROR; goto wsrep_error; @@ -8893,7 +8894,8 @@ func_exit: !wsrep_thd_ignore_table(m_user_thd)) { DBUG_PRINT("wsrep", ("update row key")); - if (wsrep_append_keys(m_user_thd, false, old_row, new_row)) { + if (wsrep_append_keys(m_user_thd, WSREP_KEY_EXCLUSIVE, old_row, + new_row)) { WSREP_DEBUG("WSREP: UPDATE_ROW_KEY FAILED"); DBUG_PRINT("wsrep", ("row key failed")); err = HA_ERR_INTERNAL_ERROR; @@ -8953,11 +8955,12 @@ ha_innobase::delete_row( innobase_active_small(); #ifdef WITH_WSREP - if (error == DB_SUCCESS && - wsrep_thd_exec_mode(m_user_thd) == LOCAL_STATE && - wsrep_on(m_user_thd) && - !wsrep_thd_ignore_table(m_user_thd)) { - if (wsrep_append_keys(m_user_thd, false, record, NULL)) { + if (error == DB_SUCCESS + && wsrep_thd_exec_mode(m_user_thd) == LOCAL_STATE + && wsrep_on(m_user_thd) + && !wsrep_thd_ignore_table(m_user_thd)) { + if (wsrep_append_keys(m_user_thd, WSREP_KEY_EXCLUSIVE, record, + NULL)) { DBUG_PRINT("wsrep", ("delete fail")); error = (dberr_t) HA_ERR_INTERNAL_ERROR; goto wsrep_error; @@ -10138,8 +10141,22 @@ wsrep_dict_foreign_find_index( ibool check_charsets, ulint check_null); +inline +const char* +wsrep_key_type_to_str(wsrep_key_type type) +{ + switch (type) { + case WSREP_KEY_SHARED: + return "shared"; + case WSREP_KEY_SEMI: + return "semi"; + case WSREP_KEY_EXCLUSIVE: + return "exclusive"; + }; + return "unknown"; +} -extern dberr_t +ulint wsrep_append_foreign_key( /*===========================*/ trx_t* trx, /*!< in: trx */ @@ -10147,7 +10164,8 @@ wsrep_append_foreign_key( const rec_t* rec, /*!<in: clustered index record */ dict_index_t* index, /*!<in: clustered index */ ibool referenced, /*!<in: is check for referenced table */ - ibool shared) /*!<in: is shared access */ + wsrep_key_type key_type) /*!< in: access type of this key + (shared, exclusive, semi...) */ { ut_a(trx); THD* thd = (THD*)trx->mysql_thd; @@ -10247,11 +10265,11 @@ wsrep_append_foreign_key( if (rcode != DB_SUCCESS) { WSREP_ERROR( "FK key set failed: " ULINTPF - " (" ULINTPF " " ULINTPF "), index: %s %s, %s", - rcode, referenced, shared, - (index) ? index->name() : "void index", + " (" ULINTPF " %s), index: %s %s, %s", + rcode, referenced, wsrep_key_type_to_str(key_type), + index ? index->name() : "void index", (index && index->table) ? index->table->name.m_name : - "void table", + "void table", wsrep_thd_query(thd)); return DB_ERROR; } @@ -10305,7 +10323,7 @@ wsrep_append_foreign_key( wsrep_ws_handle(thd, trx), &wkey, 1, - shared ? WSREP_KEY_SHARED : WSREP_KEY_EXCLUSIVE, + key_type, copy); if (rcode) { @@ -10328,15 +10346,16 @@ wsrep_append_key( TABLE_SHARE *table_share, const char* key, uint16_t key_len, - bool shared + wsrep_key_type key_type /*!< in: access type of this key + (shared, exclusive, semi...) */ ) { DBUG_ENTER("wsrep_append_key"); bool const copy = true; #ifdef WSREP_DEBUG_PRINT fprintf(stderr, "%s conn %ld, trx %llu, keylen %d, table %s\n Query: %s ", - (shared) ? "Shared" : "Exclusive", - thd_get_thread_id(thd), (long long)trx->id, key_len, + wsrep_key_type_to_str(key_type), + wsrep_thd_thread_id(thd), trx->id, key_len, table_share->table_name.str, wsrep_thd_query(thd)); for (int i=0; i<key_len; i++) { fprintf(stderr, "%hhX, ", key[i]); @@ -10365,7 +10384,7 @@ wsrep_append_key( wsrep_ws_handle(thd, trx), &wkey, 1, - shared ? WSREP_KEY_SHARED : WSREP_KEY_EXCLUSIVE, + key_type, copy); if (rcode) { DBUG_PRINT("wsrep", ("row key failed: %d", rcode)); @@ -10407,7 +10426,8 @@ int ha_innobase::wsrep_append_keys( /*===========================*/ THD *thd, - bool shared, + wsrep_key_type key_type, /*!< in: access type of this key + (shared, exclusive, semi...) */ const uchar* record0, /* in: row in MySQL format */ const uchar* record1) /* in: row in MySQL format */ { @@ -10439,11 +10459,9 @@ ha_innobase::wsrep_append_keys( if (!is_null) { rcode = wsrep_append_key( thd, trx, table_share, keyval, - len, shared); + len, key_type); - if (rcode) { - DBUG_RETURN(rcode); - } + if (rcode) DBUG_RETURN(rcode); } else { WSREP_DEBUG("NULL key skipped (proto 0): %s", wsrep_thd_query(thd)); @@ -10493,13 +10511,11 @@ ha_innobase::wsrep_append_keys( if (!is_null) { rcode = wsrep_append_key( thd, trx, table_share, - keyval0, len+1, shared); - - if (rcode) { - DBUG_RETURN(rcode); - } + keyval0, len+1, key_type); + if (rcode) DBUG_RETURN(rcode); - if (key_info->flags & HA_NOSAME || shared) + if (key_info->flags & HA_NOSAME || + key_type == WSREP_KEY_SHARED) key_appended = true; } else { WSREP_DEBUG("NULL key skipped: %s", @@ -10512,10 +10528,12 @@ ha_innobase::wsrep_append_keys( WSREP_MAX_SUPPORTED_KEY_LENGTH, record1, &is_null); - if (!is_null && memcmp(key0, key1, len)) { + if (!is_null + && memcmp(key0, key1, len)) { rcode = wsrep_append_key( thd, trx, table_share, - keyval1, len+1, shared); + keyval1, len+1, + key_type); if (rcode) DBUG_RETURN(rcode); } } @@ -10532,7 +10550,7 @@ ha_innobase::wsrep_append_keys( if ((rcode = wsrep_append_key(thd, trx, table_share, (const char*) digest, 16, - shared))) { + key_type))) { DBUG_RETURN(rcode); } @@ -10541,7 +10559,7 @@ ha_innobase::wsrep_append_keys( digest, record1, table, m_prebuilt); if ((rcode = wsrep_append_key(thd, trx, table_share, (const char*) digest, - 16, shared))) { + 16, key_type))) { DBUG_RETURN(rcode); } } diff --git a/storage/innobase/handler/ha_innodb.h b/storage/innobase/handler/ha_innodb.h index 6f0c5b535fb..c2c93ad823c 100644 --- a/storage/innobase/handler/ha_innodb.h +++ b/storage/innobase/handler/ha_innodb.h @@ -1,7 +1,7 @@ /***************************************************************************** Copyright (c) 2000, 2017, Oracle and/or its affiliates. All Rights Reserved. -Copyright (c) 2013, 2018, MariaDB Corporation. +Copyright (c) 2013, 2019, MariaDB Corporation. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software @@ -17,6 +17,11 @@ this program; if not, write to the Free Software Foundation, Inc., *****************************************************************************/ +#ifdef WITH_WSREP +# include <mysql/service_wsrep.h> +# include "../../../wsrep/wsrep_api.h" +#endif /* WITH_WSREP */ + /* The InnoDB handler: the interface between MySQL and InnoDB. */ /** "GEN_CLUST_INDEX" is the name reserved for InnoDB default @@ -444,7 +449,7 @@ protected: dict_index_t* innobase_get_index(uint keynr); #ifdef WITH_WSREP - int wsrep_append_keys(THD *thd, bool shared, + int wsrep_append_keys(THD *thd, wsrep_key_type key_type, const uchar* record0, const uchar* record1); #endif /** Builds a 'template' to the prebuilt struct. @@ -570,7 +575,6 @@ thd_get_work_part_info( struct trx_t; #ifdef WITH_WSREP -#include <mysql/service_wsrep.h> //extern "C" int wsrep_trx_order_before(void *thd1, void *thd2); extern "C" bool wsrep_thd_is_wsrep_on(THD *thd); @@ -621,10 +625,6 @@ innobase_index_name_is_reserved( be created. */ MY_ATTRIBUTE((nonnull(1), warn_unused_result)); -#ifdef WITH_WSREP -//extern "C" int wsrep_trx_is_aborting(void *thd_ptr); -#endif - /** Parse hint for table and its indexes, and update the information in dictionary. @param[in] thd Connection thread diff --git a/storage/innobase/handler/handler0alter.cc b/storage/innobase/handler/handler0alter.cc index 587ae7f5402..58de40761c5 100644 --- a/storage/innobase/handler/handler0alter.cc +++ b/storage/innobase/handler/handler0alter.cc @@ -1,7 +1,7 @@ /***************************************************************************** Copyright (c) 2005, 2018, Oracle and/or its affiliates. All Rights Reserved. -Copyright (c) 2013, 2018, MariaDB Corporation. +Copyright (c) 2013, 2019, MariaDB Corporation. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software @@ -6570,12 +6570,14 @@ check_if_ok_to_rename: continue; } + dict_foreign_t* foreign; + for (dict_foreign_set::iterator it = m_prebuilt->table->foreign_set.begin(); it != m_prebuilt->table->foreign_set.end(); ++it) { - dict_foreign_t* foreign = *it; + foreign = *it; const char* fid = strchr(foreign->id, '/'); DBUG_ASSERT(fid); @@ -6586,7 +6588,6 @@ check_if_ok_to_rename: if (!my_strcasecmp(system_charset_info, fid, drop->name)) { - drop_fk[n_drop_fk++] = foreign; goto found_fk; } } @@ -6595,13 +6596,20 @@ check_if_ok_to_rename: drop->type_name(), drop->name); goto err_exit; found_fk: + for (ulint i = n_drop_fk; i--; ) { + if (drop_fk[i] == foreign) { + goto dup_fk; + } + } + drop_fk[n_drop_fk++] = foreign; +dup_fk: continue; } DBUG_ASSERT(n_drop_fk > 0); DBUG_ASSERT(n_drop_fk - == ha_alter_info->alter_info->drop_list.elements); + <= ha_alter_info->alter_info->drop_list.elements); } else { drop_fk = NULL; } @@ -7756,7 +7764,7 @@ err_exit: rename_foreign: trx->op_info = "renaming column in SYS_FOREIGN_COLS"; - std::list<dict_foreign_t*> fk_evict; + std::set<dict_foreign_t*> fk_evict; bool foreign_modified; for (dict_foreign_set::const_iterator it = user_table->foreign_set.begin(); @@ -7796,7 +7804,7 @@ rename_foreign: } if (foreign_modified) { - fk_evict.push_back(foreign); + fk_evict.insert(foreign); } } @@ -7838,7 +7846,7 @@ rename_foreign: } if (foreign_modified) { - fk_evict.push_back(foreign); + fk_evict.insert(foreign); } } @@ -8630,6 +8638,8 @@ commit_try_rebuild( DBUG_ASSERT(!(ha_alter_info->handler_flags & ALTER_DROP_FOREIGN_KEY) || ctx->num_to_drop_fk > 0); + DBUG_ASSERT(ctx->num_to_drop_fk + <= ha_alter_info->alter_info->drop_list.elements); for (dict_index_t* index = dict_table_get_first_index(rebuilt_table); index; @@ -8929,7 +8939,7 @@ commit_try_norebuild( & ALTER_DROP_FOREIGN_KEY) || ctx->num_to_drop_fk > 0); DBUG_ASSERT(ctx->num_to_drop_fk - == ha_alter_info->alter_info->drop_list.elements + <= ha_alter_info->alter_info->drop_list.elements || ctx->num_to_drop_vcol == ha_alter_info->alter_info->drop_list.elements); @@ -9428,7 +9438,6 @@ ha_innobase::commit_inplace_alter_table( Alter_inplace_info* ha_alter_info, bool commit) { - dberr_t error; ha_innobase_inplace_ctx*ctx0; struct mtr_buf_copy_t logs; @@ -9516,7 +9525,7 @@ ha_innobase::commit_inplace_alter_table( transactions collected during crash recovery could be holding InnoDB locks only, not MySQL locks. */ - error = row_merge_lock_table( + dberr_t error = row_merge_lock_table( m_prebuilt->trx, ctx->old_table, LOCK_X); if (error != DB_SUCCESS) { @@ -9706,9 +9715,9 @@ ha_innobase::commit_inplace_alter_table( file operations that will be performed in commit_cache_rebuild(), and if none, generate the redo log for these operations. */ - error = fil_mtr_rename_log(ctx->old_table, - ctx->new_table, - ctx->tmp_name, &mtr); + dberr_t error = fil_mtr_rename_log( + ctx->old_table, ctx->new_table, ctx->tmp_name, + &mtr); if (error != DB_SUCCESS) { /* Out of memory or a problem will occur when renaming files. */ @@ -9844,30 +9853,30 @@ ha_innobase::commit_inplace_alter_table( /* Rename the tablespace files. */ commit_cache_rebuild(ctx); - error = innobase_update_foreign_cache(ctx, m_user_thd); - if (error != DB_SUCCESS) { - goto foreign_fail; - } - } else { - error = innobase_update_foreign_cache(ctx, m_user_thd); - - if (error != DB_SUCCESS) { + if (innobase_update_foreign_cache(ctx, m_user_thd) + != DB_SUCCESS + && m_prebuilt->trx->check_foreigns) { foreign_fail: - /* The data dictionary cache - should be corrupted now. The - best solution should be to - kill and restart the server, - but the *.frm file has not - been replaced yet. */ push_warning_printf( m_user_thd, Sql_condition::WARN_LEVEL_WARN, ER_ALTER_INFO, - "InnoDB: Could not add foreign" - " key constraints."); - } else { - commit_cache_norebuild(ha_alter_info, ctx, - table, trx); + "failed to load FOREIGN KEY" + " constraints"); + } + } else { + bool fk_fail = innobase_update_foreign_cache( + ctx, m_user_thd) != DB_SUCCESS; + + commit_cache_norebuild(ha_alter_info, ctx, + table, trx); + innobase_rename_or_enlarge_columns_cache( + ha_alter_info, table, ctx->new_table); +#ifdef MYSQL_RENAME_INDEX + rename_indexes_in_cache(ctx, ha_alter_info); +#endif + if (fk_fail && m_prebuilt->trx->check_foreigns) { + goto foreign_fail; } } @@ -10074,7 +10083,7 @@ foreign_fail: before this is completed, some orphan tables with ctx->tmp_name may be recovered. */ trx_start_for_ddl(trx, TRX_DICT_OP_TABLE); - error = row_merge_drop_table(trx, ctx->old_table); + dberr_t error = row_merge_drop_table(trx, ctx->old_table); if (error != DB_SUCCESS) { ib::error() << "Inplace alter table " << ctx->old_table->name diff --git a/storage/innobase/row/row0ins.cc b/storage/innobase/row/row0ins.cc index 406cf7fa689..94a4ad3d122 100644 --- a/storage/innobase/row/row0ins.cc +++ b/storage/innobase/row/row0ins.cc @@ -1,7 +1,7 @@ /***************************************************************************** Copyright (c) 1996, 2016, Oracle and/or its affiliates. All Rights Reserved. -Copyright (c) 2016, 2018, MariaDB Corporation. +Copyright (c) 2016, 2019, MariaDB Corporation. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software @@ -45,6 +45,12 @@ Created 4/20/1996 Heikki Tuuri #include "fts0fts.h" #include "fts0types.h" +#ifdef WITH_WSREP +#include <mysql/service_wsrep.h> +#include "../../../wsrep/wsrep_api.h" +#include "wsrep_mysqld_c.h" +#endif /* WITH_WSREP */ + /************************************************************************* IMPORTANT NOTE: Any operation that generates redo MUST check that there is enough space in the redo log before for that operation. This is @@ -1043,11 +1049,11 @@ func_exit: #ifdef WITH_WSREP dberr_t wsrep_append_foreign_key(trx_t *trx, - dict_foreign_t* foreign, - const rec_t* clust_rec, - dict_index_t* clust_index, - ibool referenced, - ibool shared); + dict_foreign_t* foreign, + const rec_t* clust_rec, + dict_index_t* clust_index, + ibool referenced, + enum wsrep_key_type key_type); #endif /* WITH_WSREP */ /*********************************************************************//** @@ -1432,7 +1438,7 @@ row_ins_foreign_check_on_constraint( #ifdef WITH_WSREP err = wsrep_append_foreign_key(trx, foreign, clust_rec, clust_index, - FALSE, FALSE); + FALSE, WSREP_KEY_EXCLUSIVE); if (err != DB_SUCCESS) { fprintf(stderr, "WSREP: foreign key append failed: %d\n", err); @@ -1807,13 +1813,31 @@ row_ins_check_foreign_constraint( if (check_ref) { err = DB_SUCCESS; #ifdef WITH_WSREP + if (!wsrep_on(trx->mysql_thd)) { + goto end_scan; + } + enum wsrep_key_type key_type; + if (upd_node != NULL) { + key_type = WSREP_KEY_SHARED; + } else { + switch (wsrep_certification_rules) { + default: + case WSREP_CERTIFICATION_RULES_STRICT: + key_type = WSREP_KEY_EXCLUSIVE; + break; + case WSREP_CERTIFICATION_RULES_OPTIMIZED: + key_type = WSREP_KEY_SEMI; + break; + } + } + err = wsrep_append_foreign_key( - thr_get_trx(thr), + trx, foreign, rec, check_index, check_ref, - (upd_node) ? TRUE : FALSE); + key_type); #endif /* WITH_WSREP */ goto end_scan; } else if (foreign->type != 0) { diff --git a/storage/innobase/row/row0mysql.cc b/storage/innobase/row/row0mysql.cc index 80a3d2f046b..3e290633cf6 100644 --- a/storage/innobase/row/row0mysql.cc +++ b/storage/innobase/row/row0mysql.cc @@ -4463,9 +4463,6 @@ row_rename_table_for_mysql( " = TO_BINARY(:old_table_name);\n" "END;\n" , FALSE, trx); - if (err != DB_SUCCESS) { - goto end; - } } else if (n_constraints_to_drop > 0) { /* Drop some constraints of tmp tables. */ diff --git a/storage/innobase/row/row0sel.cc b/storage/innobase/row/row0sel.cc index 7e3a320b2d4..6faa458033b 100644 --- a/storage/innobase/row/row0sel.cc +++ b/storage/innobase/row/row0sel.cc @@ -2,7 +2,7 @@ Copyright (c) 1997, 2017, Oracle and/or its affiliates. All Rights Reserved. Copyright (c) 2008, Google Inc. -Copyright (c) 2015, 2018, MariaDB Corporation. +Copyright (c) 2015, 2019, MariaDB Corporation. Portions of this file contain modifications contributed and copyrighted by Google, Inc. Those modifications are gratefully acknowledged and are described @@ -3063,20 +3063,20 @@ row_sel_store_mysql_field( Note that the template in prebuilt may advise us to copy only a few columns to mysql_rec, other columns are left blank. All columns may not be needed in the query. -@param[out] mysql_rec row in the MySQL format -@param[in] prebuilt prebuilt structure -@param[in] rec Innobase record in the index - which was described in prebuilt's - template, or in the clustered index; - must be protected by a page latch -@param[in] vrow virtual columns -@param[in] rec_clust whether the rec in the clustered index -@param[in] index index of rec -@param[in] offsets array returned by rec_get_offsets(rec) -@return TRUE on success, FALSE if not all columns could be retrieved */ -static MY_ATTRIBUTE((warn_unused_result)) -ibool -row_sel_store_mysql_rec( +@param[out] mysql_rec row in the MySQL format +@param[in] prebuilt cursor +@param[in] rec Innobase record in the index + which was described in prebuilt's + template, or in the clustered index; + must be protected by a page latch +@param[in] vrow virtual columns +@param[in] rec_clust whether index must be the clustered index +@param[in] index index of rec +@param[in] offsets array returned by rec_get_offsets(rec) +@retval true on success +@retval false if not all columns could be retrieved */ +MY_ATTRIBUTE((warn_unused_result)) +static bool row_sel_store_mysql_rec( byte* mysql_rec, row_prebuilt_t* prebuilt, const rec_t* rec, @@ -3098,13 +3098,18 @@ row_sel_store_mysql_rec( const mysql_row_templ_t*templ = &prebuilt->mysql_template[i]; if (templ->is_virtual && dict_index_is_clust(index)) { + /* Virtual columns are never declared NOT NULL. */ + ut_ad(templ->mysql_null_bit_mask); /* Skip virtual columns if it is not a covered search or virtual key read is not requested. */ - if (!dict_index_has_virtual(prebuilt->index) + if (!rec_clust + || !prebuilt->index->has_virtual() || (!prebuilt->read_just_key - && !prebuilt->m_read_virtual_key) - || !rec_clust) { + && !prebuilt->m_read_virtual_key)) { + /* Initialize the NULL bit. */ + mysql_rec[templ->mysql_null_byte_offset] + |= (byte) templ->mysql_null_bit_mask; continue; } @@ -3178,7 +3183,7 @@ row_sel_store_mysql_rec( rec, index, offsets, field_no, templ)) { - DBUG_RETURN(FALSE); + DBUG_RETURN(false); } } @@ -3195,7 +3200,7 @@ row_sel_store_mysql_rec( } } - DBUG_RETURN(TRUE); + DBUG_RETURN(true); } /*********************************************************************//** diff --git a/storage/tokudb/PerconaFT/COPYING.APACHEv2 b/storage/tokudb/PerconaFT/COPYING.APACHEv2 new file mode 100644 index 00000000000..ecbfc770fa9 --- /dev/null +++ b/storage/tokudb/PerconaFT/COPYING.APACHEv2 @@ -0,0 +1,174 @@ +Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. diff --git a/storage/tokudb/PerconaFT/README.md b/storage/tokudb/PerconaFT/README.md index ffb646b67af..26333df877e 100644 --- a/storage/tokudb/PerconaFT/README.md +++ b/storage/tokudb/PerconaFT/README.md @@ -104,11 +104,14 @@ All source code and test contributions must be provided under a [BSD 2-Clause][b License ------- +Portions of the PerconaFT library (the 'locktree' and 'omt') are available under the Apache version 2 license. PerconaFT is available under the GPL version 2, and AGPL version 3. -See [COPYING.AGPLv3][agpllicense], +See [COPYING.APACHEv2][apachelicense], +[COPYING.AGPLv3][agpllicense], [COPYING.GPLv2][gpllicense], and [PATENTS][patents]. +[apachelicense]: http://github.com/Percona/PerconaFT/blob/master/COPYING.APACHEv2 [agpllicense]: http://github.com/Percona/PerconaFT/blob/master/COPYING.AGPLv3 [gpllicense]: http://github.com/Percona/PerconaFT/blob/master/COPYING.GPLv2 [patents]: http://github.com/Percona/PerconaFT/blob/master/PATENTS diff --git a/storage/tokudb/PerconaFT/ft/txn/txn_manager.h b/storage/tokudb/PerconaFT/ft/txn/txn_manager.h index 7cdc52c4f43..25fa6032112 100644 --- a/storage/tokudb/PerconaFT/ft/txn/txn_manager.h +++ b/storage/tokudb/PerconaFT/ft/txn/txn_manager.h @@ -46,11 +46,11 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. void set_test_txn_sync_callback(void (*) (pthread_t, void*), void*); #define toku_test_txn_sync_callback(a) ((test_txn_sync_callback)? test_txn_sync_callback( a,test_txn_sync_callback_extra) : (void) 0) -#if TOKU_DEBUG_TXN_SYNC +#if defined(TOKU_DEBUG_TXN_SYNC) #define toku_debug_txn_sync(a) toku_test_txn_sync_callback(a) #else #define toku_debug_txn_sync(a) ((void) 0) -#endif +#endif // defined(TOKU_DEBUG_TXN_SYNC) typedef struct txn_manager *TXN_MANAGER; diff --git a/storage/tokudb/PerconaFT/locktree/concurrent_tree.cc b/storage/tokudb/PerconaFT/locktree/concurrent_tree.cc index 9347267db49..e07f32c98fb 100644 --- a/storage/tokudb/PerconaFT/locktree/concurrent_tree.cc +++ b/storage/tokudb/PerconaFT/locktree/concurrent_tree.cc @@ -32,6 +32,20 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/concurrent_tree.h b/storage/tokudb/PerconaFT/locktree/concurrent_tree.h index 1eb339b7317..66a7ff176bb 100644 --- a/storage/tokudb/PerconaFT/locktree/concurrent_tree.h +++ b/storage/tokudb/PerconaFT/locktree/concurrent_tree.h @@ -32,6 +32,20 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/keyrange.cc b/storage/tokudb/PerconaFT/locktree/keyrange.cc index 8c2a69d4703..2b4b3bbd4fd 100644 --- a/storage/tokudb/PerconaFT/locktree/keyrange.cc +++ b/storage/tokudb/PerconaFT/locktree/keyrange.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/keyrange.h b/storage/tokudb/PerconaFT/locktree/keyrange.h index 079ac3d7a80..a454287cbc8 100644 --- a/storage/tokudb/PerconaFT/locktree/keyrange.h +++ b/storage/tokudb/PerconaFT/locktree/keyrange.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/lock_request.cc b/storage/tokudb/PerconaFT/locktree/lock_request.cc index c0829e3f4e1..51898d4ccb1 100644 --- a/storage/tokudb/PerconaFT/locktree/lock_request.cc +++ b/storage/tokudb/PerconaFT/locktree/lock_request.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/lock_request.h b/storage/tokudb/PerconaFT/locktree/lock_request.h index 9e82b31541e..455433cb90c 100644 --- a/storage/tokudb/PerconaFT/locktree/lock_request.h +++ b/storage/tokudb/PerconaFT/locktree/lock_request.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/locktree.cc b/storage/tokudb/PerconaFT/locktree/locktree.cc index 069aae26f66..8ba3f0f00ae 100644 --- a/storage/tokudb/PerconaFT/locktree/locktree.cc +++ b/storage/tokudb/PerconaFT/locktree/locktree.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/locktree.h b/storage/tokudb/PerconaFT/locktree/locktree.h index 1ba7a51b124..7006b6fb01d 100644 --- a/storage/tokudb/PerconaFT/locktree/locktree.h +++ b/storage/tokudb/PerconaFT/locktree/locktree.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/manager.cc b/storage/tokudb/PerconaFT/locktree/manager.cc index 6bb5c77bf32..21f8dc6cf01 100644 --- a/storage/tokudb/PerconaFT/locktree/manager.cc +++ b/storage/tokudb/PerconaFT/locktree/manager.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/range_buffer.cc b/storage/tokudb/PerconaFT/locktree/range_buffer.cc index 3ddfd0faf97..d1f14fc4a52 100644 --- a/storage/tokudb/PerconaFT/locktree/range_buffer.cc +++ b/storage/tokudb/PerconaFT/locktree/range_buffer.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/range_buffer.h b/storage/tokudb/PerconaFT/locktree/range_buffer.h index b0e36968e73..811b0f85e69 100644 --- a/storage/tokudb/PerconaFT/locktree/range_buffer.h +++ b/storage/tokudb/PerconaFT/locktree/range_buffer.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/treenode.cc b/storage/tokudb/PerconaFT/locktree/treenode.cc index cc3a4969643..0247242f975 100644 --- a/storage/tokudb/PerconaFT/locktree/treenode.cc +++ b/storage/tokudb/PerconaFT/locktree/treenode.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/treenode.h b/storage/tokudb/PerconaFT/locktree/treenode.h index 08aad2b6636..981e8b5a9cf 100644 --- a/storage/tokudb/PerconaFT/locktree/treenode.h +++ b/storage/tokudb/PerconaFT/locktree/treenode.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/txnid_set.cc b/storage/tokudb/PerconaFT/locktree/txnid_set.cc index 82b59453156..bd4e9723155 100644 --- a/storage/tokudb/PerconaFT/locktree/txnid_set.cc +++ b/storage/tokudb/PerconaFT/locktree/txnid_set.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/txnid_set.h b/storage/tokudb/PerconaFT/locktree/txnid_set.h index 109d7f798e4..81fd45b6dde 100644 --- a/storage/tokudb/PerconaFT/locktree/txnid_set.h +++ b/storage/tokudb/PerconaFT/locktree/txnid_set.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/wfg.cc b/storage/tokudb/PerconaFT/locktree/wfg.cc index 9a234f50060..26b7a3b5295 100644 --- a/storage/tokudb/PerconaFT/locktree/wfg.cc +++ b/storage/tokudb/PerconaFT/locktree/wfg.cc @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/locktree/wfg.h b/storage/tokudb/PerconaFT/locktree/wfg.h index c56886e1362..5c1599592e6 100644 --- a/storage/tokudb/PerconaFT/locktree/wfg.h +++ b/storage/tokudb/PerconaFT/locktree/wfg.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/portability/toku_instr_mysql.cc b/storage/tokudb/PerconaFT/portability/toku_instr_mysql.cc index d742555f878..786a6ef0546 100644 --- a/storage/tokudb/PerconaFT/portability/toku_instr_mysql.cc +++ b/storage/tokudb/PerconaFT/portability/toku_instr_mysql.cc @@ -184,9 +184,9 @@ void toku_instr_file_io_end(toku_io_instrumentation &io_instr, ssize_t count) { void toku_instr_mutex_init(const toku_instr_key &key, toku_mutex_t &mutex) { mutex.psi_mutex = PSI_MUTEX_CALL(init_mutex)(key.id(), &mutex.pmutex); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) mutex.instr_key_id = key.id(); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) } void toku_instr_mutex_destroy(PSI_mutex *&mutex_instr) { @@ -242,9 +242,9 @@ void toku_instr_mutex_unlock(PSI_mutex *mutex_instr) { void toku_instr_cond_init(const toku_instr_key &key, toku_cond_t &cond) { cond.psi_cond = PSI_COND_CALL(init_cond)(key.id(), &cond.pcond); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) cond.instr_key_id = key.id(); -#endif +#endif // // defined(TOKU_PTHREAD_DEBUG) } void toku_instr_cond_destroy(PSI_cond *&cond_instr) { @@ -295,9 +295,9 @@ void toku_instr_cond_broadcast(const toku_cond_t &cond) { void toku_instr_rwlock_init(const toku_instr_key &key, toku_pthread_rwlock_t &rwlock) { rwlock.psi_rwlock = PSI_RWLOCK_CALL(init_rwlock)(key.id(), &rwlock.rwlock); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) rwlock.instr_key_id = key.id(); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) } void toku_instr_rwlock_destroy(PSI_rwlock *&rwlock_instr) { diff --git a/storage/tokudb/PerconaFT/portability/toku_instr_mysql.h b/storage/tokudb/PerconaFT/portability/toku_instr_mysql.h index d6b0ed35ce9..beb833a163c 100644 --- a/storage/tokudb/PerconaFT/portability/toku_instr_mysql.h +++ b/storage/tokudb/PerconaFT/portability/toku_instr_mysql.h @@ -12,8 +12,15 @@ // undefine them here to avoid compilation errors. #undef __STDC_FORMAT_MACROS #undef __STDC_LIMIT_MACROS -#include <mysql/psi/mysql_file.h> // PSI_file -#include <mysql/psi/mysql_thread.h> // PSI_mutex +#include "mysql/psi/mysql_file.h" // PSI_file +#include "mysql/psi/mysql_thread.h" // PSI_mutex +#include "mysql/psi/mysql_stage.h" // PSI_stage + +#if (MYSQL_VERSION_ID >= 80000) && ( MYSQL_VERSION_ID <= 100000) +#include "mysql/psi/mysql_cond.h" +#include "mysql/psi/mysql_mutex.h" +#include "mysql/psi/mysql_rwlock.h" +#endif // (MYSQL_VERSION_ID >= nn) #ifndef HAVE_PSI_MUTEX_INTERFACE #error HAVE_PSI_MUTEX_INTERFACE required diff --git a/storage/tokudb/PerconaFT/portability/toku_pthread.h b/storage/tokudb/PerconaFT/portability/toku_pthread.h index a0dfcc246a7..d05c6fabf53 100644 --- a/storage/tokudb/PerconaFT/portability/toku_pthread.h +++ b/storage/tokudb/PerconaFT/portability/toku_pthread.h @@ -64,23 +64,23 @@ struct toku_mutex_t { pthread_mutex_t pmutex; struct PSI_mutex *psi_mutex; /* The performance schema instrumentation hook */ -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) pthread_t owner; // = pthread_self(); // for debugging bool locked; bool valid; pfs_key_t instr_key_id; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) }; struct toku_cond_t { pthread_cond_t pcond; struct PSI_cond *psi_cond; -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) pfs_key_t instr_key_id; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) }; -#ifdef TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) #define TOKU_COND_INITIALIZER \ { \ .pcond = PTHREAD_COND_INITIALIZER, .psi_cond = nullptr, \ @@ -89,14 +89,14 @@ struct toku_cond_t { #else #define TOKU_COND_INITIALIZER \ { .pcond = PTHREAD_COND_INITIALIZER, .psi_cond = nullptr } -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) struct toku_pthread_rwlock_t { pthread_rwlock_t rwlock; struct PSI_rwlock *psi_rwlock; -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) pfs_key_t instr_key_id; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) }; typedef struct toku_mutex_aligned { @@ -117,7 +117,7 @@ typedef struct toku_mutex_aligned { #define ZERO_MUTEX_INITIALIZER \ {} -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) #define TOKU_MUTEX_INITIALIZER \ { \ .pmutex = PTHREAD_MUTEX_INITIALIZER, .psi_mutex = nullptr, .owner = 0, \ @@ -126,12 +126,12 @@ typedef struct toku_mutex_aligned { #else #define TOKU_MUTEX_INITIALIZER \ { .pmutex = PTHREAD_MUTEX_INITIALIZER, .psi_mutex = nullptr } -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) // Darwin doesn't provide adaptive mutexes #if defined(__APPLE__) #define TOKU_MUTEX_ADAPTIVE PTHREAD_MUTEX_DEFAULT -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) #define TOKU_ADAPTIVE_MUTEX_INITIALIZER \ { \ .pmutex = PTHREAD_MUTEX_INITIALIZER, .psi_mutex = nullptr, .owner = 0, \ @@ -140,10 +140,10 @@ typedef struct toku_mutex_aligned { #else #define TOKU_ADAPTIVE_MUTEX_INITIALIZER \ { .pmutex = PTHREAD_MUTEX_INITIALIZER, .psi_mutex = nullptr } -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) #else // __FreeBSD__, __linux__, at least #define TOKU_MUTEX_ADAPTIVE PTHREAD_MUTEX_ADAPTIVE_NP -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) #define TOKU_ADAPTIVE_MUTEX_INITIALIZER \ { \ .pmutex = PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP, .psi_mutex = nullptr, \ @@ -152,8 +152,8 @@ typedef struct toku_mutex_aligned { #else #define TOKU_ADAPTIVE_MUTEX_INITIALIZER \ { .pmutex = PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP, .psi_mutex = nullptr } -#endif -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) +#endif // defined(__APPLE__) // Different OSes implement mutexes as different amounts of nested structs. // C++ will fill out all missing values with zeroes if you provide at least one @@ -198,7 +198,7 @@ toku_mutexattr_destroy(toku_pthread_mutexattr_t *attr) { assert_zero(r); } -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) static inline void toku_mutex_assert_locked(const toku_mutex_t *mutex) { invariant(mutex->locked); invariant(mutex->owner == pthread_self()); @@ -207,7 +207,7 @@ static inline void toku_mutex_assert_locked(const toku_mutex_t *mutex) { static inline void toku_mutex_assert_locked(const toku_mutex_t *mutex __attribute__((unused))) { } -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) // asserting that a mutex is unlocked only makes sense // if the calling thread can guaruntee that no other threads @@ -217,7 +217,7 @@ toku_mutex_assert_locked(const toku_mutex_t *mutex __attribute__((unused))) { // when a node is locked the caller knows that no other threads // can be trying to lock its childrens' mutexes. the children // are in one of two fixed states: locked or unlocked. -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) static inline void toku_mutex_assert_unlocked(toku_mutex_t *mutex) { invariant(mutex->owner == 0); @@ -226,7 +226,7 @@ toku_mutex_assert_unlocked(toku_mutex_t *mutex) { #else static inline void toku_mutex_assert_unlocked(toku_mutex_t *mutex __attribute__((unused))) {} -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) #define toku_mutex_lock(M) \ toku_mutex_lock_with_source_location(M, __FILE__, __LINE__) @@ -241,13 +241,13 @@ static inline void toku_cond_init(toku_cond_t *cond, toku_mutex_trylock_with_source_location(M, __FILE__, __LINE__) inline void toku_mutex_unlock(toku_mutex_t *mutex) { -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(mutex->owner == pthread_self()); invariant(mutex->valid); invariant(mutex->locked); mutex->locked = false; mutex->owner = 0; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) toku_instr_mutex_unlock(mutex->psi_mutex); int r = pthread_mutex_unlock(&mutex->pmutex); assert_zero(r); @@ -264,13 +264,13 @@ inline void toku_mutex_lock_with_source_location(toku_mutex_t *mutex, toku_instr_mutex_lock_end(mutex_instr, r); assert_zero(r); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(mutex->valid); invariant(!mutex->locked); invariant(mutex->owner == 0); mutex->locked = true; mutex->owner = pthread_self(); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) } inline int toku_mutex_trylock_with_source_location(toku_mutex_t *mutex, @@ -283,7 +283,7 @@ inline int toku_mutex_trylock_with_source_location(toku_mutex_t *mutex, const int r = pthread_mutex_lock(&mutex->pmutex); toku_instr_mutex_lock_end(mutex_instr, r); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) if (r == 0) { invariant(mutex->valid); invariant(!mutex->locked); @@ -291,7 +291,7 @@ inline int toku_mutex_trylock_with_source_location(toku_mutex_t *mutex, mutex->locked = true; mutex->owner = pthread_self(); } -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) return r; } @@ -320,11 +320,11 @@ inline void toku_cond_wait_with_source_location(toku_cond_t *cond, const char *src_file, uint src_line) { -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(mutex->locked); mutex->locked = false; mutex->owner = 0; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) /* Instrumentation start */ toku_cond_instrumentation cond_instr; @@ -342,11 +342,11 @@ inline void toku_cond_wait_with_source_location(toku_cond_t *cond, toku_instr_cond_wait_end(cond_instr, r); assert_zero(r); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(!mutex->locked); mutex->locked = true; mutex->owner = pthread_self(); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) } inline int toku_cond_timedwait_with_source_location(toku_cond_t *cond, @@ -354,11 +354,11 @@ inline int toku_cond_timedwait_with_source_location(toku_cond_t *cond, toku_timespec_t *wakeup_at, const char *src_file, uint src_line) { -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(mutex->locked); mutex->locked = false; mutex->owner = 0; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) /* Instrumentation start */ toku_cond_instrumentation cond_instr; @@ -376,11 +376,11 @@ inline int toku_cond_timedwait_with_source_location(toku_cond_t *cond, /* Instrumentation end */ toku_instr_cond_wait_end(cond_instr, r); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(!mutex->locked); mutex->locked = true; mutex->owner = pthread_self(); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) return r; } @@ -399,26 +399,26 @@ inline void toku_cond_broadcast(toku_cond_t *cond) { inline void toku_mutex_init(const toku_instr_key &key, toku_mutex_t *mutex, const toku_pthread_mutexattr_t *attr) { -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) mutex->valid = true; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) toku_instr_mutex_init(key, *mutex); const int r = pthread_mutex_init(&mutex->pmutex, attr); assert_zero(r); -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) mutex->locked = false; invariant(mutex->valid); mutex->valid = true; mutex->owner = 0; -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) } inline void toku_mutex_destroy(toku_mutex_t *mutex) { -#if TOKU_PTHREAD_DEBUG +#if defined(TOKU_PTHREAD_DEBUG) invariant(mutex->valid); mutex->valid = false; invariant(!mutex->locked); -#endif +#endif // defined(TOKU_PTHREAD_DEBUG) toku_instr_mutex_destroy(mutex->psi_mutex); int r = pthread_mutex_destroy(&mutex->pmutex); assert_zero(r); diff --git a/storage/tokudb/PerconaFT/util/growable_array.h b/storage/tokudb/PerconaFT/util/growable_array.h index e8873ae4abd..ad60ea6395b 100644 --- a/storage/tokudb/PerconaFT/util/growable_array.h +++ b/storage/tokudb/PerconaFT/util/growable_array.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/PerconaFT/util/omt.cc b/storage/tokudb/PerconaFT/util/omt.cc index 1fae0712c77..846c4df7f54 100644 --- a/storage/tokudb/PerconaFT/util/omt.cc +++ b/storage/tokudb/PerconaFT/util/omt.cc @@ -32,1105 +32,1356 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ -#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." +#ident \ + "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." -#include <string.h> #include <db.h> +#include <string.h> #include <portability/memory.h> namespace toku { -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create(void) { - this->create_internal(2); - if (supports_marks) { - this->convert_to_tree(); + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::create(void) { + this->create_internal(2); + if (supports_marks) { + this->convert_to_tree(); + } } -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create_no_array(void) { - if (!supports_marks) { - this->create_internal_no_array(0); - } else { - this->is_array = false; - this->capacity = 0; - this->d.t.nodes = nullptr; - this->d.t.root.set_to_null(); - this->d.t.free_idx = 0; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create_from_sorted_array(const omtdata_t *const values, const uint32_t numvalues) { - this->create_internal(numvalues); - memcpy(this->d.a.values, values, numvalues * (sizeof values[0])); - this->d.a.num_values = numvalues; - if (supports_marks) { - this->convert_to_tree(); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create_steal_sorted_array(omtdata_t **const values, const uint32_t numvalues, const uint32_t new_capacity) { - paranoid_invariant_notnull(values); - this->create_internal_no_array(new_capacity); - this->d.a.num_values = numvalues; - this->d.a.values = *values; - *values = nullptr; - if (supports_marks) { - this->convert_to_tree(); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -int omt<omtdata_t, omtdataout_t, supports_marks>::split_at(omt *const newomt, const uint32_t idx) { - barf_if_marked(*this); - paranoid_invariant_notnull(newomt); - if (idx > this->size()) { return EINVAL; } - this->convert_to_array(); - const uint32_t newsize = this->size() - idx; - newomt->create_from_sorted_array(&this->d.a.values[this->d.a.start_idx + idx], newsize); - this->d.a.num_values = idx; - this->maybe_resize_array(idx); - if (supports_marks) { - this->convert_to_tree(); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::merge(omt *const leftomt, omt *const rightomt) { - barf_if_marked(*this); - paranoid_invariant_notnull(leftomt); - paranoid_invariant_notnull(rightomt); - const uint32_t leftsize = leftomt->size(); - const uint32_t rightsize = rightomt->size(); - const uint32_t newsize = leftsize + rightsize; - - if (leftomt->is_array) { - if (leftomt->capacity - (leftomt->d.a.start_idx + leftomt->d.a.num_values) >= rightsize) { - this->create_steal_sorted_array(&leftomt->d.a.values, leftomt->d.a.num_values, leftomt->capacity); - this->d.a.start_idx = leftomt->d.a.start_idx; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::create_no_array(void) { + if (!supports_marks) { + this->create_internal_no_array(0); + } else { + this->is_array = false; + this->capacity = 0; + this->d.t.nodes = nullptr; + this->d.t.root.set_to_null(); + this->d.t.free_idx = 0; + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::create_from_sorted_array( + const omtdata_t *const values, + const uint32_t numvalues) { + this->create_internal(numvalues); + memcpy(this->d.a.values, values, numvalues * (sizeof values[0])); + this->d.a.num_values = numvalues; + if (supports_marks) { + this->convert_to_tree(); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void + omt<omtdata_t, omtdataout_t, supports_marks>::create_steal_sorted_array( + omtdata_t **const values, + const uint32_t numvalues, + const uint32_t new_capacity) { + paranoid_invariant_notnull(values); + this->create_internal_no_array(new_capacity); + this->d.a.num_values = numvalues; + this->d.a.values = *values; + *values = nullptr; + if (supports_marks) { + this->convert_to_tree(); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + int omt<omtdata_t, omtdataout_t, supports_marks>::split_at( + omt *const newomt, + const uint32_t idx) { + barf_if_marked(*this); + paranoid_invariant_notnull(newomt); + if (idx > this->size()) { + return EINVAL; + } + this->convert_to_array(); + const uint32_t newsize = this->size() - idx; + newomt->create_from_sorted_array( + &this->d.a.values[this->d.a.start_idx + idx], newsize); + this->d.a.num_values = idx; + this->maybe_resize_array(idx); + if (supports_marks) { + this->convert_to_tree(); + } + return 0; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::merge( + omt *const leftomt, + omt *const rightomt) { + barf_if_marked(*this); + paranoid_invariant_notnull(leftomt); + paranoid_invariant_notnull(rightomt); + const uint32_t leftsize = leftomt->size(); + const uint32_t rightsize = rightomt->size(); + const uint32_t newsize = leftsize + rightsize; + + if (leftomt->is_array) { + if (leftomt->capacity - + (leftomt->d.a.start_idx + leftomt->d.a.num_values) >= + rightsize) { + this->create_steal_sorted_array(&leftomt->d.a.values, + leftomt->d.a.num_values, + leftomt->capacity); + this->d.a.start_idx = leftomt->d.a.start_idx; + } else { + this->create_internal(newsize); + memcpy(&this->d.a.values[0], + &leftomt->d.a.values[leftomt->d.a.start_idx], + leftomt->d.a.num_values * (sizeof this->d.a.values[0])); + } } else { this->create_internal(newsize); + leftomt->fill_array_with_subtree_values(&this->d.a.values[0], + leftomt->d.t.root); + } + leftomt->destroy(); + this->d.a.num_values = leftsize; + + if (rightomt->is_array) { + memcpy( + &this->d.a.values[this->d.a.start_idx + this->d.a.num_values], + &rightomt->d.a.values[rightomt->d.a.start_idx], + rightomt->d.a.num_values * (sizeof this->d.a.values[0])); + } else { + rightomt->fill_array_with_subtree_values( + &this->d.a.values[this->d.a.start_idx + this->d.a.num_values], + rightomt->d.t.root); + } + rightomt->destroy(); + this->d.a.num_values += rightsize; + paranoid_invariant(this->size() == newsize); + if (supports_marks) { + this->convert_to_tree(); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::clone(const omt &src) { + barf_if_marked(*this); + this->create_internal(src.size()); + if (src.is_array) { memcpy(&this->d.a.values[0], - &leftomt->d.a.values[leftomt->d.a.start_idx], - leftomt->d.a.num_values * (sizeof this->d.a.values[0])); - } - } else { - this->create_internal(newsize); - leftomt->fill_array_with_subtree_values(&this->d.a.values[0], leftomt->d.t.root); - } - leftomt->destroy(); - this->d.a.num_values = leftsize; - - if (rightomt->is_array) { - memcpy(&this->d.a.values[this->d.a.start_idx + this->d.a.num_values], - &rightomt->d.a.values[rightomt->d.a.start_idx], - rightomt->d.a.num_values * (sizeof this->d.a.values[0])); - } else { - rightomt->fill_array_with_subtree_values(&this->d.a.values[this->d.a.start_idx + this->d.a.num_values], - rightomt->d.t.root); - } - rightomt->destroy(); - this->d.a.num_values += rightsize; - paranoid_invariant(this->size() == newsize); - if (supports_marks) { - this->convert_to_tree(); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::clone(const omt &src) { - barf_if_marked(*this); - this->create_internal(src.size()); - if (src.is_array) { - memcpy(&this->d.a.values[0], &src.d.a.values[src.d.a.start_idx], src.d.a.num_values * (sizeof this->d.a.values[0])); - } else { - src.fill_array_with_subtree_values(&this->d.a.values[0], src.d.t.root); - } - this->d.a.num_values = src.size(); - if (supports_marks) { - this->convert_to_tree(); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::clear(void) { - if (this->is_array) { - this->d.a.start_idx = 0; - this->d.a.num_values = 0; - } else { - this->d.t.root.set_to_null(); - this->d.t.free_idx = 0; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::destroy(void) { - this->clear(); - this->capacity = 0; - if (this->is_array) { - if (this->d.a.values != nullptr) { - toku_free(this->d.a.values); + &src.d.a.values[src.d.a.start_idx], + src.d.a.num_values * (sizeof this->d.a.values[0])); + } else { + src.fill_array_with_subtree_values(&this->d.a.values[0], + src.d.t.root); } - this->d.a.values = nullptr; - } else { - if (this->d.t.nodes != nullptr) { - toku_free(this->d.t.nodes); + this->d.a.num_values = src.size(); + if (supports_marks) { + this->convert_to_tree(); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::clear(void) { + if (this->is_array) { + this->d.a.start_idx = 0; + this->d.a.num_values = 0; + } else { + this->d.t.root.set_to_null(); + this->d.t.free_idx = 0; + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::destroy(void) { + this->clear(); + this->capacity = 0; + if (this->is_array) { + if (this->d.a.values != nullptr) { + toku_free(this->d.a.values); + } + this->d.a.values = nullptr; + } else { + if (this->d.t.nodes != nullptr) { + toku_free(this->d.t.nodes); + } + this->d.t.nodes = nullptr; } - this->d.t.nodes = nullptr; } -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::size(void) const { - if (this->is_array) { - return this->d.a.num_values; - } else { - return this->nweight(this->d.t.root); + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::size(void) const { + if (this->is_array) { + return this->d.a.num_values; + } else { + return this->nweight(this->d.t.root); + } } -} + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::insert( + const omtdata_t &value, + const omtcmp_t &v, + uint32_t *const idx) { + int r; + uint32_t insert_idx; -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::insert(const omtdata_t &value, const omtcmp_t &v, uint32_t *const idx) { - int r; - uint32_t insert_idx; + r = this->find_zero<omtcmp_t, h>(v, nullptr, &insert_idx); + if (r == 0) { + if (idx) + *idx = insert_idx; + return DB_KEYEXIST; + } + if (r != DB_NOTFOUND) + return r; - r = this->find_zero<omtcmp_t, h>(v, nullptr, &insert_idx); - if (r==0) { - if (idx) *idx = insert_idx; - return DB_KEYEXIST; + if ((r = this->insert_at(value, insert_idx))) + return r; + if (idx) + *idx = insert_idx; + + return 0; } - if (r != DB_NOTFOUND) return r; - if ((r = this->insert_at(value, insert_idx))) return r; - if (idx) *idx = insert_idx; + // The following 3 functions implement a static if for us. + template <typename omtdata_t, typename omtdataout_t> + static void barf_if_marked( + const omt<omtdata_t, omtdataout_t, false> &UU(omt)) {} - return 0; -} + template <typename omtdata_t, typename omtdataout_t> + static void barf_if_marked(const omt<omtdata_t, omtdataout_t, true> &omt) { + invariant(!omt.has_marks()); + } -// The following 3 functions implement a static if for us. -template<typename omtdata_t, typename omtdataout_t> -static void barf_if_marked(const omt<omtdata_t, omtdataout_t, false> &UU(omt)) { -} + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + bool omt<omtdata_t, omtdataout_t, supports_marks>::has_marks(void) const { + static_assert(supports_marks, "Does not support marks"); + if (this->d.t.root.is_null()) { + return false; + } + const omt_node &node = this->d.t.nodes[this->d.t.root.get_index()]; + return node.get_marks_below() || node.get_marked(); + } -template<typename omtdata_t, typename omtdataout_t> -static void barf_if_marked(const omt<omtdata_t, omtdataout_t, true> &omt) { - invariant(!omt.has_marks()); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -bool omt<omtdata_t, omtdataout_t, supports_marks>::has_marks(void) const { - static_assert(supports_marks, "Does not support marks"); - if (this->d.t.root.is_null()) { - return false; - } - const omt_node &node = this->d.t.nodes[this->d.t.root.get_index()]; - return node.get_marks_below() || node.get_marked(); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -int omt<omtdata_t, omtdataout_t, supports_marks>::insert_at(const omtdata_t &value, const uint32_t idx) { - barf_if_marked(*this); - if (idx > this->size()) { return EINVAL; } - - this->maybe_resize_or_convert(this->size() + 1); - if (this->is_array && idx != this->d.a.num_values && - (idx != 0 || this->d.a.start_idx == 0)) { - this->convert_to_tree(); - } - if (this->is_array) { - if (idx == this->d.a.num_values) { - this->d.a.values[this->d.a.start_idx + this->d.a.num_values] = value; - } - else { - this->d.a.values[--this->d.a.start_idx] = value; - } - this->d.a.num_values++; - } - else { - subtree *rebalance_subtree = nullptr; - this->insert_internal(&this->d.t.root, value, idx, &rebalance_subtree); - if (rebalance_subtree != nullptr) { - this->rebalance(rebalance_subtree); - } - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -int omt<omtdata_t, omtdataout_t, supports_marks>::set_at(const omtdata_t &value, const uint32_t idx) { - barf_if_marked(*this); - if (idx >= this->size()) { return EINVAL; } - - if (this->is_array) { - this->set_at_internal_array(value, idx); - } else { - this->set_at_internal(this->d.t.root, value, idx); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -int omt<omtdata_t, omtdataout_t, supports_marks>::delete_at(const uint32_t idx) { - barf_if_marked(*this); - if (idx >= this->size()) { return EINVAL; } - - this->maybe_resize_or_convert(this->size() - 1); - if (this->is_array && idx != 0 && idx != this->d.a.num_values - 1) { - this->convert_to_tree(); - } - if (this->is_array) { - //Testing for 0 does not rule out it being the last entry. - //Test explicitly for num_values-1 - if (idx != this->d.a.num_values - 1) { - this->d.a.start_idx++; - } - this->d.a.num_values--; - } else { - subtree *rebalance_subtree = nullptr; - this->delete_internal(&this->d.t.root, idx, nullptr, &rebalance_subtree); - if (rebalance_subtree != nullptr) { - this->rebalance(rebalance_subtree); - } - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate(iterate_extra_t *const iterate_extra) const { - return this->iterate_on_range<iterate_extra_t, f>(0, this->size(), iterate_extra); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_on_range(const uint32_t left, const uint32_t right, iterate_extra_t *const iterate_extra) const { - if (right > this->size()) { return EINVAL; } - if (left == right) { return 0; } - if (this->is_array) { - return this->iterate_internal_array<iterate_extra_t, f>(left, right, iterate_extra); - } - return this->iterate_internal<iterate_extra_t, f>(left, right, this->d.t.root, 0, iterate_extra); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_and_mark_range(const uint32_t left, const uint32_t right, iterate_extra_t *const iterate_extra) { - static_assert(supports_marks, "does not support marks"); - if (right > this->size()) { return EINVAL; } - if (left == right) { return 0; } - paranoid_invariant(!this->is_array); - return this->iterate_and_mark_range_internal<iterate_extra_t, f>(left, right, this->d.t.root, 0, iterate_extra); -} - -//TODO: We can optimize this if we steal 3 bits. 1 bit: this node is marked. 1 bit: left subtree has marks. 1 bit: right subtree has marks. -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_over_marked(iterate_extra_t *const iterate_extra) const { - static_assert(supports_marks, "does not support marks"); - paranoid_invariant(!this->is_array); - return this->iterate_over_marked_internal<iterate_extra_t, f>(this->d.t.root, 0, iterate_extra); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::unmark(const subtree &subtree, const uint32_t index, GrowableArray<node_idx> *const indexes) { - if (subtree.is_null()) { return; } - omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t index_root = index + this->nweight(n.left); - - const bool below = n.get_marks_below(); - if (below) { - this->unmark(n.left, index, indexes); - } - if (n.get_marked()) { - indexes->push(index_root); - } - n.clear_stolen_bits(); - if (below) { - this->unmark(n.right, index_root + 1, indexes); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::delete_all_marked(void) { - static_assert(supports_marks, "does not support marks"); - if (!this->has_marks()) { - return; - } - paranoid_invariant(!this->is_array); - GrowableArray<node_idx> marked_indexes; - marked_indexes.init(); - - // Remove all marks. - // We need to delete all the stolen bits before calling delete_at to prevent barfing. - this->unmark(this->d.t.root, 0, &marked_indexes); - - for (uint32_t i = 0; i < marked_indexes.get_size(); i++) { - // Delete from left to right, shift by number already deleted. - // Alternative is delete from right to left. - int r = this->delete_at(marked_indexes.fetch_unchecked(i) - i); - lazy_assert_zero(r); - } - marked_indexes.deinit(); - barf_if_marked(*this); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::verify_marks_consistent_internal(const subtree &subtree, const bool UU(allow_marks)) const { - if (subtree.is_null()) { + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + int omt<omtdata_t, omtdataout_t, supports_marks>::insert_at( + const omtdata_t &value, + const uint32_t idx) { + barf_if_marked(*this); + if (idx > this->size()) { + return EINVAL; + } + + this->maybe_resize_or_convert(this->size() + 1); + if (this->is_array && idx != this->d.a.num_values && + (idx != 0 || this->d.a.start_idx == 0)) { + this->convert_to_tree(); + } + if (this->is_array) { + if (idx == this->d.a.num_values) { + this->d.a.values[this->d.a.start_idx + this->d.a.num_values] = + value; + } else { + this->d.a.values[--this->d.a.start_idx] = value; + } + this->d.a.num_values++; + } else { + subtree *rebalance_subtree = nullptr; + this->insert_internal( + &this->d.t.root, value, idx, &rebalance_subtree); + if (rebalance_subtree != nullptr) { + this->rebalance(rebalance_subtree); + } + } return 0; } - const omt_node &node = this->d.t.nodes[subtree.get_index()]; - uint32_t num_marks = verify_marks_consistent_internal(node.left, node.get_marks_below()); - num_marks += verify_marks_consistent_internal(node.right, node.get_marks_below()); - if (node.get_marks_below()) { - paranoid_invariant(allow_marks); - paranoid_invariant(num_marks > 0); - } else { - // redundant with invariant below, but nice to have explicitly - paranoid_invariant(num_marks == 0); - } - if (node.get_marked()) { - paranoid_invariant(allow_marks); - ++num_marks; - } - return num_marks; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::verify_marks_consistent(void) const { - static_assert(supports_marks, "does not support marks"); - paranoid_invariant(!this->is_array); - this->verify_marks_consistent_internal(this->d.t.root, true); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> -void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr(iterate_extra_t *const iterate_extra) { - if (this->is_array) { - this->iterate_ptr_internal_array<iterate_extra_t, f>(0, this->size(), iterate_extra); - } else { - this->iterate_ptr_internal<iterate_extra_t, f>(0, this->size(), this->d.t.root, 0, iterate_extra); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -int omt<omtdata_t, omtdataout_t, supports_marks>::fetch(const uint32_t idx, omtdataout_t *const value) const { - if (idx >= this->size()) { return EINVAL; } - if (this->is_array) { - this->fetch_internal_array(idx, value); - } else { - this->fetch_internal(this->d.t.root, idx, value); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_zero(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - uint32_t tmp_index; - uint32_t *const child_idxp = (idxp != nullptr) ? idxp : &tmp_index; - int r; - if (this->is_array) { - r = this->find_internal_zero_array<omtcmp_t, h>(extra, value, child_idxp); - } - else { - r = this->find_internal_zero<omtcmp_t, h>(this->d.t.root, extra, value, child_idxp); - } - return r; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find(const omtcmp_t &extra, int direction, omtdataout_t *const value, uint32_t *const idxp) const { - uint32_t tmp_index; - uint32_t *const child_idxp = (idxp != nullptr) ? idxp : &tmp_index; - paranoid_invariant(direction != 0); - if (direction < 0) { + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + int omt<omtdata_t, omtdataout_t, supports_marks>::set_at( + const omtdata_t &value, + const uint32_t idx) { + barf_if_marked(*this); + if (idx >= this->size()) { + return EINVAL; + } + if (this->is_array) { - return this->find_internal_minus_array<omtcmp_t, h>(extra, value, child_idxp); + this->set_at_internal_array(value, idx); } else { - return this->find_internal_minus<omtcmp_t, h>(this->d.t.root, extra, value, child_idxp); + this->set_at_internal(this->d.t.root, value, idx); + } + return 0; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + int omt<omtdata_t, omtdataout_t, supports_marks>::delete_at( + const uint32_t idx) { + barf_if_marked(*this); + if (idx >= this->size()) { + return EINVAL; + } + + this->maybe_resize_or_convert(this->size() - 1); + if (this->is_array && idx != 0 && idx != this->d.a.num_values - 1) { + this->convert_to_tree(); } - } else { if (this->is_array) { - return this->find_internal_plus_array<omtcmp_t, h>(extra, value, child_idxp); + // Testing for 0 does not rule out it being the last entry. + // Test explicitly for num_values-1 + if (idx != this->d.a.num_values - 1) { + this->d.a.start_idx++; + } + this->d.a.num_values--; } else { - return this->find_internal_plus<omtcmp_t, h>(this->d.t.root, extra, value, child_idxp); + subtree *rebalance_subtree = nullptr; + this->delete_internal( + &this->d.t.root, idx, nullptr, &rebalance_subtree); + if (rebalance_subtree != nullptr) { + this->rebalance(rebalance_subtree); + } } + return 0; } -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -size_t omt<omtdata_t, omtdataout_t, supports_marks>::memory_size(void) { - if (this->is_array) { - return (sizeof *this) + this->capacity * (sizeof this->d.a.values[0]); + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate( + iterate_extra_t *const iterate_extra) const { + return this->iterate_on_range<iterate_extra_t, f>( + 0, this->size(), iterate_extra); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_on_range( + const uint32_t left, + const uint32_t right, + iterate_extra_t *const iterate_extra) const { + if (right > this->size()) { + return EINVAL; + } + if (left == right) { + return 0; + } + if (this->is_array) { + return this->iterate_internal_array<iterate_extra_t, f>( + left, right, iterate_extra); + } + return this->iterate_internal<iterate_extra_t, f>( + left, right, this->d.t.root, 0, iterate_extra); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_and_mark_range( + const uint32_t left, + const uint32_t right, + iterate_extra_t *const iterate_extra) { + static_assert(supports_marks, "does not support marks"); + if (right > this->size()) { + return EINVAL; + } + if (left == right) { + return 0; + } + paranoid_invariant(!this->is_array); + return this->iterate_and_mark_range_internal<iterate_extra_t, f>( + left, right, this->d.t.root, 0, iterate_extra); + } + + // TODO: We can optimize this if we steal 3 bits. 1 bit: this node is + // marked. 1 bit: left subtree has marks. 1 bit: right subtree has marks. + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_over_marked( + iterate_extra_t *const iterate_extra) const { + static_assert(supports_marks, "does not support marks"); + paranoid_invariant(!this->is_array); + return this->iterate_over_marked_internal<iterate_extra_t, f>( + this->d.t.root, 0, iterate_extra); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::unmark( + const subtree &st, + const uint32_t index, + GrowableArray<node_idx> *const indexes) { + if (st.is_null()) { + return; + } + omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t index_root = index + this->nweight(n.left); + + const bool below = n.get_marks_below(); + if (below) { + this->unmark(n.left, index, indexes); + } + if (n.get_marked()) { + indexes->push(index_root); + } + n.clear_stolen_bits(); + if (below) { + this->unmark(n.right, index_root + 1, indexes); + } } - return (sizeof *this) + this->capacity * (sizeof this->d.t.nodes[0]); -} + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::delete_all_marked(void) { + static_assert(supports_marks, "does not support marks"); + if (!this->has_marks()) { + return; + } + paranoid_invariant(!this->is_array); + GrowableArray<node_idx> marked_indexes; + marked_indexes.init(); + + // Remove all marks. + // We need to delete all the stolen bits before calling delete_at to + // prevent barfing. + this->unmark(this->d.t.root, 0, &marked_indexes); + + for (uint32_t i = 0; i < marked_indexes.get_size(); i++) { + // Delete from left to right, shift by number already deleted. + // Alternative is delete from right to left. + int r = this->delete_at(marked_indexes.fetch_unchecked(i) - i); + lazy_assert_zero(r); + } + marked_indexes.deinit(); + barf_if_marked(*this); + } -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create_internal_no_array(const uint32_t new_capacity) { - this->is_array = true; - this->d.a.start_idx = 0; - this->d.a.num_values = 0; - this->d.a.values = nullptr; - this->capacity = new_capacity; -} + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + uint32_t omt<omtdata_t, omtdataout_t, supports_marks>:: + verify_marks_consistent_internal(const subtree &st, + const bool UU(allow_marks)) const { + if (st.is_null()) { + return 0; + } + const omt_node &node = this->d.t.nodes[st.get_index()]; + uint32_t num_marks = + verify_marks_consistent_internal(node.left, node.get_marks_below()); + num_marks += verify_marks_consistent_internal(node.right, + node.get_marks_below()); + if (node.get_marks_below()) { + paranoid_invariant(allow_marks); + paranoid_invariant(num_marks > 0); + } else { + // redundant with invariant below, but nice to have explicitly + paranoid_invariant(num_marks == 0); + } + if (node.get_marked()) { + paranoid_invariant(allow_marks); + ++num_marks; + } + return num_marks; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::verify_marks_consistent( + void) const { + static_assert(supports_marks, "does not support marks"); + paranoid_invariant(!this->is_array); + this->verify_marks_consistent_internal(this->d.t.root, true); + } -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::create_internal(const uint32_t new_capacity) { - this->create_internal_no_array(new_capacity); - XMALLOC_N(this->capacity, this->d.a.values); -} + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename iterate_extra_t, + int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> + void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr( + iterate_extra_t *const iterate_extra) { + if (this->is_array) { + this->iterate_ptr_internal_array<iterate_extra_t, f>( + 0, this->size(), iterate_extra); + } else { + this->iterate_ptr_internal<iterate_extra_t, f>( + 0, this->size(), this->d.t.root, 0, iterate_extra); + } + } -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::nweight(const subtree &subtree) const { - if (subtree.is_null()) { + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + int omt<omtdata_t, omtdataout_t, supports_marks>::fetch( + const uint32_t idx, + omtdataout_t *const value) const { + if (idx >= this->size()) { + return EINVAL; + } + if (this->is_array) { + this->fetch_internal_array(idx, value); + } else { + this->fetch_internal(this->d.t.root, idx, value); + } return 0; - } else { - return this->d.t.nodes[subtree.get_index()].weight; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -typename omt<omtdata_t, omtdataout_t, supports_marks>::node_idx omt<omtdata_t, omtdataout_t, supports_marks>::node_malloc(void) { - paranoid_invariant(this->d.t.free_idx < this->capacity); - omt_node &n = this->d.t.nodes[this->d.t.free_idx]; - n.clear_stolen_bits(); - return this->d.t.free_idx++; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::node_free(const node_idx UU(idx)) { - paranoid_invariant(idx < this->capacity); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::maybe_resize_array(const uint32_t n) { - const uint32_t new_size = n<=2 ? 4 : 2*n; - const uint32_t room = this->capacity - this->d.a.start_idx; - - if (room < n || this->capacity / 2 >= new_size) { - omtdata_t *XMALLOC_N(new_size, tmp_values); - memcpy(tmp_values, &this->d.a.values[this->d.a.start_idx], - this->d.a.num_values * (sizeof tmp_values[0])); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_zero( + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + uint32_t tmp_index; + uint32_t *const child_idxp = (idxp != nullptr) ? idxp : &tmp_index; + int r; + if (this->is_array) { + r = this->find_internal_zero_array<omtcmp_t, h>( + extra, value, child_idxp); + } else { + r = this->find_internal_zero<omtcmp_t, h>( + this->d.t.root, extra, value, child_idxp); + } + return r; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find( + const omtcmp_t &extra, + int direction, + omtdataout_t *const value, + uint32_t *const idxp) const { + uint32_t tmp_index; + uint32_t *const child_idxp = (idxp != nullptr) ? idxp : &tmp_index; + paranoid_invariant(direction != 0); + if (direction < 0) { + if (this->is_array) { + return this->find_internal_minus_array<omtcmp_t, h>( + extra, value, child_idxp); + } else { + return this->find_internal_minus<omtcmp_t, h>( + this->d.t.root, extra, value, child_idxp); + } + } else { + if (this->is_array) { + return this->find_internal_plus_array<omtcmp_t, h>( + extra, value, child_idxp); + } else { + return this->find_internal_plus<omtcmp_t, h>( + this->d.t.root, extra, value, child_idxp); + } + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + size_t omt<omtdata_t, omtdataout_t, supports_marks>::memory_size(void) { + if (this->is_array) { + return (sizeof *this) + + this->capacity * (sizeof this->d.a.values[0]); + } + return (sizeof *this) + this->capacity * (sizeof this->d.t.nodes[0]); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::create_internal_no_array( + const uint32_t new_capacity) { + this->is_array = true; this->d.a.start_idx = 0; - this->capacity = new_size; - toku_free(this->d.a.values); - this->d.a.values = tmp_values; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::fill_array_with_subtree_values(omtdata_t *const array, const subtree &subtree) const { - if (subtree.is_null()) return; - const omt_node &tree = this->d.t.nodes[subtree.get_index()]; - this->fill_array_with_subtree_values(&array[0], tree.left); - array[this->nweight(tree.left)] = tree.value; - this->fill_array_with_subtree_values(&array[this->nweight(tree.left) + 1], tree.right); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::convert_to_array(void) { - if (!this->is_array) { - const uint32_t num_values = this->size(); - uint32_t new_size = 2*num_values; - new_size = new_size < 4 ? 4 : new_size; - - omtdata_t *XMALLOC_N(new_size, tmp_values); - this->fill_array_with_subtree_values(tmp_values, this->d.t.root); - toku_free(this->d.t.nodes); - this->is_array = true; - this->capacity = new_size; - this->d.a.num_values = num_values; - this->d.a.values = tmp_values; - this->d.a.start_idx = 0; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::rebuild_from_sorted_array(subtree *const subtree, const omtdata_t *const values, const uint32_t numvalues) { - if (numvalues==0) { - subtree->set_to_null(); - } else { - const uint32_t halfway = numvalues/2; - const node_idx newidx = this->node_malloc(); - omt_node *const newnode = &this->d.t.nodes[newidx]; - newnode->weight = numvalues; - newnode->value = values[halfway]; - subtree->set_index(newidx); - // update everything before the recursive calls so the second call can be a tail call. - this->rebuild_from_sorted_array(&newnode->left, &values[0], halfway); - this->rebuild_from_sorted_array(&newnode->right, &values[halfway+1], numvalues - (halfway+1)); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::convert_to_tree(void) { - if (this->is_array) { - const uint32_t num_nodes = this->size(); - uint32_t new_size = num_nodes*2; - new_size = new_size < 4 ? 4 : new_size; - - omt_node *XMALLOC_N(new_size, new_nodes); - omtdata_t *const values = this->d.a.values; - omtdata_t *const tmp_values = &values[this->d.a.start_idx]; - this->is_array = false; - this->d.t.nodes = new_nodes; - this->capacity = new_size; - this->d.t.free_idx = 0; - this->d.t.root.set_to_null(); - this->rebuild_from_sorted_array(&this->d.t.root, tmp_values, num_nodes); - toku_free(values); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::maybe_resize_or_convert(const uint32_t n) { - if (this->is_array) { - this->maybe_resize_array(n); - } else { - const uint32_t new_size = n<=2 ? 4 : 2*n; - const uint32_t num_nodes = this->nweight(this->d.t.root); - if ((this->capacity/2 >= new_size) || - (this->d.t.free_idx >= this->capacity && num_nodes < n) || - (this->capacity<n)) { - this->convert_to_array(); - // if we had a free list, the "supports_marks" version could - // just resize, as it is now, we have to convert to and back - // from an array. - if (supports_marks) { - this->convert_to_tree(); + this->d.a.num_values = 0; + this->d.a.values = nullptr; + this->capacity = new_capacity; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::create_internal( + const uint32_t new_capacity) { + this->create_internal_no_array(new_capacity); + XMALLOC_N(this->capacity, this->d.a.values); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + uint32_t omt<omtdata_t, omtdataout_t, supports_marks>::nweight( + const subtree &st) const { + if (st.is_null()) { + return 0; + } else { + return this->d.t.nodes[st.get_index()].weight; + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + typename omt<omtdata_t, omtdataout_t, supports_marks>::node_idx + omt<omtdata_t, omtdataout_t, supports_marks>::node_malloc(void) { + paranoid_invariant(this->d.t.free_idx < this->capacity); + omt_node &n = this->d.t.nodes[this->d.t.free_idx]; + n.clear_stolen_bits(); + return this->d.t.free_idx++; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::node_free( + const node_idx UU(idx)) { + paranoid_invariant(idx < this->capacity); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::maybe_resize_array( + const uint32_t n) { + const uint32_t new_size = n <= 2 ? 4 : 2 * n; + const uint32_t room = this->capacity - this->d.a.start_idx; + + if (room < n || this->capacity / 2 >= new_size) { + omtdata_t *XMALLOC_N(new_size, tmp_values); + memcpy(tmp_values, + &this->d.a.values[this->d.a.start_idx], + this->d.a.num_values * (sizeof tmp_values[0])); + this->d.a.start_idx = 0; + this->capacity = new_size; + toku_free(this->d.a.values); + this->d.a.values = tmp_values; + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>:: + fill_array_with_subtree_values(omtdata_t *const array, + const subtree &st) const { + if (st.is_null()) + return; + const omt_node &tree = this->d.t.nodes[st.get_index()]; + this->fill_array_with_subtree_values(&array[0], tree.left); + array[this->nweight(tree.left)] = tree.value; + this->fill_array_with_subtree_values( + &array[this->nweight(tree.left) + 1], tree.right); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::convert_to_array(void) { + if (!this->is_array) { + const uint32_t num_values = this->size(); + uint32_t new_size = 2 * num_values; + new_size = new_size < 4 ? 4 : new_size; + + omtdata_t *XMALLOC_N(new_size, tmp_values); + this->fill_array_with_subtree_values(tmp_values, this->d.t.root); + toku_free(this->d.t.nodes); + this->is_array = true; + this->capacity = new_size; + this->d.a.num_values = num_values; + this->d.a.values = tmp_values; + this->d.a.start_idx = 0; + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void + omt<omtdata_t, omtdataout_t, supports_marks>::rebuild_from_sorted_array( + subtree *const st, + const omtdata_t *const values, + const uint32_t numvalues) { + if (numvalues == 0) { + st->set_to_null(); + } else { + const uint32_t halfway = numvalues / 2; + const node_idx newidx = this->node_malloc(); + omt_node *const newnode = &this->d.t.nodes[newidx]; + newnode->weight = numvalues; + newnode->value = values[halfway]; + st->set_index(newidx); + // update everything before the recursive calls so the second call + // can be a tail call. + this->rebuild_from_sorted_array( + &newnode->left, &values[0], halfway); + this->rebuild_from_sorted_array(&newnode->right, + &values[halfway + 1], + numvalues - (halfway + 1)); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::convert_to_tree(void) { + if (this->is_array) { + const uint32_t num_nodes = this->size(); + uint32_t new_size = num_nodes * 2; + new_size = new_size < 4 ? 4 : new_size; + + omt_node *XMALLOC_N(new_size, new_nodes); + omtdata_t *const values = this->d.a.values; + omtdata_t *const tmp_values = &values[this->d.a.start_idx]; + this->is_array = false; + this->d.t.nodes = new_nodes; + this->capacity = new_size; + this->d.t.free_idx = 0; + this->d.t.root.set_to_null(); + this->rebuild_from_sorted_array( + &this->d.t.root, tmp_values, num_nodes); + toku_free(values); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::maybe_resize_or_convert( + const uint32_t n) { + if (this->is_array) { + this->maybe_resize_array(n); + } else { + const uint32_t new_size = n <= 2 ? 4 : 2 * n; + const uint32_t num_nodes = this->nweight(this->d.t.root); + if ((this->capacity / 2 >= new_size) || + (this->d.t.free_idx >= this->capacity && num_nodes < n) || + (this->capacity < n)) { + this->convert_to_array(); + // if we had a free list, the "supports_marks" version could + // just resize, as it is now, we have to convert to and back + // from an array. + if (supports_marks) { + this->convert_to_tree(); + } } } } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -bool omt<omtdata_t, omtdataout_t, supports_marks>::will_need_rebalance(const subtree &subtree, const int leftmod, const int rightmod) const { - if (subtree.is_null()) { return false; } - const omt_node &n = this->d.t.nodes[subtree.get_index()]; - // one of the 1's is for the root. - // the other is to take ceil(n/2) - const uint32_t weight_left = this->nweight(n.left) + leftmod; - const uint32_t weight_right = this->nweight(n.right) + rightmod; - return ((1+weight_left < (1+1+weight_right)/2) - || - (1+weight_right < (1+1+weight_left)/2)); -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::insert_internal(subtree *const subtreep, const omtdata_t &value, const uint32_t idx, subtree **const rebalance_subtree) { - if (subtreep->is_null()) { - paranoid_invariant_zero(idx); - const node_idx newidx = this->node_malloc(); - omt_node *const newnode = &this->d.t.nodes[newidx]; - newnode->weight = 1; - newnode->left.set_to_null(); - newnode->right.set_to_null(); - newnode->value = value; - subtreep->set_index(newidx); - } else { + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + bool omt<omtdata_t, omtdataout_t, supports_marks>::will_need_rebalance( + const subtree &st, + const int leftmod, + const int rightmod) const { + if (st.is_null()) { + return false; + } + const omt_node &n = this->d.t.nodes[st.get_index()]; + // one of the 1's is for the root. + // the other is to take ceil(n/2) + const uint32_t weight_left = this->nweight(n.left) + leftmod; + const uint32_t weight_right = this->nweight(n.right) + rightmod; + return ((1 + weight_left < (1 + 1 + weight_right) / 2) || + (1 + weight_right < (1 + 1 + weight_left) / 2)); + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::insert_internal( + subtree *const subtreep, + const omtdata_t &value, + const uint32_t idx, + subtree **const rebalance_subtree) { + if (subtreep->is_null()) { + paranoid_invariant_zero(idx); + const node_idx newidx = this->node_malloc(); + omt_node *const newnode = &this->d.t.nodes[newidx]; + newnode->weight = 1; + newnode->left.set_to_null(); + newnode->right.set_to_null(); + newnode->value = value; + subtreep->set_index(newidx); + } else { + omt_node &n = this->d.t.nodes[subtreep->get_index()]; + n.weight++; + if (idx <= this->nweight(n.left)) { + if (*rebalance_subtree == nullptr && + this->will_need_rebalance(*subtreep, 1, 0)) { + *rebalance_subtree = subtreep; + } + this->insert_internal(&n.left, value, idx, rebalance_subtree); + } else { + if (*rebalance_subtree == nullptr && + this->will_need_rebalance(*subtreep, 0, 1)) { + *rebalance_subtree = subtreep; + } + const uint32_t sub_index = idx - this->nweight(n.left) - 1; + this->insert_internal( + &n.right, value, sub_index, rebalance_subtree); + } + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::set_at_internal_array( + const omtdata_t &value, + const uint32_t idx) { + this->d.a.values[this->d.a.start_idx + idx] = value; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::set_at_internal( + const subtree &st, + const omtdata_t &value, + const uint32_t idx) { + paranoid_invariant(!st.is_null()); + omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t leftweight = this->nweight(n.left); + if (idx < leftweight) { + this->set_at_internal(n.left, value, idx); + } else if (idx == leftweight) { + n.value = value; + } else { + this->set_at_internal(n.right, value, idx - leftweight - 1); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::delete_internal( + subtree *const subtreep, + const uint32_t idx, + omt_node *const copyn, + subtree **const rebalance_subtree) { + paranoid_invariant_notnull(subtreep); + paranoid_invariant_notnull(rebalance_subtree); + paranoid_invariant(!subtreep->is_null()); omt_node &n = this->d.t.nodes[subtreep->get_index()]; - n.weight++; - if (idx <= this->nweight(n.left)) { - if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 1, 0)) { + const uint32_t leftweight = this->nweight(n.left); + if (idx < leftweight) { + n.weight--; + if (*rebalance_subtree == nullptr && + this->will_need_rebalance(*subtreep, -1, 0)) { *rebalance_subtree = subtreep; } - this->insert_internal(&n.left, value, idx, rebalance_subtree); + this->delete_internal(&n.left, idx, copyn, rebalance_subtree); + } else if (idx == leftweight) { + if (n.left.is_null()) { + const uint32_t oldidx = subtreep->get_index(); + *subtreep = n.right; + if (copyn != nullptr) { + copyn->value = n.value; + } + this->node_free(oldidx); + } else if (n.right.is_null()) { + const uint32_t oldidx = subtreep->get_index(); + *subtreep = n.left; + if (copyn != nullptr) { + copyn->value = n.value; + } + this->node_free(oldidx); + } else { + if (*rebalance_subtree == nullptr && + this->will_need_rebalance(*subtreep, 0, -1)) { + *rebalance_subtree = subtreep; + } + // don't need to copy up value, it's only used by this + // next call, and when that gets to the bottom there + // won't be any more recursion + n.weight--; + this->delete_internal(&n.right, 0, &n, rebalance_subtree); + } } else { - if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 0, 1)) { + n.weight--; + if (*rebalance_subtree == nullptr && + this->will_need_rebalance(*subtreep, 0, -1)) { *rebalance_subtree = subtreep; } - const uint32_t sub_index = idx - this->nweight(n.left) - 1; - this->insert_internal(&n.right, value, sub_index, rebalance_subtree); - } - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::set_at_internal_array(const omtdata_t &value, const uint32_t idx) { - this->d.a.values[this->d.a.start_idx + idx] = value; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::set_at_internal(const subtree &subtree, const omtdata_t &value, const uint32_t idx) { - paranoid_invariant(!subtree.is_null()); - omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t leftweight = this->nweight(n.left); - if (idx < leftweight) { - this->set_at_internal(n.left, value, idx); - } else if (idx == leftweight) { - n.value = value; - } else { - this->set_at_internal(n.right, value, idx - leftweight - 1); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::delete_internal(subtree *const subtreep, const uint32_t idx, omt_node *const copyn, subtree **const rebalance_subtree) { - paranoid_invariant_notnull(subtreep); - paranoid_invariant_notnull(rebalance_subtree); - paranoid_invariant(!subtreep->is_null()); - omt_node &n = this->d.t.nodes[subtreep->get_index()]; - const uint32_t leftweight = this->nweight(n.left); - if (idx < leftweight) { - n.weight--; - if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, -1, 0)) { - *rebalance_subtree = subtreep; - } - this->delete_internal(&n.left, idx, copyn, rebalance_subtree); - } else if (idx == leftweight) { - if (n.left.is_null()) { - const uint32_t oldidx = subtreep->get_index(); - *subtreep = n.right; - if (copyn != nullptr) { - copyn->value = n.value; + this->delete_internal( + &n.right, idx - leftweight - 1, copyn, rebalance_subtree); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_internal_array( + const uint32_t left, + const uint32_t right, + iterate_extra_t *const iterate_extra) const { + int r; + for (uint32_t i = left; i < right; ++i) { + r = f(this->d.a.values[this->d.a.start_idx + i], i, iterate_extra); + if (r != 0) { + return r; } - this->node_free(oldidx); - } else if (n.right.is_null()) { - const uint32_t oldidx = subtreep->get_index(); - *subtreep = n.left; - if (copyn != nullptr) { - copyn->value = n.value; + } + return 0; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename iterate_extra_t, + int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> + void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr_internal( + const uint32_t left, + const uint32_t right, + const subtree &st, + const uint32_t idx, + iterate_extra_t *const iterate_extra) { + if (!st.is_null()) { + omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t idx_root = idx + this->nweight(n.left); + if (left < idx_root) { + this->iterate_ptr_internal<iterate_extra_t, f>( + left, right, n.left, idx, iterate_extra); } - this->node_free(oldidx); - } else { - if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 0, -1)) { - *rebalance_subtree = subtreep; + if (left <= idx_root && idx_root < right) { + int r = f(&n.value, idx_root, iterate_extra); + lazy_assert_zero(r); + } + if (idx_root + 1 < right) { + this->iterate_ptr_internal<iterate_extra_t, f>( + left, right, n.right, idx_root + 1, iterate_extra); } - // don't need to copy up value, it's only used by this - // next call, and when that gets to the bottom there - // won't be any more recursion - n.weight--; - this->delete_internal(&n.right, 0, &n, rebalance_subtree); - } - } else { - n.weight--; - if (*rebalance_subtree == nullptr && this->will_need_rebalance(*subtreep, 0, -1)) { - *rebalance_subtree = subtreep; - } - this->delete_internal(&n.right, idx - leftweight - 1, copyn, rebalance_subtree); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_internal_array(const uint32_t left, const uint32_t right, - iterate_extra_t *const iterate_extra) const { - int r; - for (uint32_t i = left; i < right; ++i) { - r = f(this->d.a.values[this->d.a.start_idx + i], i, iterate_extra); - if (r != 0) { - return r; } } - return 0; -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> -void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr_internal(const uint32_t left, const uint32_t right, - const subtree &subtree, const uint32_t idx, - iterate_extra_t *const iterate_extra) { - if (!subtree.is_null()) { - omt_node &n = this->d.t.nodes[subtree.get_index()]; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename iterate_extra_t, + int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> + void + omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr_internal_array( + const uint32_t left, + const uint32_t right, + iterate_extra_t *const iterate_extra) { + for (uint32_t i = left; i < right; ++i) { + int r = + f(&this->d.a.values[this->d.a.start_idx + i], i, iterate_extra); + lazy_assert_zero(r); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_internal( + const uint32_t left, + const uint32_t right, + const subtree &st, + const uint32_t idx, + iterate_extra_t *const iterate_extra) const { + if (st.is_null()) { + return 0; + } + int r; + const omt_node &n = this->d.t.nodes[st.get_index()]; const uint32_t idx_root = idx + this->nweight(n.left); if (left < idx_root) { - this->iterate_ptr_internal<iterate_extra_t, f>(left, right, n.left, idx, iterate_extra); + r = this->iterate_internal<iterate_extra_t, f>( + left, right, n.left, idx, iterate_extra); + if (r != 0) { + return r; + } } if (left <= idx_root && idx_root < right) { - int r = f(&n.value, idx_root, iterate_extra); - lazy_assert_zero(r); + r = f(n.value, idx_root, iterate_extra); + if (r != 0) { + return r; + } } if (idx_root + 1 < right) { - this->iterate_ptr_internal<iterate_extra_t, f>(left, right, n.right, idx_root + 1, iterate_extra); - } - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(omtdata_t *, const uint32_t, iterate_extra_t *const)> -void omt<omtdata_t, omtdataout_t, supports_marks>::iterate_ptr_internal_array(const uint32_t left, const uint32_t right, - iterate_extra_t *const iterate_extra) { - for (uint32_t i = left; i < right; ++i) { - int r = f(&this->d.a.values[this->d.a.start_idx + i], i, iterate_extra); - lazy_assert_zero(r); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_internal(const uint32_t left, const uint32_t right, - const subtree &subtree, const uint32_t idx, - iterate_extra_t *const iterate_extra) const { - if (subtree.is_null()) { return 0; } - int r; - const omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t idx_root = idx + this->nweight(n.left); - if (left < idx_root) { - r = this->iterate_internal<iterate_extra_t, f>(left, right, n.left, idx, iterate_extra); - if (r != 0) { return r; } - } - if (left <= idx_root && idx_root < right) { - r = f(n.value, idx_root, iterate_extra); - if (r != 0) { return r; } - } - if (idx_root + 1 < right) { - return this->iterate_internal<iterate_extra_t, f>(left, right, n.right, idx_root + 1, iterate_extra); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_and_mark_range_internal(const uint32_t left, const uint32_t right, - const subtree &subtree, const uint32_t idx, - iterate_extra_t *const iterate_extra) { - paranoid_invariant(!subtree.is_null()); - int r; - omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t idx_root = idx + this->nweight(n.left); - if (left < idx_root && !n.left.is_null()) { - n.set_marks_below_bit(); - r = this->iterate_and_mark_range_internal<iterate_extra_t, f>(left, right, n.left, idx, iterate_extra); - if (r != 0) { return r; } - } - if (left <= idx_root && idx_root < right) { - n.set_marked_bit(); - r = f(n.value, idx_root, iterate_extra); - if (r != 0) { return r; } - } - if (idx_root + 1 < right && !n.right.is_null()) { - n.set_marks_below_bit(); - return this->iterate_and_mark_range_internal<iterate_extra_t, f>(left, right, n.right, idx_root + 1, iterate_extra); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename iterate_extra_t, - int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> -int omt<omtdata_t, omtdataout_t, supports_marks>::iterate_over_marked_internal(const subtree &subtree, const uint32_t idx, - iterate_extra_t *const iterate_extra) const { - if (subtree.is_null()) { return 0; } - int r; - const omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t idx_root = idx + this->nweight(n.left); - if (n.get_marks_below()) { - r = this->iterate_over_marked_internal<iterate_extra_t, f>(n.left, idx, iterate_extra); - if (r != 0) { return r; } - } - if (n.get_marked()) { - r = f(n.value, idx_root, iterate_extra); - if (r != 0) { return r; } - } - if (n.get_marks_below()) { - return this->iterate_over_marked_internal<iterate_extra_t, f>(n.right, idx_root + 1, iterate_extra); - } - return 0; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::fetch_internal_array(const uint32_t i, omtdataout_t *const value) const { - if (value != nullptr) { - copyout(value, &this->d.a.values[this->d.a.start_idx + i]); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::fetch_internal(const subtree &subtree, const uint32_t i, omtdataout_t *const value) const { - omt_node &n = this->d.t.nodes[subtree.get_index()]; - const uint32_t leftweight = this->nweight(n.left); - if (i < leftweight) { - this->fetch_internal(n.left, i, value); - } else if (i == leftweight) { - if (value != nullptr) { - copyout(value, &n); - } - } else { - this->fetch_internal(n.right, i - leftweight - 1, value); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::fill_array_with_subtree_idxs(node_idx *const array, const subtree &subtree) const { - if (!subtree.is_null()) { - const omt_node &tree = this->d.t.nodes[subtree.get_index()]; - this->fill_array_with_subtree_idxs(&array[0], tree.left); - array[this->nweight(tree.left)] = subtree.get_index(); - this->fill_array_with_subtree_idxs(&array[this->nweight(tree.left) + 1], tree.right); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::rebuild_subtree_from_idxs(subtree *const subtree, const node_idx *const idxs, const uint32_t numvalues) { - if (numvalues==0) { - subtree->set_to_null(); - } else { - uint32_t halfway = numvalues/2; - subtree->set_index(idxs[halfway]); - //node_idx newidx = idxs[halfway]; - omt_node &newnode = this->d.t.nodes[subtree->get_index()]; - newnode.weight = numvalues; - // value is already in there. - this->rebuild_subtree_from_idxs(&newnode.left, &idxs[0], halfway); - this->rebuild_subtree_from_idxs(&newnode.right, &idxs[halfway+1], numvalues-(halfway+1)); - //n_idx = newidx; - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::rebalance(subtree *const subtree) { - node_idx idx = subtree->get_index(); - if (idx==this->d.t.root.get_index()) { - //Try to convert to an array. - //If this fails, (malloc) nothing will have changed. - //In the failure case we continue on to the standard rebalance - //algorithm. - this->convert_to_array(); - if (supports_marks) { - this->convert_to_tree(); + return this->iterate_internal<iterate_extra_t, f>( + left, right, n.right, idx_root + 1, iterate_extra); } - } else { - const omt_node &n = this->d.t.nodes[idx]; - node_idx *tmp_array; - size_t mem_needed = n.weight * (sizeof tmp_array[0]); - size_t mem_free = (this->capacity - this->d.t.free_idx) * (sizeof this->d.t.nodes[0]); - bool malloced; - if (mem_needed<=mem_free) { - //There is sufficient free space at the end of the nodes array - //to hold enough node indexes to rebalance. - malloced = false; - tmp_array = reinterpret_cast<node_idx *>(&this->d.t.nodes[this->d.t.free_idx]); - } - else { - malloced = true; - XMALLOC_N(n.weight, tmp_array); - } - this->fill_array_with_subtree_idxs(tmp_array, *subtree); - this->rebuild_subtree_from_idxs(subtree, tmp_array, n.weight); - if (malloced) toku_free(tmp_array); - } -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t *const out, const omt_node *const n) { - *out = n->value; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t **const out, omt_node *const n) { - *out = &n->value; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t *const out, const omtdata_t *const stored_value_ptr) { - *out = *stored_value_ptr; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -void omt<omtdata_t, omtdataout_t, supports_marks>::copyout(omtdata_t **const out, omtdata_t *const stored_value_ptr) { - *out = stored_value_ptr; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_zero_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - uint32_t min = this->d.a.start_idx; - uint32_t limit = this->d.a.start_idx + this->d.a.num_values; - uint32_t best_pos = subtree::NODE_NULL; - uint32_t best_zero = subtree::NODE_NULL; - - while (min!=limit) { - uint32_t mid = (min + limit) / 2; - int hv = h(this->d.a.values[mid], extra); - if (hv<0) { - min = mid+1; - } - else if (hv>0) { - best_pos = mid; - limit = mid; - } - else { - best_zero = mid; - limit = mid; - } - } - if (best_zero!=subtree::NODE_NULL) { - //Found a zero - if (value != nullptr) { - copyout(value, &this->d.a.values[best_zero]); + return 0; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int omt<omtdata_t, omtdataout_t, supports_marks>:: + iterate_and_mark_range_internal(const uint32_t left, + const uint32_t right, + const subtree &st, + const uint32_t idx, + iterate_extra_t *const iterate_extra) { + paranoid_invariant(!st.is_null()); + int r; + omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t idx_root = idx + this->nweight(n.left); + if (left < idx_root && !n.left.is_null()) { + n.set_marks_below_bit(); + r = this->iterate_and_mark_range_internal<iterate_extra_t, f>( + left, right, n.left, idx, iterate_extra); + if (r != 0) { + return r; + } + } + if (left <= idx_root && idx_root < right) { + n.set_marked_bit(); + r = f(n.value, idx_root, iterate_extra); + if (r != 0) { + return r; + } + } + if (idx_root + 1 < right && !n.right.is_null()) { + n.set_marks_below_bit(); + return this->iterate_and_mark_range_internal<iterate_extra_t, f>( + left, right, n.right, idx_root + 1, iterate_extra); } - *idxp = best_zero - this->d.a.start_idx; return 0; } - if (best_pos!=subtree::NODE_NULL) *idxp = best_pos - this->d.a.start_idx; - else *idxp = this->d.a.num_values; - return DB_NOTFOUND; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_zero(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - if (subtree.is_null()) { - *idxp = 0; - return DB_NOTFOUND; + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template < + typename iterate_extra_t, + int (*f)(const omtdata_t &, const uint32_t, iterate_extra_t *const)> + int + omt<omtdata_t, omtdataout_t, supports_marks>::iterate_over_marked_internal( + const subtree &st, + const uint32_t idx, + iterate_extra_t *const iterate_extra) const { + if (st.is_null()) { + return 0; + } + int r; + const omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t idx_root = idx + this->nweight(n.left); + if (n.get_marks_below()) { + r = this->iterate_over_marked_internal<iterate_extra_t, f>( + n.left, idx, iterate_extra); + if (r != 0) { + return r; + } + } + if (n.get_marked()) { + r = f(n.value, idx_root, iterate_extra); + if (r != 0) { + return r; + } + } + if (n.get_marks_below()) { + return this->iterate_over_marked_internal<iterate_extra_t, f>( + n.right, idx_root + 1, iterate_extra); + } + return 0; } - omt_node &n = this->d.t.nodes[subtree.get_index()]; - int hv = h(n.value, extra); - if (hv<0) { - int r = this->find_internal_zero<omtcmp_t, h>(n.right, extra, value, idxp); - *idxp += this->nweight(n.left)+1; - return r; - } else if (hv>0) { - return this->find_internal_zero<omtcmp_t, h>(n.left, extra, value, idxp); - } else { - int r = this->find_internal_zero<omtcmp_t, h>(n.left, extra, value, idxp); - if (r==DB_NOTFOUND) { - *idxp = this->nweight(n.left); + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::fetch_internal_array( + const uint32_t i, + omtdataout_t *const value) const { + if (value != nullptr) { + copyout(value, &this->d.a.values[this->d.a.start_idx + i]); + } + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::fetch_internal( + const subtree &st, + const uint32_t i, + omtdataout_t *const value) const { + omt_node &n = this->d.t.nodes[st.get_index()]; + const uint32_t leftweight = this->nweight(n.left); + if (i < leftweight) { + this->fetch_internal(n.left, i, value); + } else if (i == leftweight) { if (value != nullptr) { copyout(value, &n); } - r = 0; + } else { + this->fetch_internal(n.right, i - leftweight - 1, value); } - return r; } -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_plus_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - uint32_t min = this->d.a.start_idx; - uint32_t limit = this->d.a.start_idx + this->d.a.num_values; - uint32_t best = subtree::NODE_NULL; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void + omt<omtdata_t, omtdataout_t, supports_marks>::fill_array_with_subtree_idxs( + node_idx *const array, + const subtree &st) const { + if (!st.is_null()) { + const omt_node &tree = this->d.t.nodes[st.get_index()]; + this->fill_array_with_subtree_idxs(&array[0], tree.left); + array[this->nweight(tree.left)] = st.get_index(); + this->fill_array_with_subtree_idxs( + &array[this->nweight(tree.left) + 1], tree.right); + } + } - while (min != limit) { - const uint32_t mid = (min + limit) / 2; - const int hv = h(this->d.a.values[mid], extra); - if (hv > 0) { - best = mid; - limit = mid; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void + omt<omtdata_t, omtdataout_t, supports_marks>::rebuild_subtree_from_idxs( + subtree *const st, + const node_idx *const idxs, + const uint32_t numvalues) { + if (numvalues == 0) { + st->set_to_null(); } else { - min = mid + 1; + uint32_t halfway = numvalues / 2; + st->set_index(idxs[halfway]); + // node_idx newidx = idxs[halfway]; + omt_node &newnode = this->d.t.nodes[st->get_index()]; + newnode.weight = numvalues; + // value is already in there. + this->rebuild_subtree_from_idxs(&newnode.left, &idxs[0], halfway); + this->rebuild_subtree_from_idxs( + &newnode.right, &idxs[halfway + 1], numvalues - (halfway + 1)); + // n_idx = newidx; } } - if (best == subtree::NODE_NULL) { return DB_NOTFOUND; } - if (value != nullptr) { - copyout(value, &this->d.a.values[best]); - } - *idxp = best - this->d.a.start_idx; - return 0; -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_plus(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - if (subtree.is_null()) { - return DB_NOTFOUND; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::rebalance( + subtree *const st) { + node_idx idx = st->get_index(); + if (idx == this->d.t.root.get_index()) { + // Try to convert to an array. + // If this fails, (malloc) nothing will have changed. + // In the failure case we continue on to the standard rebalance + // algorithm. + this->convert_to_array(); + if (supports_marks) { + this->convert_to_tree(); + } + } else { + const omt_node &n = this->d.t.nodes[idx]; + node_idx *tmp_array; + size_t mem_needed = n.weight * (sizeof tmp_array[0]); + size_t mem_free = (this->capacity - this->d.t.free_idx) * + (sizeof this->d.t.nodes[0]); + bool malloced; + if (mem_needed <= mem_free) { + // There is sufficient free space at the end of the nodes array + // to hold enough node indexes to rebalance. + malloced = false; + tmp_array = reinterpret_cast<node_idx *>( + &this->d.t.nodes[this->d.t.free_idx]); + } else { + malloced = true; + XMALLOC_N(n.weight, tmp_array); + } + this->fill_array_with_subtree_idxs(tmp_array, *st); + this->rebuild_subtree_from_idxs(st, tmp_array, n.weight); + if (malloced) + toku_free(tmp_array); + } } - omt_node *const n = &this->d.t.nodes[subtree.get_index()]; - int hv = h(n->value, extra); - int r; - if (hv > 0) { - r = this->find_internal_plus<omtcmp_t, h>(n->left, extra, value, idxp); - if (r == DB_NOTFOUND) { - *idxp = this->nweight(n->left); - if (value != nullptr) { - copyout(value, n); + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::copyout( + omtdata_t *const out, + const omt_node *const n) { + *out = n->value; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::copyout( + omtdata_t **const out, + omt_node *const n) { + *out = &n->value; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::copyout( + omtdata_t *const out, + const omtdata_t *const stored_value_ptr) { + *out = *stored_value_ptr; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + void omt<omtdata_t, omtdataout_t, supports_marks>::copyout( + omtdata_t **const out, + omtdata_t *const stored_value_ptr) { + *out = stored_value_ptr; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_zero_array( + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + uint32_t min = this->d.a.start_idx; + uint32_t limit = this->d.a.start_idx + this->d.a.num_values; + uint32_t best_pos = subtree::NODE_NULL; + uint32_t best_zero = subtree::NODE_NULL; + + while (min != limit) { + uint32_t mid = (min + limit) / 2; + int hv = h(this->d.a.values[mid], extra); + if (hv < 0) { + min = mid + 1; + } else if (hv > 0) { + best_pos = mid; + limit = mid; + } else { + best_zero = mid; + limit = mid; } - r = 0; } - } else { - r = this->find_internal_plus<omtcmp_t, h>(n->right, extra, value, idxp); - if (r == 0) { - *idxp += this->nweight(n->left) + 1; + if (best_zero != subtree::NODE_NULL) { + // Found a zero + if (value != nullptr) { + copyout(value, &this->d.a.values[best_zero]); + } + *idxp = best_zero - this->d.a.start_idx; + return 0; } + if (best_pos != subtree::NODE_NULL) + *idxp = best_pos - this->d.a.start_idx; + else + *idxp = this->d.a.num_values; + return DB_NOTFOUND; } - return r; -} - -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_minus_array(const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - uint32_t min = this->d.a.start_idx; - uint32_t limit = this->d.a.start_idx + this->d.a.num_values; - uint32_t best = subtree::NODE_NULL; - while (min != limit) { - const uint32_t mid = (min + limit) / 2; - const int hv = h(this->d.a.values[mid], extra); + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_zero( + const subtree &st, + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + if (st.is_null()) { + *idxp = 0; + return DB_NOTFOUND; + } + omt_node &n = this->d.t.nodes[st.get_index()]; + int hv = h(n.value, extra); if (hv < 0) { - best = mid; - min = mid + 1; + int r = this->find_internal_zero<omtcmp_t, h>( + n.right, extra, value, idxp); + *idxp += this->nweight(n.left) + 1; + return r; + } else if (hv > 0) { + return this->find_internal_zero<omtcmp_t, h>( + n.left, extra, value, idxp); } else { - limit = mid; + int r = this->find_internal_zero<omtcmp_t, h>( + n.left, extra, value, idxp); + if (r == DB_NOTFOUND) { + *idxp = this->nweight(n.left); + if (value != nullptr) { + copyout(value, &n); + } + r = 0; + } + return r; } } - if (best == subtree::NODE_NULL) { return DB_NOTFOUND; } - if (value != nullptr) { - copyout(value, &this->d.a.values[best]); - } - *idxp = best - this->d.a.start_idx; - return 0; -} -template<typename omtdata_t, typename omtdataout_t, bool supports_marks> -template<typename omtcmp_t, - int (*h)(const omtdata_t &, const omtcmp_t &)> -int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_minus(const subtree &subtree, const omtcmp_t &extra, omtdataout_t *const value, uint32_t *const idxp) const { - paranoid_invariant_notnull(idxp); - if (subtree.is_null()) { - return DB_NOTFOUND; + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_plus_array( + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + uint32_t min = this->d.a.start_idx; + uint32_t limit = this->d.a.start_idx + this->d.a.num_values; + uint32_t best = subtree::NODE_NULL; + + while (min != limit) { + const uint32_t mid = (min + limit) / 2; + const int hv = h(this->d.a.values[mid], extra); + if (hv > 0) { + best = mid; + limit = mid; + } else { + min = mid + 1; + } + } + if (best == subtree::NODE_NULL) { + return DB_NOTFOUND; + } + if (value != nullptr) { + copyout(value, &this->d.a.values[best]); + } + *idxp = best - this->d.a.start_idx; + return 0; } - omt_node *const n = &this->d.t.nodes[subtree.get_index()]; - int hv = h(n->value, extra); - if (hv < 0) { - int r = this->find_internal_minus<omtcmp_t, h>(n->right, extra, value, idxp); - if (r == 0) { - *idxp += this->nweight(n->left) + 1; - } else if (r == DB_NOTFOUND) { - *idxp = this->nweight(n->left); - if (value != nullptr) { - copyout(value, n); + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_plus( + const subtree &st, + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + if (st.is_null()) { + return DB_NOTFOUND; + } + omt_node *const n = &this->d.t.nodes[st.get_index()]; + int hv = h(n->value, extra); + int r; + if (hv > 0) { + r = this->find_internal_plus<omtcmp_t, h>( + n->left, extra, value, idxp); + if (r == DB_NOTFOUND) { + *idxp = this->nweight(n->left); + if (value != nullptr) { + copyout(value, n); + } + r = 0; + } + } else { + r = this->find_internal_plus<omtcmp_t, h>( + n->right, extra, value, idxp); + if (r == 0) { + *idxp += this->nweight(n->left) + 1; } - r = 0; } return r; - } else { - return this->find_internal_minus<omtcmp_t, h>(n->left, extra, value, idxp); } -} -} // namespace toku + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_minus_array( + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + uint32_t min = this->d.a.start_idx; + uint32_t limit = this->d.a.start_idx + this->d.a.num_values; + uint32_t best = subtree::NODE_NULL; + + while (min != limit) { + const uint32_t mid = (min + limit) / 2; + const int hv = h(this->d.a.values[mid], extra); + if (hv < 0) { + best = mid; + min = mid + 1; + } else { + limit = mid; + } + } + if (best == subtree::NODE_NULL) { + return DB_NOTFOUND; + } + if (value != nullptr) { + copyout(value, &this->d.a.values[best]); + } + *idxp = best - this->d.a.start_idx; + return 0; + } + + template <typename omtdata_t, typename omtdataout_t, bool supports_marks> + template <typename omtcmp_t, int (*h)(const omtdata_t &, const omtcmp_t &)> + int omt<omtdata_t, omtdataout_t, supports_marks>::find_internal_minus( + const subtree &st, + const omtcmp_t &extra, + omtdataout_t *const value, + uint32_t *const idxp) const { + paranoid_invariant_notnull(idxp); + if (st.is_null()) { + return DB_NOTFOUND; + } + omt_node *const n = &this->d.t.nodes[st.get_index()]; + int hv = h(n->value, extra); + if (hv < 0) { + int r = this->find_internal_minus<omtcmp_t, h>( + n->right, extra, value, idxp); + if (r == 0) { + *idxp += this->nweight(n->left) + 1; + } else if (r == DB_NOTFOUND) { + *idxp = this->nweight(n->left); + if (value != nullptr) { + copyout(value, n); + } + r = 0; + } + return r; + } else { + return this->find_internal_minus<omtcmp_t, h>( + n->left, extra, value, idxp); + } + } +} // namespace toku diff --git a/storage/tokudb/PerconaFT/util/omt.h b/storage/tokudb/PerconaFT/util/omt.h index 36946401381..dc26b2d5718 100644 --- a/storage/tokudb/PerconaFT/util/omt.h +++ b/storage/tokudb/PerconaFT/util/omt.h @@ -32,6 +32,19 @@ Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. You should have received a copy of the GNU Affero General Public License along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. + +---------------------------------------- + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and ======= */ #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." diff --git a/storage/tokudb/ha_tokudb.cc b/storage/tokudb/ha_tokudb.cc index 4196440ec79..b8f6a732585 100644 --- a/storage/tokudb/ha_tokudb.cc +++ b/storage/tokudb/ha_tokudb.cc @@ -7241,6 +7241,16 @@ int ha_tokudb::create( tokudb_trx_data *trx = NULL; THD* thd = ha_thd(); + String database_name, table_name, dictionary_name; + tokudb_split_dname(name, database_name, table_name, dictionary_name); + if (database_name.is_empty() || table_name.is_empty()) { + push_warning_printf(thd, + Sql_condition::WARN_LEVEL_WARN, + ER_TABLE_NAME, + "TokuDB: Table Name or Database Name is empty"); + DBUG_RETURN(ER_TABLE_NAME); + } + memset(&kc_info, 0, sizeof(kc_info)); #if 100000 <= MYSQL_VERSION_ID && MYSQL_VERSION_ID <= 100999 diff --git a/storage/tokudb/hatoku_hton.cc b/storage/tokudb/hatoku_hton.cc index b03b8c72f08..81355ea20ff 100644 --- a/storage/tokudb/hatoku_hton.cc +++ b/storage/tokudb/hatoku_hton.cc @@ -571,10 +571,10 @@ static int tokudb_init_func(void *p) { db_env->set_update(db_env, tokudb_update_fun); - db_env_set_direct_io(tokudb::sysvars::directio == TRUE); + db_env_set_direct_io(tokudb::sysvars::directio); db_env_set_compress_buffers_before_eviction( - tokudb::sysvars::compress_buffers_before_eviction == TRUE); + tokudb::sysvars::compress_buffers_before_eviction); db_env->change_fsync_log_period(db_env, tokudb::sysvars::fsync_log_period); diff --git a/storage/tokudb/hatoku_hton.h b/storage/tokudb/hatoku_hton.h index e632a9afe88..816a66aa440 100644 --- a/storage/tokudb/hatoku_hton.h +++ b/storage/tokudb/hatoku_hton.h @@ -190,7 +190,6 @@ inline bool tokudb_killed_thd_callback(void* extra, return thd_kill_level(thd) != 0; } -extern HASH tokudb_open_tables; extern const char* tokudb_hton_name; extern int tokudb_hton_initialized; extern tokudb::thread::rwlock_t tokudb_hton_initialized_lock; diff --git a/storage/tokudb/mysql-test/tokudb_bugs/r/PS-4979.result b/storage/tokudb/mysql-test/tokudb_bugs/r/PS-4979.result new file mode 100644 index 00000000000..5bf7a270fe5 --- /dev/null +++ b/storage/tokudb/mysql-test/tokudb_bugs/r/PS-4979.result @@ -0,0 +1,2 @@ +CREATE TABLE `#mysql50#q.q`(f1 INT KEY) ENGINE=TOKUDB; +ERROR 42000: Incorrect table name '#mysql50#q.q' diff --git a/storage/tokudb/mysql-test/tokudb_bugs/t/PS-4979.test b/storage/tokudb/mysql-test/tokudb_bugs/t/PS-4979.test new file mode 100644 index 00000000000..cb902f6e52a --- /dev/null +++ b/storage/tokudb/mysql-test/tokudb_bugs/t/PS-4979.test @@ -0,0 +1,13 @@ +--source include/have_tokudb.inc +# PS-4979 : Dropping TokuDB table with non-alphanumeric characters could lead +# to a crash +# +# `#mysql50#q.q` is an invalid table name, but the server side doesn't detect it +# and complain. Instead it passes in an empty table name to the engine. The +# engine expects a table name in the form of a relative path like +# "./databasename/tablename". InnoDB detects this in parsing the table name +# during the creation and returns an error. +# MariaDB server detect above error. + +--error ER_WRONG_TABLE_NAME +CREATE TABLE `#mysql50#q.q`(f1 INT KEY) ENGINE=TOKUDB; diff --git a/storage/tokudb/tokudb_background.cc b/storage/tokudb/tokudb_background.cc index 13e0e9321cc..19f03dbca65 100644 --- a/storage/tokudb/tokudb_background.cc +++ b/storage/tokudb/tokudb_background.cc @@ -182,14 +182,14 @@ void* job_manager_t::real_thread_func() { if (res == tokudb::thread::semaphore_t::E_INTERRUPTED || _shutdown) { break; } else if (res == tokudb::thread::semaphore_t::E_SIGNALLED) { -#if TOKUDB_DEBUG +#if defined(TOKUDB_DEBUG) if (TOKUDB_UNLIKELY( tokudb::sysvars::debug_pause_background_job_manager)) { _sem.signal(); tokudb::time::sleep_microsec(250000); continue; } -#endif // TOKUDB_DEBUG +#endif // defined(TOKUDB_DEBUG) mutex_t_lock(_mutex); assert_debug(_background_jobs.size() > 0); diff --git a/storage/tokudb/tokudb_sysvars.cc b/storage/tokudb/tokudb_sysvars.cc index 1e841f3b959..b269ae2ef08 100644 --- a/storage/tokudb/tokudb_sysvars.cc +++ b/storage/tokudb/tokudb_sysvars.cc @@ -661,13 +661,13 @@ static MYSQL_THDVAR_ULONGLONG( ~0ULL, 1); -static MYSQL_THDVAR_STR( - last_lock_timeout, - PLUGIN_VAR_MEMALLOC, - "last lock timeout", - NULL, - NULL, - NULL); +static MYSQL_THDVAR_STR(last_lock_timeout, + PLUGIN_VAR_MEMALLOC | PLUGIN_VAR_NOCMDOPT | + PLUGIN_VAR_READONLY, + "last lock timeout", + NULL, + NULL, + NULL); static MYSQL_THDVAR_BOOL( load_save_space, diff --git a/storage/tokudb/tokudb_sysvars.h b/storage/tokudb/tokudb_sysvars.h index 2454f8fefd2..23199baa7be 100644 --- a/storage/tokudb/tokudb_sysvars.h +++ b/storage/tokudb/tokudb_sysvars.h @@ -113,10 +113,10 @@ extern my_bool gdb_on_fatal; extern my_bool check_jemalloc; -#if TOKUDB_DEBUG +#if defined(TOKUDB_DEBUG) // used to control background job manager extern my_bool debug_pause_background_job_manager; -#endif // TOKUDB_DEBUG +#endif // defined(TOKUDB_DEBUG) // session/thread my_bool alter_print_error(THD* thd); |