git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
747ddb4ebc8622953578f1ff8df37c24ff8ef9e2 blob 2997 bytes (raw)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
 
#include "cache.h"
#include "prefix-map.h"

static int map_cmp(const void *unused_cmp_data,
		   const void *entry,
		   const void *entry_or_key,
		   const void *unused_keydata)
{
	const struct prefix_map_entry *a = entry;
	const struct prefix_map_entry *b = entry_or_key;

	return a->prefix_length != b->prefix_length ||
		strncmp(a->name, b->name, a->prefix_length);
}

static void add_prefix_entry(struct hashmap *map, const char *name,
			     size_t prefix_length, struct prefix_item *item)
{
	struct prefix_map_entry *result = xmalloc(sizeof(*result));
	result->name = name;
	result->prefix_length = prefix_length;
	result->item = item;
	hashmap_entry_init(result, memhash(name, prefix_length));
	hashmap_add(map, result);
}

static void init_prefix_map(struct prefix_map *prefix_map,
			    int min_prefix_length, int max_prefix_length)
{
	hashmap_init(&prefix_map->map, map_cmp, NULL, 0);
	prefix_map->min_length = min_prefix_length;
	prefix_map->max_length = max_prefix_length;
}

static void add_prefix_item(struct prefix_map *prefix_map,
			    struct prefix_item *item)
{
	struct prefix_map_entry e = { { NULL } }, *e2;
	int j;

	e.item = item;
	e.name = item->name;

	for (j = prefix_map->min_length;
	     j <= prefix_map->max_length && e.name[j]; j++) {
		/* Avoid breaking UTF-8 multi-byte sequences */
		if (!isascii(e.name[j]))
			break;

		e.prefix_length = j;
		hashmap_entry_init(&e, memhash(e.name, j));
		e2 = hashmap_get(&prefix_map->map, &e, NULL);
		if (!e2) {
			/* prefix is unique at this stage */
			item->prefix_length = j;
			add_prefix_entry(&prefix_map->map, e.name, j, item);
			break;
		}

		if (!e2->item)
			continue; /* non-unique prefix */

		if (j != e2->item->prefix_length || memcmp(e.name, e2->name, j))
			BUG("unexpected prefix length: %d != %d (%s != %s)",
			    j, (int)e2->item->prefix_length, e.name, e2->name);

		/* skip common prefix */
		for (; j < prefix_map->max_length && e.name[j]; j++) {
			if (e.item->name[j] != e2->item->name[j])
				break;
			add_prefix_entry(&prefix_map->map, e.name, j + 1,
					 NULL);
		}

		/* e2 no longer refers to a unique prefix */
		if (j < prefix_map->max_length && e2->name[j]) {
			/* found a new unique prefix for e2's item */
			e2->item->prefix_length = j + 1;
			add_prefix_entry(&prefix_map->map, e2->name, j + 1,
					 e2->item);
		}
		else
			e2->item->prefix_length = 0;
		e2->item = NULL;

		if (j < prefix_map->max_length && e.name[j]) {
			/* found a unique prefix for the item */
			e.item->prefix_length = j + 1;
			add_prefix_entry(&prefix_map->map, e.name, j + 1,
					 e.item);
		} else
			/* item has no (short enough) unique prefix */
			e.item->prefix_length = 0;

		break;
	}
}

void find_unique_prefixes(struct prefix_item **list, size_t nr,
			  int min_length, int max_length)
{
	int i;
	struct prefix_map prefix_map;

	init_prefix_map(&prefix_map, min_length, max_length);
	for (i = 0; i < nr; i++)
		add_prefix_item(&prefix_map, list[i]);
	hashmap_free(&prefix_map.map, 1);
}
debug log:

solving 747ddb4ebc ...
found 747ddb4ebc in https://public-inbox.org/git/3000d7d08dfb64511b4ebf9d05617897dd7252f7.1563289115.git.gitgitgadget@gmail.com/ ||
	https://public-inbox.org/git/e02a52c3acf64657c012744108d7ccc3ecdf1b43.1557768471.git.gitgitgadget@gmail.com/

applying [1/2] https://public-inbox.org/git/3000d7d08dfb64511b4ebf9d05617897dd7252f7.1563289115.git.gitgitgadget@gmail.com/
diff --git a/prefix-map.c b/prefix-map.c
new file mode 100644
index 0000000000..747ddb4ebc

Checking patch prefix-map.c...
Applied patch prefix-map.c cleanly.

skipping https://public-inbox.org/git/e02a52c3acf64657c012744108d7ccc3ecdf1b43.1557768471.git.gitgitgadget@gmail.com/ for 747ddb4ebc
index at:
100644 747ddb4ebc8622953578f1ff8df37c24ff8ef9e2	prefix-map.c

git@vger.kernel.org list mirror (unofficial, one of many)

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V1 git git/ https://public-inbox.org/git \
		git@vger.kernel.org
	public-inbox-index git

Example config snippet for mirrors.
Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://7fh6tueqddpjyxjmgtdiueylzoqt6pt7hec3pukyptlmohoowvhde4yd.onion/inbox.comp.version-control.git
	nntp://ie5yzdi7fg72h7s4sdcztq5evakq23rdt33mfyfcddc5u3ndnw24ogqd.onion/inbox.comp.version-control.git
	nntp://4uok3hntl7oi7b4uf4rtfwefqeexfzil2w6kgk2jn5z2f764irre7byd.onion/inbox.comp.version-control.git
	nntp://news.gmane.io/gmane.comp.version-control.git
 note: .onion URLs require Tor: https://www.torproject.org/

code repositories for project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

AGPL code for this site: git clone https://public-inbox.org/public-inbox.git