types.h
author Kristian H?gsberg <krh@redhat.com>
Mon Jun 09 12:47:37 2008 -0400 (2008-06-09)
changeset 230 c1e2aed8dd07
parent 140 017f92f7039a
permissions -rw-r--r--
Rewrite depsolver to use a series of passes over all packages.

The big change is that we follow one step of the depedency chain for
each package to resolve in each iteration, and repeat until there are
no more possible moves. In contrast the old depsolver would try to
follow the dependency chain completely for one package at a time.

This new approach is simpler and faster, and at the same time more
roboust. Instead of knowing how one newly installed package may
affect other packages (obsoleting, pulling in new packages etc), the
new algorithm just looks at the total list of requires, provides,
obsoletes and conflicts after installing new packages.
     1 #ifndef _RAZOR_TYPES_H_
     2 #define _RAZOR_TYPES_H_
     3 
     4 #include <stdint.h>
     5 
     6 struct array {
     7 	void *data;
     8 	int size, alloc;
     9 };
    10 
    11 void array_init(struct array *array);
    12 void array_release(struct array *array);
    13 void *array_add(struct array *array, int size);
    14 
    15 
    16 struct list_head {
    17 	uint list_ptr : 24;
    18 	uint flags    : 8;
    19 };
    20 
    21 struct list {
    22 	uint data  : 24;
    23 	uint flags : 8;
    24 };
    25 
    26 void list_set_empty(struct list_head *head);
    27 void list_set_ptr(struct list_head *head, uint32_t ptr);
    28 void list_set_array(struct list_head *head, struct array *pool, struct array *items, int force_indirect);
    29 
    30 struct list *list_first(struct list_head *head, struct array *pool);
    31 struct list *list_next(struct list *list);
    32 
    33 void list_remap_pool(struct array *pool, uint32_t *map);
    34 void list_remap_head(struct list_head *list, uint32_t *map);
    35 
    36 
    37 struct hashtable {
    38 	struct array buckets;
    39 	struct array *pool;
    40 };
    41 
    42 void hashtable_init(struct hashtable *table, struct array *pool);
    43 void hashtable_release(struct hashtable *table);
    44 uint32_t hashtable_insert(struct hashtable *table, const char *key);
    45 uint32_t hashtable_lookup(struct hashtable *table, const char *key);
    46 uint32_t hashtable_tokenize(struct hashtable *table, const char *string);
    47 
    48 
    49 struct bitarray {
    50 	uint32_t *bits;
    51 };
    52 
    53 void bitarray_init(struct bitarray *bitarray, int size, int intial_value);
    54 void bitarray_release(struct bitarray *bitarray);
    55 void bitarray_set(struct bitarray *bitarray, int bit, int value);
    56 int bitarray_get(struct bitarray *bitarray, int bit);
    57 
    58 
    59 #endif /* _RAZOR_TYPES_H_ */