Commit Diff


commit - 77968bb039a04d0243df811be0423030770e2696be962859269f46d0509744b8
commit + 1b4a5311e029af3216154de43599c34a9cf5f0eb01708564bd49ae836a846998
blob - 3843bb8098b47cd3315f751266c163c46dac066ffb4bac3e70d9c9b3ec7c20f2
blob + ceed13125579331c118fd3d464ffb908a5b37112c9830b76c576b98238f6aa99
--- include/got_object.h	
+++ include/got_object.h	
@@ -20,6 +20,7 @@
 enum got_hash_algorithm {
 	GOT_HASH_SHA1,
 	GOT_HASH_SHA256,
+	GOT_NUM_HASH_ALGOS,
 };
 
 struct got_object_id {
blob - b528934474fa2f67f073138ff30c0bf1c92af12ca6e7d0227dc707274e9f9401
blob + 3a9362075b104b203b30573a6e14ff1b7b44a1ef9b92e962a7c1d10cd3e42ede
--- lib/object_idset.c	
+++ lib/object_idset.c	
@@ -41,8 +41,19 @@
 
 #define GOT_OBJECT_IDSET_MIN_BUCKETS	64
 
+#define GOT_OBJECT_IDSET_SLOT_EMPTY	GOT_NUM_HASH_ALGOS
+
+struct got_object_idset_bucket {
+	/* The first element hashed into this bucket is stored inline. */
+	struct got_object_id id;
+	void *data;
+
+	/* List of further elements populated during hash collisions. */
+	struct got_object_id_queue ids;
+};
+
 struct got_object_idset {
-	struct got_object_id_queue *ids;
+	struct got_object_idset_bucket *buckets;
 	size_t nbuckets;
 	unsigned int totelem;
 	unsigned int flags;
@@ -51,24 +62,35 @@ struct got_object_idset {
 	SIPHASH_KEY key;
 };
 
+static void
+init_hash_buckets(struct got_object_idset_bucket *buckets, int nbuckets)
+{
+	int i;
+
+	for (i = 0; i < nbuckets; i++) {
+		buckets[i].id.algo = GOT_OBJECT_IDSET_SLOT_EMPTY;
+		STAILQ_INIT(&buckets[i].ids);
+	}
+}
+
 struct got_object_idset *
 got_object_idset_alloc(void)
 {
 	struct got_object_idset *set;
-	int i;
 
 	set = malloc(sizeof(*set));
 	if (set == NULL)
 		return NULL;
 
-	set->ids = calloc(GOT_OBJECT_IDSET_MIN_BUCKETS, sizeof(set->ids[0]));
-	if (set->ids == NULL) {
+	set->buckets = calloc(GOT_OBJECT_IDSET_MIN_BUCKETS,
+	    sizeof(set->buckets[0]));
+	if (set->buckets == NULL) {
 		free(set);
 		return NULL;
-	}
-	for (i = 0; i < GOT_OBJECT_IDSET_MIN_BUCKETS; i++)
-		STAILQ_INIT(&set->ids[i]);
+	} 
 
+	init_hash_buckets(set->buckets, GOT_OBJECT_IDSET_MIN_BUCKETS);
+
 	set->totelem = 0;
 	set->nbuckets = GOT_OBJECT_IDSET_MIN_BUCKETS;
 	set->flags = 0;
@@ -83,31 +105,69 @@ got_object_idset_free(struct got_object_idset *set)
 	struct got_object_qid *qid;
 
 	for (i = 0; i < set->nbuckets; i++) {
-		while (!STAILQ_EMPTY(&set->ids[i])) {
-			qid = STAILQ_FIRST(&set->ids[i]);
-			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
+		while (!STAILQ_EMPTY(&set->buckets[i].ids)) {
+			qid = STAILQ_FIRST(&set->buckets[i].ids);
+			STAILQ_REMOVE(&set->buckets[i].ids, qid,
+			    got_object_qid, entry);
 			got_object_qid_free(qid);
 		}
 	}
 	/* User data should be freed by caller. */
-	free(set->ids);
+	free(set->buckets);
 	free(set);
 }
 
 static uint64_t
-idset_hash(struct got_object_idset *set, struct got_object_id *id)
+idset_hash(SIPHASH_KEY *key, struct got_object_id *id)
 {
-	return SipHash24(&set->key, id->hash, got_hash_digest_length(id->algo));
+	return SipHash24(key, id->hash, got_hash_digest_length(id->algo));
 }
 
 static const struct got_error *
+idset_add(struct got_object_idset_bucket *bucket, struct got_object_id *id,
+    void *data)
+{
+	const struct got_error *err;
+	struct got_object_qid *qid;
+
+	/*
+	 * The initial element added is stored in the array itself to
+	 * to save some malloc/free calls.
+	 j We overload id->algo as an 'empty slot' flag which works
+	 * because valid IDs always use a valid hash algorithm.
+	 */
+	if (id->algo == GOT_OBJECT_IDSET_SLOT_EMPTY)
+		return got_error_fmt(GOT_ERR_BAD_OBJ_ID, "%s", __func__);
+	if (bucket->id.algo == GOT_OBJECT_IDSET_SLOT_EMPTY) {
+		memcpy(&bucket->id, id, sizeof(bucket->id));
+		bucket->data = data;
+		return NULL;
+	}
+
+	/*
+	 * There is a hash collision. Append this element to the linked list
+	 * instead of storing it inline, paying the cost of malloc/free.
+	 */
+	err = got_object_qid_alloc_partial(&qid);
+	if (err)
+		return err;
+
+	memcpy(&qid->id, id, sizeof(qid->id));
+	qid->data = data;
+	STAILQ_INSERT_HEAD(&bucket->ids, qid, entry);
+	return NULL;
+}
+
+static const struct got_error *
 idset_resize(struct got_object_idset *set, size_t nbuckets)
 {
-	struct got_object_id_queue *ids;
+	const struct got_error *err = NULL;
+	struct got_object_idset_bucket *buckets;
+	SIPHASH_KEY key;
 	size_t i;
 
-	ids = calloc(nbuckets, sizeof(ids[0]));
-	if (ids == NULL) {
+	buckets = calloc(nbuckets, sizeof(buckets[0]));
+	if (buckets == NULL) {
 		if (errno != ENOMEM)
 			return got_error_from_errno("calloc");
 		/* Proceed with our current amount of hash buckets. */
@@ -115,25 +175,60 @@ idset_resize(struct got_object_idset *set, size_t nbuc
 		return NULL;
 	}
 
-	for (i = 0; i < nbuckets; i++)
-		STAILQ_INIT(&ids[i]);
+	init_hash_buckets(buckets, nbuckets);
 
-	arc4random_buf(&set->key, sizeof(set->key));
+	arc4random_buf(&key, sizeof(key));
 
 	for (i = 0; i < set->nbuckets; i++) {
-		while (!STAILQ_EMPTY(&set->ids[i])) {
+		uint64_t idx;
+	
+		if (set->buckets[i].id.algo == GOT_OBJECT_IDSET_SLOT_EMPTY)
+			continue;
+
+		/*
+		 * Copy collisions into the new table first since this
+		 * might free up some memory. The new larger hash table
+		 * should be able to store more elements inline.
+		 */
+		while (!STAILQ_EMPTY(&set->buckets[i].ids)) {
 			struct got_object_qid *qid;
-			uint64_t idx;
-			qid = STAILQ_FIRST(&set->ids[i]);
-			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
-			idx = idset_hash(set, &qid->id) % nbuckets;
-			STAILQ_INSERT_HEAD(&ids[idx], qid, entry);
+
+			qid = STAILQ_FIRST(&set->buckets[i].ids);
+			STAILQ_REMOVE(&set->buckets[i].ids, qid,
+			    got_object_qid, entry);
+			idx = idset_hash(&key, &qid->id) % nbuckets;
+
+			if (buckets[idx].id.algo ==
+			    GOT_OBJECT_IDSET_SLOT_EMPTY) {
+				memcpy(&buckets[idx].id, &qid->id,
+				    sizeof(buckets[idx].id));
+				buckets[idx].data = qid->data;
+				got_object_qid_free(qid);
+			} else {
+				STAILQ_INSERT_HEAD(&buckets[idx].ids, qid,
+				    entry);
+			}
 		}
+
+		/*
+		 * Now add the inline element. We will have to allocate memory
+		 * if there is a hash collision. We don't try to cope with
+		 * allocation failure here because our previous hash table
+		 * has already been partly destroyed and trying to rebuild
+		 * it would likely also fail.
+		 */
+		idx = idset_hash(&key, &set->buckets[i].id) % nbuckets;
+		err = idset_add(&buckets[idx], &set->buckets[i].id,
+		    set->buckets[i].data);
+		if (err)
+			return err;
+
 	}
 
-	free(set->ids);
-	set->ids = ids;
+	free(set->buckets);
+	set->buckets = buckets;
 	set->nbuckets = nbuckets;
+	memcpy(&set->key, &key, sizeof(set->key));
 	return NULL;
 }
 
@@ -142,7 +237,8 @@ idset_grow(struct got_object_idset *set)
 {
 	size_t nbuckets;
 
-	if (set->flags & GOT_OBJECT_IDSET_F_NOMEM)
+	if ((set->flags & GOT_OBJECT_IDSET_F_NOMEM) ||
+	    set->nbuckets == UINT_MAX)
 		return NULL;
 
 	if (set->nbuckets >= UINT_MAX / 2)
@@ -158,9 +254,8 @@ got_object_idset_add(struct got_object_idset *set, str
     void *data)
 {
 	const struct got_error *err;
-	struct got_object_qid *qid;
 	uint64_t idx;
-	struct got_object_id_queue *head;
+	struct got_object_idset_bucket *bucket;
 
 	/* This function may resize the set. */
 	if (set->flags & GOT_OBJECT_IDSET_F_TRAVERSAL)
@@ -170,43 +265,56 @@ got_object_idset_add(struct got_object_idset *set, str
 	if (set->totelem == UINT_MAX)
 		return got_error(GOT_ERR_NO_SPACE);
 
-	err = got_object_qid_alloc_partial(&qid);
+	idx = idset_hash(&set->key, id) % set->nbuckets;
+	bucket = &set->buckets[idx];
+	err = idset_add(bucket, id, data);
 	if (err)
 		return err;
-	memcpy(&qid->id, id, sizeof(qid->id));
-	qid->data = data;
-
-	idx = idset_hash(set, id) % set->nbuckets;
-	head = &set->ids[idx];
-	STAILQ_INSERT_HEAD(head, qid, entry);
 	set->totelem++;
 
-	if (set->nbuckets < set->totelem)
+	if (((uint64_t)set->nbuckets) * 3 < ((uint64_t)set->totelem) * 4)
 		err = idset_grow(set);
 
 	return err;
 }
 
-static struct got_object_qid *
-find_element(struct got_object_idset *set, struct got_object_id *id)
+static void
+find_element(struct got_object_id **id_found, void **data_found,
+    struct got_object_idset *set, struct got_object_id *id)
 {
-	uint64_t idx = idset_hash(set, id) % set->nbuckets;
-	struct got_object_id_queue *head = &set->ids[idx];
+	uint64_t idx = idset_hash(&set->key, id) % set->nbuckets;
+	struct got_object_idset_bucket *bucket = &set->buckets[idx];
 	struct got_object_qid *qid;
 
-	STAILQ_FOREACH(qid, head, entry) {
-		if (got_object_id_cmp(&qid->id, id) == 0)
-			return qid;
+	*id_found = NULL;
+	*data_found = NULL;
+
+	if (bucket->id.algo == GOT_OBJECT_IDSET_SLOT_EMPTY)
+		return;
+
+	if (got_object_id_cmp(&bucket->id, id) == 0) {
+		*id_found = id;
+		*data_found = bucket->data;
+		return;
 	}
 
-	return NULL;
+	STAILQ_FOREACH(qid, &bucket->ids, entry) {
+		if (got_object_id_cmp(&qid->id, id) == 0) {
+			*id_found = id;
+			*data_found = qid->data;
+			return;
+		}
+	}
 }
 
 void *
 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
 {
-	struct got_object_qid *qid = find_element(set, id);
-	return qid ? qid->data : NULL;
+	struct got_object_id *id_found;
+	void *data_found;
+
+	find_element(&id_found, &data_found, set, id);
+	return id_found ? data_found : NULL;
 }
 
 const struct got_error *
@@ -214,8 +322,8 @@ got_object_idset_remove(void **data, struct got_object
     struct got_object_id *id)
 {
 	uint64_t idx;
-	struct got_object_id_queue *head;
-	struct got_object_qid *qid;
+	struct got_object_idset_bucket *bucket;
+	struct got_object_qid *qid = NULL;
 
 	if (data)
 		*data = NULL;
@@ -226,26 +334,64 @@ got_object_idset_remove(void **data, struct got_object
 	if (id == NULL) {
 		/* Remove a "random" element. */
 		for (idx = 0; idx < set->nbuckets; idx++) {
-			head = &set->ids[idx];
-			qid = STAILQ_FIRST(head);
-			if (qid)
+			bucket = &set->buckets[idx];
+			if (bucket->id.algo == GOT_OBJECT_IDSET_SLOT_EMPTY)	
+				continue;
+
+			if (STAILQ_EMPTY(&bucket->ids)) {
+				if (data)
+					*data = bucket->data;
+				bucket->data = NULL;
+				memset(&bucket->id, 0, sizeof(bucket->id));
+				bucket->id.algo = GOT_OBJECT_IDSET_SLOT_EMPTY;
 				break;
+			} else {
+				qid = STAILQ_FIRST(&bucket->ids);
+				STAILQ_REMOVE(&bucket->ids, qid,
+				    got_object_qid, entry);
+				if (data)
+					*data = qid->data;
+				got_object_qid_free(qid);
+				break;
+			}
 		}
 	} else {
-		idx = idset_hash(set, id) % set->nbuckets;
-		head = &set->ids[idx];
-		STAILQ_FOREACH(qid, head, entry) {
-			if (got_object_id_cmp(&qid->id, id) == 0)
-				break;
-		}
-		if (qid == NULL)
+		idx = idset_hash(&set->key, id) % set->nbuckets;
+		bucket = &set->buckets[idx];
+		if (bucket->id.algo == GOT_OBJECT_IDSET_SLOT_EMPTY)	
 			return got_error_no_obj(id);
+
+		if (got_object_id_cmp(&bucket->id, id) == 0) {
+			if (data)
+				*data = bucket->data;
+			if (STAILQ_EMPTY(&bucket->ids)) {
+				bucket->data = NULL;
+				memset(&bucket->id, 0, sizeof(bucket->id));
+				bucket->id.algo = GOT_OBJECT_IDSET_SLOT_EMPTY;
+			} else {
+				qid = STAILQ_FIRST(&bucket->ids);
+				STAILQ_REMOVE(&bucket->ids, qid,
+				    got_object_qid, entry);
+				memcpy(&bucket->id, &qid->id,
+				    sizeof(bucket->id));
+				bucket->data = qid->data;
+				got_object_qid_free(qid);
+			}
+		} else {
+			STAILQ_FOREACH(qid, &bucket->ids, entry) {
+				if (got_object_id_cmp(&qid->id, id) == 0)
+					break;
+			}
+			if (qid == NULL)
+				return got_error_no_obj(id);
+
+			STAILQ_REMOVE(&bucket->ids, qid, got_object_qid, entry);
+			if (data)
+				*data = qid->data;
+			got_object_qid_free(qid);
+		}
 	}
 
-	if (data)
-		*data = qid->data;
-	STAILQ_REMOVE(head, qid, got_object_qid, entry);
-	got_object_qid_free(qid);
 	set->totelem--;
 
 	return NULL;
@@ -255,8 +401,11 @@ int
 got_object_idset_contains(struct got_object_idset *set,
     struct got_object_id *id)
 {
-	struct got_object_qid *qid = find_element(set, id);
-	return qid ? 1 : 0;
+	struct got_object_id *id_found;
+	void *data_found;
+
+	find_element(&id_found, &data_found, set, id);
+	return id_found ? 1 : 0;
 }
 
 const struct got_error *
@@ -265,14 +414,22 @@ got_object_idset_for_each(struct got_object_idset *set
     void *arg)
 {
 	const struct got_error *err = NULL;
-	struct got_object_id_queue *head;
+	struct got_object_idset_bucket *bucket;
 	struct got_object_qid *qid, *tmp;
 	size_t i;
 
 	set->flags |= GOT_OBJECT_IDSET_F_TRAVERSAL;
 	for (i = 0; i < set->nbuckets; i++) {
-		head = &set->ids[i];
-		STAILQ_FOREACH_SAFE(qid, head, entry, tmp) {
+		bucket = &set->buckets[i];
+	
+		if (bucket->id.algo == GOT_OBJECT_IDSET_SLOT_EMPTY)
+			continue;
+
+		err = (*cb)(&bucket->id, bucket->data, arg);
+		if (err)
+			break;
+
+		STAILQ_FOREACH_SAFE(qid, &bucket->ids, entry, tmp) {
 			err = (*cb)(&qid->id, qid->data, arg);
 			if (err)
 				goto done;