<commit_before>
#include <stdlib.h>
#include <string.h>

#include "SKIP_LIST.h"

namespace SKIP_LIST {

  struct HANDLE {
    int (*compare) ( void const * node1, void const * node2 );
    int max_level;
    int current_level;
    double prob;
    unsigned short rand_state[3];
    size_t num_items;
    struct NODE * header;
  };

  struct HANDLE * init( int (*compare) ( void const * node1, void const * node2 ), int max_level, double prob ) {
    struct HANDLE *h = (struct HANDLE *) calloc( 1, sizeof(struct HANDLE) );
    h->compare = compare;
    if(max_level < 1) max_level = 32;
    if(prob < 0 || prob >= 1) prob = 0.25;
    h->max_level = max_level;
    h->current_level = 0;
    h->prob = prob;
    h->header = (struct NODE *) calloc( 1, sizeof(struct NODE) + sizeof(struct NODE*) * h->max_level );
    h->header->data = NULL;
    h->header->num_forward = h->max_level;
    h->num_items = 0;
    return h;
  }

  void destroy( struct HANDLE *& h ) {
    free(h);
    h = NULL;
  }

  int generate_level( HANDLE * h ) {
    int level = 0;
    double r;
    do {
      r = erand48(h->rand_state);
      ++level;
    } while(r < h->prob && level < h->max_level);
    return level;
  }

  void insert( struct HANDLE * h, void * item, size_t item_len ) {
    struct NODE ** update = (struct NODE **) calloc( 1, sizeof(struct NODE*) * h->max_level );
    struct NODE * n = h->header;
    struct NODE ** forward = (struct NODE **) (n+1);
    for( int i=h->current_level; i>0; --i ) {
      while( n->num_forward >= i && forward[i-1] && h->compare((forward[i-1])->data, item) < 0 ) {
	n = forward[i-1];
	forward = (struct NODE **) (n+1);
      }
      update[i-1] = n;
    }
    n = *(struct NODE **) (n+1);
    if( n && h->compare(n->data, item) == 0 )
      return;
    else {
      int new_level = generate_level( h );
      if( new_level > h->current_level ) {
	for( int i=h->current_level; i<new_level; ++i ) {
	  update[i] = h->header;
	}
	h->current_level = new_level;
      }
      NODE * new_node = (struct NODE *) calloc( 1, sizeof(struct NODE) + item_len + sizeof(struct NODE*) * new_level );
      new_node->data = ((char *) (new_node+1)) + sizeof(struct NODE *) * new_level;
      memcpy( new_node->data, item, item_len );
      new_node->data_len = item_len;
      new_node->num_forward = new_level;
      struct NODE ** nforward = (struct NODE **) (new_node+1);
      for( int i=0; i<new_level; ++i ) {
	struct NODE ** forward = (struct NODE **) (update[i]+1);
	nforward[i] = forward[i];
	forward[i] = new_node;
      }
      h->num_items += 1;
    }
    free( update );
  }

  void remove( struct HANDLE * h, void * item ) {
    struct NODE ** update = (struct NODE **) calloc( 1, sizeof(struct NODE*) * h->max_level );
    struct NODE * n = h->header;
    struct NODE ** forward = (struct NODE **) (n+1);
    for( int i=h->current_level; i>0; --i ) {<commit_msg>Update SKIP_LIST.cc<commit_after>
#include <stdlib.h>
#include <string.h>

#include "SKIP_LIST.h"

namespace SKIP_LIST {

  struct HANDLE {
    int (*compare) ( void const * node1, void const * node2 );
    int max_level;
    int current_level;
    double prob;
    unsigned short rand_state[3];
    size_t num_items;
    struct NODE * header;
  };

  struct HANDLE * init( int (*compare) ( void const * node1, void const * node2 ), int max_level, double prob ) {
    struct HANDLE *h = (struct HANDLE *) calloc( 1, sizeof(struct HANDLE) );
    h->compare = compare;
    if(max_level < 1) max_level = 32;
    if(prob < 0 || prob >= 1) prob = 0.25;
    h->max_level = max_level;
    h->current_level = 0;
    h->prob = prob;
    h->header = (struct NODE *) calloc( 1, sizeof(struct NODE) + sizeof(struct NODE*) * h->max_level );
    h->header->data = NULL;
    h->header->num_forward = h->max_level;
    h->num_items = 0;
    return h;
  }

  void destroy( struct HANDLE *& h ) {
    free(h);
    h = NULL;
  }

  int generate_level( HANDLE * h ) {
    int level = 0;
    double r;
    do {
      r = erand48(h->rand_state);
      ++level;
    } while(r < h->prob && level < h->max_level);
    return level;
  }

  void insert( struct HANDLE * h, void * item, size_t item_len ) {
    struct NODE ** update = (struct NODE **) calloc( 1, sizeof(struct NODE*) * h->max_level );
    struct NODE * n = h->header;
    struct NODE ** forward = (struct NODE **) (n+1);
    for( int i=h->current_level; i>0; --i ) {
      while( n->num_forward >= i && forward[i-1] && h->compare((forward[i-1])->data, item) < 0 ) {
	n = forward[i-1];
	forward = (struct NODE **) (n+1);
      }
      update[i-1] = n;
    }
    n = *(struct NODE **) (n+1);
    if( n && h->compare(n->data, item) == 0 ) {
    	free( update );
    	return;
    }
    else {
      int new_level = generate_level( h );
      if( new_level > h->current_level ) {
	for( int i=h->current_level; i<new_level; ++i ) {
	  update[i] = h->header;
	}
	h->current_level = new_level;
      }
      NODE * new_node = (struct NODE *) calloc( 1, sizeof(struct NODE) + item_len + sizeof(struct NODE*) * new_level );
      new_node->data = ((char *) (new_node+1)) + sizeof(struct NODE *) * new_level;
      memcpy( new_node->data, item, item_len );
      new_node->data_len = item_len;
      new_node->num_forward = new_level;
      struct NODE ** nforward = (struct NODE **) (new_node+1);
      for( int i=0; i<new_level; ++i ) {
	struct NODE ** forward = (struct NODE **) (update[i]+1);
	nforward[i] = forward[i];
	forward[i] = new_node;
      }
      h->num_items += 1;
    }
    free( update );
  }

  void remove( struct HANDLE * h, void * item ) {
    struct NODE ** update = (struct NODE **) calloc( 1, sizeof(struct NODE*) * h->max_level );
    struct NODE * n = h->header;
    struct NODE ** forward = (struct NODE **) (n+1);
    for( int i=h->current_level; i>0; --i ) {
{'fraction_non_alphanumeric': 0.1679889617109348, 'fraction_numerical': 0.013797861331493619, 'mean_word_length': 2.6889312977099236, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 87, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2175622', 'n_tokens_mistral': 2223, 'n_tokens_neox': 2148, 'n_words': 561}