git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 3/3] decorate: use "map" for the underlying implementation

From
Jeff King <peff@peff.net>
Date
Jul 14, 2011, 17:53 UTC
Message-ID
<20110714175348.GC21771@sigill.intra.peff.net>
In-Reply-To
<20110714173454.GA21657@sigill.intra.peff.net>

The decoration API maps objects to void pointers. This is a subset of what the map API is capable of, so let's get rid of the duplicate implementation.

We could just fix all callers of decorate to call the map API directly. However, the map API is very generic since it is meant to handle any type. In particular, it can't use sentinel values like "NULL" to indicate "entry not found" (since it doesn't know whether the type can represent such a sentinel value).

Instead, the decorate API just becomes a set of wrappers, and no callers need to be updated at all.

Signed-off-by: Jeff King <peff@peff.net>
---
The result should perform identically to the existing decorate code with
the exception of the extra "used" field, which makes each hash entry
bigger (see the comments in patch 1/3).
 decorate.c |  105 ++++++++++--------------------------------------------------
 decorate.h |   10 ++----
 map.c      |    1 +
 map.h      |    1 +
 4 files changed, 22 insertions(+), 95 deletions(-)
 rewrite decorate.c (89%)
diff --git a/decorate.c b/decorate.c
dissimilarity index 89%
index 2f8a63e..31e9656 100644
--- a/decorate.c
+++ b/decorate.c
@@ -1,88 +1,17 @@
-/*
- * decorate.c - decorate a git object with some arbitrary
- * data.
- */
-#include "cache.h"
-#include "object.h"
-#include "decorate.h"
-
-static unsigned int hash_obj(const struct object *obj, unsigned int n)
-{
-	unsigned int hash;
-
-	memcpy(&hash, obj->sha1, sizeof(unsigned int));
-	return hash % n;
-}
-
-static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)
-{
-	int size = n->size;
-	struct object_decoration *hash = n->hash;
-	unsigned int j = hash_obj(base, size);
-
-	while (hash[j].base) {
-		if (hash[j].base == base) {
-			void *old = hash[j].decoration;
-			hash[j].decoration = decoration;
-			return old;
-		}
-		if (++j >= size)
-			j = 0;
-	}
-	hash[j].base = base;
-	hash[j].decoration = decoration;
-	n->nr++;
-	return NULL;
-}
-
-static void grow_decoration(struct decoration *n)
-{
-	int i;
-	int old_size = n->size;
-	struct object_decoration *old_hash = n->hash;
-
-	n->size = (old_size + 1000) * 3 / 2;
-	n->hash = xcalloc(n->size, sizeof(struct object_decoration));
-	n->nr = 0;
-
-	for (i = 0; i < old_size; i++) {
-		const struct object *base = old_hash[i].base;
-		void *decoration = old_hash[i].decoration;
-
-		if (!base)
-			continue;
-		insert_decoration(n, base, decoration);
-	}
-	free(old_hash);
-}
-
-/* Add a decoration pointer, return any old one */
-void *add_decoration(struct decoration *n, const struct object *obj,
-		void *decoration)
-{
-	int nr = n->nr + 1;
-
-	if (nr > n->size * 2 / 3)
-		grow_decoration(n);
-	return insert_decoration(n, obj, decoration);
-}
-
-/* Lookup a decoration pointer */
-void *lookup_decoration(struct decoration *n, const struct object *obj)
-{
-	unsigned int j;
-
-	/* nothing to lookup */
-	if (!n->size)
-		return NULL;
-	j = hash_obj(obj, n->size);
-	for (;;) {
-		struct object_decoration *ref = n->hash + j;
-		if (ref->base == obj)
-			return ref->decoration;
-		if (!ref->base)
-			return NULL;
-		if (++j == n->size)
-			j = 0;
-	}
-}
+#include "cache.h"
+#include "decorate.h"
+
+void *add_decoration(struct decoration *n, const struct object *obj,
+		     void *decoration)
+{
+	void *ret = NULL;
+	map_set_object_void(&n->map, obj, decoration, &ret);
+	return ret;
+}
+
+void *lookup_decoration(struct decoration *n, const struct object *obj)
+{
+	void *ret = NULL;
+	map_get_object_void(&n->map, obj, &ret);
+	return ret;
+}
diff --git a/decorate.h b/decorate.h
index e732804..6a3adcd 100644
--- a/decorate.h
+++ b/decorate.h
@@ -1,15 +1,11 @@
 #ifndef DECORATE_H
 #define DECORATE_H
 
-struct object_decoration {
-	const struct object *base;
-	void *decoration;
-};
+#include "map.h"
 
 struct decoration {
-	const char *name;
-	unsigned int size, nr;
-	struct object_decoration *hash;
+	char *name;
+	struct map_object_void map;
 };
 
 extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);
