>From f18753810645de29abdcf32c551a7c51e2645724 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Mon, 10 Dec 2018 00:59:28 +0100 Subject: [PATCH 1/8] omap: New module. * lib/gl_omap.h: New file. * lib/gl_omap.c: New file. * modules/omap: New file. --- ChangeLog | 7 ++ lib/gl_omap.c | 3 + lib/gl_omap.h | 379 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ modules/omap | 24 ++++ 4 files changed, 413 insertions(+) create mode 100644 lib/gl_omap.c create mode 100644 lib/gl_omap.h create mode 100644 modules/omap diff --git a/ChangeLog b/ChangeLog index 70e269d..caa2f3e 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +2018-12-09 Bruno Haible + + omap: New module. + * lib/gl_omap.h: New file. + * lib/gl_omap.c: New file. + * modules/omap: New file. + 2018-12-08 Bruno Haible Fix comments. diff --git a/lib/gl_omap.c b/lib/gl_omap.c new file mode 100644 index 0000000..7c2c9d8 --- /dev/null +++ b/lib/gl_omap.c @@ -0,0 +1,3 @@ +#include +#define GL_OMAP_INLINE _GL_EXTERN_INLINE +#include "gl_omap.h" diff --git a/lib/gl_omap.h b/lib/gl_omap.h new file mode 100644 index 0000000..d00a699 --- /dev/null +++ b/lib/gl_omap.h @@ -0,0 +1,379 @@ +/* Abstract ordered map data type. + Copyright (C) 2006-2007, 2009-2018 Free Software Foundation, Inc. + Written by Bruno Haible , 2018. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + +#ifndef _GL_OMAP_H +#define _GL_OMAP_H + +#include +#include + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef GL_OMAP_INLINE +# define GL_OMAP_INLINE _GL_INLINE +#endif + +#ifdef __cplusplus +extern "C" { +#endif + + +/* gl_omap is an abstract ordered map data type. It can contain any number + of (key, value) pairs, where + - keys and values are objects ('void *' or 'const void *' pointers), + - The (key, value) pairs are ordered by the key, in the order of a given + comparator function. + - There are no (key, value1) and (key, value2) pairs with the same key + (in the sense of the comparator function). + + There are several implementations of this ordered map datatype, optimized + for different operations or for memory. You can start using the simplest + ordered map implementation, GL_ARRAY_OMAP, and switch to a different + implementation later, when you realize which operations are performed + the most frequently. The API of the different implementations is exactly + the same; when switching to a different implementation, you only have to + change the gl_omap_create call. + + The implementations are: + GL_ARRAY_OMAP a growable array + GL_AVLTREE_OMAP a binary tree (AVL tree) + GL_RBTREE_OMAP a binary tree (red-black tree) + + The memory consumption is asymptotically the same: O(1) for every pair + in the map. When looking more closely at the average memory consumed + for an pair, GL_ARRAY_OMAP is the most compact representation, and + GL_AVLTREE_OMAP, GL_RBTREE_OMAP need more memory. + + The guaranteed average performance of the operations is, for a map of + n pairs: + + Operation ARRAY TREE + + gl_omap_size O(1) O(1) + gl_omap_get O(log n) O(log n) + gl_omap_put O(n) O(log n) + gl_omap_remove O(n) O(log n) + gl_omap_search O(log n) O(log n) + gl_omap_search_atleast O(log n) O(log n) + gl_omap_iterator O(1) O(log n) + gl_omap_iterator_next O(1) O(log n) + */ + +/* -------------------------- gl_omap_t Data Type -------------------------- */ + +/* Type of function used to compare two keys. Same as for qsort(). + NULL denotes pointer comparison. */ +typedef int (*gl_mapkey_compar_fn) (const void *key1, const void *key2); + +/* Type of function used to dispose a key once a (key, value) pair is removed + from a map. NULL denotes a no-op. */ +typedef void (*gl_mapkey_dispose_fn) (const void *key); + +/* Type of function used to dispose a value once a (key, value) pair is removed + from a map. NULL denotes a no-op. */ +typedef void (*gl_mapvalue_dispose_fn) (const void *value); + +/* Type of function used to compare a key with a threshold. + Return true if the key is greater or equal than the threshold. */ +typedef bool (*gl_mapkey_threshold_fn) (const void *key, const void *threshold); + +struct gl_omap_impl; +/* Type representing an entire ordered map. */ +typedef struct gl_omap_impl * gl_omap_t; + +struct gl_omap_implementation; +/* Type representing a ordered map datatype implementation. */ +typedef const struct gl_omap_implementation * gl_omap_implementation_t; + +#if 0 /* Unless otherwise specified, these are defined inline below. */ + +/* Create an empty map. + IMPLEMENTATION is one of GL_ARRAY_OMAP, GL_AVLTREE_OMAP, GL_RBTREE_OMAP. + COMPAR_FN is a key comparison function or NULL. + KDISPOSE_FN is a key disposal function or NULL. + VDISPOSE_FN is a value disposal function or NULL. */ +/* declared in gl_xomap.h */ +extern gl_omap_t gl_omap_create_empty (gl_omap_implementation_t implementation, + gl_mapkey_compar_fn compar_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_omap_t gl_omap_nx_create_empty (gl_omap_implementation_t implementation, + gl_mapkey_compar_fn compar_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn); + +/* Return the current number of pairs in an ordered map. */ +extern size_t gl_omap_size (gl_omap_t map); + +/* Search whether a pair with the given key is already in the ordered map. + Return the value if found, or NULL if not present in the map. */ +extern const void * gl_omap_get (gl_omap_t map, const void *key); + +/* Search whether a pair with the given key is already in the ordered map. + Return true and set *VALUEP to the value if found. + Return false if not present in the map. */ +extern bool gl_omap_search (gl_omap_t map, const void *key, + const void **valuep); + +/* Search the pair with the least key in the ordered map that compares + greater or equal to the given THRESHOLD. The representation of the + THRESHOLD is defined by the THRESHOLD_FN. + Return true and store the found pair in *KEYP and *VALUEP if found. + Otherwise return false. */ +extern bool gl_omap_search_atleast (gl_omap_t map, + gl_mapkey_threshold_fn threshold_fn, + const void *threshold, + const void **keyp, const void **valuep); + +/* Add a pair to an ordered map. + Return true if a pair with the given key was not already in the map and so + this pair was added. + Return false if a pair with the given key was already in the map and only + its value was replaced. */ +/* declared in gl_xomap.h */ +extern bool gl_omap_put (gl_omap_t map, const void *key, const void *value); +/* Likewise. Return -1 upon out-of-memory. */ +extern int gl_omap_nx_put (gl_omap_t map, const void *key, const void *value) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Add a pair to an ordered map and retrieve the previous value. + Return true if a pair with the given key was not already in the map and so + this pair was added. + Return false and set *OLDVALUEP to the previous value, if a pair with the + given key was already in the map and only its value was replaced. */ +/* declared in gl_xomap.h */ +extern bool gl_omap_getput (gl_omap_t map, const void *key, const void *value, + const void **oldvaluep); +/* Likewise. Return -1 upon out-of-memory. */ +extern int gl_omap_nx_getput (gl_omap_t map, const void *key, const void *value, + const void **oldvaluep) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Remove a pair from an ordered map. + Return true if the key was found and its pair removed. + Return false otherwise. */ +extern bool gl_omap_remove (gl_omap_t map, const void *key); + +/* Remove a pair from an ordered map and retrieve the previous value. + Return true and set *OLDVALUEP to the previous value, if the key was found + and its pair removed. + Return false otherwise. */ +extern bool gl_omap_getremove (gl_omap_t map, const void *key, + const void **oldvaluep); + +/* Free an entire ordered map. + (But this call does not free the keys and values of the pairs in the map. + It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value + of the pairs in the map.) */ +extern void gl_omap_free (gl_omap_t map); + +#endif /* End of inline and gl_xomap.h-defined functions. */ + +/* ---------------------- gl_omap_iterator_t Data Type ---------------------- */ + +/* Functions for iterating through an ordered map. */ + +/* Type of an iterator that traverses an ordered map. + This is a fixed-size struct, so that creation of an iterator doesn't need + memory allocation on the heap. */ +typedef struct +{ + /* For fast dispatch of gl_omap_iterator_next. */ + const struct gl_omap_implementation *vtable; + /* For detecting whether the last returned pair was removed. */ + gl_omap_t map; + size_t count; + /* Other, implementation-private fields. */ + void *p; void *q; + size_t i; size_t j; +} gl_omap_iterator_t; + +#if 0 /* These are defined inline below. */ + +/* Create an iterator traversing an ordered map. + The map's contents must not be modified while the iterator is in use, + except for modifying the value of the last returned key or removing the + last returned pair. */ +extern gl_omap_iterator_t gl_omap_iterator (gl_omap_t map); + +/* If there is a next pair, store the next pair in *KEYP and *VALUEP, advance + the iterator, and return true. Otherwise, return false. */ +extern bool gl_omap_iterator_next (gl_omap_iterator_t *iterator, + const void **keyp, const void **valuep); + +/* Free an iterator. */ +extern void gl_omap_iterator_free (gl_omap_iterator_t *iterator); + +#endif /* End of inline functions. */ + +/* ------------------------- Implementation Details ------------------------- */ + +struct gl_omap_implementation +{ + /* gl_omap_t functions. */ + gl_omap_t (*nx_create_empty) (gl_omap_implementation_t implementation, + gl_mapkey_compar_fn compar_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn); + size_t (*size) (gl_omap_t map); + bool (*search) (gl_omap_t map, const void *key, const void **valuep); + bool (*search_atleast) (gl_omap_t map, + gl_mapkey_threshold_fn threshold_fn, + const void *threshold, + const void **keyp, const void **valuep); + int (*nx_getput) (gl_omap_t map, const void *key, const void *value, + const void **oldvaluep); + bool (*getremove) (gl_omap_t map, const void *key, const void **oldvaluep); + void (*omap_free) (gl_omap_t map); + /* gl_omap_iterator_t functions. */ + gl_omap_iterator_t (*iterator) (gl_omap_t map); + bool (*iterator_next) (gl_omap_iterator_t *iterator, + const void **keyp, const void **valuep); + void (*iterator_free) (gl_omap_iterator_t *iterator); +}; + +struct gl_omap_impl_base +{ + const struct gl_omap_implementation *vtable; + gl_mapkey_compar_fn compar_fn; + gl_mapkey_dispose_fn kdispose_fn; + gl_mapvalue_dispose_fn vdispose_fn; +}; + +/* Define most functions of this file as accesses to the + struct gl_omap_implementation. */ + +GL_OMAP_INLINE gl_omap_t +gl_omap_nx_create_empty (gl_omap_implementation_t implementation, + gl_mapkey_compar_fn compar_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn) +{ + return implementation->nx_create_empty (implementation, compar_fn, + kdispose_fn, vdispose_fn); +} + +GL_OMAP_INLINE size_t +gl_omap_size (gl_omap_t map) +{ + return ((const struct gl_omap_impl_base *) map)->vtable->size (map); +} + +GL_OMAP_INLINE bool +gl_omap_search (gl_omap_t map, const void *key, const void **valuep) +{ + return ((const struct gl_omap_impl_base *) map)->vtable + ->search (map, key, valuep); +} + +GL_OMAP_INLINE bool +gl_omap_search_atleast (gl_omap_t map, + gl_mapkey_threshold_fn threshold_fn, + const void *threshold, + const void **keyp, const void **valuep) +{ + return ((const struct gl_omap_impl_base *) map)->vtable + ->search_atleast (map, threshold_fn, threshold, keyp, valuep); +} + +GL_OMAP_INLINE int +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_omap_nx_getput (gl_omap_t map, const void *key, const void *value, + const void **oldvaluep) +{ + return ((const struct gl_omap_impl_base *) map)->vtable + ->nx_getput (map, key, value, oldvaluep); +} + +GL_OMAP_INLINE bool +gl_omap_getremove (gl_omap_t map, const void *key, const void **oldvaluep) +{ + return ((const struct gl_omap_impl_base *) map)->vtable + ->getremove (map, key, oldvaluep); +} + +GL_OMAP_INLINE void +gl_omap_free (gl_omap_t map) +{ + ((const struct gl_omap_impl_base *) map)->vtable->omap_free (map); +} + +GL_OMAP_INLINE gl_omap_iterator_t +gl_omap_iterator (gl_omap_t map) +{ + return ((const struct gl_omap_impl_base *) map)->vtable->iterator (map); +} + +GL_OMAP_INLINE bool +gl_omap_iterator_next (gl_omap_iterator_t *iterator, + const void **keyp, const void **valuep) +{ + return iterator->vtable->iterator_next (iterator, keyp, valuep); +} + +GL_OMAP_INLINE void +gl_omap_iterator_free (gl_omap_iterator_t *iterator) +{ + iterator->vtable->iterator_free (iterator); +} + +/* Define the convenience functions, that is, the functions that are independent + of the implementation. */ + +GL_OMAP_INLINE const void * +gl_omap_get (gl_omap_t map, const void *key) +{ + const void *value = NULL; + gl_omap_search (map, key, &value); + return value; +} + +GL_OMAP_INLINE int +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_omap_nx_put (gl_omap_t map, const void *key, const void *value) +{ + const void *oldvalue; + return gl_omap_nx_getput (map, key, value, &oldvalue); +} + +GL_OMAP_INLINE bool +gl_omap_remove (gl_omap_t map, const void *key) +{ + const void *oldvalue; + return gl_omap_getremove (map, key, &oldvalue); +} + +#ifdef __cplusplus +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* _GL_OMAP_H */ diff --git a/modules/omap b/modules/omap new file mode 100644 index 0000000..63c9ec8 --- /dev/null +++ b/modules/omap @@ -0,0 +1,24 @@ +Description: +Abstract ordered map data type. + +Files: +lib/gl_omap.h +lib/gl_omap.c + +Depends-on: +extern-inline +stdbool + +configure.ac: + +Makefile.am: +lib_SOURCES += gl_omap.h gl_omap.c + +Include: +"gl_omap.h" + +License: +GPL + +Maintainer: +all -- 2.7.4