diff options
| author | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2017-04-14 14:10:12 +0200 |
|---|---|---|
| committer | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-07-01 00:18:44 +0200 |
| commit | 12ade83c58720c9e0c18789f5ea6078a9eec1505 (patch) | |
| tree | 86ab3d397e0be4e56fb0872194ed41538b38950a | |
| parent | aa4bd0297606ed5c6803a8149bff0a38d8a89827 (diff) | |
| download | sparse-dev-12ade83c58720c9e0c18789f5ea6078a9eec1505.tar.gz | |
ptrmap: core implementation
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.
There is also another similar need:
- a map of object (aka: dictionnary, table, ...)
where the only needed operations are:
- add a new element (with it's key)
- lookup an element via it's key
- replace the element corresponding to a 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 input files
(the current implementation is no worse than walking through
the ptrlists).
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
| -rw-r--r-- | Makefile | 1 | ||||
| -rw-r--r-- | ptrmap.c | 109 | ||||
| -rw-r--r-- | ptrmap.h | 12 |
3 files changed, 122 insertions, 0 deletions
@@ -54,6 +54,7 @@ LIB_OBJS += optimize.o LIB_OBJS += parse.o LIB_OBJS += pre-process.o LIB_OBJS += ptrlist.o +LIB_OBJS += ptrmap.o LIB_OBJS += scope.o LIB_OBJS += show-parse.o LIB_OBJS += simplify.o diff --git a/ptrmap.c b/ptrmap.c new file mode 100644 index 00000000..ff07e19a --- /dev/null +++ b/ptrmap.c @@ -0,0 +1,109 @@ +// SPDX-License-Identifier: MIT +/* + * Stupid implementation of pointer -> pointer map. + * + * Copyright (c) 2017 Luc Van Oostenryck. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#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 00000000..070db15e --- /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 |