Subversion Repositories HelenOS-historic

Compare Revisions

Ignore whitespace Rev 1391 → Rev 1392

/uspace/trunk/libc/include/libadt/hash_table.h
0,0 → 1,80
/*
* Copyright (C) 2006 Jakub Jermar
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#ifndef __HASH_TABLE_H__
#define __HASH_TABLE_H__
 
#include <libadt/list.h>
#include <unistd.h>
 
typedef unsigned long hash_count_t;
typedef unsigned long hash_index_t;
typedef struct hash_table hash_table_t;
typedef struct hash_table_operations hash_table_operations_t;
 
/** Hash table structure. */
struct hash_table {
link_t *entry;
hash_count_t entries;
hash_count_t max_keys;
hash_table_operations_t *op;
};
 
/** Set of operations for hash table. */
struct hash_table_operations {
/** Hash function.
*
* @param key Array of keys needed to compute hash index. All keys must be passed.
*
* @return Index into hash table.
*/
hash_index_t (* hash)(unsigned long key[]);
/** Hash table item comparison function.
*
* @param key Array of keys that will be compared with item. It is not necessary to pass all keys.
*
* @return true if the keys match, false otherwise.
*/
int (*compare)(unsigned long key[], hash_count_t keys, link_t *item);
 
/** Hash table item removal callback.
*
* @param item Item that was removed from the hash table.
*/
void (*remove_callback)(link_t *item);
};
 
#define hash_table_get_instance(item, type, member) list_get_instance((item), type, member)
 
extern int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, hash_table_operations_t *op);
extern void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item);
extern link_t *hash_table_find(hash_table_t *h, unsigned long key[]);
extern void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys);
 
#endif
/uspace/trunk/libc/include/libadt/list.h
0,0 → 1,185
/*
* Copyright (C) 2001-2004 Jakub Jermar
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#ifndef __LIST_H__
#define __LIST_H__
 
#include<unistd.h>
 
#ifndef true
# define true 1
#endif
#ifndef false
# define false 0
#endif
 
typedef struct link link_t;
 
/** Doubly linked list head and link type. */
struct link {
link_t *prev; /**< Pointer to the previous item in the list. */
link_t *next; /**< Pointer to the next item in the list. */
};
 
/** Declare and initialize statically allocated list.
*
* @param name Name of the new statically allocated list.
*/
#define LIST_INITIALIZE(name) link_t name = { .prev = &name, .next = &name }
 
/** Initialize doubly-linked circular list link
*
* Initialize doubly-linked list link.
*
* @param link Pointer to link_t structure to be initialized.
*/
static inline void link_initialize(link_t *link)
{
link->prev = NULL;
link->next = NULL;
}
 
/** Initialize doubly-linked circular list
*
* Initialize doubly-linked circular list.
*
* @param head Pointer to link_t structure representing head of the list.
*/
static inline void list_initialize(link_t *head)
{
head->prev = head;
head->next = head;
}
 
/** Add item to the beginning of doubly-linked circular list
*
* Add item to the beginning of doubly-linked circular list.
*
* @param link Pointer to link_t structure to be added.
* @param head Pointer to link_t structure representing head of the list.
*/
static inline void list_prepend(link_t *link, link_t *head)
{
link->next = head->next;
link->prev = head;
head->next->prev = link;
head->next = link;
}
 
/** Add item to the end of doubly-linked circular list
*
* Add item to the end of doubly-linked circular list.
*
* @param link Pointer to link_t structure to be added.
* @param head Pointer to link_t structure representing head of the list.
*/
static inline void list_append(link_t *link, link_t *head)
{
link->prev = head->prev;
link->next = head;
head->prev->next = link;
head->prev = link;
}
 
/** Remove item from doubly-linked circular list
*
* Remove item from doubly-linked circular list.
*
* @param link Pointer to link_t structure to be removed from the list it is contained in.
*/
static inline void list_remove(link_t *link)
{
link->next->prev = link->prev;
link->prev->next = link->next;
link_initialize(link);
}
 