diff --git a/map.c b/map.c
index 28f885e..93e0364 100644
--- a/map.c
+++ b/map.c
@@ -86,3 +86,4 @@ int map_get_##name(struct map_##name *m, \
 }
 
 MAP_IMPLEMENT(object_uint32, struct object *, uint32_t, cmp_obj, hash_obj)
+MAP_IMPLEMENT(object_void, struct object *, void *, cmp_obj, hash_obj)
diff --git a/map.h b/map.h
index e80d85d..737054e 100644
--- a/map.h
+++ b/map.h
@@ -22,5 +22,6 @@ extern int map_set_##name(struct map_##name *, \
 			  vtype *old); \
 
 DECLARE_MAP(object_uint32, struct object *, uint32_t)
+DECLARE_MAP(object_void, struct object *, void *)
 
 #endif /* MAP_H */

-- 
1.7.6.38.ge5b33
Previous: Jeff KingNext: Junio C Hamano
Message 16 of 57 in “[RFC/PATCHv2 0/6] generation numbers for faster traversals”
  1. Jeff KingJul 13, 2011
  2. 1/6 decorate: allow storing values instead of pointersJeff King, Jul 13, 2011
  3. Jonathan NiederJul 13, 2011
  4. Jeff KingJul 13, 2011
  5. Jeff KingJul 14, 2011
  6. 1/3 implement generic key/value mapJeff King, Jul 14, 2011
  7. Bert WesargJul 14, 2011
  8. Bert WesargJul 14, 2011
  9. Jeff KingJul 14, 2011
  10. Bert WesargJul 14, 2011
  11. Jeff KingJul 14, 2011
  12. Bert WesargJul 14, 2011
  13. 2/3 fast-export: use object to uint32 map instead of "decorate"Jeff King, Jul 14, 2011
  14. Sverre RabbelierJul 15, 2011
  15. Jeff KingJul 15, 2011
  16. 3/3 decorate: use "map" for the underlying implementationJeff King, Jul 14, 2011
  17. Junio C HamanoJul 14, 2011
  18. 0/5 macro-based key/value mapsJeff King, Aug 4, 2011
  19. 1/5 implement generic key/value mapJeff King, Aug 4, 2011
  20. 2/5 fast-export: use object to uint32 map instead of "decorate"Jeff King, Aug 4, 2011
  21. 3/5 decorate: use "map" for the underlying implementationJeff King, Aug 4, 2011
  22. 4/5 map: implement persistent mapsJeff King, Aug 4, 2011
  23. 5/5 implement metadata cache subsystemJeff King, Aug 4, 2011
  24. 0/2 patch-id cachingJeff King, Aug 4, 2011
  25. 1/2 cherry: read default configJeff King, Aug 4, 2011
  26. 2/2 cache patch ids on diskJeff King, Aug 4, 2011
  27. Jeff KingAug 4, 2011
  28. Jeff KingAug 5, 2011
  29. René ScharfeAug 5, 2011
  30. Jeff KingAug 6, 2011
  31. 2/6 add metadata-cache infrastructureJeff King, Jul 13, 2011
  32. Bert WesargJul 13, 2011
  33. Jeff KingJul 13, 2011
  34. Bert WesargJul 13, 2011
  35. Jeff KingJul 13, 2011
  36. Junio C HamanoJul 13, 2011
  37. Junio C HamanoJul 13, 2011
  38. Jeff KingJul 13, 2011
  39. 3/6 commit: add commit_generation functionJeff King, Jul 13, 2011
  40. Eric SunshineJul 13, 2011
  41. 4/6 pretty: support %G to show the generation number of a commitJeff King, Jul 13, 2011
  42. 5/6 check commit generation cache validity against graftsJeff King, Jul 13, 2011
  43. Eric SunshineJul 13, 2011
  44. Jeff KingJul 13, 2011
  45. 6/6 limit "contains" traversals based on commit generationJeff King, Jul 13, 2011
  46. Jeff KingJul 13, 2011
  47. Junio C HamanoJul 13, 2011
  48. Jeff KingJul 13, 2011
  49. Junio C HamanoJul 13, 2011
  50. Jeff KingJul 13, 2011
  51. Junio C HamanoJul 15, 2011
  52. Jeff KingJul 15, 2011
  53. Junio C HamanoJul 15, 2011
  54. Jeff KingJul 15, 2011
  55. Generation numbers and replacement objectsJakub Narebski, Jul 15, 2011
  56. Jeff KingJul 15, 2011
  57. Jakub NarebskiJul 16, 2011

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.