diff options
Diffstat (limited to 'src/backend/lib')
| -rw-r--r-- | src/backend/lib/bit.c | 27 | ||||
| -rw-r--r-- | src/backend/lib/dllist.c | 246 | ||||
| -rw-r--r-- | src/backend/lib/fstack.c | 146 | ||||
| -rw-r--r-- | src/backend/lib/hasht.c | 48 | ||||
| -rw-r--r-- | src/backend/lib/lispsort.c | 67 | ||||
| -rw-r--r-- | src/backend/lib/qsort.c | 186 | ||||
| -rw-r--r-- | src/backend/lib/stringinfo.c | 142 |
7 files changed, 457 insertions, 405 deletions
diff --git a/src/backend/lib/bit.c b/src/backend/lib/bit.c index 680f349a520..439566c0b75 100644 --- a/src/backend/lib/bit.c +++ b/src/backend/lib/bit.c @@ -1,13 +1,13 @@ /*------------------------------------------------------------------------- * * bit.c-- - * Standard bit array code. + * Standard bit array code. * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/lib/Attic/bit.c,v 1.4 1996/11/06 08:27:09 scrappy Exp $ + * $Header: /cvsroot/pgsql/src/backend/lib/Attic/bit.c,v 1.5 1997/09/07 04:41:54 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -22,27 +22,26 @@ void BitArraySetBit(BitArray bitArray, BitIndex bitIndex) -{ - bitArray[bitIndex/BitsPerByte] +{ + bitArray[bitIndex / BitsPerByte] |= (1 << (BitsPerByte - (bitIndex % BitsPerByte) - 1)); - return; + return; } void BitArrayClearBit(BitArray bitArray, BitIndex bitIndex) { - bitArray[bitIndex/BitsPerByte] + bitArray[bitIndex / BitsPerByte] &= ~(1 << (BitsPerByte - (bitIndex % BitsPerByte) - 1)); - return; + return; } bool BitArrayBitIsSet(BitArray bitArray, BitIndex bitIndex) -{ - return( (bool) (((bitArray[bitIndex / BitsPerByte] & - (1 << (BitsPerByte - (bitIndex % BitsPerByte) - - 1) - ) - ) != 0 ) ? 1 : 0) ); +{ + return ((bool) (((bitArray[bitIndex / BitsPerByte] & + (1 << (BitsPerByte - (bitIndex % BitsPerByte) + - 1) + ) + ) != 0) ? 1 : 0)); } - diff --git a/src/backend/lib/dllist.c b/src/backend/lib/dllist.c index b8dd14a231b..70feee02bb9 100644 --- a/src/backend/lib/dllist.c +++ b/src/backend/lib/dllist.c @@ -1,15 +1,15 @@ /*------------------------------------------------------------------------- * * dllist.c-- - * this is a simple doubly linked list implementation - * replaces the old simplelists stuff - * the elements of the lists are void* + * this is a simple doubly linked list implementation + * replaces the old simplelists stuff + * the elements of the lists are void* * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/lib/dllist.c,v 1.5 1997/08/19 21:31:16 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/lib/dllist.c,v 1.6 1997/09/07 04:41:56 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -18,191 +18,197 @@ #include <lib/dllist.h> -Dllist* +Dllist * DLNewList(void) { - Dllist* l; + Dllist *l; - l = malloc(sizeof(Dllist)); - l->dll_head = 0; - l->dll_tail = 0; + l = malloc(sizeof(Dllist)); + l->dll_head = 0; + l->dll_tail = 0; - return l; + return l; } - /* free up a list and all the nodes in it*/ + /* free up a list and all the nodes in it */ void -DLFreeList(Dllist* l) +DLFreeList(Dllist * l) { - Dlelem* curr; + Dlelem *curr; - while ( (curr = DLRemHead(l)) != 0) - free(curr); + while ((curr = DLRemHead(l)) != 0) + free(curr); - free(l); + free(l); } -Dlelem* -DLNewElem(void* val) +Dlelem * +DLNewElem(void *val) { - Dlelem* e; - e = malloc(sizeof(Dlelem)); - e->dle_next = 0; - e->dle_prev = 0; - e->dle_val = val; - e->dle_list = 0; - return e; + Dlelem *e; + + e = malloc(sizeof(Dlelem)); + e->dle_next = 0; + e->dle_prev = 0; + e->dle_val = val; + e->dle_list = 0; + return e; } void -DLFreeElem(Dlelem* e) +DLFreeElem(Dlelem * e) { - free(e); + free(e); } -Dlelem* -DLGetHead(Dllist* l) +Dlelem * +DLGetHead(Dllist * l) { - return (l ? l->dll_head : 0); + return (l ? l->dll_head : 0); } /* get the value stored in the first element */ #ifdef NOT_USED -void* -DLGetHeadVal(Dllist* l) +void * +DLGetHeadVal(Dllist * l) { - Dlelem* e = DLGetHead(l); - - return (e ? e->dle_val : 0); + Dlelem *e = DLGetHead(l); + + return (e ? e->dle_val : 0); } + #endif -Dlelem* -DLGetTail(Dllist* l) +Dlelem * +DLGetTail(Dllist * l) { - return (l ? l->dll_tail : 0); + return (l ? l->dll_tail : 0); } /* get the value stored in the first element */ #ifdef NOT_USED -void* -DLGetTailVal(Dllist* l) +void * +DLGetTailVal(Dllist * l) { - Dlelem* e = DLGetTail(l); - - return (e ? e->dle_val : 0); + Dlelem *e = DLGetTail(l); + + return (e ? e->dle_val : 0); } + #endif -Dlelem* -DLGetPred(Dlelem* e) /* get predecessor */ +Dlelem * +DLGetPred(Dlelem * e) /* get predecessor */ { - return (e ? e->dle_prev : 0); + return (e ? e->dle_prev : 0); } -Dlelem* -DLGetSucc(Dlelem* e) /* get successor */ +Dlelem * +DLGetSucc(Dlelem * e) /* get successor */ { - return (e ? e->dle_next : 0); + return (e ? e->dle_next : 0); } void -DLRemove(Dlelem* e) +DLRemove(Dlelem * e) { - Dllist* l; + Dllist *l; - if (e->dle_prev) - e->dle_prev->dle_next = e->dle_next; - if (e->dle_next) - e->dle_next->dle_prev = e->dle_prev; + if (e->dle_prev) + e->dle_prev->dle_next = e->dle_next; + if (e->dle_next) + e->dle_next->dle_prev = e->dle_prev; - /* check to see if we're removing the head or tail */ - l = e->dle_list; - if (e == l->dll_head) - DLRemHead(l); - if (e == l->dll_tail) - DLRemTail(l); + /* check to see if we're removing the head or tail */ + l = e->dle_list; + if (e == l->dll_head) + DLRemHead(l); + if (e == l->dll_tail) + DLRemTail(l); } -void -DLAddHead(Dllist* l, Dlelem* e) +void +DLAddHead(Dllist * l, Dlelem * e) { - e->dle_list = l; - - if (l->dll_head) { - l->dll_head->dle_prev = e; - e->dle_next = l->dll_head; - } - e->dle_prev = 0; - l->dll_head = e; - - if (l->dll_tail == 0) /* if this is first element added */ - l->dll_tail = l->dll_head; + e->dle_list = l; + + if (l->dll_head) + { + l->dll_head->dle_prev = e; + e->dle_next = l->dll_head; + } + e->dle_prev = 0; + l->dll_head = e; + + if (l->dll_tail == 0) /* if this is first element added */ + l->dll_tail = l->dll_head; } void -DLAddTail(Dllist* l, Dlelem* e) +DLAddTail(Dllist * l, Dlelem * e) { - e->dle_list = l; - - if (l->dll_tail) { - l->dll_tail->dle_next = e; - e->dle_prev = l->dll_tail; - } - e->dle_next = 0; - l->dll_tail = e; - - if (l->dll_head == 0) /* if this is first element added */ - l->dll_head = l->dll_tail; + e->dle_list = l; + + if (l->dll_tail) + { + l->dll_tail->dle_next = e; + e->dle_prev = l->dll_tail; + } + e->dle_next = 0; + l->dll_tail = e; + + if (l->dll_head == 0) /* if this is first element added */ + l->dll_head = l->dll_tail; } -Dlelem* -DLRemHead(Dllist* l) +Dlelem * +DLRemHead(Dllist * l) { - /* remove and return the head */ - Dlelem* result; + /* remove and return the head */ + Dlelem *result; - if (l->dll_head == 0) - return 0; + if (l->dll_head == 0) + return 0; - result = l->dll_head; - if (l->dll_head->dle_next) { - l->dll_head->dle_next->dle_prev = 0; - } + result = l->dll_head; + if (l->dll_head->dle_next) + { + l->dll_head->dle_next->dle_prev = 0; + } - l->dll_head = l->dll_head->dle_next; + l->dll_head = l->dll_head->dle_next; - result->dle_next = 0; - result->dle_list = 0; - - if (result == l->dll_tail) /* if the head is also the tail */ - l->dll_tail = 0; + result->dle_next = 0; + result->dle_list = 0; - return result; + if (result == l->dll_tail) /* if the head is also the tail */ + l->dll_tail = 0; + + return result; } -Dlelem* -DLRemTail(Dllist* l) +Dlelem * +DLRemTail(Dllist * l) { - /* remove and return the tail */ - Dlelem* result; + /* remove and return the tail */ + Dlelem *result; - if (l->dll_tail == 0 ) - return 0; + if (l->dll_tail == 0) + return 0; - result = l->dll_tail; - if (l->dll_tail->dle_prev) { - l->dll_tail->dle_prev->dle_next = 0; - } - l->dll_tail = l->dll_tail->dle_prev; + result = l->dll_tail; + if (l->dll_tail->dle_prev) + { + l->dll_tail->dle_prev->dle_next = 0; + } + l->dll_tail = l->dll_tail->dle_prev; - result->dle_prev = 0; - result->dle_list = 0; + result->dle_prev = 0; + result->dle_list = 0; - if (result == l->dll_head) /* if the tail is also the head */ - l->dll_head = 0; + if (result == l->dll_head) /* if the tail is also the head */ + l->dll_head = 0; - return result; + return result; } - diff --git a/src/backend/lib/fstack.c b/src/backend/lib/fstack.c index 68f1505b167..f97d467fe92 100644 --- a/src/backend/lib/fstack.c +++ b/src/backend/lib/fstack.c @@ -1,13 +1,13 @@ /*------------------------------------------------------------------------- * * fstack.c-- - * Fixed format stack definitions. + * Fixed format stack definitions. * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/lib/Attic/fstack.c,v 1.4 1997/06/06 22:02:37 scrappy Exp $ + * $Header: /cvsroot/pgsql/src/backend/lib/Attic/fstack.c,v 1.5 1997/09/07 04:42:00 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -21,25 +21,25 @@ /* * FixedItemIsValid -- - * True iff item is valid. + * True iff item is valid. */ #define FixedItemIsValid(item) PointerIsValid(item) /* * FixedStackGetItemBase -- - * Returns base of enclosing structure. + * Returns base of enclosing structure. */ #define FixedStackGetItemBase(stack, item) \ - ((Pointer)((char *)(item) - (stack)->offset)) + ((Pointer)((char *)(item) - (stack)->offset)) /* * FixedStackGetItem -- - * Returns item of given pointer to enclosing structure. + * Returns item of given pointer to enclosing structure. */ #define FixedStackGetItem(stack, pointer) \ - ((FixedItem)((char *)(pointer) + (stack)->offset)) + ((FixedItem)((char *)(pointer) + (stack)->offset)) -#define FixedStackIsValid(stack) ((bool)PointerIsValid(stack)) +#define FixedStackIsValid(stack) ((bool)PointerIsValid(stack)) /* * External functions @@ -48,99 +48,105 @@ void FixedStackInit(FixedStack stack, Offset offset) { - AssertArg(PointerIsValid(stack)); - - stack->top = NULL; - stack->offset = offset; + AssertArg(PointerIsValid(stack)); + + stack->top = NULL; + stack->offset = offset; } Pointer FixedStackPop(FixedStack stack) { - Pointer pointer; - - AssertArg(FixedStackIsValid(stack)); - - if (!PointerIsValid(stack->top)) { - return (NULL); - } - - pointer = FixedStackGetItemBase(stack, stack->top); - stack->top = stack->top->next; - - return (pointer); + Pointer pointer; + + AssertArg(FixedStackIsValid(stack)); + + if (!PointerIsValid(stack->top)) + { + return (NULL); + } + + pointer = FixedStackGetItemBase(stack, stack->top); + stack->top = stack->top->next; + + return (pointer); } void FixedStackPush(FixedStack stack, Pointer pointer) { - FixedItem item = FixedStackGetItem(stack, pointer); - - AssertArg(FixedStackIsValid(stack)); - AssertArg(PointerIsValid(pointer)); - - item->next = stack->top; - stack->top = item; + FixedItem item = FixedStackGetItem(stack, pointer); + + AssertArg(FixedStackIsValid(stack)); + AssertArg(PointerIsValid(pointer)); + + item->next = stack->top; + stack->top = item; } -#ifndef NO_ASSERT_CHECKING +#ifndef NO_ASSERT_CHECKING /* * FixedStackContains -- - * True iff ordered stack contains given element. + * True iff ordered stack contains given element. * * Note: - * This is inefficient. It is intended for debugging use only. + * This is inefficient. It is intended for debugging use only. * * Exceptions: - * BadArg if stack is invalid. - * BadArg if pointer is invalid. + * BadArg if stack is invalid. + * BadArg if pointer is invalid. */ -static bool +static bool FixedStackContains(FixedStack stack, Pointer pointer) { - FixedItem next; - FixedItem item; - - AssertArg(FixedStackIsValid(stack)); - AssertArg(PointerIsValid(pointer)); - - item = FixedStackGetItem(stack, pointer); - - for (next = stack->top; FixedItemIsValid(next); next = next->next) { - if (next == item) { - return (true); + FixedItem next; + FixedItem item; + + AssertArg(FixedStackIsValid(stack)); + AssertArg(PointerIsValid(pointer)); + + item = FixedStackGetItem(stack, pointer); + + for (next = stack->top; FixedItemIsValid(next); next = next->next) + { + if (next == item) + { + return (true); + } } - } - return (false); + return (false); } + #endif Pointer FixedStackGetTop(FixedStack stack) { - AssertArg(FixedStackIsValid(stack)); - - if (!PointerIsValid(stack->top)) { - return (NULL); - } - - return (FixedStackGetItemBase(stack, stack->top)); + AssertArg(FixedStackIsValid(stack)); + + if (!PointerIsValid(stack->top)) + { + return (NULL); + } + + return (FixedStackGetItemBase(stack, stack->top)); } Pointer FixedStackGetNext(FixedStack stack, Pointer pointer) { - FixedItem item; - - /* AssertArg(FixedStackIsValid(stack)); */ - /* AssertArg(PointerIsValid(pointer)); */ - AssertArg(FixedStackContains(stack, pointer)); - - item = FixedStackGetItem(stack, pointer)->next; - - if (!PointerIsValid(item)) { - return (NULL); - } - - return(FixedStackGetItemBase(stack, item)); + FixedItem item; + + /* AssertArg(FixedStackIsValid(stack)); */ + /* AssertArg(PointerIsValid(pointer)); */ + AssertArg(FixedStackContains(stack, pointer)); + + item = FixedStackGetItem(stack, pointer)->next; + + if (!PointerIsValid(item)) + { + return (NULL); + } + + return (FixedStackGetItemBase(stack, item)); } diff --git a/src/backend/lib/hasht.c b/src/backend/lib/hasht.c index baceabfcf7a..4e12dcf30eb 100644 --- a/src/backend/lib/hasht.c +++ b/src/backend/lib/hasht.c @@ -1,14 +1,14 @@ /*------------------------------------------------------------------------- * * hasht.c-- - * hash table related functions that are not directly supported - * by the hashing packages under utils/hash. + * hash table related functions that are not directly supported + * by the hashing packages under utils/hash. * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/lib/Attic/hasht.c,v 1.4 1997/08/12 22:52:42 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/lib/Attic/hasht.c,v 1.5 1997/09/07 04:42:03 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -19,29 +19,31 @@ #include <lib/hasht.h> /* ----------------------------------- - * HashTableWalk + * HashTableWalk * - * call function on every element in hashtable - * one extra argument, arg may be supplied + * call function on every element in hashtable + * one extra argument, arg may be supplied * ----------------------------------- */ void -HashTableWalk(HTAB *hashtable, HashtFunc function, int arg) +HashTableWalk(HTAB * hashtable, HashtFunc function, int arg) { - long *hashent; - long *data; - int keysize; - - keysize = hashtable->hctl->keysize; - hash_seq((HTAB *)NULL); - while ((hashent = hash_seq(hashtable)) != (long *) TRUE) { - if (hashent == NULL) - elog(FATAL, "error in HashTableWalk."); - /* - * XXX the corresponding hash table insertion does NOT - * LONGALIGN -- make sure the keysize is ok - */ - data = (long *) LONGALIGN((char*) hashent + keysize); - (*function)(data, arg); - } + long *hashent; + long *data; + int keysize; + + keysize = hashtable->hctl->keysize; + hash_seq((HTAB *) NULL); + while ((hashent = hash_seq(hashtable)) != (long *) TRUE) + { + if (hashent == NULL) + elog(FATAL, "error in HashTableWalk."); + + /* + * XXX the corresponding hash table insertion does NOT LONGALIGN + * -- make sure the keysize is ok + */ + data = (long *) LONGALIGN((char *) hashent + keysize); + (*function) (data, arg); + } } diff --git a/src/backend/lib/lispsort.c b/src/backend/lib/lispsort.c index 11acc5683b2..bf346ecc1a6 100644 --- a/src/backend/lib/lispsort.c +++ b/src/backend/lib/lispsort.c @@ -6,7 +6,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/lib/Attic/lispsort.c,v 1.4 1997/08/19 21:31:18 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/lib/Attic/lispsort.c,v 1.5 1997/09/07 04:42:05 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -24,38 +24,41 @@ #ifdef NOT_USED /* -** lisp_qsort: Takes a lisp list as input, copies it into an array of lisp -** nodes which it sorts via qsort() with the comparison function -** as passed into lisp_qsort(), and returns a new list with -** the nodes sorted. The old list is *not* freed or modified (?) +** lisp_qsort: Takes a lisp list as input, copies it into an array of lisp +** nodes which it sorts via qsort() with the comparison function +** as passed into lisp_qsort(), and returns a new list with +** the nodes sorted. The old list is *not* freed or modified (?) */ -List *lisp_qsort(List *the_list, /* the list to be sorted */ - int (*compare)()) /* function to compare two nodes */ +List * +lisp_qsort(List * the_list, /* the list to be sorted */ + int (*compare) ()) /* function to compare two nodes */ { - int i; - size_t num; - List **nodearray; - List *tmp, *output; - - /* find size of list */ - num = length(the_list); - if (num < 2) - return(copyObject(the_list)); - - /* copy elements of the list into an array */ - nodearray = (List **) palloc(num * sizeof(List *)); - - for (tmp = the_list, i = 0; tmp != NIL; tmp = lnext(tmp), i++) - nodearray[i] = copyObject(lfirst(tmp)); - - /* sort the array */ - pg_qsort(nodearray, num, sizeof(List *), compare); - - /* lcons together the array elements */ - output = NIL; - for (i = num - 1; i >= 0; i--) - output = lcons(nodearray[i], output); - - return(output); + int i; + size_t num; + List **nodearray; + List *tmp, + *output; + + /* find size of list */ + num = length(the_list); + if (num < 2) + return (copyObject(the_list)); + + /* copy elements of the list into an array */ + nodearray = (List **) palloc(num * sizeof(List *)); + + for (tmp = the_list, i = 0; tmp != NIL; tmp = lnext(tmp), i++) + nodearray[i] = copyObject(lfirst(tmp)); + + /* sort the array */ + pg_qsort(nodearray, num, sizeof(List *), compare); + + /* lcons together the array elements */ + output = NIL; + for (i = num - 1; i >= 0; i--) + output = lcons(nodearray[i], output); + + return (output); } + #endif diff --git a/src/backend/lib/qsort.c b/src/backend/lib/qsort.c index e0f3cbbb2c2..ff2bbfa16d9 100644 --- a/src/backend/lib/qsort.c +++ b/src/backend/lib/qsort.c @@ -1,13 +1,13 @@ /*------------------------------------------------------------------------- * * qsort.c-- - * + * * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/lib/Attic/qsort.c,v 1.2 1996/11/06 08:27:15 scrappy Exp $ + * $Header: /cvsroot/pgsql/src/backend/lib/Attic/qsort.c,v 1.3 1997/09/07 04:42:06 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -19,22 +19,22 @@ * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. + * notice, this list of conditions and the following disclaimer. * 2. 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. + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. + * may be used to endorse or promote products derived from this software + * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``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 REGENTS OR CONTRIBUTORS BE LIABLE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS 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) @@ -45,8 +45,9 @@ */ #if defined(LIBC_SCCS) && !defined(lint) -static char sccsid[] = "@(#)qsort.c 5.9 (Berkeley) 2/23/91"; -#endif /* LIBC_SCCS and not lint */ +static char sccsid[] = "@(#)qsort.c 5.9 (Berkeley) 2/23/91"; + +#endif /* LIBC_SCCS and not lint */ #include <sys/types.h> @@ -58,21 +59,22 @@ static char sccsid[] = "@(#)qsort.c 5.9 (Berkeley) 2/23/91"; * MTHRESH is the smallest partition for which we compare for a median * value instead of using the middle value. */ -#define MTHRESH 6 +#define MTHRESH 6 /* * THRESH is the minimum number of entries in a partition for continued * partitioning. */ -#define THRESH 4 +#define THRESH 4 -static void insertion_sort(char* bot, int nmemb, int size, int (*compar)()); -static void quick_sort(char* bot, int nmemb, int size, int (*compar)()); +static void insertion_sort(char *bot, int nmemb, int size, int (*compar) ()); +static void quick_sort(char *bot, int nmemb, int size, int (*compar) ()); -void pg_qsort(void *bot, - size_t nmemb, - size_t size, - int (*compar)(void *, void *)) +void +pg_qsort(void *bot, + size_t nmemb, + size_t size, + int (*compar) (void *, void *)) { if (nmemb <= 1) @@ -85,19 +87,19 @@ void pg_qsort(void *bot, } /* - * Swap two areas of size number of bytes. Although qsort(3) permits random + * Swap two areas of size number of bytes. Although qsort(3) permits random * blocks of memory to be sorted, sorting pointers is almost certainly the * common case (and, were it not, could easily be made so). Regardless, it * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer * arithmetic gets lost in the time required for comparison function calls. */ -#define SWAP(a, b) { \ - cnt = size; \ - do { \ - ch = *a; \ - *a++ = *b; \ - *b++ = ch; \ - } while (--cnt); \ +#define SWAP(a, b) { \ + cnt = size; \ + do { \ + ch = *a; \ + *a++ = *b; \ + *b++ = ch; \ + } while (--cnt); \ } /* @@ -114,24 +116,28 @@ void pg_qsort(void *bot, * Knuth, page 122, equation 26), since the quicksort algorithm does less * comparisons than the insertion sort. */ -#define SORT(bot, n) { \ - if (n > 1) \ - if (n == 2) { \ - t1 = bot + size; \ - if (compar(t1, bot) < 0) \ - SWAP(t1, bot); \ - } else \ - insertion_sort(bot, n, size, compar); \ +#define SORT(bot, n) { \ + if (n > 1) \ + if (n == 2) { \ + t1 = bot + size; \ + if (compar(t1, bot) < 0) \ + SWAP(t1, bot); \ + } else \ + insertion_sort(bot, n, size, compar); \ } static void -quick_sort(char* bot, int nmemb, int size, int (*compar)()) +quick_sort(char *bot, int nmemb, int size, int (*compar) ()) { - register int cnt; + register int cnt; register u_char ch; - register char *top, *mid, *t1, *t2; - register int n1, n2; - char *bsv; + register char *top, + *mid, + *t1, + *t2; + register int n1, + n2; + char *bsv; /* bot and nmemb must already be set. */ partition: @@ -145,7 +151,8 @@ partition: * Vol. 3, page 123, Eq. 28). This test order gets the equalities * right. */ - if (nmemb >= MTHRESH) { + if (nmemb >= MTHRESH) + { n1 = compar(bot, mid); n2 = compar(mid, top); if (n1 < 0 && n2 > 0) @@ -156,28 +163,33 @@ partition: t1 = mid; /* if mid element not selected, swap selection there */ - if (t1 != mid) { + if (t1 != mid) + { SWAP(t1, mid); mid -= size; } } /* Standard quicksort, Knuth, Vol. 3, page 116, Algorithm Q. */ -#define didswap n1 -#define newbot t1 -#define replace t2 +#define didswap n1 +#define newbot t1 +#define replace t2 didswap = 0; - for (bsv = bot;;) { + for (bsv = bot;;) + { for (; bot < mid && compar(bot, mid) <= 0; bot += size); - while (top > mid) { - if (compar(mid, top) <= 0) { + while (top > mid) + { + if (compar(mid, top) <= 0) + { top -= size; continue; } - newbot = bot + size; /* value of bot after swap */ + newbot = bot + size;/* value of bot after swap */ if (bot == mid) /* top <-> mid, mid == top */ replace = mid = top; - else { /* bot <-> top */ + else + { /* bot <-> top */ replace = top; top -= size; } @@ -191,7 +203,7 @@ partition: newbot = mid = bot; /* value of bot after swap */ top -= size; -swap: SWAP(bot, replace); +swap: SWAP(bot, replace); bot = newbot; didswap = 1; } @@ -200,14 +212,15 @@ swap: SWAP(bot, replace); * Quicksort behaves badly in the presence of data which is already * sorted (see Knuth, Vol. 3, page 119) going from O N lg N to O N^2. * To avoid this worst case behavior, if a re-partitioning occurs - * without swapping any elements, it is not further partitioned and - * is insert sorted. This wins big with almost sorted data sets and - * only loses if the data set is very strangely partitioned. A fix - * for those data sets would be to return prematurely if the insertion + * without swapping any elements, it is not further partitioned and is + * insert sorted. This wins big with almost sorted data sets and only + * loses if the data set is very strangely partitioned. A fix for + * those data sets would be to return prematurely if the insertion * sort routine is forced to make an excessive number of swaps, and * continue the partitioning. */ - if (!didswap) { + if (!didswap) + { insertion_sort(bsv, nmemb, size, compar); return; } @@ -216,34 +229,41 @@ swap: SWAP(bot, replace); * Re-partition or sort as necessary. Note that the mid element * itself is correctly positioned and can be ignored. */ -#define nlower n1 -#define nupper n2 +#define nlower n1 +#define nupper n2 bot = bsv; - nlower = (mid - bot) / size; /* size of lower partition */ + nlower = (mid - bot) / size;/* size of lower partition */ mid += size; - nupper = nmemb - nlower - 1; /* size of upper partition */ + nupper = nmemb - nlower - 1;/* size of upper partition */ /* * If must call recursively, do it on the smaller partition; this * bounds the stack to lg N entries. */ - if (nlower > nupper) { + if (nlower > nupper) + { if (nupper >= THRESH) quick_sort(mid, nupper, size, compar); - else { + else + { SORT(mid, nupper); - if (nlower < THRESH) { + if (nlower < THRESH) + { SORT(bot, nlower); return; } } nmemb = nlower; - } else { + } + else + { if (nlower >= THRESH) quick_sort(bot, nlower, size, compar); - else { + else + { SORT(bot, nlower); - if (nupper < THRESH) { + if (nupper < THRESH) + { SORT(mid, nupper); return; } @@ -255,30 +275,38 @@ swap: SWAP(bot, replace); } static void -insertion_sort(char* bot, int nmemb, int size, int (*compar)()) +insertion_sort(char *bot, int nmemb, int size, int (*compar) ()) { - register int cnt; + register int cnt; register u_char ch; - register char *s1, *s2, *t1, *t2, *top; + register char *s1, + *s2, + *t1, + *t2, + *top; /* - * A simple insertion sort (see Knuth, Vol. 3, page 81, Algorithm - * S). Insertion sort has the same worst case as most simple sorts - * (O N^2). It gets used here because it is (O N) in the case of - * sorted data. + * A simple insertion sort (see Knuth, Vol. 3, page 81, Algorithm S). + * Insertion sort has the same worst case as most simple sorts (O + * N^2). It gets used here because it is (O N) in the case of sorted + * data. */ top = bot + nmemb * size; - for (t1 = bot + size; t1 < top;) { + for (t1 = bot + size; t1 < top;) + { for (t2 = t1; (t2 -= size) >= bot && compar(t1, t2) < 0;); - if (t1 != (t2 += size)) { + if (t1 != (t2 += size)) + { /* Bubble bytes up through each element. */ - for (cnt = size; cnt--; ++t1) { + for (cnt = size; cnt--; ++t1) + { ch = *t1; for (s1 = s2 = t1; (s2 -= size) >= t2; s1 = s2) *s1 = *s2; *s1 = ch; } - } else + } + else t1 += size; } } diff --git a/src/backend/lib/stringinfo.c b/src/backend/lib/stringinfo.c index 18cfc89f982..34108c04c72 100644 --- a/src/backend/lib/stringinfo.c +++ b/src/backend/lib/stringinfo.c @@ -1,15 +1,15 @@ /*------------------------------------------------------------------------- * * stringinfo.c-- - * These are routines that can be used to write informations to a string, - * without having to worry about string lengths, space allocation etc. - * Ideally the interface should look like the file i/o interface, + * These are routines that can be used to write informations to a string, + * without having to worry about string lengths, space allocation etc. + * Ideally the interface should look like the file i/o interface, * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/lib/stringinfo.c,v 1.3 1997/08/12 20:15:15 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/lib/stringinfo.c,v 1.4 1997/09/07 04:42:07 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -30,30 +30,33 @@ StringInfo makeStringInfo() { - StringInfo res; - long size; - - res = (StringInfo) palloc(sizeof(StringInfoData)); - if (res == NULL) { - elog(WARN, "makeStringInfo: Out of memory!"); - } - - size = 100; - res->data = palloc(size); - if (res->data == NULL) { - elog(WARN, - "makeStringInfo: Out of memory! (%ld bytes requested)", size); - } - res->maxlen = size; - res->len = 0; - /* - * NOTE: we must initialize `res->data' to the empty string because - * we use 'strcat' in 'appendStringInfo', which of course it always - * expects a null terminated string. - */ - res->data[0] = '\0'; - - return(res); + StringInfo res; + long size; + + res = (StringInfo) palloc(sizeof(StringInfoData)); + if (res == NULL) + { + elog(WARN, "makeStringInfo: Out of memory!"); + } + + size = 100; + res->data = palloc(size); + if (res->data == NULL) + { + elog(WARN, + "makeStringInfo: Out of memory! (%ld bytes requested)", size); + } + res->maxlen = size; + res->len = 0; + + /* + * NOTE: we must initialize `res->data' to the empty string because we + * use 'strcat' in 'appendStringInfo', which of course it always + * expects a null terminated string. + */ + res->data[0] = '\0'; + + return (res); } /*--------------------------------------------------------------------- @@ -69,48 +72,53 @@ makeStringInfo() void appendStringInfo(StringInfo str, char *buffer) { - int buflen, newlen; - char *s; - - Assert((str!=NULL)); - - /* - * do we have enough space to append the new string? - * (don't forget to count the null string terminating char!) - * If no, then reallocate some more. - */ - buflen = strlen(buffer); - if (buflen + str->len >= str->maxlen-1) { + int buflen, + newlen; + char *s; + + Assert((str != NULL)); + /* - * how much more space to allocate ? - * Let's say double the current space... - * However we must check if this is enough! + * do we have enough space to append the new string? (don't forget to + * count the null string terminating char!) If no, then reallocate + * some more. */ - newlen = 2 * str->len; - while (buflen + str->len >= newlen-1) { - newlen = 2 * newlen; + buflen = strlen(buffer); + if (buflen + str->len >= str->maxlen - 1) + { + + /* + * how much more space to allocate ? Let's say double the current + * space... However we must check if this is enough! + */ + newlen = 2 * str->len; + while (buflen + str->len >= newlen - 1) + { + newlen = 2 * newlen; + } + + /* + * allocate enough space. + */ + s = palloc(newlen); + if (s == NULL) + { + elog(WARN, + "appendStringInfo: Out of memory (%d bytes requested)", + newlen); + } + memmove(s, str->data, str->len + 1); + pfree(str->data); + str->maxlen = newlen; + str->data = s; } + /* - * allocate enough space. + * OK, we have enough space now, append 'buffer' at the end of the + * string & update the string length. NOTE: this is a text string + * (i.e. printable characters) so 'strcat' will do the job (no need to + * use 'bcopy' et all...) */ - s = palloc(newlen); - if (s==NULL) { - elog(WARN, - "appendStringInfo: Out of memory (%d bytes requested)", - newlen); - } - memmove(s, str->data, str->len+1); - pfree(str->data); - str->maxlen = newlen; - str->data = s; - } - - /* - * OK, we have enough space now, append 'buffer' at the - * end of the string & update the string length. - * NOTE: this is a text string (i.e. printable characters) - * so 'strcat' will do the job (no need to use 'bcopy' et all...) - */ - strcat(str->data, buffer); - str->len += buflen; + strcat(str->data, buffer); + str->len += buflen; } |