/** Query emptiness of doubly-linked circular list
*
* Query emptiness of doubly-linked circular list.
*
* @param head Pointer to link_t structure representing head of the list.
*/
static inline int list_empty(link_t *head)
{
return head->next == head ? true : false;
}
 
 
/** Split or concatenate headless doubly-linked circular list
*
* Split or concatenate headless doubly-linked circular list.
*
* Note that the algorithm works both directions:
* concatenates splitted lists and splits concatenated lists.
*
* @param part1 Pointer to link_t structure leading the first (half of the headless) list.
* @param part2 Pointer to link_t structure leading the second (half of the headless) list.
*/
static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
{
link_t *hlp;
 
part1->prev->next = part2;
part2->prev->next = part1;
hlp = part1->prev;
part1->prev = part2->prev;
part2->prev = hlp;
}
 
 
/** Split headless doubly-linked circular list
*
* Split headless doubly-linked circular list.
*
* @param part1 Pointer to link_t structure leading the first half of the headless list.
* @param part2 Pointer to link_t structure leading the second half of the headless list.
*/
static inline void headless_list_split(link_t *part1, link_t *part2)
{
headless_list_split_or_concat(part1, part2);
}
 
/** Concatenate two headless doubly-linked circular lists
*
* Concatenate two headless doubly-linked circular lists.
*
* @param part1 Pointer to link_t structure leading the first headless list.
* @param part2 Pointer to link_t structure leading the second headless list.
*/
static inline void headless_list_concat(link_t *part1, link_t *part2)
{
headless_list_split_or_concat(part1, part2);
}
 
#define list_get_instance(link,type,member) (type *)(((char *)(link))-((char *)&(((type *)NULL)->member)))
 
extern int list_member(const link_t *link, const link_t *head);
extern void list_concat(link_t *head1, link_t *head2);
 
#endif
/uspace/trunk/libc/include/libadt/fifo.h
0,0 → 1,115
/*
* Copyright (C) 2006 Jakub Jermar
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
/*
* This implementation of FIFO stores values in an array
* (static or dynamic). As such, these FIFOs have upper bound
* on number of values they can store. Push and pop operations
* are done via accessing the array through head and tail indices.
* Because of better operation ordering in fifo_pop(), the access
* policy for these two indices is to 'increment (mod size of FIFO)
* and use'.
*/
 
#ifndef __FIFO_H__
#define __FIFO_H__
 
#include <malloc.h>
 
typedef unsigned long fifo_count_t;
typedef unsigned long fifo_index_t;
 
/** Create and initialize static FIFO.
*
* FIFO is allocated statically.
* This macro is suitable for creating smaller FIFOs.
*
* @param name Name of FIFO.
* @param t Type of values stored in FIFO.
* @param itms Number of items that can be stored in FIFO.
*/
#define FIFO_INITIALIZE_STATIC(name, t, itms) \
struct { \
t fifo[(itms)]; \
fifo_count_t items; \
fifo_index_t head; \
fifo_index_t tail; \
} name = { \
.items = (itms), \
.head = 0, \
.tail = 0 \
}
 
/** Create and prepare dynamic FIFO.
*
* FIFO is allocated dynamically.
* This macro is suitable for creating larger FIFOs.
*
* @param name Name of FIFO.
* @param t Type of values stored in FIFO.
* @param itms Number of items that can be stored in FIFO.
*/
#define FIFO_INITIALIZE_DYNAMIC(name, t, itms) \
struct { \
t *fifo; \
fifo_count_t items; \
fifo_index_t head; \
fifo_index_t tail; \
} name = { \
.fifo = NULL, \
.items = (itms), \
.head = 0, \
.tail = 0 \
}
 
/** Pop value from head of FIFO.
*
* @param name FIFO name.
*
* @return Leading value in FIFO.
*/
#define fifo_pop(name) \
name.fifo[name.head = (name.head + 1) < name.items ? (name.head + 1) : 0]
 
/** Push value to tail of FIFO.
*
* @param name FIFO name.
* @param value Value to be appended to FIFO.
*
*/
#define fifo_push(name, value) \
name.fifo[name.tail = (name.tail + 1) < name.items ? (name.tail + 1) : 0] = (value)
 
/** Allocate memory for dynamic FIFO.
*
* @param name FIFO name.
*/
#define fifo_create(name) \
name.fifo = malloc(sizeof(*name.fifo) * name.items)
 
#endif