<commit_before>////////////////////////////////////////////////////////////////////////////////
/// @brief index
///
/// @file
///
/// DISCLAIMER
///
/// Copyright 2004-2013 triAGENS GmbH, Cologne, Germany
///
/// 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.
///
/// Copyright holder is triAGENS GmbH, Cologne, Germany
///
/// @author Dr. <NAME>
/// @author Copyright 2011-2013, triAGENS GmbH, Cologne, Germany
////////////////////////////////////////////////////////////////////////////////

#include "index.h"

#include "BasicsC/conversions.h"
#include "BasicsC/files.h"
#include "BasicsC/json.h"
#include "BasicsC/linked-list.h"
#include "BasicsC/logging.h"
#include "BasicsC/string-buffer.h"
#include "BasicsC/tri-strings.h"
#include "BasicsC/utf8-helper.h"
#include "BasicsC/fasthash.h"
#include "BasicsC/xxhash.h"
#include "CapConstraint/cap-constraint.h"
#include "GeoIndex/geo-index.h"
#include "FulltextIndex/fulltext-index.h"
#include "FulltextIndex/fulltext-wordlist.h"
#include "GeoIndex/geo-index.h"
#include "HashIndex/hash-index.h"
#include "ShapedJson/shape-accessor.h"
#include "ShapedJson/shaped-json.h"
#include "VocBase/document-collection.h"
#include "VocBase/edge-collection.h"
#include "VocBase/replication-logger.h"
#include "VocBase/server.h"
#include "VocBase/voc-shaper.h"

// -----------------------------------------------------------------------------
// --SECTION--                                                             INDEX
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
// --SECTION--                                      constructors and destructors
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief initialise basic index properties
////////////////////////////////////////////////////////////////////////////////

void TRI_InitIndex (TRI_index_t* idx, 
                    TRI_idx_iid_t iid,
                    TRI_idx_type_e type, 
                    struct TRI_primary_collection_s* primary,
                    bool unique) {
  // note: primary can be NULL
  assert(idx != NULL);

  if (iid > 0) {
    // use iid if specified
    idx->_iid = iid;
  }
  else if (type == TRI_IDX_TYPE_PRIMARY_INDEX) {
    // override iid
    idx->_iid = 0;
  }
  else {
    idx->_iid = TRI_NewTickServer();
  }

  idx->_type              = type;
  idx->_collection        = primary;
  idx->_unique            = unique;
  
  // init common functions
  idx->removeIndex       = NULL;
  idx->cleanup           = NULL;
  idx->sizeHint          = NULL;

  idx->postInsert        = NULL;

  LOG_TRACE("initialising index of type %s", TRI_TypeNameIndex(idx->_type));
}

////////////////////////////////////////////////////////////////////////////////
/// @}
////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// --SECTION--                                                  public functions
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief whether or not an index needs full coverage
////////////////////////////////////////////////////////////////////////////////

