From c4ec4181cf4dc98c580213ef302f4b9faa655592 Mon Sep 17 00:00:00 2001 From: ticktock35 Date: Mon, 15 Dec 2008 05:31:50 +0000 Subject: [PATCH 1/1] opkg: introduce the protype of active_list This can be used for upgrade path git-svn-id: http://opkg.googlecode.com/svn/trunk@166 e8e0d7a0-c8d9-11dd-a880-a1081c7ac358 --- libopkg/Makefile.am | 3 +- libopkg/active_list.c | 81 +++++++++ libopkg/active_list.h | 36 ++++ libopkg/list.h | 304 ++++++++++++++++++++++++++++++++++ tests/opkg_active_list_test.c | 103 ++++++++++++ 5 files changed, 526 insertions(+), 1 deletion(-) create mode 100644 libopkg/active_list.c create mode 100644 libopkg/active_list.h create mode 100644 libopkg/list.h create mode 100644 tests/opkg_active_list_test.c diff --git a/libopkg/Makefile.am b/libopkg/Makefile.am index fbc2dd8..8783f15 100644 --- a/libopkg/Makefile.am +++ b/libopkg/Makefile.am @@ -24,7 +24,8 @@ opkg_list_sources = conffile.c conffile.h conffile_list.c conffile_list.h \ nv_pair.c nv_pair.h nv_pair_list.c nv_pair_list.h \ pkg_dest.c pkg_dest.h pkg_dest_list.c pkg_dest_list.h \ pkg_src.c pkg_src.h pkg_src_list.c pkg_src_list.h \ - str_list.c str_list.h void_list.c void_list.h + str_list.c str_list.h void_list.c void_list.h \ + active_list.c active.list.h list.h opkg_util_sources = file_util.c file_util.h opkg_message.h opkg_message.c md5.c md5.h \ sprintf_alloc.c sprintf_alloc.h str_util.c str_util.h \ xregex.c xregex.h xsystem.c xsystem.h diff --git a/libopkg/active_list.c b/libopkg/active_list.c new file mode 100644 index 0000000..b4bbef9 --- /dev/null +++ b/libopkg/active_list.c @@ -0,0 +1,81 @@ +/* active_list.h - the opkg package management system + + Tick Chen + + Copyright (C) 2008 Openmoko Inc. + + 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 2, 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. +*/ + + +#include "active_list.h" +#include + + +void active_list_init(struct active_list *ptr) { + INIT_LIST_HEAD(&ptr->node); + INIT_LIST_HEAD(&ptr->depend); + ptr->walked=0; + ptr->depended = NULL; +} + +/** + */ +struct active_list * active_list_next(struct active_list *head, struct active_list *ptr) { + struct active_list *next=NULL; + if (!head || !ptr) { + fprintf(stderr, "active_list_prev head = %p, ptr = %p invalid value!!\n", head, ptr); + return NULL; + } + if (ptr == head) { + head->walked = !head->walked; + next = list_entry(ptr->node.next, struct active_list, node); + if (next == head) + return NULL; + return active_list_next(head, next); + } + if (ptr->depend.next != &ptr->depend) { + next = list_entry(ptr->depend.next, struct active_list, node); + if (head->walked != next->walked) { + ptr->walked = head->walked; + return active_list_next(head, next); + } + } + if (ptr->walked != head->walked) { + ptr->walked = head->walked; + return ptr; + } + + if (ptr->depended && ptr->node.next == &ptr->depended->depend ) { + return ptr->depended; + } + + if (ptr->node.next != &head->node) { + next = list_entry(ptr->node.next, struct active_list, node); + return active_list_next(head, next); + } + return NULL; +} + + +void active_list_clear(struct active_list *head) { +} + +void active_list_add_depend(struct active_list *node, struct active_list *depend) { + list_del_init(&depend->node); + list_add_tail(&depend->node, &node->depend); + depend->depended = node; +} + +void active_list_add(struct active_list *head, struct active_list *node) { + list_del_init(&node->node); + list_add_tail(&node->node, &head->node); +} diff --git a/libopkg/active_list.h b/libopkg/active_list.h new file mode 100644 index 0000000..6744234 --- /dev/null +++ b/libopkg/active_list.h @@ -0,0 +1,36 @@ +/* active_list.h - the opkg package management system + + Tick Chen + + Copyright (C) 2008 Openmoko Inc. + + 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 2, 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. +*/ + +#ifndef ACTIVE_LIST_H +#define ACTIVE_LIST_H + +#include "list.h" + +struct active_list { + struct list_head node; + struct list_head depend; + char walked; + struct active_list *depended; +} __attribute__((packed)); + +struct active_list * active_list_next(struct active_list *head, struct active_list *ptr); +void active_list_init(struct active_list *ptr); +void active_list_clear(struct active_list *head); +void active_list_add_depend(struct active_list *node, struct active_list *depend); +void active_list_add(struct active_list *head, struct active_list *node); + +#endif diff --git a/libopkg/list.h b/libopkg/list.h new file mode 100644 index 0000000..0bd87b9 --- /dev/null +++ b/libopkg/list.h @@ -0,0 +1,304 @@ +/* list.h - the opkg package management system + + Tick Chen + + Copyright (C) 2008 Openmoko Inc. + + 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 2, 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. + + This is modified from Linux Kernel. +*/ + +#ifndef _LINUX_LIST_H +#define _LINUX_LIST_H + +#define LIST_POISON1 ((void *) 0x00100100) +#define LIST_POISON2 ((void *) 0x00200200) + +struct list_head { + struct list_head *next, *prev; +}; + +#define LIST_HEAD_INIT(name) { &(name), &(name) } + +#define LIST_HEAD(name) \ + struct list_head name = LIST_HEAD_INIT(name) + +#define INIT_LIST_HEAD(ptr) do { \ + (ptr)->next = (ptr); (ptr)->prev = (ptr); \ +} while (0) + +static inline void __list_add(struct list_head *new, + struct list_head *prev, + struct list_head *next) { + next->prev = new; + new->next = next; + new->prev = prev; + prev->next = new; +} + +/** + * list_add - add a new entry + * @new: new entry to be added + * @head: list head to add it after + * + * Insert a new entry after the specified head. + * This is good for implementing stacks. + */ +static inline void list_add(struct list_head *new, struct list_head *head) { + __list_add(new, head, head->next); +} + +/** + * list_add_tail - add a new entry + * @new: new entry to be added + * @head: list head to add it before + * + * Insert a new entry before the specified head. + * This is useful for implementing queues. + */ +static inline void list_add_tail(struct list_head *new, struct list_head *head) { + __list_add(new, head->prev, head); +} + + +/* + * Delete a list entry by making the prev/next entries + * point to each other. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __list_del(struct list_head * prev, struct list_head * next) { + next->prev = prev; + prev->next = next; +} + +/** + * list_del - deletes entry from list. + * @entry: the element to delete from the list. + * Note: list_empty on entry does not return true after this, the entry is + * in an undefined state. + */ +static inline void list_del(struct list_head *entry) { + __list_del(entry->prev, entry->next); + entry->next = LIST_POISON1; + entry->prev = LIST_POISON2; +} + +/** + * list_del_init - deletes entry from list and reinitialize it. + * @entry: the element to delete from the list. + */ +static inline void list_del_init(struct list_head *entry) { + __list_del(entry->prev, entry->next); + INIT_LIST_HEAD(entry); +} + +/** + * list_move - delete from one list and add as another's head + * @list: the entry to move + * @head: the head that will precede our entry + */ +static inline void list_move(struct list_head *list, struct list_head *head) { + __list_del(list->prev, list->next); + list_add(list, head); +} + +/** + * list_move_tail - delete from one list and add as another's tail + * @list: the entry to move + * @head: the head that will follow our entry + */ +static inline void list_move_tail(struct list_head *list, + struct list_head *head) { + __list_del(list->prev, list->next); + list_add_tail(list, head); +} + +/** + * list_empty - tests whether a list is empty + * @head: the list to test. + */ +static inline int list_empty(const struct list_head *head) { + return head->next == head; +} + +/** + * list_empty_careful - tests whether a list is + * empty _and_ checks that no other CPU might be + * in the process of still modifying either member + * + * NOTE: using list_empty_careful() without synchronization + * can only be safe if the only activity that can happen + * to the list entry is list_del_init(). Eg. it cannot be used + * if another CPU could re-list_add() it. + * + * @head: the list to test. + */ +static inline int list_empty_careful(const struct list_head *head) { + struct list_head *next = head->next; + return (next == head) && (next == head->prev); +} + +static inline void __list_splice(struct list_head *list, + struct list_head *head) { + struct list_head *first = list->next; + struct list_head *last = list->prev; + struct list_head *at = head->next; + + first->prev = head; + head->next = first; + + last->next = at; + at->prev = last; +} + +/** + * list_splice - join two lists + * @list: the new list to add. + * @head: the place to add it in the first list. + */ +static inline void list_splice(struct list_head *list, struct list_head *head) { + if (!list_empty(list)) + __list_splice(list, head); +} + +/** + * list_splice_init - join two lists and reinitialise the emptied list. + * @list: the new list to add. + * @head: the place to add it in the first list. + * + * The list at @list is reinitialised + */ +static inline void list_splice_init(struct list_head *list, + struct list_head *head) { + if (!list_empty(list)) { + __list_splice(list, head); + INIT_LIST_HEAD(list); + } +} + + + +#define _offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - _offsetof(type,member) );}) + +/** + * list_entry - get the struct for this entry + * @ptr: the &struct list_head pointer. + * @type: the type of the struct this is embedded in. + * @member: the name of the list_struct within the struct. + */ +#define list_entry(ptr, type, member) \ + container_of(ptr, type, member) + +/** + * list_for_each - iterate over a list + * @pos: the &struct list_head to use as a loop counter. + * @head: the head for your list. + */ +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); \ + pos = pos->next) + +/** + * __list_for_each - iterate over a list + * @pos: the &struct list_head to use as a loop counter. + * @head: the head for your list. + * + * This variant differs from list_for_each() in that it's the + * simplest possible list iteration code, no prefetching is done. + * Use this for code that knows the list to be very short (empty + * or 1 entry) most of the time. + */ +#define __list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); pos = pos->next) + +/** + * list_for_each_prev - iterate over a list backwards + * @pos: the &struct list_head to use as a loop counter. + * @head: the head for your list. + */ +#define list_for_each_prev(pos, head) \ + for (pos = (head)->prev; pos != (head); \ + pos = pos->prev) + +/** + * list_for_each_safe - iterate over a list safe against removal of list entry + * @pos: the &struct list_head to use as a loop counter. + * @n: another &struct list_head to use as temporary storage + * @head: the head for your list. + */ +#define list_for_each_safe(pos, n, head) \ + for (pos = (head)->next, n = pos->next; pos != (head); \ + pos = n, n = pos->next) + +/** + * list_for_each_entry - iterate over list of given type + * @pos: the type * to use as a loop counter. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry(pos, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +/** + * list_for_each_entry_reverse - iterate backwards over list of given type. + * @pos: the type * to use as a loop counter. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_reverse(pos, head, member) \ + for (pos = list_entry((head)->prev, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.prev, typeof(*pos), member)) + +/** + * list_prepare_entry - prepare a pos entry for use as a start point in + * list_for_each_entry_continue + * @pos: the type * to use as a start point + * @head: the head of the list + * @member: the name of the list_struct within the struct. + */ +#define list_prepare_entry(pos, head, member) \ + ((pos) ? : list_entry(head, typeof(*pos), member)) + +/** + * list_for_each_entry_continue - iterate over list of given type + * continuing after existing point + * @pos: the type * to use as a loop counter. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_continue(pos, head, member) \ + for (pos = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +/** + * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry + * @pos: the type * to use as a loop counter. + * @n: another type * to use as temporary storage + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_safe(pos, n, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member), \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member)) + +#endif diff --git a/tests/opkg_active_list_test.c b/tests/opkg_active_list_test.c new file mode 100644 index 0000000..ec6bec1 --- /dev/null +++ b/tests/opkg_active_list_test.c @@ -0,0 +1,103 @@ + +/* +．--A---B----C----D-----E----F + | |__k---L + | |_ N + |__ G ---H ---I---J + |_M |_O + +Then the sequence will be +G M H I O J A B K N L C D E F +*/ + +#include +#include +#include + +struct active_test { + char *str; + struct active_list list; +} __attribute__((packed)); + +struct active_test *active_test_new(char *str) { + struct active_test *ans = (struct active_test *)calloc(1, sizeof(struct active_test)); + ans->str = str; + active_list_init(&ans->list); + return ans; +} +void active_test_add(struct active_list *head, struct active_test *node) { + active_list_add(head, &node->list); +} + +void active_test_add_depend(struct active_test *A, struct active_test *B) { + active_list_add_depend(&A->list, &B->list); +} + +void make_list(struct active_list *head) { + struct active_test *A = active_test_new("A"); + struct active_test *B = active_test_new("B"); + struct active_test *C = active_test_new("C"); + struct active_test *D = active_test_new("D"); + struct active_test *E = active_test_new("E"); + struct active_test *F = active_test_new("F"); + struct active_test *G = active_test_new("G"); + struct active_test *H = active_test_new("H"); + struct active_test *I = active_test_new("I"); + struct active_test *J = active_test_new("J"); + struct active_test *K = active_test_new("K"); + struct active_test *L = active_test_new("L"); + struct active_test *M = active_test_new("M"); + struct active_test *N = active_test_new("N"); + struct active_test *O = active_test_new("O"); + + active_test_add(head, A); + active_test_add(head, B); + active_test_add(head, C); + active_test_add(head, D); + active_test_add(head, E); + active_test_add(head, F); + active_test_add(head, G); + active_test_add(head, H); + active_test_add(head, I); + active_test_add(head, J); + active_test_add(head, K); + active_test_add(head, L); + active_test_add(head, M); + active_test_add(head, N); + active_test_add(head, O); + active_test_add_depend(H, M); + active_test_add_depend(A, G); + active_test_add_depend(A, H); + active_test_add_depend(A, I); + active_test_add_depend(A, J); + active_test_add_depend(J, O); + active_test_add_depend(C, K); + active_test_add_depend(C, L); + active_test_add_depend(L, N); +} + +int main (void) { + struct active_list head; + struct active_list *ptr; + struct active_test *test; + active_list_init(&head); + make_list(&head); + + for(ptr = active_list_next(&head, &head); ptr ;ptr = active_list_next(&head, ptr)) { + test = list_entry(ptr, struct active_test, list); + printf ("%s ",test->str); + } + printf("\n"); + for(ptr = active_list_next(&head, &head); ptr ;ptr = active_list_next(&head, ptr)) { + test = list_entry(ptr, struct active_test, list); + printf ("%s ",test->str); + } + printf("\n"); + for(ptr = active_list_next(&head, &head); ptr ;ptr = active_list_next(&head, ptr)) { + test = list_entry(ptr, struct active_test, list); + printf ("%s ",test->str); + } + printf("\n"); + + +} -- 2.25.1