introduce Roaring bitmaps to Git

2,986 lines not on this page · raw message

1,011 lines not on this page · raw message

index 9b126d6ce0e..9e221dd7cc9 100644
@@ -80,6 +80,11 @@ static struct option *add_common_options(struct option *prev)
 static int git_multi_pack_index_write_config(const char *var, const char *value,
 					     void *cb UNUSED)
 {
+	if (!strcmp(var, "pack.useroaringbitmap")) {
+		if (git_config_bool(var, value))
+			opts.flags |= MIDX_WRITE_ROARING_BITMAP;
+	}
+
 	if (!strcmp(var, "pack.writebitmaphashcache")) {
 		if (git_config_bool(var, value))
 			opts.flags |= MIDX_WRITE_BITMAP_HASH_CACHE;

index 3658c05cafc..439c5572c18 100644
@@ -228,7 +228,7 @@ static enum {
 	WRITE_BITMAP_QUIET,
 	WRITE_BITMAP_TRUE,
 } write_bitmap_index;
-static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE;
+static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE | BITMAP_SET_EWAH_BITMAP;
 
 static int exclude_promisor_objects;
 

@@ -1258,6 +1258,7 @@ static void write_pack_file(void)
 				    hash_to_hex(hash));
 
 			if (write_bitmap_index) {
+				bitmap_writer_init_bm_type(write_bitmap_options);
 				bitmap_writer_set_checksum(hash);
 				bitmap_writer_build_type_index(
 					&to_pack, written_list, nr_written);

@@ -3143,6 +3144,10 @@ static int git_pack_config(const char *k, const char *v, void *cb)
 		cache_max_small_delta_size = git_config_int(k, v);
 		return 0;
 	}
+	if (!strcmp(k, "pack.useroaringbitmap")) {
+		if (git_config_bool(k, v))
+			write_bitmap_options |= BITMAP_SET_ROARING_BITMAP;
+	}
 	if (!strcmp(k, "pack.writebitmaphashcache")) {
 		if (git_config_bool(k, v))
 			write_bitmap_options |= BITMAP_OPT_HASH_CACHE;

index c27d0e5f151..b80db2239a8 100644
@@ -1112,10 +1112,16 @@ static int write_midx_bitmap(const char *midx_name,
 {
 	int ret, i;
 	uint16_t options = 0;
+	unsigned version = 0;
 	struct pack_idx_entry **index;
 	char *bitmap_name = xstrfmt("%s-%s.bitmap", midx_name,
 					hash_to_hex(midx_hash));
 
+	if (flags & MIDX_WRITE_ROARING_BITMAP)
+		version |= BITMAP_SET_ROARING_BITMAP;
+	else
+		version |= BITMAP_SET_EWAH_BITMAP;
+
 	if (flags & MIDX_WRITE_BITMAP_HASH_CACHE)
 		options |= BITMAP_OPT_HASH_CACHE;
 

@@ -1131,6 +1137,7 @@ static int write_midx_bitmap(const char *midx_name,
 	for (i = 0; i < pdata->nr_objects; i++)
 		index[i] = &pdata->objects[i].idx;
 
+	bitmap_writer_init_bm_type(version);
 	bitmap_writer_show_progress(flags & MIDX_PROGRESS);
 	bitmap_writer_build_type_index(pdata, index, pdata->nr_objects);
 

index 5578cd7b835..c0b19b93c9c 100644
@@ -48,6 +48,7 @@ struct multi_pack_index {
 #define MIDX_WRITE_BITMAP (1 << 2)
 #define MIDX_WRITE_BITMAP_HASH_CACHE (1 << 3)
 #define MIDX_WRITE_BITMAP_LOOKUP_TABLE (1 << 4)
+#define MIDX_WRITE_ROARING_BITMAP (1 << 5)
 
 const unsigned char *get_midx_checksum(struct multi_pack_index *m);
 void get_midx_filename(struct strbuf *out, const char *object_dir);

index 7d71deca023..6103e0d57e7 100644
@@ -30,9 +30,6 @@ struct bitmap_disk_header {
 
 #define NEEDS_BITMAP (1u<<22)
 
-#define BITMAP_SET_EWAH_BITMAP 0x1
-#define BITMAP_SET_ROARING_BITMAP (1 << 1)
-
 /*
  * The width in bytes of a single triplet in the lookup table
  * extension:

@@ -44,7 +41,9 @@ struct bitmap_disk_header {
 
 enum pack_bitmap_opts {
 	BITMAP_OPT_FULL_DAG = 0x1,
-	BITMAP_OPT_HASH_CACHE = 0x4,
+	BITMAP_SET_EWAH_BITMAP = 0x2,
+	BITMAP_SET_ROARING_BITMAP = 0x4,
+	BITMAP_OPT_HASH_CACHE = 0x8,
 	BITMAP_OPT_LOOKUP_TABLE = 0x10,
 };
 

index df2d90544cd..ee44de20996 100644
@@ -1791,6 +1791,10 @@ bool array_container_iterate64(const array_container_t *cont, uint32_t base,
  *
  */
 int32_t array_container_write(const array_container_t *container, char *buf);
+
+int array_container_network_write(const array_container_t *container,
+				  int (*write_fn) (void *, const void *, size_t),
+				  void *data);
 /**
  * Reads the instance from buf, outputs how many bytes were read.
  * This is meant to be byte-by-byte compatible with the Java and Go versions of

@@ -1801,6 +1805,9 @@ int32_t array_container_write(const array_container_t *container, char *buf);
 int32_t array_container_read(int32_t cardinality, array_container_t *container,
                              const char *buf);
 
+int32_t array_container_network_read(int32_t cardinality, array_container_t *container,
+                        	     const char *buf);
+
 /**
  * Return the serialized size in bytes of a container (see
  * bitset_container_write)

@@ -2506,6 +2513,10 @@ bool bitset_container_iterate64(const bitset_container_t *cont, uint32_t base,
  */
 int32_t bitset_container_write(const bitset_container_t *container, char *buf);
 
+int bitset_container_network_write(const bitset_container_t *container,
+				   int (*write_fn) (void *, const void *, size_t),
+				   void *data);
+
 /**
  * Reads the instance from buf, outputs how many bytes were read.
  * This is meant to be byte-by-byte compatible with the Java and Go versions of

@@ -2515,6 +2526,9 @@ int32_t bitset_container_write(const bitset_container_t *container, char *buf);
  */
 int32_t bitset_container_read(int32_t cardinality,
                               bitset_container_t *container, const char *buf);
+
+int32_t bitset_container_network_read(int32_t cardinality, bitset_container_t *container,
+				      const char *buf);
 /**
  * Return the serialized size in bytes of a container (see
  * bitset_container_write).

@@ -3029,6 +3043,10 @@ bool run_container_iterate64(const run_container_t *cont, uint32_t base,
  */
 int32_t run_container_write(const run_container_t *container, char *buf);
 
+int run_container_network_write(const run_container_t *container,
+				int (*write_fn) (void *, const void*, size_t),
+				void *data);
+
 /**
  * Reads the instance from buf, outputs how many bytes were read.
  * This is meant to be byte-by-byte compatible with the Java and Go versions of

@@ -3041,6 +3059,9 @@ int32_t run_container_write(const run_container_t *container, char *buf);
 int32_t run_container_read(int32_t cardinality, run_container_t *container,
                            const char *buf);
 
+int32_t run_container_network_read(int32_t cardinality, run_container_t *container,
+                        	   const char *buf);
+
 /**
  * Return the serialized size in bytes of a container (see run_container_write).
  * This is meant to be compatible with the Java and Go versions of Roaring.

@@ -4513,6 +4534,24 @@ static inline int32_t container_write(
     return 0;  // unreached
 }
 
+static int container_network_write(const container_t *c, uint8_t typecode,
+				   int (*write_fn) (void *, const void *, size_t),
+				   void *data)
+{
+	c = container_unwrap_shared(c, &typecode);
+	switch (typecode) {
+		case BITSET_CONTAINER_TYPE:
+			return bitset_container_network_write(const_CAST_bitset(c), write_fn, data);
+		case ARRAY_CONTAINER_TYPE:
+			return array_container_network_write(const_CAST_array(c), write_fn, data);
+		case RUN_CONTAINER_TYPE:
+			return run_container_network_write(const_CAST_run(c), write_fn, data);
+	}
+	assert(false);
+	__builtin_unreachable();
+	return 0;
+}
+
 /**
  * Get the container size in bytes under portable serialization (see
  * container_write), requires a

@@ -6609,6 +6648,7 @@ static inline container_t *container_remove_range(
 #include <assert.h>
 #include <stdbool.h>
 #include <stdint.h>
+#include <arpa/inet.h>
 
 
 #ifdef __cplusplus

@@ -6811,6 +6851,10 @@ bool ra_range_uint32_array(const roaring_array_t *ra, size_t offset, size_t limi
  */
 size_t ra_portable_serialize(const roaring_array_t *ra, char *buf);
 
+int ra_portable_network_serialize(const roaring_array_t *ra,
+				  int (*write_fn) (void *, const void *, size_t),
+				  void *data);
+
 /**
  * read a bitmap from a serialized version. This is meant to be compatible
  * with the Java and Go versions.

@@ -7421,15 +7465,6 @@ void ra_append_range(roaring_array_t *ra, roaring_array_t *sa,
     }
 }
 
-container_t *ra_get_container(
-    roaring_array_t *ra, uint16_t x, uint8_t *typecode
-){
-    int i = binarySearch(ra->keys, (int32_t)ra->size, x);
-    if (i < 0) return NULL;
-    *typecode = ra->typecodes[i];
-    return ra->containers[i];
-}
-
 extern inline container_t *ra_get_container_at_index(
     const roaring_array_t *ra, uint16_t i,
     uint8_t *typecode);

@@ -7670,6 +7705,18 @@ uint32_t ra_portable_header_size(const roaring_array_t *ra) {
     }
 }
 
+static uint32_t ra_portable_network_header_size(const roaring_array_t *ra)
+{
+	if (ra_has_run_container(ra)) {
+		if (ra->size < NO_OFFSET_THRESHOLD) // for small bitmaps, we omit the offsets
+			return 4 + (ra->size + 7) / 8 + 4 * ra->size;
+
+		return 4 + (ra->size + 7) / 8 + 8 * ra->size;
+	} else {
+		return 4 + 8 * ra->size;
+	}
+}
+
 size_t ra_portable_size_in_bytes(const roaring_array_t *ra) {
     size_t count = ra_portable_header_size(ra);
 

@@ -7679,6 +7726,15 @@ size_t ra_portable_size_in_bytes(const roaring_array_t *ra) {
     return count;
 }
 
+static size_t ra_portable_network_size_in_bytes(const roaring_array_t *ra)
+{
+	size_t count = ra_portable_network_header_size(ra);
+
+	for (int32_t k = 0; k < ra->size; ++k)
+		count += container_size_in_bytes(ra->containers[k], ra->typecodes[k]);
+	return count;
+}
+
 size_t ra_portable_serialize(const roaring_array_t *ra, char *buf) {
     char *initbuf = buf;
     uint32_t startOffset = 0;

@@ -7740,6 +7796,80 @@ size_t ra_portable_serialize(const roaring_array_t *ra, char *buf) {
     return buf - initbuf;
 }
 
+int ra_portable_network_serialize(const roaring_array_t *ra,
+				  int (*write_fn) (void *, const void *, size_t),
+				  void *data)
+{
+	uint32_t initial_offset;
+	uint32_t cookie;
+	bool has_run = ra_has_run_container(ra);
+
+	if (has_run) {
+		uint8_t *bitmap_of_run_containers = NULL;
+		size_t bitmap_run_container_size = (ra->size + 7) / 8;
+
+		cookie = htonl(SERIAL_COOKIE | ((ra->size - 1) << 16));
+		if (write_fn(data, &cookie, 4) != 4)
+			return -1;
+		initial_offset = sizeof(cookie);
+
+		bitmap_of_run_containers = (uint8_t *)roaring_calloc(bitmap_run_container_size, 1);
+
+		for (uint32_t i = 0; i < ra->size; i++) {
+			if (get_container_type(ra->containers[i], ra->typecodes[i]) ==
+                	    RUN_CONTAINER_TYPE)
+				bitmap_of_run_containers[i / 8] |= (1 << (i % 8));
+		}
+
+		for (size_t i = 0; i < bitmap_run_container_size; i++) {
+			if (write_fn(data, bitmap_of_run_containers + i, 1) != 1) {
+				free(bitmap_of_run_containers);
+				return -1;
+			}
+		}
+		free(bitmap_of_run_containers);
+		initial_offset += bitmap_run_container_size;
+	} else {
+		cookie = htonl(SERIAL_COOKIE_NO_RUNCONTAINER | (ra->size - 1) << 16);
+		if (write_fn(data, &cookie, 4) != 4)
+			return -1;
+
+		initial_offset = sizeof(cookie);
+	}
+
+	/* description table */
+	for (uint32_t i = 0; i < ra->size; i++) {
+		uint16_t card;
+		uint16_t nt_key = htons(ra->keys[i]);
+
+		if (write_fn(data, &nt_key, sizeof(uint16_t)) != sizeof(uint16_t))
+			return -1;
+
+		card = (uint16_t)(container_get_cardinality(ra->containers[i], ra->typecodes[i]) - 1);
+		card = htons(card);
+		if (write_fn(data, &card, 2) != 2)
+			return -1;
+	}
+	initial_offset += 4 * ra->size;
+
+	if ((!has_run) || (ra->size >= NO_OFFSET_THRESHOLD)) {
+		uint32_t nt_offset;
+		initial_offset += 4 * ra->size;
+		nt_offset = htonl(initial_offset);
+		// writing the containers offsets
+		for (int32_t k = 0; k < ra->size; k++) {
+			if (write_fn(data, &nt_offset, sizeof(int32_t)) != sizeof(int32_t))
+				return -1;
+			initial_offset += container_size_in_bytes(ra->containers[k], ra->typecodes[k]);
+		}
+	}
+	for (int32_t k = 0; k < ra->size; ++k) {
+		container_network_write(ra->containers[k], ra->typecodes[k], write_fn, data);
+	}
+
+	return 0;
+}
+
 // Quickly checks whether there is a serialized bitmap at the pointer,
 // not exceeding size "maxbytes" in bytes. This function does not allocate
 // memory dynamically.

@@ -7827,6 +7957,83 @@ size_t ra_portable_deserialize_size(const char *buf, const size_t maxbytes) {
     return bytestotal;
 }
 
+size_t ra_portable_network_deserialize_size(const char *buf, const size_t maxbytes) {
+	size_t bytestotal = sizeof(int32_t);// for cookie
+	uint32_t cookie;
+	int32_t size;
+	if(bytestotal > maxbytes)
+		return 0;
+	memcpy(&cookie, buf, sizeof(int32_t));
+	cookie = ntohl(cookie);
+	buf += sizeof(uint32_t);
+	if ((cookie & 0xFFFF) != SERIAL_COOKIE &&
+		(cookie & 0xFFFF) != SERIAL_COOKIE_NO_RUNCONTAINER) {
+		return 0;
+	}
+
+	size = (cookie >> 16) + 1;
+	if (size > (1<<16)) {
+		return 0; // logically impossible
+	}
+	else if (size == (1 << 16))
+		return bytestotal;
+	char *bitmapOfRunContainers = NULL;
+	bool hasrun = (cookie & 0xFFFF) == SERIAL_COOKIE;
+	if (hasrun) {
+		int32_t s = (size + 7) / 8;
+		bytestotal += s;
+		if(bytestotal > maxbytes) return 0;
+		bitmapOfRunContainers = (char *)buf;
+		buf += s;
+	}
+	bytestotal += size * 2 * sizeof(uint16_t);
+	if(bytestotal > maxbytes) return 0;
+	uint16_t *keyscards = (uint16_t *)buf;
+	buf += size * 2 * sizeof(uint16_t);
+	if ((!hasrun) || (size >= NO_OFFSET_THRESHOLD)) {
+		// skipping the offsets
+		bytestotal += size * 4;
+		if(bytestotal > maxbytes) return 0;
+		buf += size * 4;
+	}
+	// Reading the containers
+	for (int32_t k = 0; k < size; ++k) {
+		uint16_t tmp;
+		memcpy(&tmp, keyscards + 2*k+1, sizeof(tmp));
+		uint32_t thiscard = ntohs(tmp) + 1;
+		bool isbitmap = (thiscard > DEFAULT_MAX_SIZE);
+		bool isrun = false;
+		if(hasrun && (bitmapOfRunContainers[k / 8] & (1 << (k % 8))) != 0) {
+			isbitmap = false;
+			isrun = true;
+		}
+		if (isbitmap) {
+			size_t containersize = BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t);
+			bytestotal += containersize;
+			if(bytestotal > maxbytes)
+				return 0;
+			buf += containersize;
+		} else if (isrun) {
+			bytestotal += sizeof(uint16_t);
+			if(bytestotal > maxbytes) return 0;
+			uint16_t n_runs;
+			memcpy(&n_runs, buf, sizeof(uint16_t));
+			n_runs = ntohs(n_runs);
+			buf += sizeof(uint16_t);
+			size_t containersize = n_runs * sizeof(rle16_t);
+			bytestotal += containersize;
+			if(bytestotal > maxbytes) return 0;
+			buf += containersize;
+		} else {
+			size_t containersize = thiscard * sizeof(uint16_t);
+			bytestotal += containersize;
+			if(bytestotal > maxbytes)
+				return 0;
+			buf += containersize;
+		}
+	}
+	return bytestotal;
+}
 
 // this function populates answer from the content of buf (reading up to maxbytes bytes).
 // The function returns false if a properly serialized bitmap cannot be found.

@@ -8000,6 +8207,177 @@ bool ra_portable_deserialize(roaring_array_t *answer, const char *buf, const siz
     return true;
 }
 
+bool ra_portable_network_deserialize(roaring_array_t *answer, const char *buf, const size_t maxbytes, size_t *readbytes)
+{
+	uint32_t cookie;
+	int32_t size;
+	const char *bitmapOfRunContainers = NULL;
+	int hasrun = 0;
+	uint16_t *keyscards;
+
+	*readbytes = sizeof(int32_t);// for cookie
+	if(*readbytes > maxbytes) {
+	fprintf(stderr, "Ran out of bytes while reading first 4 bytes.\n");
+	return false;
+	}
+	memcpy(&cookie, buf, sizeof(int32_t));
+	cookie = ntohl(cookie);
+	buf += sizeof(uint32_t);
+	if ((cookie & 0xFFFF) != SERIAL_COOKIE &&
+		(cookie & 0xFFFF) != SERIAL_COOKIE_NO_RUNCONTAINER) {
+		fprintf(stderr, "I failed to find one of the right cookies. Found %" PRIu32 "\n",
+			cookie);
+		return false;
+	}
+
+	size = (cookie >> 16) + 1;
+	if (size < 0) {
+		fprintf(stderr, "You cannot have a negative number of containers, the data must be corrupted: %" PRId32 "\n",
+				size);
+		return false; // logically impossible
+	}
+	if (size > (1<<16)) {
+		fprintf(stderr, "You cannot have so many containers, the data must be corrupted: %" PRId32 "\n",
+				size);
+		return false; // logically impossible
+	}
+	else if (size == (1 << 16)) {
+		ra_init_with_capacity(answer, size);
+		return true;
+	}
+	hasrun = (cookie & 0xFFFF) == SERIAL_COOKIE;
+	if (hasrun) {
+		int32_t s = (size + 7) / 8;
+		*readbytes += s;
+		if(*readbytes > maxbytes) {// data is corrupted?
+		fprintf(stderr, "Ran out of bytes while reading run bitmap.\n");
+		return false;
+		}
+		bitmapOfRunContainers = buf;
+		buf += s;
+	}
+	keyscards = (uint16_t *)buf;
+
+	*readbytes += size * 2 * sizeof(uint16_t);
+	if(*readbytes > maxbytes) {
+		fprintf(stderr, "Ran out of bytes while reading key-cardinality array.\n");
+		return false;
+	}
+	buf += size * 2 * sizeof(uint16_t);
+
+	bool is_ok = ra_init_with_capacity(answer, size);
+	if (!is_ok) {
+		fprintf(stderr, "Failed to allocate memory for roaring array. Bailing out.\n");
+		return false;
+	}
+
+	for (int32_t k = 0; k < size; ++k) {
+		uint16_t tmp;
+		memcpy(&tmp, keyscards + 2*k, sizeof(tmp));
+		answer->keys[k] = ntohs(tmp);
+	}
+	if ((!hasrun) || (size >= NO_OFFSET_THRESHOLD)) {
+		*readbytes += size * 4;
+		if(*readbytes > maxbytes) {// data is corrupted?
+			fprintf(stderr, "Ran out of bytes while reading offsets.\n");
+			ra_clear(answer);// we need to clear the containers already allocated, and the roaring array
+			return false;
+		}
+
+		// skipping the offsets
+		buf += size * 4;
+	}
+	// Reading the containers
+	for (int32_t k = 0; k < size; ++k) {
+		uint16_t tmp;
+		uint32_t thiscard;
+		bool isbitmap;
+		bool isrun;
+
+		memcpy(&tmp, keyscards + 2*k+1, sizeof(tmp));
+		thiscard = ntohs(tmp) + 1;
+		isbitmap = (thiscard > DEFAULT_MAX_SIZE);
+		isrun = false;
+		if(hasrun && (bitmapOfRunContainers[k / 8] & (1 << (k % 8))) != 0) {
+			isbitmap = false;
+			isrun = true;
+		}
+		if (isbitmap) {
+			// we check that the read is allowed
+			size_t containersize = BITSET_CONTAINER_SIZE_IN_WORDS * sizeof(uint64_t);
+			*readbytes += containersize;
+			if(*readbytes > maxbytes) {
+				fprintf(stderr, "Running out of bytes while reading a bitset container.\n");
+				ra_clear(answer);// we need to clear the containers already allocated, and the roaring array
+				return false;
+			}
+			// it is now safe to read
+			bitset_container_t *c = bitset_container_create();
+			if(c == NULL) {// memory allocation failure
+				fprintf(stderr, "Failed to allocate memory for a bitset container.\n");
+				ra_clear(answer);// we need to clear the containers already allocated, and the roaring array
+				return false;
+			}
+			answer->size++;
+			buf += bitset_container_network_read(thiscard, c, buf);
+			answer->containers[k] = c;
+			answer->typecodes[k] = BITSET_CONTAINER_TYPE;
+		} else if (isrun) {
+			// we check that the read is allowed
+			*readbytes += sizeof(uint16_t);
+			if(*readbytes > maxbytes) {
+				fprintf(stderr, "Running out of bytes while reading a run container (header).\n");
+				ra_clear(answer);// we need to clear the containers already allocated, and the roaring array
+				return false;
+			}
+			uint16_t n_runs;
+			memcpy(&n_runs, buf, sizeof(uint16_t));
+			n_runs = ntohs(n_runs);
+			size_t containersize = n_runs * sizeof(rle16_t);
+			*readbytes += containersize;
+			if(*readbytes > maxbytes) {// data is corrupted?
+				fprintf(stderr, "Running out of bytes while reading a run container.\n");
+				ra_clear(answer);// we need to clear the containers already allocated, and the roaring array
+				return false;
+			}
+			// it is now safe to read
+
+			run_container_t *c = run_container_create();
+			if(c == NULL) {// memory allocation failure
+				fprintf(stderr, "Failed to allocate memory for a run container.\n");
+				ra_clear(answer);// we need to clear the containers already allocated, and the roaring array
+				return false;
+			}
+			answer->size++;
+			buf += run_container_network_read(thiscard, c, buf);
+			answer->containers[k] = c;
+			answer->typecodes[k] = RUN_CONTAINER_TYPE;
+		} else {
+			// we check that the read is allowed
+			size_t containersize = thiscard * sizeof(uint16_t);
+			*readbytes += containersize;
+			if(*readbytes > maxbytes) {// data is corrupted?
+				fprintf(stderr, "Running out of bytes while reading an array container.\n");
+				ra_clear(answer);// we need to clear the containers already allocated, and the roaring array
+				return false;
+			}
+			// it is now safe to read
+			array_container_t *c =
+				array_container_create_given_capacity(thiscard);
+			if(c == NULL) {// memory allocation failure
+				fprintf(stderr, "Failed to allocate memory for an array container.\n");
+				ra_clear(answer);// we need to clear the containers already allocated, and the roaring array
+				return false;
+			}
+			answer->size++;
+			buf += array_container_network_read(thiscard, c, buf);
+			answer->containers[k] = c;
+			answer->typecodes[k] = ARRAY_CONTAINER_TYPE;
+		}
+	}
+	return true;
+}
+
 #ifdef __cplusplus
 } } }  // extern "C" { namespace roaring { namespace internal {
 #endif

@@ -8603,16 +8981,16 @@ extern inline void roaring_bitmap_remove_range(roaring_bitmap_t *r, uint64_t min
 void roaring_bitmap_printf(const roaring_bitmap_t *r) {
     const roaring_array_t *ra = &r->high_low_container;
 
-    printf("{");
+    fprintf(stderr, "{");
     for (int i = 0; i < ra->size; ++i) {
         container_printf_as_uint32_array(ra->containers[i], ra->typecodes[i],
                                          ((uint32_t)ra->keys[i]) << 16);
 
         if (i + 1 < ra->size) {
-            printf(",");
+            fprintf(stderr, ",");
         }
     }
-    printf("}");
+    fprintf(stderr, "}");
 }
 
 void roaring_bitmap_printf_describe(const roaring_bitmap_t *r) {

@@ -8736,6 +9114,14 @@ void roaring_bitmap_free(const roaring_bitmap_t *r) {
     roaring_free((roaring_bitmap_t*)r);
 }
 
+void roaring_bitmap_free_safe(roaring_bitmap_t **r)
+{
+	if (*r) {
+		roaring_bitmap_free((const roaring_bitmap_t *)*r);
+		r = NULL;
+	}
+}
+
 void roaring_bitmap_clear(roaring_bitmap_t *r) {
   ra_reset(&r->high_low_container);
 }

@@ -9700,6 +10086,11 @@ size_t roaring_bitmap_portable_size_in_bytes(const roaring_bitmap_t *r) {
     return ra_portable_size_in_bytes(&r->high_low_container);
 }
 
+size_t roaring_bitmap_network_portable_size_in_bytes(const roaring_bitmap_t *r)
+{
+	return ra_portable_network_size_in_bytes(&r->high_low_container);
+}
+
 
 roaring_bitmap_t *roaring_bitmap_portable_deserialize_safe(const char *buf, size_t maxbytes) {
     roaring_bitmap_t *ans =

@@ -9718,21 +10109,50 @@ roaring_bitmap_t *roaring_bitmap_portable_deserialize_safe(const char *buf, size
     return ans;
 }
 
+roaring_bitmap_t *roaring_bitmap_portable_network_deserialize_safe(const char *buf, size_t maxbytes)
+{
+	roaring_bitmap_t *ans =
+		(roaring_bitmap_t *)roaring_malloc(sizeof(roaring_bitmap_t));
+	if (ans == NULL) {
+		return NULL;
+	}
+	size_t bytesread;
+	bool is_ok = ra_portable_network_deserialize(&ans->high_low_container, buf, maxbytes, &bytesread);
+	if(is_ok) assert(bytesread <= maxbytes);
+	roaring_bitmap_set_copy_on_write(ans, false);
+	if (!is_ok) {
+		roaring_free(ans);
+		return NULL;
+	}
+	return ans;
+}
+
 roaring_bitmap_t *roaring_bitmap_portable_deserialize(const char *buf) {
     return roaring_bitmap_portable_deserialize_safe(buf, SIZE_MAX);
 }
 
-
 size_t roaring_bitmap_portable_deserialize_size(const char *buf, size_t maxbytes) {
   return ra_portable_deserialize_size(buf, maxbytes);
 }
 
+size_t roaring_bitmap_portable_network_deserialize_size(const char *buf, size_t maxbytes) {
+	size_t size = ra_portable_network_deserialize_size(buf, maxbytes);
+	return size;
+}
+
 
 size_t roaring_bitmap_portable_serialize(const roaring_bitmap_t *r,
                                          char *buf) {
     return ra_portable_serialize(&r->high_low_container, buf);
 }
 
+int roaring_bitmap_portable_network_serialize(roaring_bitmap_t *rb,
+				     int (*write_fn) (void *, const void *, size_t),
+				     void *data)
+{
+	return ra_portable_network_serialize(&rb->high_low_container, write_fn, data);
+}
+
 roaring_bitmap_t *roaring_bitmap_deserialize(const void *buf) {
     const char *bufaschar = (const char *)buf;
     if (*(const unsigned char *)buf == CROARING_SERIALIZATION_ARRAY_UINT32) {

@@ -13827,9 +14247,9 @@ void array_container_printf_as_uint32_array(const array_container_t *v,
     if (v->cardinality == 0) {
         return;
     }
-    printf("%u", v->array[0] + base);
+    fprintf(stderr, "%u", v->array[0] + base);
     for (int i = 1; i < v->cardinality; ++i) {
-        printf(",%u", v->array[i] + base);
+        fprintf(stderr, ",%u", v->array[i] + base);
     }
 }
 

@@ -13856,6 +14276,20 @@ int32_t array_container_write(const array_container_t *container, char *buf) {
     return array_container_size_in_bytes(container);
 }
 
+int array_container_network_write(const array_container_t *container,
+				  int (*write_fn) (void *, const void *, size_t),
+				  void *data)
+{
+	int32_t i;
+	size_t size = container->cardinality * sizeof(uint16_t);
+	for (i = 0; i < container->cardinality; i++) {
+		uint16_t nt_elem = htons(container->array[i]);
+		if (write_fn(data, &nt_elem, sizeof(uint16_t)) != sizeof(uint16_t))
+			return -1;
+	}
+	return 0;
+}
+
 bool array_container_is_subset(const array_container_t *container1,
                                const array_container_t *container2) {
     if (container1->cardinality > container2->cardinality) {

@@ -13890,6 +14324,23 @@ int32_t array_container_read(int32_t cardinality, array_container_t *container,
     return array_container_size_in_bytes(container);
 }
 
+int32_t array_container_network_read(int32_t cardinality, array_container_t *container,
+                        	     const char *buf)
+{
+	uint32_t i;
+	if (container->capacity < cardinality) {
+		array_container_grow(container, cardinality, false);
+	}
+	container->cardinality = cardinality;
+	for (i = 0; i < container->cardinality; i++) {
+		uint16_t val;
+		memcpy(&val, buf + i * sizeof(uint16_t), sizeof(uint16_t));
+		val = ntohs(val);
+		container->array[i] = val;
+	}
+	return array_container_size_in_bytes(container);
+}
+
 bool array_container_iterate(const array_container_t *cont, uint32_t base,
                              roaring_iterator iterator, void *ptr) {
     for (int i = 0; i < cont->cardinality; i++)

@@ -15208,13 +15659,13 @@ void run_container_printf_as_uint32_array(const run_container_t *cont,
     {
         uint32_t run_start = base + cont->runs[0].value;
         uint16_t le = cont->runs[0].length;
-        printf("%u", run_start);
-        for (uint32_t j = 1; j <= le; ++j) printf(",%u", run_start + j);
+        fprintf(stderr, "%u", run_start);
+        for (uint32_t j = 1; j <= le; ++j) fprintf(stderr, ",%u", run_start + j);
     }
     for (int32_t i = 1; i < cont->n_runs; ++i) {
         uint32_t run_start = base + cont->runs[i].value;
         uint16_t le = cont->runs[i].length;
-        for (uint32_t j = 0; j <= le; ++j) printf(",%u", run_start + j);
+        for (uint32_t j = 0; j <= le; ++j) fprintf(stderr, ",%u", run_start + j);
     }
 }
 

@@ -15225,6 +15676,28 @@ int32_t run_container_write(const run_container_t *container, char *buf) {
     return run_container_size_in_bytes(container);
 }
 
+int run_container_network_write(const run_container_t *container,
+				int (*write_fn) (void *, const void *, size_t),
+				void *data)
+{
+	uint16_t i;
+	int32_t nt_nruns = htonl(container->n_runs);
+	if (write_fn(data, &nt_nruns, sizeof(uint16_t)))
+		return -1;
+
+	for (i = 0; i < container->n_runs; i++) {
+		rle16_t run = container->runs[i];
+		uint16_t nt_value = htons(run.value);
+		uint16_t nt_len = htons(run.length);
+		if (write_fn(data, &nt_value, sizeof(uint16_t)) != sizeof(uint16_t))
+			return -1;
+		if (write_fn(data, &nt_len, sizeof(uint16_t)) != sizeof(uint16_t))
+			return -1;
+	}
+
+	return 0;
+}
+
 int32_t run_container_read(int32_t cardinality, run_container_t *container,
                            const char *buf) {
     (void)cardinality;

@@ -15238,6 +15711,29 @@ int32_t run_container_read(int32_t cardinality, run_container_t *container,
     return run_container_size_in_bytes(container);
 }
 
+int32_t run_container_network_read(int32_t cardinality, run_container_t *container,
+                        	   const char *buf)
+{
+	int32_t n_runs;
+	memcpy(&n_runs, buf, sizeof(uint16_t));
+	n_runs = ntohs(n_runs);
+	container->n_runs = n_runs;
+	if (container->n_runs > container->capacity)
+        run_container_grow(container, container->n_runs, false);
+	if(container->n_runs > 0) {
+		uint32_t i;
+
+		for (i = 0; i < container->n_runs; i++) {
+			rle16_t run;
+			memcpy(&run, buf + sizeof(uint16_t) + i * sizeof(rle16_t), sizeof(rle16_t));
+			run.length = ntohs(run.length);
+			run.value = ntohs(run.value);
+			container->runs[i] = run;
+		}
+	}
+	return run_container_size_in_bytes(container);
+}
+
 bool run_container_iterate(const run_container_t *cont, uint32_t base,
                            roaring_iterator iterator, void *ptr) {
     for (int i = 0; i < cont->n_runs; ++i) {

@@ -17417,10 +17913,10 @@ void bitset_container_printf_as_uint32_array(const bitset_container_t * v, uint3
 			uint64_t t = w & (~w + 1);
 			int r = __builtin_ctzll(w);
 			if(iamfirst) {// predicted to be false
-				printf("%u", r + base);
+				fprintf(stderr, "%u", r + base);
 				iamfirst = false;
 			} else {
-				printf(",%u",r + base);
+				fprintf(stderr, ",%u",r + base);
 			}
 			w ^= t;
 		}

@@ -17454,6 +17950,18 @@ int32_t bitset_container_write(const bitset_container_t *container,
 	return bitset_container_size_in_bytes(container);
 }
 
+int bitset_container_network_write(const bitset_container_t *container,
+				   int (*write_fn) (void *, const void *, size_t),
+				   void *data)
+{
+	uint32_t i = 0;
+	for (i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i++) {
+		uint64_t nt_word = htonll(container->words[i]);
+		if (write_fn(data, &nt_word, sizeof(uint64_t)) != sizeof(uint64_t))
+			return -1;
+	}
+	return 0;
+}
 
 int32_t bitset_container_read(int32_t cardinality, bitset_container_t *container,
 		const char *buf)  {

@@ -17462,6 +17970,23 @@ int32_t bitset_container_read(int32_t cardinality, bitset_container_t *container
 	return bitset_container_size_in_bytes(container);
 }
 
+int32_t bitset_container_network_read(int32_t cardinality, bitset_container_t *container,
+				      const char *buf)
+{
+	uint32_t i = 0;
+	const char *mbuf = buf;
+	container->cardinality = cardinality;
+
+	for (i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; i++) {
+		uint64_t nt_word;
+		memcpy(&nt_word, mbuf, sizeof(uint64_t));
+		mbuf += sizeof(uint64_t);
+
+		container->words[i] = ntohll(nt_word);
+	}
+	return bitset_container_size_in_bytes(container);
+}
+
 bool bitset_container_iterate(const bitset_container_t *cont, uint32_t base, roaring_iterator iterator, void *ptr) {
   for (int32_t i = 0; i < BITSET_CONTAINER_SIZE_IN_WORDS; ++i ) {
     uint64_t w = cont->words[i];

index bd5e0a0fe1c..84489eaa260 100644
@@ -409,6 +409,11 @@ void roaring_bitmap_andnot_inplace(roaring_bitmap_t *r1,
  */
 void roaring_bitmap_free(const roaring_bitmap_t *r);
 
+/**
+ * Frees the memory if exists
+ */
+void roaring_bitmap_free_safe(roaring_bitmap_t **r);
+
 /**
  * Add value n_args from pointer vals, faster than repeatedly calling
  * `roaring_bitmap_add()`

@@ -605,6 +610,9 @@ roaring_bitmap_t *roaring_bitmap_portable_deserialize(const char *buf);
 roaring_bitmap_t *roaring_bitmap_portable_deserialize_safe(const char *buf,
                                                            size_t maxbytes);
 
+roaring_bitmap_t *roaring_bitmap_portable_network_deserialize_safe(const char *buf,
+								   size_t maxbytes);
+
 /**
  * Check how many bytes would be read (up to maxbytes) at this pointer if there
  * is a bitmap, returns zero if there is no valid bitmap.

@@ -615,6 +623,9 @@ roaring_bitmap_t *roaring_bitmap_portable_deserialize_safe(const char *buf,
 size_t roaring_bitmap_portable_deserialize_size(const char *buf,
                                                 size_t maxbytes);
 
+size_t roaring_bitmap_portable_network_deserialize_size(const char *buf,
+							size_t maxbytes);
+
 /**
  * How many bytes are required to serialize this bitmap.
  *

@@ -623,6 +634,8 @@ size_t roaring_bitmap_portable_deserialize_size(const char *buf,
  */
 size_t roaring_bitmap_portable_size_in_bytes(const roaring_bitmap_t *r);
 
+size_t roaring_bitmap_network_portable_size_in_bytes(const roaring_bitmap_t *r);
+
 /**
  * Write a bitmap to a char buffer.  The output buffer should refer to at least
  * `roaring_bitmap_portable_size_in_bytes(r)` bytes of allocated memory.

@@ -635,6 +648,10 @@ size_t roaring_bitmap_portable_size_in_bytes(const roaring_bitmap_t *r);
  */
 size_t roaring_bitmap_portable_serialize(const roaring_bitmap_t *r, char *buf);
 
+int roaring_bitmap_portable_network_serialize(roaring_bitmap_t *rb,
+				     int (*write_fn) (void *, const void *, size_t),
+				     void *data);
+
 /*
  * "Frozen" serialization format imitates memory layout of roaring_bitmap_t.
  * Deserialized bitmap is a constant view of the underlying buffer.

226 lines not on this page · raw message

new file mode 100644
index 00000000000..d75400922cc
@@ -0,0 +1,33 @@
+#ifndef __BITMAP_H__
+#define __BITMAP_H__
+
+
+#include "git-compat-util.h"
+#include "ewah/ewok.h"
+#include "roaring/roaring.h"
+
+enum bitmap_type {
+	INIT_BITMAP_TYPE = 0,
+	EWAH,
+	ROARING
+};
+
+enum bitmap_type get_bitmap_type(void);
+void set_bitmap_type(enum bitmap_type type);
+void *roaring_or_ewah_bitmap_init(void);
+void *roaring_or_raw_bitmap_new(void);
+void *roaring_or_raw_bitmap_copy(void *bitmap);
+int roaring_or_ewah_bitmap_set(void *bitmap, uint32_t i);
+void roaring_or_raw_bitmap_set(void *bitmap, uint32_t i);
+int roaring_or_raw_bitmap_get(void *bitmap, uint32_t pos);
+int roaring_or_raw_bitmap_is_subset(void *a, void *b);
+void roaring_or_raw_bitmap_or(void *self, void *other);
+void roaring_or_raw_bitmap_free(void *bitmap);
+void roaring_or_raw_bitmap_free_safe(void **bitmap);
+void roaring_or_raw_bitmap_unset(void *bitmap, uint32_t i);
+void roaring_or_raw_bitmap_printf(void *a);
+int roaring_or_raw_bitmap_equals(void *a, void *b);
+void roaring_or_raw_bitmap_and_not(void *self, void *other);
+size_t roaring_or_raw_bitmap_cardinality(void *bitmap);
+
+#endif

index 54bb3de964c..8cf7481d325 100644
@@ -353,8 +353,8 @@ static void symdiff_prepare(struct rev_info *rev, struct symdiff *sym)
 			continue;
 		}
 		if (!map)
-			map = bitmap_new();
-		bitmap_set(map, i);
+			map = raw_bitmap_new();
+		raw_bitmap_set(map, i);
 	}
 
 	/*

@@ -364,7 +364,7 @@ static void symdiff_prepare(struct rev_info *rev, struct symdiff *sym)
 		usage(builtin_diff_usage);
 
 	if (!is_symdiff) {
-		bitmap_free(map);
+		raw_bitmap_free(map);
 		sym->warn = 0;
 		sym->skip = NULL;
 		return;

@@ -375,7 +375,7 @@ static void symdiff_prepare(struct rev_info *rev, struct symdiff *sym)
 	if (basecount == 0)
 		die(_("%s...%s: no merge base"), sym->left, sym->right);
 	sym->base = rev->pending.objects[basepos].name;
-	bitmap_unset(map, basepos);	/* unmark the base we want */
+	raw_bitmap_unset(map, basepos);	/* unmark the base we want */
 	sym->warn = basecount > 1;
 	sym->skip = map;
 }

@@ -539,7 +539,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)
 			obj = &get_commit_tree(((struct commit *)obj))->object;
 
 		if (obj->type == OBJ_TREE) {
-			if (sdiff.skip && bitmap_get(sdiff.skip, i))
+			if (sdiff.skip && raw_bitmap_get(sdiff.skip, i))
 				continue;
 			obj->flags |= flags;
 			add_object_array(obj, name, &ent);

150 lines not on this page · raw message

index 7eb8b9b6301..4fc96fd73d0 100644
@@ -171,23 +171,24 @@ struct bitmap {
 	size_t word_alloc;
 };
 
-struct bitmap *bitmap_new(void);
-struct bitmap *bitmap_word_alloc(size_t word_alloc);
-struct bitmap *bitmap_dup(const struct bitmap *src);
-void bitmap_set(struct bitmap *self, size_t pos);
-void bitmap_unset(struct bitmap *self, size_t pos);
-int bitmap_get(struct bitmap *self, size_t pos);
-void bitmap_free(struct bitmap *self);
-int bitmap_equals(struct bitmap *self, struct bitmap *other);
-int bitmap_is_subset(struct bitmap *self, struct bitmap *other);
-
-struct ewah_bitmap * bitmap_to_ewah(struct bitmap *bitmap);
-struct bitmap *ewah_to_bitmap(struct ewah_bitmap *ewah);
-
-void bitmap_and_not(struct bitmap *self, struct bitmap *other);
-void bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other);
-void bitmap_or(struct bitmap *self, const struct bitmap *other);
-
-size_t bitmap_popcount(struct bitmap *self);
+struct bitmap *raw_bitmap_new(void);
+struct bitmap *raw_bitmap_word_alloc(size_t word_alloc);
+struct bitmap *raw_bitmap_dup(const struct bitmap *src);
+void raw_bitmap_set(struct bitmap *self, size_t pos);
+void raw_bitmap_unset(struct bitmap *self, size_t pos);
+int raw_bitmap_get(struct bitmap *self, size_t pos);
+void raw_bitmap_free(struct bitmap *self);
+int raw_bitmap_equals(struct bitmap *self, struct bitmap *other);
+int raw_bitmap_is_subset(struct bitmap *self, struct bitmap *other);
+
+struct ewah_bitmap * raw_bitmap_to_ewah(struct bitmap *bitmap);
+struct bitmap *ewah_to_raw_bitmap(struct ewah_bitmap *ewah);
+
+void raw_bitmap_and_not(struct bitmap *self, struct bitmap *other);
+void raw_bitmap_or_ewah(struct bitmap *self, struct ewah_bitmap *other);
+void raw_bitmap_or(struct bitmap *self, const struct bitmap *other);
+void ewah_bitmap_print(struct ewah_bitmap *bm);
+
+size_t raw_bitmap_popcount(struct bitmap *self);
 
 #endif

562 lines not on this page · raw message

323 lines not on this page · raw message

index f0180b5276b..7d71deca023 100644
@@ -2,11 +2,18 @@
 #define PACK_BITMAP_H
 
 #include "ewah/ewok.h"
+#include "roaring/roaring.h"
+#include "bitmap.h"
 #include "khash.h"
 #include "pack.h"
 #include "pack-objects.h"
 #include "string-list.h"
 
+#define BITMAP_TYPE_INDEXES 0x54494458 /* "TIDX" */
+#define BITMAP_REACHABILITY_BITMAPS 0x5242544D /* "RBTM" */
+#define BITMAP_HASH_CACHE 0x424D4843 /* "BMHC" */
+#define BITMAP_LOOKUP_TABLE 0x424D4C54 /* "BMLT" */
+
 struct commit;
 struct repository;
 struct rev_info;

@@ -23,6 +30,9 @@ struct bitmap_disk_header {
 
 #define NEEDS_BITMAP (1u<<22)
 
+#define BITMAP_SET_EWAH_BITMAP 0x1
+#define BITMAP_SET_ROARING_BITMAP (1 << 1)
+
 /*
  * The width in bytes of a single triplet in the lookup table
  * extension:

@@ -86,16 +96,18 @@ off_t get_disk_usage_from_bitmap(struct bitmap_index *, struct rev_info *);
 
 void bitmap_writer_show_progress(int show);
 void bitmap_writer_set_checksum(const unsigned char *sha1);
+void bitmap_writer_init_bm_type(unsigned version_type);
 void bitmap_writer_build_type_index(struct packing_data *to_pack,
 				    struct pack_idx_entry **index,
 				    uint32_t index_nr);
 uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git,
 				struct packing_data *mapping);
-int rebuild_bitmap(const uint32_t *reposition,
-		   struct ewah_bitmap *source,
-		   struct bitmap *dest);
-struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
-				      struct commit *commit);
+int rebuild_bitmap(struct bitmap_index *bitmap_git,
+		   const uint32_t *reposition,
+		   void *source,
+		   void *dest);
+void *bitmap_for_commit(struct bitmap_index *bitmap_git,
+			struct commit *commit);
 void bitmap_writer_select_commits(struct commit **indexed_commits,
 		unsigned int indexed_commits_nr, int max_bitmaps);
 int bitmap_writer_build(struct packing_data *to_pack);

index 439c5572c18..e4011669889 100644
@@ -218,7 +218,7 @@ static struct progress *progress_state;
 
 static struct packed_git *reuse_packfile;
 static uint32_t reuse_packfile_objects;
-static struct bitmap *reuse_packfile_bitmap;
+static void *reuse_packfile_bitmap;
 
 static int use_bitmap_index_default = 1;
 static int use_bitmap_index = -1;

@@ -1084,15 +1084,29 @@ static size_t write_reused_pack_verbatim(struct hashfile *out,
 					 struct pack_window **w_curs)
 {
 	size_t pos = 0;
-
-	while (pos < reuse_packfile_bitmap->word_alloc &&
-			reuse_packfile_bitmap->words[pos] == (eword_t)~0)
-		pos++;
+	enum bitmap_type bm_type = get_bitmap_type();
+	trace2_region_enter("pack-objects", "write-reuse-v2-pack", the_repository);
+
+	if (bm_type == EWAH) {
+		struct bitmap *raw_reuse_packfile_bitmap = reuse_packfile_bitmap;
+		while (pos < raw_reuse_packfile_bitmap->word_alloc &&
+				raw_reuse_packfile_bitmap->words[pos] == (eword_t)~0)
+			pos++;
+		written = (pos * BITS_IN_EWORD);
+	}
+	else if (bm_type == ROARING) {
+		uint32_t cardinality = roaring_bitmap_get_cardinality(reuse_packfile_bitmap);
+		while (pos < cardinality && roaring_bitmap_contains(reuse_packfile_bitmap, pos))
+			pos++;
+		written = pos;
+	}
+	else
+		die(_("bitmap type is not initialized\n"));
+	trace2_region_leave("pack-objects", "write-reuse-v2-pack", the_repository);
 
 	if (pos) {
 		off_t to_write;
 
-		written = (pos * BITS_IN_EWORD);
 		to_write = pack_pos_to_offset(reuse_packfile, written)
 			- sizeof(struct pack_header);
 

@@ -1112,30 +1126,49 @@ static void write_reused_pack(struct hashfile *f)
 	size_t i = 0;
 	uint32_t offset;
 	struct pack_window *w_curs = NULL;
+	enum bitmap_type bm_type = get_bitmap_type();
+	trace2_region_enter("pack-objects", "write-reused-pack", the_repository);
 
 	if (allow_ofs_delta)
 		i = write_reused_pack_verbatim(f, &w_curs);
 
-	for (; i < reuse_packfile_bitmap->word_alloc; ++i) {
-		eword_t word = reuse_packfile_bitmap->words[i];
-		size_t pos = (i * BITS_IN_EWORD);
+	if (bm_type == EWAH) {
+		struct bitmap *raw_reuse_packfile_bitmap = reuse_packfile_bitmap;
+		for (; i < raw_reuse_packfile_bitmap->word_alloc; ++i) {
+			eword_t word = raw_reuse_packfile_bitmap->words[i];
+			size_t pos = (i * BITS_IN_EWORD);
 
-		for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
-			if ((word >> offset) == 0)
-				break;
+			for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
+				if ((word >> offset) == 0)
+					break;
 
-			offset += ewah_bit_ctz64(word >> offset);
-			/*
-			 * Can use bit positions directly, even for MIDX
-			 * bitmaps. See comment in try_partial_reuse()
-			 * for why.
-			 */
-			write_reused_pack_one(pos + offset, f, &w_curs);
+				offset += ewah_bit_ctz64(word >> offset);
+				/*
+				* Can use bit positions directly, even for MIDX
+				* bitmaps. See comment in try_partial_reuse()
+				* for why.
+				*/
+				write_reused_pack_one(pos + offset, f, &w_curs);
+				display_progress(progress_state, ++written);
+			}
+		}
+	}
+	else if (bm_type == ROARING) {
+		uint32_t cardinality = roaring_bitmap_get_cardinality(reuse_packfile_bitmap);
+		uint32_t *bm_arr = NULL;
+		roaring_bitmap_to_uint32_array(reuse_packfile_bitmap, bm_arr);
+
+		for (; i < cardinality; ++i) {
+			write_reused_pack_one(bm_arr[i], f, &w_curs);
 			display_progress(progress_state, ++written);
 		}
+		free(bm_arr);
 	}
+	else
+		die(_("bitmap_type not initialized"));
 
 	unuse_pack(&w_curs);
+	trace2_region_leave("pack-objects", "write-reused-pack", the_repository);
 }
 
 static void write_excluded_by_configs(void)

@@ -1260,6 +1293,7 @@ static void write_pack_file(void)
 			if (write_bitmap_index) {
 				bitmap_writer_init_bm_type(write_bitmap_options);
 				bitmap_writer_set_checksum(hash);
+				fprintf(stderr, "hi man\n");
 				bitmap_writer_build_type_index(
 					&to_pack, written_list, nr_written);
 			}

@@ -1279,9 +1313,11 @@ static void write_pack_file(void)
 				stop_progress(&progress_state);
 
 				bitmap_writer_show_progress(progress);
+				fprintf(stderr, "hello I am working good\n");
 				bitmap_writer_select_commits(indexed_commits, indexed_commits_nr, -1);
 				if (bitmap_writer_build(&to_pack) < 0)
 					die(_("failed to write bitmap index"));
+				fprintf(stderr, "after building bitmaps\n");
 				bitmap_writer_finish(written_list, nr_written,
 						     tmpname.buf, write_bitmap_options);
 				write_bitmap_index = 0;

1,486 lines not on this page · raw message

index 6103e0d57e7..e9676ec53de 100644
@@ -77,12 +77,12 @@ uint32_t midx_preferred_pack(struct bitmap_index *bitmap_git);
 int reuse_partial_packfile_from_bitmap(struct bitmap_index *,
 				       struct packed_git **packfile,
 				       uint32_t *entries,
-				       struct bitmap **reuse_out);
+				       void**reuse_out);
 int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping,
 			     kh_oid_map_t *reused_bitmaps, int show_progress);
 void free_bitmap_index(struct bitmap_index *);
 int bitmap_walk_contains(struct bitmap_index *,
-			 struct bitmap *bitmap, const struct object_id *oid);
+			 void *bitmap, const struct object_id *oid);
 
 /*
  * After a traversal has been performed by prepare_bitmap_walk(), this can be