bool TRI_NeedsFullCoverageIndex (TRI_idx_type_e type) {
  switch (type) {
    case TRI_IDX_TYPE_PRIMARY_INDEX:
    case TRI_IDX_TYPE_EDGE_INDEX:
    case TRI_IDX_TYPE_HASH_INDEX:
    case TRI_IDX_TYPE_SKIPLIST_INDEX:
    case TRI_IDX_TYPE_FULLTEXT_INDEX:
    case TRI_IDX_TYPE_GEO1_INDEX:
    case TRI_IDX_TYPE_GEO2_INDEX:
    case TRI_IDX_TYPE_CAP_CONSTRAINT:
      return true;
    case TRI_IDX_TYPE_BITARRAY_INDEX:
      return false;
    case TRI_IDX_TYPE_PRIORITY_QUEUE_INDEX:
    case TRI_IDX_TYPE_UNKNOWN:
      return false;
  }

  // unknown type...
  assert(false);
  return false;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief return the name of an index type
////////////////////////////////////////////////////////////////////////////////

TRI_idx_type_e TRI_TypeIndex (char const* type) {
  if (TRI_EqualString(type, "primary")) {
    return TRI_IDX_TYPE_PRIMARY_INDEX;
  }
  else if (TRI_EqualString(type, "edge")) {
    return TRI_IDX_TYPE_EDGE_INDEX;
  }
  else if (TRI_EqualString(type, "hash")) {
    return TRI_IDX_TYPE_HASH_INDEX;
  }
  else if (TRI_EqualString(type, "skiplist")) {
    return TRI_IDX_TYPE_SKIPLIST_INDEX;
  }
  else if (TRI_EqualString(type, "fulltext")) {
    return TRI_IDX_TYPE_FULLTEXT_INDEX;
  }
  else if (TRI_EqualString(type, "bitarray")) {
    return TRI_IDX_TYPE_BITARRAY_INDEX;
  }
  else if (TRI_EqualString(type, "cap")) {
    return TRI_IDX_TYPE_CAP_CONSTRAINT;
  }
  else if (TRI_EqualString(type, "geo1")) {
    return TRI_IDX_TYPE_GEO1_INDEX;
  }
  else if (TRI_EqualString(type, "geo2")) {
    return TRI_IDX_TYPE_GEO2_INDEX;
  }

  return TRI_IDX_TYPE_UNKNOWN;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief return the name of an index type
////////////////////////////////////////////////////////////////////////////////

char const* TRI_TypeNameIndex (TRI_idx_type_e type) {
  switch (type) {
    case TRI_IDX_TYPE_PRIMARY_INDEX:
      return "primary";
    case TRI_IDX_TYPE_GEO1_INDEX:
      return "geo1";
    case TRI_IDX_TYPE_GEO2_INDEX:
      return "geo2";
    case TRI_IDX_TYPE_HASH_INDEX:
      return "hash";
    case TRI_IDX_TYPE_EDGE_INDEX:
      return "edge";
    case TRI_IDX_TYPE_FULLTEXT_INDEX:
      return "fulltext";
    case TRI_IDX_TYPE_SKIPLIST_INDEX:
      return "skiplist";
    case TRI_IDX_TYPE_BITARRAY_INDEX:
      return "bitarray";
    case TRI_IDX_TYPE_CAP_CONSTRAINT:
      return "cap";
    case TRI_IDX_TYPE_PRIORITY_QUEUE_INDEX:
    case TRI_IDX_TYPE_UNKNOWN:
    default: {
    }
  }

  return "";
}

////////////////////////////////////////////////////////////////////////////////
/// @brief validate an index id
////////////////////////////////////////////////////////////////////////////////

bool TRI_ValidateIdIndex (char const* key) {
  char const* p = key;

  while (1) {
    const char c = *p;

    if (c == '\0') {
      return (p - key) > 0;
    }
    if (c >= '0' && c <= '9') {
      ++p;
      continue;
    }

    return false;
  }
}

////////////////////////////////////////////////////////////////////////////////
/// @brief validate an index id (collection name + / + index id)
////////////////////////////////////////////////////////////////////////////////

bool TRI_ValidateIndexIdIndex (char const* key,
                               size_t* split) {
  char const* p = key;
  char c = *p;

  // extract collection name
        
  if (! (c == '_' || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))) {
    return false;
  }

  ++p;

  while (1) {
    c = *p;

    if ((c == '_') || (c == '-') || (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
      ++p;
      continue;
    }

    if (c == '/') {
      break;
    }

    return false;
  }

  if (p - key > TRI_COL_NAME_LENGTH) {
    return false;
  }

  // store split position
  *split = p - key;
  ++p;
 
  // validate index id
  return TRI_ValidateIdIndex(p);
}

////////////////////////////////////////////////////////////////////////////////
/// @brief free an index
////////////////////////////////////////////////////////////////////////////////

void TRI_FreeIndex (TRI_index_t* idx) {
  assert(idx);

  LOG_TRACE("freeing index");

  switch (idx->_type) {
    case TRI_IDX_TYPE_GEO1_INDEX:
    case TRI_IDX_TYPE_GEO2_INDEX:
      TRI_FreeGeoIndex(idx);
      break;

    case TRI_IDX_TYPE_BITARRAY_INDEX:
      TRI_FreeBitarrayIndex(idx);
      break;

    case TRI_IDX_TYPE_HASH_INDEX:
      TRI_FreeHashIndex(idx);
      break;

    case TRI_IDX_TYPE_EDGE_INDEX:
      TRI_FreeEdgeIndex(idx);
      break;

    case TRI_IDX_TYPE_SKIPLIST_INDEX:
      TRI_FreeSkiplistIndex(idx);
      break;

    case TRI_IDX_TYPE_FULLTEXT_INDEX:
      TRI_FreeFulltextIndex(idx);
      break;

    case TRI_IDX_TYPE_CAP_CONSTRAINT:
      TRI_FreeCapConstraint(idx);
      break;

    case TRI_IDX_TYPE_PRIMARY_INDEX:
      TRI_FreePrimaryIndex(idx);
      break;

    default:
      // no action necessary
      break;
  }
}

////////////////////////////////////////////////////////////////////////////////
/// @brief removes an index file
////////////////////////////////////////////////////////////////////////////////

bool TRI_RemoveIndexFile (TRI_primary_collection_t* collection, TRI_index_t* idx) {
  char* filename;
  char* name;
  char* number;
  int res;

  // construct filename
  number = TRI_StringUInt64(idx->_iid);

  if (number == NULL) {
    TRI_set_errno(TRI_ERROR_OUT_OF_MEMORY);
    LOG_ERROR("out of memory when creating index number");
    return false;
  }

  name = TRI_Concatenate3String("index-", number, ".json");

  if (name == NULL) {
    TRI_set_errno(TRI_ERROR_OUT_OF_MEMORY);

    TRI_FreeString(TRI_CORE_MEM_ZONE, number);
    LOG_ERROR("out of memory when creating index name");
    return false;
  }

  filename = TRI_Concatenate2File(collection->base._directory, name);

  if (filename == NULL) {
    TRI_set_errno(TRI_ERROR_OUT_OF_MEMORY);

    TRI_FreeString(TRI_CORE_MEM_ZONE, number);
    TRI_FreeString(TRI_CORE_MEM_ZONE, name);
    LOG_ERROR("out of memory when creating index filename");
    return false;
  }

  TRI_FreeString(TRI_CORE_MEM_ZONE, name);
  TRI_FreeString(TRI_CORE_MEM_ZONE, number);

  res = TRI_UnlinkFile(filename);
  TRI_FreeString(TRI_CORE_MEM_ZONE, filename);

  if (res != TRI_ERROR_NO_ERROR) {
    LOG_ERROR("cannot remove index definition: %s", TRI_last_error());
    return false;
  }

  return true;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief saves an index
////////////////////////////////////////////////////////////////////////////////

int TRI_SaveIndex (TRI_primary_collection_t* primary, 
                   TRI_index_t* idx,
                   TRI_server_id_t generatingServer) {
  TRI_json_t* json;
  TRI_vocbase_t* vocbase;
  char* filename;
  char* name;
  char* number;
  bool ok;

  // convert into JSON
  json = idx->json(idx);

  if (json == NULL) {
    LOG_TRACE("cannot save index definition: index cannot be jsonified");
    return TRI_set_errno(TRI_ERROR_INTERNAL);
  }

  // construct filename
  number   = TRI_StringUInt64(idx->_iid);
  name     = TRI_Concatenate3String("index-", number, ".json");
  filename = TRI_Concatenate2File(primary->base._directory, name);

  TRI_FreeString(TRI_CORE_MEM_ZONE, name);
  TRI_FreeString(TRI_CORE_MEM_ZONE, number);

  vocbase = primary->base._vocbase;

  // and save
  ok = TRI_SaveJson(filename, json, vocbase->_settings.forceSyncProperties);
  
  TRI_FreeString(TRI_CORE_MEM_ZONE, filename);

  if (! ok) {
    LOG_ERROR("cannot save index definition: %s", TRI_last_error());
    TRI_FreeJson(TRI_CORE_MEM_ZONE, json);

    return TRI_errno();
  }

  // it is safe to use _name as we hold a read-lock on the collection status
  TRI_LogCreateIndexReplication(vocbase, 
                                primary->base._info._cid, 
                                primary->base._info._name, 
                                idx->_iid, 
                                json,
                                generatingServer);

  TRI_FreeJson(TRI_CORE_MEM_ZONE, json);

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief looks up an index identifier
////////////////////////////////////////////////////////////////////////////////

TRI_index_t* TRI_LookupIndex (TRI_primary_collection_t* primary, 
                              TRI_idx_iid_t iid) {
  TRI_document_collection_t* doc;
  TRI_index_t* idx;
  size_t i;

  doc = (TRI_document_collection_t*) primary;

  for (i = 0;  i < doc->_allIndexes._length;  ++i) {
    idx = doc->_allIndexes._buffer[i];

    if (idx->_iid == iid) {
      return idx;
    }
  }

  TRI_set_errno(TRI_ERROR_ARANGO_NO_INDEX);

  return NULL;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief creates a basic index description as JSON
/// this only contains the common index fields and needs to be extended by the
/// specialised index 
////////////////////////////////////////////////////////////////////////////////

TRI_json_t* TRI_JsonIndex (TRI_memory_zone_t* zone, 
                           TRI_index_t const* idx) {
  TRI_json_t* json;

  json = TRI_CreateArrayJson(zone);

  if (json != NULL) {
    char* number;
    
    number = TRI_StringUInt64(idx->_iid);
    TRI_Insert3ArrayJson(zone, json, "id", TRI_CreateStringCopyJson(zone, number));
    TRI_Insert3ArrayJson(zone, json, "type", TRI_CreateStringCopyJson(zone, TRI_TypeNameIndex(idx->_type)));
    TRI_Insert3ArrayJson(zone, json, "unique", TRI_CreateBooleanJson(zone, idx->_unique));

    TRI_FreeString(TRI_CORE_MEM_ZONE, number);
  }

  return json;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief destroys a result set returned by a hash index query
////////////////////////////////////////////////////////////////////////////////

void TRI_DestroyIndexResult (TRI_index_result_t* result) {
  if (result->_documents != NULL) {
    TRI_Free(TRI_UNKNOWN_MEM_ZONE, result->_documents);
  }
}

////////////////////////////////////////////////////////////////////////////////
/// @brief copies a path vector
////////////////////////////////////////////////////////////////////////////////

void TRI_CopyPathVector (TRI_vector_t* dst, TRI_vector_t* src) {
  size_t j;

  TRI_InitVector(dst, TRI_CORE_MEM_ZONE, sizeof(TRI_shape_pid_t));

  for (j = 0;  j < src->_length;  ++j) {
    TRI_shape_pid_t shape = *((TRI_shape_pid_t*)(TRI_AtVector(src,j)));

    TRI_PushBackVector(dst, &shape);
  }
}

////////////////////////////////////////////////////////////////////////////////
/// @brief converts a path vector into a field list
///
/// Note that you must free the field list itself, but not the fields. The
/// belong to the shaper.
////////////////////////////////////////////////////////////////////////////////

char const** TRI_FieldListByPathList (TRI_shaper_t* shaper,
                                      TRI_vector_t* paths) {
  char const** fieldList;
  size_t j;

  // .............................................................................
  // Allocate sufficent memory for the field list
  // .............................................................................

  fieldList = TRI_Allocate(TRI_CORE_MEM_ZONE, (sizeof(char const*) * paths->_length), false);

  // ..........................................................................  
  // Convert the attributes (field list of the hash index) into strings
  // ..........................................................................  

  for (j = 0;  j < paths->_length;  ++j) {
    TRI_shape_pid_t shape = *((TRI_shape_pid_t*)(TRI_AtVector(paths, j)));
    TRI_shape_path_t const* path = shaper->lookupAttributePathByPid(shaper, shape);

    if (path == NULL) {
      TRI_set_errno(TRI_ERROR_OUT_OF_MEMORY);
      TRI_Free(TRI_CORE_MEM_ZONE, (void*) fieldList);
      return NULL;
    }

    fieldList[j] = ((const char*) path) + sizeof(TRI_shape_path_t) + path->_aidLength * sizeof(TRI_shape_aid_t);
  }

  return fieldList;
}

////////////////////////////////////////////////////////////////////////////////
/// @}
////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// --SECTION--                                                     PRIMARY INDEX
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
// --SECTION--                                                 private functions
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief insert methods does nothing
////////////////////////////////////////////////////////////////////////////////

static int InsertPrimary (TRI_index_t* idx, 
                          TRI_doc_mptr_t const* doc, 
                          const bool isRollback) {
  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief remove methods does nothing
////////////////////////////////////////////////////////////////////////////////

static int RemovePrimary (TRI_index_t* idx, 
                          TRI_doc_mptr_t const* doc,
                          const bool isRollback) {
  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief JSON description of a primary index
////////////////////////////////////////////////////////////////////////////////

static TRI_json_t* JsonPrimary (TRI_index_t* idx) { 
  TRI_json_t* json;
  TRI_json_t* fields;

  json = TRI_JsonIndex(TRI_CORE_MEM_ZONE, idx);
  
  if (json == NULL) {
    return NULL;
  }

  fields = TRI_CreateListJson(TRI_CORE_MEM_ZONE);
  TRI_PushBack3ListJson(TRI_CORE_MEM_ZONE, fields, TRI_CreateStringCopyJson(TRI_CORE_MEM_ZONE, "_id"));
  TRI_Insert3ArrayJson(TRI_CORE_MEM_ZONE, json, "fields", fields);

  return json;
}

////////////////////////////////////////////////////////////////////////////////
/// @}
////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// --SECTION--                                        constructors / destructors
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief create the primary index
////////////////////////////////////////////////////////////////////////////////

TRI_index_t* TRI_CreatePrimaryIndex (struct TRI_primary_collection_s* primary) {
  TRI_index_t* idx;
  char* id;

  // note: primary can be NULL

  // create primary index
  idx = TRI_Allocate(TRI_CORE_MEM_ZONE, sizeof(TRI_index_t), false);

  if (idx == NULL) {
    return NULL;
  }

  id = TRI_DuplicateStringZ(TRI_CORE_MEM_ZONE, "_id");
  TRI_InitVectorString(&idx->_fields, TRI_CORE_MEM_ZONE);
  TRI_PushBackVectorString(&idx->_fields, id);

  TRI_InitIndex(idx, 0, TRI_IDX_TYPE_PRIMARY_INDEX, primary, true);

  idx->json     = JsonPrimary;
  idx->insert   = InsertPrimary;
  idx->remove   = RemovePrimary;

  return idx;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief destroys a primary index, but does not free the pointer
////////////////////////////////////////////////////////////////////////////////

void TRI_DestroyPrimaryIndex (TRI_index_t* idx) {
  LOG_TRACE("destroying primary index");

  TRI_DestroyVectorString(&idx->_fields);
}

////////////////////////////////////////////////////////////////////////////////
/// @brief free a primary index
////////////////////////////////////////////////////////////////////////////////

void TRI_FreePrimaryIndex (TRI_index_t* idx) {
 TRI_DestroyPrimaryIndex(idx);
 TRI_Free(TRI_CORE_MEM_ZONE, idx);
}

////////////////////////////////////////////////////////////////////////////////
/// @}
////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// --SECTION--                                                        EDGE INDEX
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
// --SECTION--                                                 private functions
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief hashes an edge key 
////////////////////////////////////////////////////////////////////////////////

static uint64_t HashElementKey (TRI_multi_pointer_t* array, void const* data) {
  TRI_edge_header_t const* h;
  uint64_t hash;
  char* key;

  h = data;

  assert(h->_mptr == NULL);

  key = h->_searchKey._key;

  // only include directional bits for hashing, exclude special bits
  hash = (uint64_t) (h->_flags & TRI_EDGE_BITS_DIRECTION) ^ h->_cid;
  hash ^=  (uint64_t) fasthash64(key, strlen(key), 0x87654321);

  return fasthash64(&hash, sizeof(hash), 0x56781234);
}

////////////////////////////////////////////////////////////////////////////////
/// @brief hashes an edge header
////////////////////////////////////////////////////////////////////////////////

static uint64_t HashElementEdge (TRI_multi_pointer_t* array, void const* data,
                                 bool byKey) {
  TRI_edge_header_t const* h;
  uint64_t hash;
  char const* p;

  h = data;

  assert(h->_mptr != NULL);

  // only include directional bits for hashing, exclude special bits
  hash = (uint64_t) (h->_flags & TRI_EDGE_BITS_DIRECTION) ^ h->_cid;
  if (byKey) {
    p = (char*) h->_mptr->_data + h->_searchKey._offsetKey;
    hash ^= (uint64_t) fasthash64(p, strlen(p), 0x87654321);
  }
  else {
    hash ^= (uint64_t) h->_mptr;
  }

  return fasthash64(&hash, sizeof(hash), 0x56781234);
}

////////////////////////////////////////////////////////////////////////////////
/// @brief checks if key and element match
////////////////////////////////////////////////////////////////////////////////

static bool IsEqualKeyEdge (TRI_multi_pointer_t* array,
                            void const* left,
                            void const* right) {
  // left is a key, that is with NULL master pointer
  // right is an element, that is, with non-NULL master pointer
  TRI_edge_header_t const* l;
  TRI_edge_header_t const* r;
  const char* lKey;
  const char* rKey;

  l = left;
  r = right;

  assert(l->_mptr == NULL);
  lKey = l->_searchKey._key;

  assert(r->_mptr != NULL);
  rKey = ((char*) ((TRI_doc_edge_key_marker_t const*) r->_mptr->_data)) + 
         r->_searchKey._offsetKey;

  // only include directional flags, exclude special bits
  return (strcmp(lKey, rKey) == 0) &&
         ((l->_flags & TRI_EDGE_BITS_DIRECTION) ==
          (r->_flags & TRI_EDGE_BITS_DIRECTION)) &&
         (l->_cid == r->_cid);
}

////////////////////////////////////////////////////////////////////////////////
/// @brief checks for elements are equal
////////////////////////////////////////////////////////////////////////////////

static bool IsEqualElementEdge (TRI_multi_pointer_t* array,
                                void const* left,
                                void const* right,
                                bool byKey) {
  TRI_edge_header_t const* l;
  TRI_edge_header_t const* r;
  const char* lKey;
  const char* rKey;

  l = left;
  r = right;

  assert(l->_mptr != NULL);
  assert(l->_mptr != NULL);

  if (byKey) {
    lKey = ((char*) ((TRI_doc_edge_key_marker_t const*) l->_mptr->_data)) + 
           l->_searchKey._offsetKey;
    rKey = ((char*) ((TRI_doc_edge_key_marker_t const*) r->_mptr->_data)) + 
           r->_searchKey._offsetKey;
    
    return (strcmp(lKey, rKey) == 0) &&
           ((l->_flags & TRI_EDGE_BITS_DIRECTION) ==
            (r->_flags & TRI_EDGE_BITS_DIRECTION)) &&
           (l->_cid == r->_cid);
  }
  else {
    // only include directional flags, exclude special bits
    return (l->_mptr == r->_mptr) &&
           ((l->_flags & TRI_EDGE_BITS_DIRECTION) == 
            (r->_flags & TRI_EDGE_BITS_DIRECTION));
  }
}

////////////////////////////////////////////////////////////////////////////////
/// @brief insert method for edges
////////////////////////////////////////////////////////////////////////////////

static int InsertEdge (TRI_index_t* idx, 
                       TRI_doc_mptr_t const* mptr,
                       const bool isRollback) {
  TRI_edge_header_t* entryIn;
  TRI_edge_header_t* entryOut;
  char* memory;
  TRI_doc_edge_key_marker_t const* edge;
  bool isReflexive;

  TRI_multi_pointer_t* edgesIndex = &(((TRI_edge_index_t*) idx)->_edges);

  edge = mptr->_data;

  // is the edge self-reflexive (_from & _to are identical)?
  isReflexive = (edge->_toCid == edge->_fromCid && strcmp(((char*) edge) + edge->_offsetToKey, ((char*) edge) + edge->_offsetFromKey) == 0);

  // allocate memory for both edge headers and return early if memory allocation fails
  memory = TRI_Allocate(TRI_UNKNOWN_MEM_ZONE, 2 * sizeof(TRI_edge_header_t), false);

  if (memory == NULL) {
    return TRI_set_errno(TRI_ERROR_OUT_OF_MEMORY);
  }

  entryIn  = (TRI_edge_header_t*) memory;
  entryOut = (TRI_edge_header_t*) (memory + sizeof(TRI_edge_header_t));

  // first slot: IN
  entryIn->_mptr = mptr;
  entryIn->_flags = TRI_FlagsEdge(TRI_EDGE_IN, isReflexive);
  entryIn->_cid = edge->_toCid;
  entryIn->_searchKey._offsetKey = edge->_offsetToKey;
  TRI_InsertElementMultiPointer(edgesIndex, entryIn, true, isRollback);
    
  // second slot: OUT
  entryOut->_mptr = mptr;
  entryOut->_flags = TRI_FlagsEdge(TRI_EDGE_OUT, isReflexive);
  entryOut->_cid = edge->_fromCid;
  entryOut->_searchKey._offsetKey = edge->_offsetFromKey;
  TRI_InsertElementMultiPointer(edgesIndex, entryOut, true, isRollback);
  
  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief remove an edge
////////////////////////////////////////////////////////////////////////////////

static int RemoveEdge (TRI_index_t* idx, 
                       TRI_doc_mptr_t const* doc,
                       const bool isRollback) {
  TRI_edge_header_t entry;
  TRI_edge_header_t* old;
  TRI_doc_edge_key_marker_t const* edge;
  TRI_multi_pointer_t* edgesIndex = &(((TRI_edge_index_t*) idx)->_edges);

  edge = doc->_data;

  entry._mptr = doc;

  // OUT
  entry._flags = TRI_LookupFlagsEdge(TRI_EDGE_OUT);
  entry._cid = edge->_fromCid;
  entry._searchKey._offsetKey = edge->_offsetFromKey;
  TRI_RemoveElementMultiPointer(edgesIndex, &entry);
  // we do not need to free the OUT element

  // IN
  entry._flags = TRI_LookupFlagsEdge(TRI_EDGE_IN);
  entry._cid = edge->_toCid;
  entry._searchKey._offsetKey = edge->_offsetToKey;
  old = TRI_RemoveElementMultiPointer(edgesIndex, &entry);

  // the pointer to the IN element is also the memory pointer we need to free
  if (old != NULL) {
    TRI_Free(TRI_UNKNOWN_MEM_ZONE, old);
  }

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief JSON description of edge index
////////////////////////////////////////////////////////////////////////////////

static TRI_json_t* JsonEdge (TRI_index_t* idx) {
  TRI_json_t* json;
  TRI_json_t* fields;

  json = TRI_JsonIndex(TRI_CORE_MEM_ZONE, idx);

  if (json == NULL) {
    return NULL;
  }

  fields = TRI_CreateListJson(TRI_CORE_MEM_ZONE);
  TRI_PushBack3ListJson(TRI_CORE_MEM_ZONE, fields, TRI_CreateStringCopyJson(TRI_CORE_MEM_ZONE, TRI_VOC_ATTRIBUTE_FROM));
  TRI_PushBack3ListJson(TRI_CORE_MEM_ZONE, fields, TRI_CreateStringCopyJson(TRI_CORE_MEM_ZONE, TRI_VOC_ATTRIBUTE_TO));
  TRI_Insert3ArrayJson(TRI_CORE_MEM_ZONE, json, "fields", fields);

  return json;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief provides a size hint for the edge index
////////////////////////////////////////////////////////////////////////////////

static int SizeHintEdge (TRI_index_t* idx,
                         size_t size) {

  TRI_multi_pointer_t* edgesIndex = &(((TRI_edge_index_t*) idx)->_edges);

  // we assume this is called when setting up the index and the index is still empty
  assert(edgesIndex->_nrUsed == 0);

  // set an initial size for the index and allow for some new nodes to be created
  // without resizing
  return TRI_ResizeMultiPointer(edgesIndex, 2 * size + 2049);
}

////////////////////////////////////////////////////////////////////////////////
/// @}
////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// --SECTION--                                        constructors / destructors
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief create the edge index
////////////////////////////////////////////////////////////////////////////////

TRI_index_t* TRI_CreateEdgeIndex (struct TRI_primary_collection_s* primary,
                                  TRI_idx_iid_t iid) {
  TRI_edge_index_t* edgeIndex;
  TRI_index_t* idx;
  char* id;
  int res;

  // create index
  edgeIndex = TRI_Allocate(TRI_CORE_MEM_ZONE, sizeof(TRI_edge_index_t), false);

  if (edgeIndex == NULL) {
    return NULL;
  }
 
  res = TRI_InitMultiPointer(&edgeIndex->_edges,
                             TRI_UNKNOWN_MEM_ZONE,
                             HashElementKey,
                             HashElementEdge,
                             IsEqualKeyEdge,
                             IsEqualElementEdge);
  
  if (res != TRI_ERROR_NO_ERROR) {
    TRI_Free(TRI_CORE_MEM_ZONE, edgeIndex);

    return NULL;
  }


  idx = &edgeIndex->base;

  TRI_InitVectorString(&idx->_fields, TRI_CORE_MEM_ZONE);
  id = TRI_DuplicateStringZ(TRI_CORE_MEM_ZONE, TRI_VOC_ATTRIBUTE_FROM);
  TRI_PushBackVectorString(&idx->_fields, id);
 
  TRI_InitIndex(idx, iid, TRI_IDX_TYPE_EDGE_INDEX, primary, false); 

  idx->json     = JsonEdge;
  idx->insert   = InsertEdge;
  idx->remove   = RemoveEdge;

  idx->sizeHint = SizeHintEdge;

  return idx;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief destroys the edge index, but does not free the pointer
////////////////////////////////////////////////////////////////////////////////

void TRI_DestroyEdgeIndex (TRI_index_t* idx) {
  TRI_edge_index_t* edgesIndex;
  size_t i, n;

  edgesIndex = (TRI_edge_index_t*) idx;

  LOG_TRACE("destroying edge index");

  // free all elements in the edges index
  n = (size_t) edgesIndex->_edges._nrAlloc;
  
  // deletion from the index is done in two steps as memory was only allocated for IN edges
  // the OUT edges are at memory position IN + sizeof(edge_header) and 
  // must not be freed themselves

  // step 1: zero out all the out edges (we must not free them directly)
  for (i = 0; i < n; ++i) {
    TRI_edge_header_t* element = edgesIndex->_edges._table[i];
  
    if (element != NULL && (element->_flags & TRI_EDGE_BIT_DIRECTION_OUT)) {
      edgesIndex->_edges._table[i] = NULL;
    }
  }
  
  // step 2: free the allocated memory
  for (i = 0; i < n; ++i) {
    TRI_edge_header_t* element = edgesIndex->_edges._table[i].ptr;

    if (element != NULL) {
      TRI_Free(TRI_UNKNOWN_MEM_ZONE, element);
    }<commit_msg>Fix after merge from devel.<commit_after>////////////////////////////////////////////////////////////////////////////////
/// @brief index
///
/// @file
///
/// DISCLAIMER
///
/// Copyright 2004-2013 triAGENS GmbH, Cologne, Germany
///
/// 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.
///
/// Copyright holder is triAGENS GmbH, Cologne, Germany
///
/// @author Dr. <NAME>
/// @author Copyright 2011-2013, triAGENS GmbH, Cologne, Germany
////////////////////////////////////////////////////////////////////////////////

#include "index.h"

#include "BasicsC/conversions.h"
#include "BasicsC/files.h"
#include "BasicsC/json.h"
#include "BasicsC/linked-list.h"
#include "BasicsC/logging.h"
#include "BasicsC/string-buffer.h"
#include "BasicsC/tri-strings.h"
#include "BasicsC/utf8-helper.h"
#include "BasicsC/fasthash.h"
#include "BasicsC/xxhash.h"
#include "CapConstraint/cap-constraint.h"
#include "GeoIndex/geo-index.h"
#include "FulltextIndex/fulltext-index.h"
#include "FulltextIndex/fulltext-wordlist.h"
#include "GeoIndex/geo-index.h"
#include "HashIndex/hash-index.h"
#include "ShapedJson/shape-accessor.h"
#include "ShapedJson/shaped-json.h"
#include "VocBase/document-collection.h"
#include "VocBase/edge-collection.h"
#include "VocBase/replication-logger.h"
#include "VocBase/server.h"
#include "VocBase/voc-shaper.h"

// -----------------------------------------------------------------------------
// --SECTION--                                                             INDEX
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
// --SECTION--                                      constructors and destructors
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief initialise basic index properties
////////////////////////////////////////////////////////////////////////////////

void TRI_InitIndex (TRI_index_t* idx, 
                    TRI_idx_iid_t iid,
                    TRI_idx_type_e type, 
                    struct TRI_primary_collection_s* primary,
                    bool unique) {
  // note: primary can be NULL
  assert(idx != NULL);

  if (iid > 0) {
    // use iid if specified
    idx->_iid = iid;
  }
  else if (type == TRI_IDX_TYPE_PRIMARY_INDEX) {
    // override iid
    idx->_iid = 0;
  }
  else {
    idx->_iid = TRI_NewTickServer();
  }

  idx->_type              = type;
  idx->_collection        = primary;
  idx->_unique            = unique;
  
  // init common functions
  idx->removeIndex       = NULL;
  idx->cleanup           = NULL;
  idx->sizeHint          = NULL;

  idx->postInsert        = NULL;

  LOG_TRACE("initialising index of type %s", TRI_TypeNameIndex(idx->_type));
}

////////////////////////////////////////////////////////////////////////////////
/// @}
////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// --SECTION--                                                  public functions
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief whether or not an index needs full coverage
////////////////////////////////////////////////////////////////////////////////

bool TRI_NeedsFullCoverageIndex (TRI_idx_type_e type) {
  switch (type) {
    case TRI_IDX_TYPE_PRIMARY_INDEX:
    case TRI_IDX_TYPE_EDGE_INDEX:
    case TRI_IDX_TYPE_HASH_INDEX:
    case TRI_IDX_TYPE_SKIPLIST_INDEX:
    case TRI_IDX_TYPE_FULLTEXT_INDEX:
    case TRI_IDX_TYPE_GEO1_INDEX:
    case TRI_IDX_TYPE_GEO2_INDEX:
    case TRI_IDX_TYPE_CAP_CONSTRAINT:
      return true;
    case TRI_IDX_TYPE_BITARRAY_INDEX:
      return false;
    case TRI_IDX_TYPE_PRIORITY_QUEUE_INDEX:
    case TRI_IDX_TYPE_UNKNOWN:
      return false;
  }

  // unknown type...
  assert(false);
  return false;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief return the name of an index type
////////////////////////////////////////////////////////////////////////////////

TRI_idx_type_e TRI_TypeIndex (char const* type) {
  if (TRI_EqualString(type, "primary")) {
    return TRI_IDX_TYPE_PRIMARY_INDEX;
  }
  else if (TRI_EqualString(type, "edge")) {
    return TRI_IDX_TYPE_EDGE_INDEX;
  }
  else if (TRI_EqualString(type, "hash")) {
    return TRI_IDX_TYPE_HASH_INDEX;
  }
  else if (TRI_EqualString(type, "skiplist")) {
    return TRI_IDX_TYPE_SKIPLIST_INDEX;
  }
  else if (TRI_EqualString(type, "fulltext")) {
    return TRI_IDX_TYPE_FULLTEXT_INDEX;
  }
  else if (TRI_EqualString(type, "bitarray")) {
    return TRI_IDX_TYPE_BITARRAY_INDEX;
  }
  else if (TRI_EqualString(type, "cap")) {
    return TRI_IDX_TYPE_CAP_CONSTRAINT;
  }
  else if (TRI_EqualString(type, "geo1")) {
    return TRI_IDX_TYPE_GEO1_INDEX;
  }
  else if (TRI_EqualString(type, "geo2")) {
    return TRI_IDX_TYPE_GEO2_INDEX;
  }

  return TRI_IDX_TYPE_UNKNOWN;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief return the name of an index type
////////////////////////////////////////////////////////////////////////////////

char const* TRI_TypeNameIndex (TRI_idx_type_e type) {
  switch (type) {
    case TRI_IDX_TYPE_PRIMARY_INDEX:
      return "primary";
    case TRI_IDX_TYPE_GEO1_INDEX:
      return "geo1";
    case TRI_IDX_TYPE_GEO2_INDEX:
      return "geo2";
    case TRI_IDX_TYPE_HASH_INDEX:
      return "hash";
    case TRI_IDX_TYPE_EDGE_INDEX:
      return "edge";
    case TRI_IDX_TYPE_FULLTEXT_INDEX:
      return "fulltext";
    case TRI_IDX_TYPE_SKIPLIST_INDEX:
      return "skiplist";
    case TRI_IDX_TYPE_BITARRAY_INDEX:
      return "bitarray";
    case TRI_IDX_TYPE_CAP_CONSTRAINT:
      return "cap";
    case TRI_IDX_TYPE_PRIORITY_QUEUE_INDEX:
    case TRI_IDX_TYPE_UNKNOWN:
    default: {
    }
  }

  return "";
}

////////////////////////////////////////////////////////////////////////////////
/// @brief validate an index id
////////////////////////////////////////////////////////////////////////////////

bool TRI_ValidateIdIndex (char const* key) {
  char const* p = key;

  while (1) {
    const char c = *p;

    if (c == '\0') {
      return (p - key) > 0;
    }
    if (c >= '0' && c <= '9') {
      ++p;
      continue;
    }

    return false;
  }
}

////////////////////////////////////////////////////////////////////////////////
/// @brief validate an index id (collection name + / + index id)
////////////////////////////////////////////////////////////////////////////////

bool TRI_ValidateIndexIdIndex (char const* key,
                               size_t* split) {
  char const* p = key;
  char c = *p;

  // extract collection name
        
  if (! (c == '_' || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))) {
    return false;
  }

  ++p;

  while (1) {
    c = *p;

    if ((c == '_') || (c == '-') || (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
      ++p;
      continue;
    }

    if (c == '/') {
      break;
    }

    return false;
  }

  if (p - key > TRI_COL_NAME_LENGTH) {
    return false;
  }

  // store split position
  *split = p - key;
  ++p;
 
  // validate index id
  return TRI_ValidateIdIndex(p);
}

////////////////////////////////////////////////////////////////////////////////
/// @brief free an index
////////////////////////////////////////////////////////////////////////////////

void TRI_FreeIndex (TRI_index_t* idx) {
  assert(idx);

  LOG_TRACE("freeing index");

  switch (idx->_type) {
    case TRI_IDX_TYPE_GEO1_INDEX:
    case TRI_IDX_TYPE_GEO2_INDEX:
      TRI_FreeGeoIndex(idx);
      break;

    case TRI_IDX_TYPE_BITARRAY_INDEX:
      TRI_FreeBitarrayIndex(idx);
      break;

    case TRI_IDX_TYPE_HASH_INDEX:
      TRI_FreeHashIndex(idx);
      break;

    case TRI_IDX_TYPE_EDGE_INDEX:
      TRI_FreeEdgeIndex(idx);
      break;

    case TRI_IDX_TYPE_SKIPLIST_INDEX:
      TRI_FreeSkiplistIndex(idx);
      break;

    case TRI_IDX_TYPE_FULLTEXT_INDEX:
      TRI_FreeFulltextIndex(idx);
      break;

    case TRI_IDX_TYPE_CAP_CONSTRAINT:
      TRI_FreeCapConstraint(idx);
      break;

    case TRI_IDX_TYPE_PRIMARY_INDEX:
      TRI_FreePrimaryIndex(idx);
      break;

    default:
      // no action necessary
      break;
  }
}

////////////////////////////////////////////////////////////////////////////////
/// @brief removes an index file
////////////////////////////////////////////////////////////////////////////////

bool TRI_RemoveIndexFile (TRI_primary_collection_t* collection, TRI_index_t* idx) {
  char* filename;
  char* name;
  char* number;
  int res;

  // construct filename
  number = TRI_StringUInt64(idx->_iid);

  if (number == NULL) {
    TRI_set_errno(TRI_ERROR_OUT_OF_MEMORY);
    LOG_ERROR("out of memory when creating index number");
    return false;
  }

  name = TRI_Concatenate3String("index-", number, ".json");

  if (name == NULL) {
    TRI_set_errno(TRI_ERROR_OUT_OF_MEMORY);

    TRI_FreeString(TRI_CORE_MEM_ZONE, number);
    LOG_ERROR("out of memory when creating index name");
    return false;
  }

  filename = TRI_Concatenate2File(collection->base._directory, name);

  if (filename == NULL) {
    TRI_set_errno(TRI_ERROR_OUT_OF_MEMORY);

    TRI_FreeString(TRI_CORE_MEM_ZONE, number);
    TRI_FreeString(TRI_CORE_MEM_ZONE, name);
    LOG_ERROR("out of memory when creating index filename");
    return false;
  }

  TRI_FreeString(TRI_CORE_MEM_ZONE, name);
  TRI_FreeString(TRI_CORE_MEM_ZONE, number);

  res = TRI_UnlinkFile(filename);
  TRI_FreeString(TRI_CORE_MEM_ZONE, filename);

  if (res != TRI_ERROR_NO_ERROR) {
    LOG_ERROR("cannot remove index definition: %s", TRI_last_error());
    return false;
  }

  return true;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief saves an index
////////////////////////////////////////////////////////////////////////////////

int TRI_SaveIndex (TRI_primary_collection_t* primary, 
                   TRI_index_t* idx,
                   TRI_server_id_t generatingServer) {
  TRI_json_t* json;
  TRI_vocbase_t* vocbase;
  char* filename;
  char* name;
  char* number;
  bool ok;

  // convert into JSON
  json = idx->json(idx);

  if (json == NULL) {
    LOG_TRACE("cannot save index definition: index cannot be jsonified");
    return TRI_set_errno(TRI_ERROR_INTERNAL);
  }

  // construct filename
  number   = TRI_StringUInt64(idx->_iid);
  name     = TRI_Concatenate3String("index-", number, ".json");
  filename = TRI_Concatenate2File(primary->base._directory, name);

  TRI_FreeString(TRI_CORE_MEM_ZONE, name);
  TRI_FreeString(TRI_CORE_MEM_ZONE, number);

  vocbase = primary->base._vocbase;

  // and save
  ok = TRI_SaveJson(filename, json, vocbase->_settings.forceSyncProperties);
  
  TRI_FreeString(TRI_CORE_MEM_ZONE, filename);

  if (! ok) {
    LOG_ERROR("cannot save index definition: %s", TRI_last_error());
    TRI_FreeJson(TRI_CORE_MEM_ZONE, json);

    return TRI_errno();
  }

  // it is safe to use _name as we hold a read-lock on the collection status
  TRI_LogCreateIndexReplication(vocbase, 
                                primary->base._info._cid, 
                                primary->base._info._name, 
                                idx->_iid, 
                                json,
                                generatingServer);

  TRI_FreeJson(TRI_CORE_MEM_ZONE, json);

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief looks up an index identifier
////////////////////////////////////////////////////////////////////////////////

TRI_index_t* TRI_LookupIndex (TRI_primary_collection_t* primary, 
                              TRI_idx_iid_t iid) {
  TRI_document_collection_t* doc;
  TRI_index_t* idx;
  size_t i;

  doc = (TRI_document_collection_t*) primary;

  for (i = 0;  i < doc->_allIndexes._length;  ++i) {
    idx = doc->_allIndexes._buffer[i];

    if (idx->_iid == iid) {
      return idx;
    }
  }

  TRI_set_errno(TRI_ERROR_ARANGO_NO_INDEX);

  return NULL;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief creates a basic index description as JSON
/// this only contains the common index fields and needs to be extended by the
/// specialised index 
////////////////////////////////////////////////////////////////////////////////

TRI_json_t* TRI_JsonIndex (TRI_memory_zone_t* zone, 
                           TRI_index_t const* idx) {
  TRI_json_t* json;

  json = TRI_CreateArrayJson(zone);

  if (json != NULL) {
    char* number;
    
    number = TRI_StringUInt64(idx->_iid);
    TRI_Insert3ArrayJson(zone, json, "id", TRI_CreateStringCopyJson(zone, number));
    TRI_Insert3ArrayJson(zone, json, "type", TRI_CreateStringCopyJson(zone, TRI_TypeNameIndex(idx->_type)));
    TRI_Insert3ArrayJson(zone, json, "unique", TRI_CreateBooleanJson(zone, idx->_unique));

    TRI_FreeString(TRI_CORE_MEM_ZONE, number);
  }

  return json;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief destroys a result set returned by a hash index query
////////////////////////////////////////////////////////////////////////////////

void TRI_DestroyIndexResult (TRI_index_result_t* result) {
  if (result->_documents != NULL) {
    TRI_Free(TRI_UNKNOWN_MEM_ZONE, result->_documents);
  }
}

////////////////////////////////////////////////////////////////////////////////
/// @brief copies a path vector
////////////////////////////////////////////////////////////////////////////////

void TRI_CopyPathVector (TRI_vector_t* dst, TRI_vector_t* src) {
  size_t j;

  TRI_InitVector(dst, TRI_CORE_MEM_ZONE, sizeof(TRI_shape_pid_t));

  for (j = 0;  j < src->_length;  ++j) {
    TRI_shape_pid_t shape = *((TRI_shape_pid_t*)(TRI_AtVector(src,j)));

    TRI_PushBackVector(dst, &shape);
  }
}

////////////////////////////////////////////////////////////////////////////////
/// @brief converts a path vector into a field list
///
/// Note that you must free the field list itself, but not the fields. The
/// belong to the shaper.
////////////////////////////////////////////////////////////////////////////////

char const** TRI_FieldListByPathList (TRI_shaper_t* shaper,
                                      TRI_vector_t* paths) {
  char const** fieldList;
  size_t j;

  // .............................................................................
  // Allocate sufficent memory for the field list
  // .............................................................................

  fieldList = TRI_Allocate(TRI_CORE_MEM_ZONE, (sizeof(char const*) * paths->_length), false);

  // ..........................................................................  
  // Convert the attributes (field list of the hash index) into strings
  // ..........................................................................  

  for (j = 0;  j < paths->_length;  ++j) {
    TRI_shape_pid_t shape = *((TRI_shape_pid_t*)(TRI_AtVector(paths, j)));
    TRI_shape_path_t const* path = shaper->lookupAttributePathByPid(shaper, shape);

    if (path == NULL) {
      TRI_set_errno(TRI_ERROR_OUT_OF_MEMORY);
      TRI_Free(TRI_CORE_MEM_ZONE, (void*) fieldList);
      return NULL;
    }

    fieldList[j] = ((const char*) path) + sizeof(TRI_shape_path_t) + path->_aidLength * sizeof(TRI_shape_aid_t);
  }

  return fieldList;
}

////////////////////////////////////////////////////////////////////////////////
/// @}
////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// --SECTION--                                                     PRIMARY INDEX
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
// --SECTION--                                                 private functions
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief insert methods does nothing
////////////////////////////////////////////////////////////////////////////////

static int InsertPrimary (TRI_index_t* idx, 
                          TRI_doc_mptr_t const* doc, 
                          const bool isRollback) {
  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief remove methods does nothing
////////////////////////////////////////////////////////////////////////////////

static int RemovePrimary (TRI_index_t* idx, 
                          TRI_doc_mptr_t const* doc,
                          const bool isRollback) {
  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief JSON description of a primary index
////////////////////////////////////////////////////////////////////////////////

static TRI_json_t* JsonPrimary (TRI_index_t* idx) { 
  TRI_json_t* json;
  TRI_json_t* fields;

  json = TRI_JsonIndex(TRI_CORE_MEM_ZONE, idx);
  
  if (json == NULL) {
    return NULL;
  }

  fields = TRI_CreateListJson(TRI_CORE_MEM_ZONE);
  TRI_PushBack3ListJson(TRI_CORE_MEM_ZONE, fields, TRI_CreateStringCopyJson(TRI_CORE_MEM_ZONE, "_id"));
  TRI_Insert3ArrayJson(TRI_CORE_MEM_ZONE, json, "fields", fields);

  return json;
}

////////////////////////////////////////////////////////////////////////////////
/// @}
////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// --SECTION--                                        constructors / destructors
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief create the primary index
////////////////////////////////////////////////////////////////////////////////

TRI_index_t* TRI_CreatePrimaryIndex (struct TRI_primary_collection_s* primary) {
  TRI_index_t* idx;
  char* id;

  // note: primary can be NULL

  // create primary index
  idx = TRI_Allocate(TRI_CORE_MEM_ZONE, sizeof(TRI_index_t), false);

  if (idx == NULL) {
    return NULL;
  }

  id = TRI_DuplicateStringZ(TRI_CORE_MEM_ZONE, "_id");
  TRI_InitVectorString(&idx->_fields, TRI_CORE_MEM_ZONE);
  TRI_PushBackVectorString(&idx->_fields, id);

  TRI_InitIndex(idx, 0, TRI_IDX_TYPE_PRIMARY_INDEX, primary, true);

  idx->json     = JsonPrimary;
  idx->insert   = InsertPrimary;
  idx->remove   = RemovePrimary;

  return idx;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief destroys a primary index, but does not free the pointer
////////////////////////////////////////////////////////////////////////////////

void TRI_DestroyPrimaryIndex (TRI_index_t* idx) {
  LOG_TRACE("destroying primary index");

  TRI_DestroyVectorString(&idx->_fields);
}

////////////////////////////////////////////////////////////////////////////////
/// @brief free a primary index
////////////////////////////////////////////////////////////////////////////////

void TRI_FreePrimaryIndex (TRI_index_t* idx) {
 TRI_DestroyPrimaryIndex(idx);
 TRI_Free(TRI_CORE_MEM_ZONE, idx);
}

////////////////////////////////////////////////////////////////////////////////
/// @}
////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// --SECTION--                                                        EDGE INDEX
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
// --SECTION--                                                 private functions
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief hashes an edge key 
////////////////////////////////////////////////////////////////////////////////

static uint64_t HashElementKey (TRI_multi_pointer_t* array, void const* data) {
  TRI_edge_header_t const* h;
  uint64_t hash;
  char* key;

  h = data;

  assert(h->_mptr == NULL);

  key = h->_searchKey._key;

  // only include directional bits for hashing, exclude special bits
  hash = (uint64_t) (h->_flags & TRI_EDGE_BITS_DIRECTION) ^ h->_cid;
  hash ^=  (uint64_t) fasthash64(key, strlen(key), 0x87654321);

  return fasthash64(&hash, sizeof(hash), 0x56781234);
}

////////////////////////////////////////////////////////////////////////////////
/// @brief hashes an edge header
////////////////////////////////////////////////////////////////////////////////

static uint64_t HashElementEdge (TRI_multi_pointer_t* array, void const* data,
                                 bool byKey) {
  TRI_edge_header_t const* h;
  uint64_t hash;
  char const* p;

  h = data;

  assert(h->_mptr != NULL);

  // only include directional bits for hashing, exclude special bits
  hash = (uint64_t) (h->_flags & TRI_EDGE_BITS_DIRECTION) ^ h->_cid;
  if (byKey) {
    p = (char*) h->_mptr->_data + h->_searchKey._offsetKey;
    hash ^= (uint64_t) fasthash64(p, strlen(p), 0x87654321);
  }
  else {
    hash ^= (uint64_t) h->_mptr;
  }

  return fasthash64(&hash, sizeof(hash), 0x56781234);
}

////////////////////////////////////////////////////////////////////////////////
/// @brief checks if key and element match
////////////////////////////////////////////////////////////////////////////////

static bool IsEqualKeyEdge (TRI_multi_pointer_t* array,
                            void const* left,
                            void const* right) {
  // left is a key, that is with NULL master pointer
  // right is an element, that is, with non-NULL master pointer
  TRI_edge_header_t const* l;
  TRI_edge_header_t const* r;
  const char* lKey;
  const char* rKey;

  l = left;
  r = right;

  assert(l->_mptr == NULL);
  lKey = l->_searchKey._key;

  assert(r->_mptr != NULL);
  rKey = ((char*) ((TRI_doc_edge_key_marker_t const*) r->_mptr->_data)) + 
         r->_searchKey._offsetKey;

  // only include directional flags, exclude special bits
  return (strcmp(lKey, rKey) == 0) &&
         ((l->_flags & TRI_EDGE_BITS_DIRECTION) ==
          (r->_flags & TRI_EDGE_BITS_DIRECTION)) &&
         (l->_cid == r->_cid);
}

////////////////////////////////////////////////////////////////////////////////
/// @brief checks for elements are equal
////////////////////////////////////////////////////////////////////////////////

static bool IsEqualElementEdge (TRI_multi_pointer_t* array,
                                void const* left,
                                void const* right,
                                bool byKey) {
  TRI_edge_header_t const* l;
  TRI_edge_header_t const* r;
  const char* lKey;
  const char* rKey;

  l = left;
  r = right;

  assert(l->_mptr != NULL);
  assert(l->_mptr != NULL);

  if (byKey) {
    lKey = ((char*) ((TRI_doc_edge_key_marker_t const*) l->_mptr->_data)) + 
           l->_searchKey._offsetKey;
    rKey = ((char*) ((TRI_doc_edge_key_marker_t const*) r->_mptr->_data)) + 
           r->_searchKey._offsetKey;
    
    return (strcmp(lKey, rKey) == 0) &&
           ((l->_flags & TRI_EDGE_BITS_DIRECTION) ==
            (r->_flags & TRI_EDGE_BITS_DIRECTION)) &&
           (l->_cid == r->_cid);
  }
  else {
    // only include directional flags, exclude special bits
    return (l->_mptr == r->_mptr) &&
           ((l->_flags & TRI_EDGE_BITS_DIRECTION) == 
            (r->_flags & TRI_EDGE_BITS_DIRECTION));
  }
}

////////////////////////////////////////////////////////////////////////////////
/// @brief insert method for edges
////////////////////////////////////////////////////////////////////////////////

static int InsertEdge (TRI_index_t* idx, 
                       TRI_doc_mptr_t const* mptr,
                       const bool isRollback) {
  TRI_edge_header_t* entryIn;
  TRI_edge_header_t* entryOut;
  char* memory;
  TRI_doc_edge_key_marker_t const* edge;
  bool isReflexive;

  TRI_multi_pointer_t* edgesIndex = &(((TRI_edge_index_t*) idx)->_edges);

  edge = mptr->_data;

  // is the edge self-reflexive (_from & _to are identical)?
  isReflexive = (edge->_toCid == edge->_fromCid && strcmp(((char*) edge) + edge->_offsetToKey, ((char*) edge) + edge->_offsetFromKey) == 0);

  // allocate memory for both edge headers and return early if memory allocation fails
  memory = TRI_Allocate(TRI_UNKNOWN_MEM_ZONE, 2 * sizeof(TRI_edge_header_t), false);

  if (memory == NULL) {
    return TRI_set_errno(TRI_ERROR_OUT_OF_MEMORY);
  }

  entryIn  = (TRI_edge_header_t*) memory;
  entryOut = (TRI_edge_header_t*) (memory + sizeof(TRI_edge_header_t));

  // first slot: IN
  entryIn->_mptr = mptr;
  entryIn->_flags = TRI_FlagsEdge(TRI_EDGE_IN, isReflexive);
  entryIn->_cid = edge->_toCid;
  entryIn->_searchKey._offsetKey = edge->_offsetToKey;
  TRI_InsertElementMultiPointer(edgesIndex, entryIn, true, isRollback);
    
  // second slot: OUT
  entryOut->_mptr = mptr;
  entryOut->_flags = TRI_FlagsEdge(TRI_EDGE_OUT, isReflexive);
  entryOut->_cid = edge->_fromCid;
  entryOut->_searchKey._offsetKey = edge->_offsetFromKey;
  TRI_InsertElementMultiPointer(edgesIndex, entryOut, true, isRollback);
  
  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief remove an edge
////////////////////////////////////////////////////////////////////////////////

static int RemoveEdge (TRI_index_t* idx, 
                       TRI_doc_mptr_t const* doc,
                       const bool isRollback) {
  TRI_edge_header_t entry;
  TRI_edge_header_t* old;
  TRI_doc_edge_key_marker_t const* edge;
  TRI_multi_pointer_t* edgesIndex = &(((TRI_edge_index_t*) idx)->_edges);

  edge = doc->_data;

  entry._mptr = doc;

  // OUT
  entry._flags = TRI_LookupFlagsEdge(TRI_EDGE_OUT);
  entry._cid = edge->_fromCid;
  entry._searchKey._offsetKey = edge->_offsetFromKey;
  TRI_RemoveElementMultiPointer(edgesIndex, &entry);
  // we do not need to free the OUT element

  // IN
  entry._flags = TRI_LookupFlagsEdge(TRI_EDGE_IN);
  entry._cid = edge->_toCid;
  entry._searchKey._offsetKey = edge->_offsetToKey;
  old = TRI_RemoveElementMultiPointer(edgesIndex, &entry);

  // the pointer to the IN element is also the memory pointer we need to free
  if (old != NULL) {
    TRI_Free(TRI_UNKNOWN_MEM_ZONE, old);
  }

  return TRI_ERROR_NO_ERROR;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief JSON description of edge index
////////////////////////////////////////////////////////////////////////////////

static TRI_json_t* JsonEdge (TRI_index_t* idx) {
  TRI_json_t* json;
  TRI_json_t* fields;

  json = TRI_JsonIndex(TRI_CORE_MEM_ZONE, idx);

  if (json == NULL) {
    return NULL;
  }

  fields = TRI_CreateListJson(TRI_CORE_MEM_ZONE);
  TRI_PushBack3ListJson(TRI_CORE_MEM_ZONE, fields, TRI_CreateStringCopyJson(TRI_CORE_MEM_ZONE, TRI_VOC_ATTRIBUTE_FROM));
  TRI_PushBack3ListJson(TRI_CORE_MEM_ZONE, fields, TRI_CreateStringCopyJson(TRI_CORE_MEM_ZONE, TRI_VOC_ATTRIBUTE_TO));
  TRI_Insert3ArrayJson(TRI_CORE_MEM_ZONE, json, "fields", fields);

  return json;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief provides a size hint for the edge index
////////////////////////////////////////////////////////////////////////////////

static int SizeHintEdge (TRI_index_t* idx,
                         size_t size) {

  TRI_multi_pointer_t* edgesIndex = &(((TRI_edge_index_t*) idx)->_edges);

  // we assume this is called when setting up the index and the index is still empty
  assert(edgesIndex->_nrUsed == 0);

  // set an initial size for the index and allow for some new nodes to be created
  // without resizing
  return TRI_ResizeMultiPointer(edgesIndex, 2 * size + 2049);
}

////////////////////////////////////////////////////////////////////////////////
/// @}
////////////////////////////////////////////////////////////////////////////////

// -----------------------------------------------------------------------------
// --SECTION--                                        constructors / destructors
// -----------------------------------------------------------------------------

////////////////////////////////////////////////////////////////////////////////
/// @addtogroup VocBase
/// @{
////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
/// @brief create the edge index
////////////////////////////////////////////////////////////////////////////////

TRI_index_t* TRI_CreateEdgeIndex (struct TRI_primary_collection_s* primary,
                                  TRI_idx_iid_t iid) {
  TRI_edge_index_t* edgeIndex;
  TRI_index_t* idx;
  char* id;
  int res;

  // create index
  edgeIndex = TRI_Allocate(TRI_CORE_MEM_ZONE, sizeof(TRI_edge_index_t), false);

  if (edgeIndex == NULL) {
    return NULL;
  }
 
  res = TRI_InitMultiPointer(&edgeIndex->_edges,
                             TRI_UNKNOWN_MEM_ZONE,
                             HashElementKey,
                             HashElementEdge,
                             IsEqualKeyEdge,
                             IsEqualElementEdge);
  
  if (res != TRI_ERROR_NO_ERROR) {
    TRI_Free(TRI_CORE_MEM_ZONE, edgeIndex);

    return NULL;
  }


  idx = &edgeIndex->base;

  TRI_InitVectorString(&idx->_fields, TRI_CORE_MEM_ZONE);
  id = TRI_DuplicateStringZ(TRI_CORE_MEM_ZONE, TRI_VOC_ATTRIBUTE_FROM);
  TRI_PushBackVectorString(&idx->_fields, id);
 
  TRI_InitIndex(idx, iid, TRI_IDX_TYPE_EDGE_INDEX, primary, false); 

  idx->json     = JsonEdge;
  idx->insert   = InsertEdge;
  idx->remove   = RemoveEdge;

  idx->sizeHint = SizeHintEdge;

  return idx;
}

////////////////////////////////////////////////////////////////////////////////
/// @brief destroys the edge index, but does not free the pointer
////////////////////////////////////////////////////////////////////////////////

void TRI_DestroyEdgeIndex (TRI_index_t* idx) {
  TRI_edge_index_t* edgesIndex;
  size_t i, n;

  edgesIndex = (TRI_edge_index_t*) idx;

  LOG_TRACE("destroying edge index");

  // free all elements in the edges index
  n = (size_t) edgesIndex->_edges._nrAlloc;
  
  // deletion from the index is done in two steps as memory was only allocated for IN edges
  // the OUT edges are at memory position IN + sizeof(edge_header) and 
  // must not be freed themselves

  // step 1: zero out all the out edges (we must not free them directly)
  for (i = 0; i < n; ++i) {
    TRI_edge_header_t* element = edgesIndex->_edges._table[i].ptr;
  
    if (element != NULL && (element->_flags & TRI_EDGE_BIT_DIRECTION_OUT)) {
      edgesIndex->_edges._table[i].ptr = NULL;
    }
  }
  
  // step 2: free the allocated memory
  for (i = 0; i < n; ++i) {
    TRI_edge_header_t* element = edgesIndex->_edges._table[i].ptr;

    if (element != NULL) {
      TRI_Free(TRI_UNKNOWN_MEM_ZONE, element);
    }
{'fraction_non_alphanumeric': 0.33980979495411456, 'fraction_numerical': 0.004270527304116062, 'mean_word_length': 1.2052831952978893, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 257, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 36, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7521544', 'n_tokens_mistral': 18271, 'n_tokens_neox': 17473, 'n_words': 3910}