| Message ID | 20170816153455.97693-18-luc.vanoostenryck@gmail.com (mailing list archive) |
|---|---|
| State | Changes Requested, archived |
| Headers | show |
On Wed, Aug 16, 2017 at 11:34 AM, Luc Van Oostenryck <luc.vanoostenryck@gmail.com> wrote: > The implementation done in this patch is a very simple one > based on list of blocks of key-value pairs. > > The idea being to later switch to a dynamic structure using > a hash-table as soon as the number of element reach some threshold. > However, these hash-table are only needed for some huge > and artificial input files. > > Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> > --- > Makefile | 1 + > ptrmap.c | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > ptrmap.h | 12 ++++++++++ > 3 files changed, 97 insertions(+) > create mode 100644 ptrmap.c > create mode 100644 ptrmap.h > > diff --git a/Makefile b/Makefile > index 48e1f508f..762aee505 100644 > --- a/Makefile > +++ b/Makefile > @@ -117,6 +117,7 @@ LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \ > expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \ > char.o sort.o allocate.o compat-$(OS).o ptrlist.o \ > builtin.o \ > + ptrmap.o \ > stats.o \ > flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o > > diff --git a/ptrmap.c b/ptrmap.c > new file mode 100644 > index 000000000..2a08380c9 > --- /dev/null > +++ b/ptrmap.c > @@ -0,0 +1,84 @@ > +#include "ptrmap.h" > +#include "allocate.h" > +#include <stddef.h> > + > +#define MAP_NR 7 > + > +struct ptrpair { > + void *key; > + void *val; > +}; > +struct ptrmap { > + struct ptrmap *next; > + int nr; > + struct ptrpair pairs[MAP_NR]; > +}; If you are going for simple. why not just make struct ptrpair as allocatable object then have struct ptrpair_list as normal ptrlist? The add would be normal ptrlist add. The lookup is just FOREACH_PTR loop. The update is lookup then change the value. That could safe you some code. The difference will be, your current ptrlist has better cache behavior. But if you care that much then it should move to hash implementation Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, Aug 18, 2017 at 11:02 PM, Christopher Li <sparse@chrisli.org> wrote: > > If you are going for simple. why not just make > struct ptrpair as allocatable object then have > struct ptrpair_list as normal ptrlist? A bit less memory and one indirection less. > The add would be normal ptrlist add. > The lookup is just FOREACH_PTR loop. > The update is lookup then change the value. > > That could safe you some code. The difference > will be, your current ptrlist has better cache > behavior. But if you care that much then it should > move to hash implementation It will be done soon. -- Luc -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/Makefile b/Makefile index 48e1f508f..762aee505 100644 --- a/Makefile +++ b/Makefile @@ -117,6 +117,7 @@ LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \ expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \ char.o sort.o allocate.o compat-$(OS).o ptrlist.o \ builtin.o \ + ptrmap.o \ stats.o \ flow.o cse.o simplify.o memops.o liveness.o storage.o unssa.o dissect.o diff --git a/ptrmap.c b/ptrmap.c new file mode 100644 index 000000000..2a08380c9 --- /dev/null +++ b/ptrmap.c @@ -0,0 +1,84 @@ +#include "ptrmap.h" +#include "allocate.h" +#include <stddef.h> + +#define MAP_NR 7 + +struct ptrpair { + void *key; + void *val; +}; +struct ptrmap { + struct ptrmap *next; + int nr; + struct ptrpair pairs[MAP_NR]; +}; + +DECLARE_ALLOCATOR(ptrmap); +ALLOCATOR(ptrmap, "ptrmap"); + +void __ptrmap_add(struct ptrmap **mapp, void *key, void *val) +{ + struct ptrmap *head = *mapp; + struct ptrmap *newmap; + struct ptrmap *map; + struct ptrpair *pair; + int nr; + + if ((map = head)) { + struct ptrmap *next = map->next; + if (next) // head is full + map = next; + if ((nr = map->nr) < MAP_NR) + goto oldmap; + } + + // need a new block + newmap = __alloc_ptrmap(0); + if (!head) { + *mapp = newmap; + } else { + newmap->next = head->next; + head->next = newmap; + } + map = newmap; + nr = 0; + +oldmap: + pair = &map->pairs[nr]; + pair->key = key; + pair->val = val; + map->nr = ++nr; +} + +void *__ptrmap_lookup(struct ptrmap *map, void *key) +{ + for (; map; map = map->next) { + int i, n = map->nr; + for (i = 0; i < n; i++) { + struct ptrpair *pair = &map->pairs[i]; + if (pair->key == key) + return pair->val; + } + } + return NULL; +} + +void __ptrmap_update(struct ptrmap **mapp, void *key, void *val) +{ + struct ptrmap *map = *mapp; + + for (; map; map = map->next) { + int i, n = map->nr; + for (i = 0; i < n; i++) { + struct ptrpair *pair = &map->pairs[i]; + if (pair->key == key) { + if (pair->val != val) + pair->val = val; + return; + } + } + } + + __ptrmap_add(mapp, key, val); +} diff --git a/ptrmap.h b/ptrmap.h new file mode 100644 index 000000000..070db15e2 --- /dev/null +++ b/ptrmap.h @@ -0,0 +1,12 @@ +#ifndef PTRMAP_H +#define PTRMAP_H + +struct ptrmap; + + +/* ptrmap.c */ +void __ptrmap_add(struct ptrmap **mapp, void *key, void *val); +void __ptrmap_update(struct ptrmap **mapp, void *key, void *val); +void *__ptrmap_lookup(struct ptrmap *map, void *key); + +#endif
Sparse currently has a memory efficient implementation for lists of pointers to some objects. These are used for 2 different purposes: - either for a simple set of objects - either as a sequence (ordered) of objects. Incoming develpment has another need: - a map of object (aka: dictionnary, table, ...) where the only needed operations are: - add a new element (with it's key) - replace the element corresponding to a key) - lookup an element via it's key The implementation done in this patch is a very simple one based on list of blocks of key-value pairs. The idea being to later switch to a dynamic structure using a hash-table as soon as the number of element reach some threshold. However, these hash-table are only needed for some huge and artificial input files. Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com> --- Makefile | 1 + ptrmap.c | 84 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ptrmap.h | 12 ++++++++++ 3 files changed, 97 insertions(+) create mode 100644 ptrmap.c create mode 100644 ptrmap.h